4.链表和稀疏矩阵
4.1 线性表的链式表示与实现
4.2 循环链表与双向链表
4.3 稀疏矩阵
|
第8章 类和动态存储
指针与动态数据结构 |
4 |
自习 |
|
第9章 链表
节点类 构造链表 设计链表类 类LinkedList LinkedList类的实现 用链表实现集合 实例研究：打印缓冲池 循环表 双向链表 实例研究：窗口管理 |
4 |
重点 |
4.1 线性表的链式表示与实现
教学目的： 掌握线性链表、单链表、静态链表的概念、表示及实现方法
教学重点： 线性链表之单链表的表示及实现方法。
教学难点： 线性链表的概念。
授课内容：
一、复习顺序表的定义。
二、线性链表的概念：
以链式结构存储的线性表称之为线性链表。
特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储一个指示其直接衙继的信息。这两部分信息组成数据元素的存储映象，称为结点。
|
|
|
|
例:下图是若干抽屉，每个抽屉中放一个数据元素和一个指向后继元素的指针，一号抽屉中放线性表的第一个元素，它的下一个即第二个元素的位置标为5，即放在第5个抽屉中，而第三个放在2号抽屉中。第三个元素即为最后一个，它的下一个元素的指针标为空，用0表示。
用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的
二、线性链表的存储实现
struct LNODE{
ElemType data;
struct LNODE *next;
};
typedef struct LNODE LNode;
typedef struct LNODE * LinkList;
头指针与头结点的区别：
头指针只相当于结点的指针域，头结点即整个线性链表的第一个结点，它的数据域可以放数据元素，也可以放线性表的长度等附加信息，也可以不存储任何信息。
三、线性表的操作实现(类C语言)
1初始化操作
Status Init_L(LinkList L){
if (L=(LinkList *)malloc(sizeof(LNode)))
{L->next=NULL;return 1;}
else return 0;
}
2插入操作
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L,j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
return OK;
}//ListInsert_L
3删除操作
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L,j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p->next||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
return OK;
}//ListDelete_L
4取某序号元素的操作
Status GetElem_L(LinkList &L,int i,ElemType &e){
p=L->next,j=1;
while(p&&j<i){p=p->next;++j;}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}//GetElem_L
5归并两个单链表的算法
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
//已知单链线性表La和Lb的元素按值非递减排列
//归并后得到新的单链线性表Lc,元素也按值非递减排列
pa=La->next;pb=Lb->next;
Lc=pc=La;
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb;
free(Lb);
}//MergeList_L
C语言实现的例子。
四、总结
1、线性链表的概念。
2、线性链表的存储
3、线性链表的操作
4.2 循环链表与双向链表
教学目的： 掌握循环链表的概念，掌握双向链表的的表示与实现
教学重点： 双向链表的表示与实现
教学难点： 双向链表的存储表示
授课内容：
一、复习线性链表的存储结构
二、循环链表的存储结构
循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。
三、双向链表的存储结构
提问：单向链表的缺点是什么？
提示：如何寻找结点的直接前趋。
双向链表可以克服单链表的单向性的缺点。
在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。
1、线性表的双向链表存储结构
typedef struct DulNode{
struct DulNode *prior;
ElemType data;
struct DulNode *next;
}DulNode,*DuLinkList;
对指向双向链表任一结点的指针d，有下面的关系：
d->next->priou=d->priou->next=d
即：当前结点后继的前趋是自身，当前结点前趋的后继也是自身。
2、双向链表的删除操作
|
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
if(!(p=GetElemP_DuL(L,i))) return ERROR; e=p->data; p->prior->next=p->next; p->next->prior=p->pror; free(p); return OK; }//ListDelete_DuL |
3、双向链表的插入操作
|
Status ListInsert_DuL(DuLinkList &L,int i,ElemType &e){
if(!(p=GetElemP_DuL(L,i))) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return OK; }//ListInsert_DuL |
四、一个完整的带头结点的线性链表类型定义：
typedef struct LNode{
ElemType data;
struct LNode *next;
}*Link,*Position;
typedef struct{
Link head,tail;
int len;
}LinkList;
Status MakeNode(Link &p,ElemType e);
//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
void FreeNode(Link &p);
//释放p所指结点
Status InitLinst(LinkList &L);
//构造一个空的线性链表L
Status DestroyLinst(LinkList &L);
//销毁线性链表L，L不再存在
Status ClearList(LinkList &L);
//将线性链表L重置为空表，并释放原链表的结点空间
Status InsFirst(Link h,Link s);
//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
Status DelFirst(Link h,Link &q);
//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
Status Append(LinkList &L,Link s);
//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
Status Remove(LinkList &L,Link &q);
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
Status InsBefore(LinkList &L,Link &p,Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点
Status InsAfter(LinkList &L,Link &p,Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点
Status SetCurElem(Link &p,ElemType e);
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
ElemType GetCurElem(Link p);
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
Status ListEmpty(LinkList L);
//若线性链表L为空表，则返回TRUE,否则返回FALSE
int ListLength(LinkList L);
//返回线性链表L中的元素个数
Position GetHead(LinkList L);
//返回线性链表L中头结点的位置
Position GetLast(LinkList L);
//返回线性链表L中最后一个结点的位置
Position PriorPos(LinkList L,Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接前趋的值
//若无前趋，返回NULL
Position NextPos(LinkList L,Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的值
//若无后继，返回NULL
Status LocatePos(LinkList L,int i,Link &p);
//返回p指示线性链表L中第i个结点的位置并返回OK,i值不合法时返回ERROR
Position LocateElem(LinkList L,ElemType e,
Status(*compare)(ElemType,ElemType));
//返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置，
//若下存在这样的元素，则返回NULL
Status ListTraverse(LinkList L,Status(*visit)());
//依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。
五、总结本课内容
循环链表的存储结构
双向链表的存储结构
4.3 稀疏矩阵
http://student.zjzkb.edu.cn/course_ware/data_structure/web/duoweishuzu/duoweishuzu5.2.3.1.htm
设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，则称A为稀疏矩阵。
1、稀疏矩阵的压缩存储
为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。
稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法【参见参考书目】。
2、三元组表
将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。
注意：
以下的讨论中，均假定三元组是按行优先顺序排列的。
【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)
（1）三元组表的类型说明
为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：
#define MaxSize 10000
//由用户定义
typedef int DataType； //由用户定义
typedef struct { //三元组
int i，j；//非零元的行、列号
DataType v； //非零元的值
}TriTupleNode；
typedef struct{ //三元组表
TriTupleNode data[MaxSize]； //三元组表空间
int
m,n，t； //矩阵的行数、列数及非零元个数
}TriTupleTable；
(2) 压缩存储结构上矩阵的转置运算
一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
A[i][j]=B[j][i]，0≤i<m，0≤j<n，
即A的行是B的列，A的列是B的行。
【例】下图中的B和上图中的A互为转置矩阵。
①三元组表表示的矩阵转置的思想方法
第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data。
②三元组表的转置
方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。
③具体算法：
void TransMatrix(TriTupleTable
*b，TriTupleTable *a)
{//*a，*b是矩阵A、B的三元组表表示，求A转置为B
int p，q，col；
b->m=a->n； b->n=a->m； //A和B的行列总数互换
b->t=a->t；
//非零元总数
if(b->t<=0)
Error("A=0")； //A中无非零元，退出
q=0；
for(col=0；col<a->n；col++) //对A的每一列
for(p=0；p<a->t；p++)
//扫描A的三元组表
if(a->data[p]．j==col){ //找列号为col的三元组
b->data[q)．i=a->data[p].j；
b->data[q]．j=a->data[p].i；
b->data[q]．v=a->data[p].v；
q++；
}
}
//TransMatrix
④算法分析
该算法的时间主要耗费在col和p的二重循环上：
若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。
通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。
由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。