第二章 线性表 线性表是一种最简单的线性结构 线性结构是一个数据元素的有序（次序）集.

Presentation on theme: "第二章 线性表 线性表是一种最简单的线性结构 线性结构是一个数据元素的有序（次序）集."— Presentation transcript:

1 第二章 线性表 线性表是一种最简单的线性结构 线性结构是一个数据元素的有序（次序）集

2 线性结构的基本特征: 1．集合中必存在唯一的一个“第一元素”； 2．集合中必存在唯一的一个 “最后元素”
3．除最后元素之外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。

3 例如：alphabet=(a,b,c,…,z) 和 prime=(2,3,5,7,11,…,97)alphabet是字母表，其结点是一个英文字母，prime是100以内的素数表，结点是整型数。且只有一个域的线性表， 在稍复杂的线性表中,一个结点(数据元素)可以由若干个数据项组成,此时常把结点称为记录,含有大量记录的线性表以称文件.例如学生登记表(如表2.1所示)可以构成线性表形式的一个文件。表中每个学生对应一个结构或记录类型，由学号、姓名、班级、性别、出生年月等数据项组成。 学号 姓名 班级 性别 出生年月 王浩 光126 男 1996.1 杨帅 高波 1995.1 …

4 线性表的抽象数据类型 线性表是一种相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可进行插入和删除等操作。

5 ADT List { 数据关系： 线性表的抽象数据类型定义如下：
数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } { 称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } { 设线性表为 (a1，a2, ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。称a1为“起始结点”，an为“终止结点”。ai的前驱为ai-1，后续为ai+1。}

6 加工型操作 引用型操作 结构销毁操作 } ADT List 基本操作： DestroyList( &L ) ListEmpty( L )
结构初始化操作 InitList( &L ) 结构销毁操作 DestroyList( &L ) ListEmpty( L ) ListLength( L ) 引用型操作 PriorElem( L, cur_e, &pre_e ) NextElem( L, cur_e, &next_e ) GetElem( L, i, &e ) ListTraverse(L, visit( )) LocateElem( L, e, compare( ) ) 加工型操作 ClearList( &L ) PutElem( &L, i, &e ) ListInsert( &L, i, e ) ListDelete(&L, i, &e) } ADT List

7 2.2 线性表的顺序表示和实现 在计算机内，存储线性表最简单的方式就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储。
2.2 线性表的顺序表示和实现 在计算机内，存储线性表最简单的方式就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储。 线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表，

8 依次存放线性表中的数据元素 线性表的起始地址， 称作线性表的基地址 用一组地址连续的存储单元（一组数组）
a1 a2 … ai-1 ai … an 线性表的起始地址， 称作线性表的基地址

9 以“存储位置相邻”表示有序对<ai-1，ai> 即：LOC(ai) = LOC(ai-1) + C
一个元素占用的存储单元个数 ↑ 所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址

10 DATATYPE library[maxsize]; 备用空间
V数组下标 内存 元素序号 a0 1 #define maxsize 1000 int data[maxsize]; 1 a1 2 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[maxsize]; n-1 an-1 n 备用空间 maxsize-1 数据元素不是简单类型时,可定义结构体数组

11 只要知道顺序表的基地址和每个数据元素所占的存储单元的个数，就可以求出顺序表中任何一个数据元素的存储地址。由于计算顺序表中每个数据元素存储地址的时间相同，所以顺序表具有随机存取的特点。
由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组来描述。

12 #define LISTINCREMENT 10 // 线性表存储空间的分配增量
#define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { } SqList; // 俗称 顺序表/ 把该段程序代码作为一个独立文件，命名为mem2-1.cpp ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位)

13 在上述定义中，数组指针elem指示线性表的基地址，length指示线性表的当前长度。顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”。listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。

14 线性表的基本操作在顺序表中的实现 InitList(&L) // 结构初始化 ListInsert(&L, i, e) // 插入元素 ListDelete(&L, i) // 删除元素 LocateElem(L, e, compare()) // 查找

15 处理动态链表所需的函数 malloc函数 void * malloc(unsigned int size);
在内存的动态存储区中分配一个长度size的连续空间.此函数的返回值是一个指向分配域起始地址的指针(类型为void). 2. calloc函数 void * calloc(unsigned n,unsigned size); 其作用是在内存的动态分配区中分配n个长度为size的连续空间.函数返回一个指向分配域起始地址的指针;如果分配不成功返回NULL. 3. realloc函数 void * realloc(void *p, unsigned size) P24 将 p 所指的已分配空间大小调整为 size 个字节,size可以比原来分配的空间大或小。 4. free函数 void free(void *p); 释放p所指向的内存区,使这部分内存区被其他变量使用

