第4讲线性表(三)

1、第第4 4讲讲 第第2 2章线性表章线性表 (三)2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 2.5 2.5 有序表有序表 2.3.3 2.3.3 双链表双链表 对于双链表对于双链表,采用类似于单链表的类型定义采用类似于单链表的类型定义,其其DLinkList类型的定义如下类型的定义如下: typedef struct DNode /*定义双链表结点类型定义双链表结点类型*/ ElemType data; struct DNode *prior; /*指向前驱结点指向前驱结点*/struct DNode *next; /*指向后继结点指向后继结点*

2、/ DLinkList;2.3 2.3 线性表的链式存储线性表的链式存储 在双链表中在双链表中, ,有些操作如求长度、取元素值和有些操作如求长度、取元素值和查找元素等操作算法与单链表中相应算法是相同的查找元素等操作算法与单链表中相应算法是相同的, ,这里不多讨论。但在单链表中这里不多讨论。但在单链表中, ,进行结点插入和删除进行结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链时涉及到前后结点的一个指针域的变化。而在双链表中表中, ,结点的插入和删除操作涉及到前后结点的两个结点的插入和删除操作涉及到前后结点的两个指针域的变化。指针域的变化。双链表中插入结点示意图双链表中插入结点示意图

3、归纳起来归纳起来,在双链表中在双链表中p所指的结点之后插入所指的结点之后插入一个一个*s结点。其操作语句描述为结点。其操作语句描述为: s-next=p-next;/*将将*s插入到插入到*p之后之后*/ p-next-prior=s; s-prior=p; p-next=s;删除结点示意图删除结点示意图 在 双 链 表在 双 链 表中删除一个中删除一个结点的过程结点的过程如右图所示如右图所示: 归纳起来归纳起来, ,删除双链表删除双链表L L中中* *p p结点的后续结点。结点的后续结点。其操作语句描述为其操作语句描述为: : p-next=q-next; q-next-prior=p;2.

4、3.4 2.3.4 循环链表循环链表 循环链表循环链表是另一种形式的链式存储结构。它的是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空特点是表中最后一个结点的指针域不再是空, ,而是而是指向表头结点指向表头结点, ,整个链表形成一个环。由此整个链表形成一个环。由此, ,从表中从表中任一结点出发均可找到链表中其他结点。任一结点出发均可找到链表中其他结点。 带头结点的循环单链表和循环双链表的示意图带头结点的循环单链表和循环双链表的示意图 例例2.7 编写出判断带头结点的双向循环链表编写出判断带头结点的双向循环链表L是否是否对称相等的算法。对称相等的算法。 解解:p从左向右扫描

5、从左向右扫描L,q从右向左扫描从右向左扫描L,若对应数若对应数据结点的据结点的data域不相等域不相等,则退出循环则退出循环,否则继续比较否则继续比较,直到直到p与与q相等或相等或p的下一个结点为的下一个结点为*q为止。对应算为止。对应算法如下法如下:int Equeal(DLinkList *L) int same=1; DLinkList *p=L-next; /*p指向第一个数据结点指向第一个数据结点*/ DLinkList *q=L-prior; /*q指向最后数据结点指向最后数据结点*/ while (same=1) if (p-data!=q-data) same=0; else

6、if (p=q) break; /*数据结点为偶数的情况数据结点为偶数的情况*/ q=q-prior; if (p=q) break; /*数据结点为奇数的情况数据结点为奇数的情况*/ p=p-next; return same;2.3.5 2.3.5 静态链表静态链表 静态链表借用一维数组来描述线性链表。数组中静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点的一个分量表示一个结点,同时使用同时使用游标游标(指示器指示器cur即即为为伪指针伪指针)代替指针以指示结点在数组中的相对位置。代替指针以指示结点在数组中的相对位置。数组中的第数组中的第0个分量可以看成头结点个分量可以看成

7、头结点,其指针域指示静其指针域指示静态链表的第一个结点。态链表的第一个结点。 这种存储结构仍然需要预先分配一个较大空间这种存储结构仍然需要预先分配一个较大空间,但但是在进行线性表的插入和删除操作时不需要移动元素是在进行线性表的插入和删除操作时不需要移动元素,仅需要修改仅需要修改“指针指针”,因此仍然具有链式存储结构的主因此仍然具有链式存储结构的主要优点。要优点。 1 0 张斌 2 1 刘丽 3 2 李英 4 3 陈华 5 4 王奇 6 5 董强 7 6 王萍 0 7 8 9 数数据据域域 游游标标域域 1 0 张斌 2 1 刘丽 3 2 李英 5 3 陈华 5 4 王奇 6 5 董强 7 6

8、王萍 0 7 8 9 数数据据域域 游游标标域域 删删除除“陈陈华华” （a） 1 0 张斌 2 1 刘丽 8 2 李英 5 3 4 王奇 6 5 董强 7 6 王萍 0 7 王华 3 8 9 数数据据域域 游游标标域域 在在“刘刘丽丽”之之后后插插入入“王王华华” （b） （c） 下图给出了一个静态链表的示例。图下图给出了一个静态链表的示例。图(a)是一个修改之前是一个修改之前的静态链表的静态链表,图图(b)是删除数据元素是删除数据元素“陈华陈华”之后的静态链表之后的静态链表,图图(c)插入数据元素插入数据元素“王华王华”之后的静态链表之后的静态链表,图中用阴影表示修图中用阴影表示修改的游标

9、。改的游标。 2.4 2.4 线性表的应用线性表的应用 计算任意两个表的简单自然连接过程讨论线性计算任意两个表的简单自然连接过程讨论线性表的应用。假设有两个表表的应用。假设有两个表A和和B,分别是分别是m1行、行、n1列列和和m2行、行、n2列列,它们简单自然连接结果它们简单自然连接结果C=A B,其其中中i表示表表示表A中列号中列号,j表示表表示表B中的列号中的列号,C为为A和和B的的笛卡儿积中满足指定连接条件的所有记录组笛卡儿积中满足指定连接条件的所有记录组,该连接该连接条件为表条件为表A的第的第i列与表列与表B的第的第j列相等。例如列相等。例如:i=j 111332321A436153B

10、C=A B的计算结果如下的计算结果如下: 3=16111143332533324332153321 由于每个表的行数不确定由于每个表的行数不确定,为此为此,用单链表作为表用单链表作为表的存储结构的存储结构,每行作为一个数据结点。另外每行作为一个数据结点。另外,每行中的每行中的数据个数也是不确定的数据个数也是不确定的,但由于提供随机查找行中的但由于提供随机查找行中的数据数据,所以每行的数据采用顺序存储结构所以每行的数据采用顺序存储结构,这里用长度这里用长度为为MaxCol的数组存储每行的数据。因此的数组存储每行的数据。因此,该单链表该单链表中数据结点类型定义如下中数据结点类型定义如下: #def

11、ine MaxCol 10/*最大列数最大列数*/ typedef struct Node1/*定义数据结点类型定义数据结点类型*/ ElemType dataMaxCol; struct Node1 *next; /*指向后继数据结点指向后继数据结点*/ DList; 另外另外,需要指定每个表的行数和列数需要指定每个表的行数和列数,为此将单链为此将单链表的头结点类型定义如下表的头结点类型定义如下: typedef struct Node2/*定义头结点类型定义头结点类型*/ int Row,Col;/*行数和列数行数和列数*/ DList *next;/*指向第一个数据结点指向第一个数据结点

12、*/ HList; 采用尾插法建表方法创建单链表采用尾插法建表方法创建单链表,用户先输入表用户先输入表的行数和列数的行数和列数,然后输入各行的数据然后输入各行的数据,为了简便为了简便,假设表假设表中数据为中数据为int型型,因此定义因此定义: typedef int ElemType; 对应的建表算法如下对应的建表算法如下: void create(HList *&h) int i,j; DList *r,*s; h=(HList *)malloc(sizeof(HList);h-next=NULL; printf(表的行数表的行数,列数列数:); scanf(%d%d,&h-

13、Row,&h-Col); for (i=0;iRow;i+) printf( 第第%d行行:,i+1); s=(DList *)malloc(sizeof(DList); for (j=0;jCol;j+) scanf(%d,&s-dataj); if (h-next=NULL) h-next=s; else r-next=s; r=s; /*r始终指向最后一个数据结点始终指向最后一个数据结点*/ r-next=NULL; 对应的输出表的算法如下对应的输出表的算法如下:void display(HList *h) int j; DList *p=h-next; while (p

14、!=NULL) for (j=0;jCol;j+) printf(%4d,p-dataj); printf(n); p=p-next; 为了实现两个表为了实现两个表h1和和h2的简单自然连接的简单自然连接,先要输入先要输入两个表连接的列序号两个表连接的列序号f1和和f2,然后扫描单链表然后扫描单链表h1,对于对于h1的每个结点的每个结点,从头至尾扫描单链表从头至尾扫描单链表h2,若自然连接条若自然连接条件成立件成立,即即h1的当前结点的当前结点*p和和h2的当前结点的当前结点*q满足满足: p-dataf1-1=q-dataf2-1则在新建单链表则在新建单链表h中添加一个新结点。中添加一个新结

15、点。 新建的单链表新建的单链表h也是采用尾插法建表方法创建的。也是采用尾插法建表方法创建的。 实现两个表实现两个表h1和和h2的简单自然连接并生成结果的简单自然连接并生成结果h的算法如下的算法如下:void link(HList *h1,HList *h2,HList *&h) int f1,f2,i;DList *p=h1-next,*q,*s,*r; printf(连接字段是连接字段是:第第1个表位序个表位序,第第2个表位序个表位序:); scanf(%d%d,&f1,&f2); h=(HList *)malloc(sizeof(HList); h-Row=0; h

16、-Col=h1-Col+h2-Col; h-next=NULL; while (p!=NULL) q=h2-next; while (q!=NULL) if (p-dataf1-1=q-dataf2-1) /*对应字段值相等对应字段值相等*/ s=(DList *)malloc(sizeof(DList); /*创建一个数据结点创建一个数据结点*/ for (i=0;iCol;i+) /*复制表复制表1的当前行的当前行*/ s-datai=p-datai;for (i=0;iCol;i+) s-datah1-Col+i=q-datai;/*复制表复制表2的当前行的当前行*/ if (h-nex

17、t=NULL) h-next=s;else r-next=s;r=s; /*r始终指向最后数据结点始终指向最后数据结点*/h-Row+; /*表行数增表行数增1*/ q=q-next; /*表表2下移一个记录下移一个记录*/ p=p-next; /*表表1下移一个记录下移一个记录*/ r-next=NULL;/*表尾结点表尾结点next域置空域置空*/ 2.5 2.5 有序表有序表 所谓所谓有序表有序表,是指这样的线性表是指这样的线性表,其中所有元素其中所有元素以递增或递减方式排列以递增或递减方式排列,并规定有序表中不存在元并规定有序表中不存在元素值相同的元素。在这里仍以顺序表进行存储。素值相同的元素。在这里仍以顺序表进行存储。 其中只有其中只有ListInsert()基本运算与前面的顺序表基本运算与前面的顺序表对应的运算有所差异对应的运算有所差异,其余都是相同的。有序表其余都是相同的。有序表的的ListInsert()运算对应的算法如下运算对应的算法如下: int ListInsert(SqList &L,ElemT