16 Status InitList_Sq( SqList & L) { // 构造一个最大容量为 LIST_INIT_SIZE 的顺序表
L.elem = (ElemType*)malloc(LIST_INIT_SIZE *sizeof( ElemType)); // 为顺序表分配大小为 LIST_INIT_SIZE 的数组空间 if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK;

17 ListInsert(&L, i, e)的实现：
线性表操作 ListInsert(&L, i, e)的实现： 首先分析: 插入元素时， 线性表的逻辑结构发生什么变化？

18 … an a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai e
(a1, …, ai-1, e, ai, …, an) <ai-1, ai> <ai-1, e>, <e, ai> a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai … an e 表的长度增加

19 // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1
Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1 ElemType * newbase,*q,*p; //所需变量的定义 } // ListInsert_Sq if(i<1||i>L.length +1) return ERROR//i值不合法 if(L.length>=L.listsize{ //当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMET)*sizeof(ElemType))}); if(newbase)exit(OVERFLOW);//存储分配失败 L.elem=newbase;//新基址 L.listsize+=LISTINCREMENT;//增加存储容量 }

20 …… // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1
Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1 } // ListInsert_Sq …… q = &(L.elem[i-1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入e ++L.length; // 表长增1 return OK; 元素右移

21 ListDelete(&L, i, &e)的实现：
线性表操作 ListDelete(&L, i, &e)的实现： 首先分析： 删除元素时， 线性表的逻辑结构发生什么变化？

22 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an
<ai-1, ai>, <ai, ai+1> <ai-1, ai+1> a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an 表的长度减少

23 if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法
Status ListDelete_Sq (SqList &L, int i, ElemType &e) { ElemType *p,*q; //变量定义 } // ListDelete_Sq if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法 p = &(L.elem[i-1]); // p 为被删除元素的位置 e = *p; // 被删除元素的值赋给 e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; // 表长减1 return OK; 元素左移

24 考虑移动元素的平均情况: 在等概率的情况下,在长度为n的线性表中插入一个元素所需移动元素的平均次数为：
在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时,其时间主要耗费在移动元素上(即移动元素的操作为算法时间复杂度的基本操作),移动元素的个数取决于插入或删除元素的位置. 在顺序存储结构的线性表中插入或删除一个数据元素,平均约移动表中一半元素, 则插入或删除算法的时间复杂度为: O( ListLength(L)) 在等概率的情况下,在长度为n的线性表中插入一个元素所需移动元素的平均次数为： 在线性表中任何一个位置上删除一个元素所移动元素的平均次数为：

25 利用上述定义的线性表类型 可以实现其它更复杂的操作 例 2-1 例 2-2

26 例 2-1 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合A＝A∪B。

27 上述问题可演绎为： 要求对线性表作如下操作：
扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。

28 La v i v i v i v i v i v i v h y a f c z b v e d i Lb v a c e d i i

29 操作步骤： 1．从线性表 LB 中依次察看每个数据元素; GetElem(LB, i)→e 2．依值在线性表 LA 中进行查访;
LocateElem(LA, e, equal( )) 3．若不存在，则插入之。 ListInsert(LA, n+1, e) ( n 表示线性表 LA 当前长度)

30 操作过程可用下列算法描述并实现。 #include"head1-1.h" //本书第一章定义的头文件 #include"mem2-1.cpp" //本节定义的顺序存储结构 #include"op2-1.cpp" //本节由算法2.1～算法2.7组成的独立文件

31 void unionlist(SqList &La, SqList Lb)
{ //将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len, Lb_len, i; ElemType e; La_len=ListLength(La); Lb_len=ListLength(Lb); //求线性表的长度 for (i = 1; i<=Lb_len; i++){ GetElem(Lb, i, e); //取Lb中第i个数据元素赋给e if(!LocateElem(La, e)) ListInsert(La, ++La_len, e); //La中不存在和e相同的数据元素，则插入之 }

32 int main() //主程序用来验证unionlist算法以及部分基本操作
{ int i; SqList Lc, Ld; InitList(Lc); //构造空的顺序表Lc和Ld InitList(Ld); for(i=1; i<5; i++) ListInsert(Lc, i, i); //构造顺序表Lc=(1,2,3,4) ListInsert(Ld, i, 2*i); //构造顺序表Ld=(2,4,6,8) unionlist(Lc, Ld) //验证Lc∪Ld算法 for(i=0; i<Lc.length; i++) printf("%d ", Lc.elem[i]); return 0; }

33 归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。
例 2-2 归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。 设 La = (a1, …, ai, …, an), Lb = (b1, …, bj, …, bm) Lc = (c1, …, ck, …, cm+n) 则 k = 1, 2, …, m+n

34 2 3 5 6 8 8 8 9 11 11 Lc La 3 5 8 11 i i i i i Lb 2 6 8 9 11 j j j j j j

35 例如，设La = (3，5，8，11)，Lb = (2，6，8，9，15，20)。
则Lc = (2，3，5，6，8，8，9，11，15，20) 算法思路：依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给Lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。 按升序合并两个表的算法实现如下: #include"head1-1.h" //本书第1章定义的头文件 #include"mem2-1.cpp" //本节定义的顺序存储结构 #include"op2-1.cpp" //本节由算法2.1～算法2.7组成一个独立的文件

36 void MergeList(SqList La, SqList Lb, SqList &Lc)
{ //归并La和Lb得到新的线性表Lc，Lc的数据元素按值从小到大升序排列 int i=1, j=1, k=1; int La_len, Lb_len; ElemType ai, bj; La_len=ListLength(La); Lb_len = ListLength(Lb); while( (i<=La_len)&&(j<=Lb_len)){//La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai<=bj){ListInsert(Lc, k++, ai); i++;} else{ListInsert(Lc, k++, bj); j++;} } while(i<=La_len) { //插入La中剩下的元素 GetElem(La, i++, ai); ListInsert(Lc, k++, ai); } while (j<=Lb_len) { //插入Lb中剩下的元素 GetElem(Lb, j++, bj); ListInsert(Lc, k++, bj); }

37 int main() //主程序用来验证MergeList算法的实现
{ int i; SqList Lc, Ld, Le; InitList(Lc); //构造空的顺序表Lc、Ld和Le InitList(Ld); InitList(Le); for(i=1; i<5; i++) ListInsert(Lc, i, i); //构造升序顺序表Lc=(1,2,3,4) ListInsert(Ld, i, 2*i); //构造升序顺序表Ld=(2,4,6,8) MergeList(Lc, Ld, Le); //验证Lc和Ld归并算法 printf("Lc和Ld归并的结果为:\n"); for(i=0; i<Le.length; i++) printf(" %d ", Le.elem[i]); printf("\n"); return 0; }

38 2.3 线性表类型 的实现----链式映象

39 一、单链表 二、结点和单链表的 C 语言描述 三、线性表的操作在单链表中的实现 四、其它形式的链表

40 用一组地址任意的存储单元存放线性表中的数据元素。
一、单链表 用一组地址任意的存储单元存放线性表中的数据元素。 data next 以数据域 + 指针域 = 结点 N个结点链结成一个链表即为线性表的链式存储结构. 若链表中每个结点中只包含一个指针域,称线性链表或单链表

41 如图所示是线性表(a1，a2，a3，a4，a5，a6)对应的链式存储结构示意图。

42 通常把链表画成用箭头相链接的结点的序列，结点之间的箭头表示指针域中的存储地址。如上图所示的线性链表可画成如下图所示的形式，这是因为在使用链表时，人们关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。

43 以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针.
单链表由头指针H唯一确定。头指针指向单链表的第一个结点，也就是把单链表第一个结点的地址放在H中，所以，H是一个Node类型的变量。头指针为NULL(空)表示一个空表。在C语言中可用“结构指针”来描述。 H … bat cat eat mat ^

44 a1 a2 … ... an ^ 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针 头指针 头指针
线性表为空表时， 头结点的指针域为空 头指针 空指针 头结点 a a … an ^ 

45 a1 ai an ….. 在链表的开始结点之前附加一个头结点，会带来两个优点： a、链表在第一个位置上的操作和在表中其它位置上的操作一致，无需进行特殊处理； b、头指针总是指向头结点，空表和非空表的处理方法一样。 在单链表中,任何两个元素的存储位置之间没有固定的联系,每个元素的存储位置都包含在直接前驱结点中,由此,在取第i个元素时必须从头指针出发寻找,因此,单链表是非随机存取的存储结构.

46 ElemType data; // 数据域 struct Lnode *next; //后继结点的指针域
//线性表的单链表存储结构如下 Typedef struct LNode { ElemType data; // 数据域 struct Lnode *next; //后继结点的指针域 } LNode, *LinkList; 注：1、线性表的单链表存储结构在本书作为一个独立文件命名为mem2-2.cpp。 2、为了程序调试的方便，把算法2.8～算法2.15做成一个独立的文件，命名为op2-2.cpp。

47 2.3.2 单链表基本操作实现 void InitList(LinkList &L) //构造一个空单链表
单链表基本操作实现 void InitList(LinkList &L) //构造一个空单链表 int ListLength(LinkList L) //求单链表长度 ListInsert(&L, i, e) // 插入数据元素 ListDelete(&L, i, e) // 删除数据元素 GetElem(L, i, e) // 取第i个数据元素 ListEmpty(LinkList L) // 单链表是否为空 LocatElem(LinkList L, ElemType e) // 按值查找单链表

48 线性表的操作 ListInsert(&L, i, e)
在单链表中的实现： 有序对 <ai-1, ai> 改变为 <ai-1, e> 和<e, ai> ai-1 ai-1 ai e

49 可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。

50 O(ListLength(L)) 算法的时间复杂度为:
Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L LinkList p=L, s; int j=0; while (p && j < i-1) { p = p->next; j ++; } // 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; // i 大于表长或者小于1 s = （LinkList）malloc(sizeof(Lnode)) ; // 生成新结点 if ( s == NULL) return ERROR; s->data = e; s->next = p->next; p->next = s; // 插入 return OK; O(ListLength(L)) 算法的时间复杂度为:

51 L a1 ai-1 an ….. ai P p

52 if ( s == NULL) return ERROR; s->data = e;
s = （LinkList）malloc(sizeof(Lnode)) ; // 生成新结点 if ( s == NULL) return ERROR; s->data = e; s->next = p->next; p->next = s; // 插入 return OK; p ai-1 ai-1 ai e s

53 线性表的操作ListDelete (&L, i, &e)在链表中的实现:
有序对<ai-1, ai> 和 <ai, ai+1> 改变为 <ai-1, ai+1> ai-1 ai-1 ai ai+1

54 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。
q = p->next; p->next = q->next; e = q->data; delete(q); p q ai-1 ai-1 ai ai+1

55 算法的时间复杂度为: O(ListLength(L))
Status ListDelete_L(LinkList L, int i, ElemType &e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete_L LinkList p=L, q; int j=0; while (p && j < i-1) { p = p->next; ++j; } // 寻找第 i-1 个结点，并令 p 指向其前趋 if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理 q = p->next; p->next = q->next; // 删除并释放结点 e = q->data; free(q); return OK; 算法的时间复杂度为: O(ListLength(L))

56 L a1 ai-1 an ….. ai P j=0 P j=0 P j=i-2

57 如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。

58 操作步骤： 例：从前向后输入 n 个数据元素的值， 建立带头结点的单链表。 一、建立一个“空表”； 二、从前向后一个一个建
立结点输入数据元素 ai，并插入； a1 ….. ai ….. an 三、依次类推，直至输入an为止。

59 操作步骤： 例：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。 一、建立一个“空表”； 二、建立结点输入数据 元素an，并插入；
三、建立结点输入数据 元素an-1，并插入； an an-1 四、依次类推，直至输入a1为止。

60 O(Listlength(L)) void CreateList_L(LinkList &L, int n) {
LinkList p, int i; //算法所需变量的定义 L = (LinkList)malloc(sizeof(LNode)) L->next = NULL; // 先建立一个带头结点的单链表 for (i = n; i > 0; i --) { p = (LinkList)malloc(sizeof(Lnode)) ; scanf(“%d”,&p->data); // 输入元素值 p->next = L->next; L->next = p; // 插入 } 算法的时间复杂度为: O(Listlength(L))

61 用上述定义的单链表实现线性表的操作时， 存在的问题： 1．单链表的表长是一个隐含的值； 2．在单链表的最后一个元素之后插入元素时， 需遍历整个链表；

62 单链表应用举例 例2.3 设有两个集合A和B，现要求一个新的集合A＝A∪B(本例采用链式存储结构实现该算法)。 算法思路： 用链表La和Lb表示两个集合，即链表中的数据元素为集合中的成员。将存在于线性表Lb中而不存在于线性表La中的数据元素插入到线性表La中去。操作步骤同例2.1，只是采用的存储结构不同。

63 算法具体实现如下： #include"head1-1.h" //本书第一章定义的头文件
#include"mem2-2.cpp" //本节定义的链式存储结构 #include"op2-2.cpp“ //本节由算法2.8～算法2.15组成独立文件 void unionlist(LinkList &La, LinkList Lb) { //将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len, Lb_len, i; ElemType e; La_len=ListLength(La); Lb_len=ListLength(Lb); //求线性表的长度 for (i = 1; i<=Lb_len; i++) GetElem(Lb, i, e); //取Lb中第i个数据元素赋给e if(!LocateElem(La, e)) ListInsert(La, ++La_len, e); //La中不存在和e相同的数据元素，则插入之 }

64 int main() //主程序用来验证unionlist算法以及部分基本操作
{ int i; LinkList Lc, Ld; InitList(Lc); //构造空的单链表Lc和Ld InitList(Ld); for(i=1; i<5; i++) ListInsert(Lc, i, i); //构造单链表Lc=(1,2,3,4) ListInsert(Ld, i, 2*i); //构造单链表表Ld=(2,4,6,8) unionlist(Lc, Ld) //验证Lc∪Ld算法 printf(" 归并后的结果为:\n "); for(i=1; i<=ListLength(Lc); i++) { GetElem(Lc, i, e); //用e返回单链表的第i个元素，并打印输出 printf("%d ", e); } return 0;

65 例2.4 已知线性表La和Lb中的数据元素按值从小到大升序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值从小到大升序排列(本例采用链式存储结构实现该算法)。 算法思路： 建立3个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点。把La的头结点作为Lc的头结点，依次扫描La和Lb的结点，比较La和Lb当前结点数据域的值，将较小值的结点附加到Lc的末尾，如此直到一个单链表被扫描完，然后将未完的那个单链表中余下的结点附加到Lc的末尾即可。

66 将两表合并成一表的算法实现如下： #include"head1-1.h" #include"mem2-2.cpp" #include"op2-2.cpp" void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) { //已知单链线性表La和Lb的元素按值升序排列 //归并La和Lb得到新的单链线性表Lc , Lc的元素也按值升序排列 LinkList pa, pb, pc; pa=La->next; pb=Lb ->next ; Lc=pc=La; //用La的头结点作为Lc的头结点 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); //释放Lb的头结点

67 int main() //主程序用来验证MergeList算法的实现
{ int i; LinkList Lc, Ld, Le, p; InitList(Lc); //构造空的顺序表Lc、Ld和Le InitList(Ld); for(i=1; i<5; i++) ListInsert(Lc, i, i); /构造升序顺序表Lc=(1,2,3,4) ListInsert(Ld, i, 2*i); //构造升序顺序表Ld=(2,4,6,8) MergeList(Lc, Ld, Le); //调用Lc和Ld归并算法，得到Le printf("Lc和Ld归并的结果为:\n"); p=Le->next; while(p){printf(" %d ", p->data); //打印输出归并后的结果 p=p->next; } printf("\n"); return 0; 例2.4中的算法也可采用链表基本操作的组合来实现，其算法类似于例2.2。

68 四、其它形式的链表 1. 双向链表 前面介绍的单链表允许从一个结点直接访问它的后继结点，找直接后继结点的时间复杂度是O(1)。要找某个结点的直接前驱结点，只能从表的头指针开始遍历各结点，则找直接前驱结点的时间复杂度是O(n)，n是单链表的长度。 如果希望找直接前驱结点和直接后继结点的时间复杂度都是O(1)，那么，需要在结点中设两个指针域： 一个保存直接前驱结点的地址，称为prior指针域； 一个保存直接后继结点的地址，称为next指针域。 这样的链表就是双向链表。双向链表的结点结构示意图如图所示。

69 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior;
双向链表结点的定义与单链表结点的定义很相似，只是双向链 表多了一个字段prior。 双向链表结点的C语言描述如下： typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList;

70 ai ai-1 ai+1 p p->next->prior=p p=p->prior->next

71 双向链表的优点： 基本操作--找当前结点p的前驱, 双向链表的时间复杂度是常量级。 在线性表中，既找后继又找前驱的操作，多采用双向链表。

72 双向链表的操作特点： 1、“查询”（找特点的元素或者找第i个元素）和单链表相同。
2、“插入” 和“删除”时需要同时修改两个方向上的指针,改变结点之间的逻辑关系。

73 插入 p ai-1 ai-1 ai ai e s s->next = p->next; p->next = s; s->next->prior = s; s->prior = p;

74 删除 ai-1 ai-1 ai ai+1 p p->prior->next = p->next; p->next->prior = p->prior; free(p);

75 2.4.2 循环链表 a1 a2 … ... an 最后一个结点的指针域的指针又指回第一个结点的链表
循环链表 最后一个结点的指针域的指针又指回第一个结点的链表 a a … an 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

76 双向循环链表 空表 非空表 a a2 … an

77 从上面两节的讨论中可见，由于链表在空间的合理利用上，以及插入、删除时不需要移动元素等优点，因此在很多场合下，链表是线性表的首选存储结构。 然而，在实现某些基本操作中它也存在着缺点，如求线性表的长度时不如顺序存储结构； 另一方面，由于在链表中结点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念已淡化，而被数据元素在线性链表中的“位置”所代替。 读者可从实际应用角度出发重新定义线性链表及其基本操作。