第二章 线性表 ⒈教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。

Presentation on theme: "第二章 线性表 ⒈教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。"— Presentation transcript:

1 第二章 线性表 ⒈教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。
⒈教学内容：2.1 线性表逻辑结构； 2.2 线性表的顺序存储及运算实现； 2.3 线性表的链式存储和实现。 ⒉教学目的：⑴理解线性表的定义及其运算； ⑵理解顺序表和链表的定义、组织形式、结构特征和类型说明； ⑶掌握在这两种表上实现的插入、删除和按值查找的算法； ⑷了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。

2 第二章 线性表 ⒊教学重点： ⑴线性表的定义及逻辑上的特点； ⑵顺序表上插入、删除和定位运算的实现； ⑶单链表的结构特点及类型说明；
⑷头指针和头结点的作用及区别； ⑸定位、删除、插入运算在单链表上的实现； ⑹循环链表、双链表的结构特点，循环链表、双链表上删除与插入运算的实现。

3 第二章 线性表 ⒋教学难点： ⑴线性表与线性结构的联系与区别； ⑵头结点在链表中的作用；指针操作； ⑶删除、插入运算中的指针操作顺序；
⑷双链表上指针的操作顺序。

4 第二章 线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素
除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继

5 2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列 例 英文字母表（A,B,C,…..Z)是一个线性表
(26，37，58，80，192，388) 例 数据元素

6 特征： 含有n个数据元素的线性表是一个数据结构： Linear_List=(D，R)
其中，D={ai|ai∈D0，i=1，2，…，n，n≥0} D0为某个数据对象； R={N}，N={<ai-1，ai>|ai-1,ai∈D0，i=1，2，…，n}； （a1 ，a2 ，……，ai ，……，an ） 特征： 元素个数n—表长度，n=0空表 1<i<n时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项

7 基本操作： Init_List(L) 初始化 Length_List (L) 求长度 Get_List(L，i) 取元素 Locate_List(L，x) 按值查找（定位） Insert_List (L，i，x) 插入（前插） Delete_List (L，i) 删除

8 ⑴线性表初始化：Init_List(L)
操作结果：构造一个空的线性表 ⑵求线性表的长度：Length_List(L) 初始条件：表L存在 操作结果：返回线性表中的所含元素的个数 ⑶取表元：Get_List(L,i) 初始条件：表L存在且1<=i<=Length_List(L) 操作结果：返回线性表L中的第ｉ个元素的值或地址

9 ⑷按值查找：Locate_List(L,x)，
ｘ是给定的一个数据元素。 初始条件：线性表L存在 操作结果：返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功；否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。

10 ⑸插入操作：Insert_List(L,i,x)
操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1，插入后表长=原表长+1。

11 ⑹删除操作：Delete_List(L,i)
1<=i<=n 操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，新表长＝原表长－１。

12 2.2 线性表的顺序存储及运算实现 线性表的顺序存储 顺序表上基本运算的实现 顺序表应用举例

13 2.2.1 线性表的顺序存储 顺序表： 定义：用一组地址连续的存储单元存放一个 线性表叫顺序表 元素地址计算方法：
线性表的顺序存储 顺序表： 定义：用一组地址连续的存储单元存放一个 线性表叫顺序表 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*d ≤i≤n LOC(a i+1)=LOC(a i)+d 其中： d—一个元素占用的存储单元个数 LOC(a1) —基地址 LOC(a i)—线性表第i个元素的地址

14 顺序映象(sequential mapping)
特点： 实现逻辑上相邻—物理地址相邻 实现随机存取 实现：可用C语言的一维数组实现

15 typedef int datatype; #define M 1000 datatype data[M]; int n;
V数组下标 内存 元素序号 a1 a2 an 1 2 n M 备用空间 n+1 typedef int datatype; #define M 1000 datatype data[M]; int n;

16 typedef struct { datatype data[MAXSIZE]; int last; } SeqList;
typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }datatype; datatype library[M]; typedef struct { datatype data[MAXSIZE]; int last; } SeqList; 数据元素不是简单类型时,可定义结构体数组

17 typedef struct SeqList *PSeqList；
void f(struet SeqList L，…) f(L1) typedef struct SeqList *PSeqList； void f(PSeqList pl) pl=&L1； f(pl)； PSeqList palist； Palist->n Palist->data[1], … , Palist->data[Palist->n]

18 顺序表上基本运算的实现 ⒈ 顺序表的初始化 顺序表的初始化即构造一个空表，对表是一个加工型的运算，因此，将 L设为指针参数，首先动态分配存储空间，然后，将表中 last 指针置为－1，表示表中没有数据元素。

19 SeqList *init_SeqList( )
{ SeqList *L; L=malloc(sizeof(SeqList)); L->last=-1; return L; }

20 ⒉插入运算 定义：线性表的插入是指在第i（1i  n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 变成长度为n+1的线性表
需将第i至第n共（n-i+1)个元素后移 算法 Ch2_1.c

21 x 内存 a1 a2 ai ai+1 an 1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai
1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai ai+1 an 1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 an-1 x

22 int Insert_SeqList(SeqList *L，int i，datatype x)
{　int j; if (L->last == MAXSIZE－1) { printf(＂表满＂); return(-1); } /*表空间已满，不能插入*/ if (i<1 || i>L->last+2)　　 /*检查插入位置的正确性*/ { printf(＂位置错＂); return(0); } for(j=L->last; j>=i-1; j--) L->data[j+1]=L->data[j]; /* 结点移动 */ L->data[i-1]=x;　　 　　 /*新元素插入*/ L->last++; 　 /*last仍指向最后元素*/ return (1);　 　/*插入成功，返回*/ }

23 插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在数据的移动上，在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 n－i＋1个元素，而 i 的取值范围为 ：1≤ i≤ n+1。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数： 设：Pi=1/ (n+1) ，即为等概率情况，则： 在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为Ｏ(n)。

24 定义：线性表的删除是指将第i（1i  n）个元素删除，使长度为n的线性表
⒊删除运算 定义：线性表的删除是指将第i（1i  n）个元素删除，使长度为n的线性表 变成长度为n-1的线性表 需将第i+1至第n共（n-i)个元素前移 算法 Ch2_2.c

25 内存 a1 a2 ai ai+1 an 1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai+1 V数组下标 1 i-1 n-2 i n-1 2 元素序号 i+1 n an ai+2

26 int Delete_SeqList(SeqList *L;int i)
{ int j; if(i<1 || i>L->last+1) /*检查空表及删除位置的合法性*/ { printf (＂不存在第i个元素＂); return(0); } for(j=i; j<=L->last; j++) L->data[j-1]=L->data[j]; /*向上移动*/ L->last--; return(1); /*删除成功*/ }

27 删除算法的时间性能分析 与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1--an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。 故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低

28 顺序存储结构的优缺点 优点 缺点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配，利用不充分 表容量难以扩充

29 ⒋按值查找 int Location_SeqList(SeqList *L, datatype x)
{ int i=0; while(i<=L.last && L->data[i]!= x) i++; if (i>L->last) return -1; else return i; /*返回的是存储位置*/ } 本算法的主要运算是比较。显然比较的次数与x在表中的位置有关，也与表长有关。平均比较次数为（n+1）/2，时间性能为O(n)。

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

31 例 2-1 将顺序表 (a1，a2，... ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大。 划分的基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： ⑴当前数据元素 ai 比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一个。 ⑵当前结点若比a1小，说明它应该在a1的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。

32 即最坏情况下移动数据时间性能为Ｏ(ｎ２)。
算法如下： void part(SeqList *L) { int i,j; datatype x,y; x=L->data[0]; /* 将基准置入 x 中*/ for (i=1; i<=L->last; i++) if (L->data[i]<x) /*当前元素小于基准*/ { y = L->data[i]; for(j=i-1;j>=0;j--) /*移动*/ L－>data[j+1]=L->data[j]; L->data[0]=y; } } 总的移动次数为 ： 即最坏情况下移动数据时间性能为Ｏ(ｎ２)。

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

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

35 操作步骤： 1．从线性表LB中依次察看每个数据元素; Get_List(LB，i)→e 2．依值在线性表LA中进行查访;
Locate_List(LA，e) 3．若不存在，则插入之。 Insert_List(LA, n+1, e)

36 void union(List &La, List Lb) {
La_len = Length_List(La); // 求线性表的长度 Lb_len = Length_List(Lb); for (i = 1; i <= Lb_len; i++) { Get_List(Lb, i, e); // 取Lb中第i个数据元素赋给e if (! Locate_List(La, e) ) Insert_List(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之 } } // union

37 例 2-3 已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。 仍选用线性表表示集合。

38 集合 B 集合 A 从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上 因此，算法的策略应该和例2-2相同

39 void union(List &La, List Lb) {
La_len=Length_List(La); Lb_len=Length_List(Lb); } // union Init_List(La); // 构造(空的)线性表LA for (i = 1; i <= Lb_len; i++) { } Get_List(Lb, i, e); // 取Lb中第 i 个数据元素赋给 e if (!Locate_List (La, e, equal( )) ) Insert_List (La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之

40 例 2-4 假设 La＝(3，5，8，11) Lb＝(2，6，8，9，11，15，20) 则
Lc＝(2，3，5，6，8，8，9，11，11，15，20) a 当a≤b时 C = b 当a>b时

41 void mergeList(List La, List Lb, List &Lc)
{ Init_List(Lc); i=j=1; k=0; La_len=Length_List(La);Lb_len=Length_List(Lb); while ((i<=La_len)&&(j<=Lb_len)) { Get_List(La,i,ai); Get_List(Lb,j,bj); if (ai<=bj) { Insert_List(Lc,++k,ai);++i; } else { Insert_List(Lc,++k,bj);++j; } } while (i<=La_len) { Get_List(La,i++,ai); Insert_List(Lc,++k,ai); } while (j<=Lb_len) { Get_List(Lb,j++,bj); Insert_List(Lc,++k,bj); } } //MergeList

42 算法2-4: O(Length_List(La)+Length_List(Lb)) 算法2-2、2-3: O(Length_List(La)×Length_List(Lb))

43 线性表顺序存储结构小结 顺序存储结构的优点 1.可以方便地随机存取线性表中任一个数据元素，且存取任一个数据元素所花费的时间相同。
2.存储空间连续，不必增加额外的存储空间。 顺序存储结构的缺点 1.插入或者删除一个数据元素时，需要对插入点或者删除点后面的全部元素逐个进行移动，操作不便，也需要花费较多的时间。 2.在给长度变化较大的线性表预先分配空间时，必须按照最大空间分配，使存储空间不能得到充分利用。 3.线性表的容量难以扩充。

44 2.3 线性表的链式存储和运算实现 单链表 循环链表 双向链表 静态链表 单链表应用举例

45 单链表 线性链表(单链表) (Linked List) 是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息

46 数据域 指针域 结点 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置

47 (A，B，C，D，E，F) 头指针 空指针 首元结点 尾结点

48 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
存储地址 1 7 13 19 25 31 37 43 数据域 指针域 43 头指针 13 31 H 1 NULL 37 7 19 25 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H

49 线性链表 typedef struce LNode { datatype data; struce LNode *next;
定义：结点中只含一个指针域的链表叫~，也叫单链表 链表是由一个个结点构成的，结点定义如下： typedef struce LNode { datatype data; struce LNode *next; } LNode, *LinkList; 定义头指针变量： LinkList H；

50 头结点：在单链表第一个结点前附设一个结点叫~ 头结点指针域为空表示线性表为空
h a1 a2 头结点 an ^ …... h 空表 ^

51 LNode *h , *p ; data next p 结点（*p） (*p)表示p所指向的结点 (*p).datap->data表示p指向结点的数据域 (*p).nextp->next表示p指向结点的指针域 p->data=ai p->next->data＝ai+1

52 2.3.2 单链表上基本运算的实现 ⒈建立单链表 在链表的头部插入结点建立单链表 LinkList Creat_LinkList1( )
2.3.2 单链表上基本运算的实现 ⒈建立单链表 在链表的头部插入结点建立单链表 LinkList Creat_LinkList1( ) { LinkList L=NULL； /*空表*/ Lnode *s; int x; /*设数据元素的类型为int*/ scanf(＂%d＂,&x); while (x!=flag) { s=malloc(sizeof(LNode)); s->data=x; s->next=L; L=s; scanf (＂%d＂,&x); } return L; }

53 动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针
在单链表的尾部插入结点建立单链表 动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针 h 头结点 an-1 an ^ h 头结点 an ^ h 头结点 ^ h a1 a2 头结点 an ^ …... a2 …... h 头结点 an-1 an ^ 算法描述 算法评价 Ch2_3.c

54 LinkList Creat_LinkList2( )
{ LinkList L=NULL; Lnode *s,*r=NULL; int x; /*设数据元素的类型为int*/ scanf(＂%d＂,&x); while (x!=flag) { s=malloc(sizeof(LNode)); s->data=x; if (L==NULL) L=s; /*第一个结点的处理*/ else r->next=s; /*其它结点的处理*/ r=s; /*r 指向新的尾结点*/ scanf(＂%d＂,&x); } if ( r!=NULL) r->next=NULL; /*对于非空表，最后结点的指针域放空指针*/ return L; }

55 ⒉求表长 设L是带头结点的单链表(线性表的长度不包括头结点)。 int Length_LinkList1 (LinkList L)
{ Lnode * p=L; /* p指向头结点*/ int j=0; while (p->next) { p=p->next; j++ } /* p所指的是第 j 个结点*/ return j; }

56 设L是不带头结点的单链表。 int Length_LinkList2 (LinkList L) { Lnode * p=L; int j;
if (p==NULL) return 0; /*空表的情况*/ j=1; /*在非空表的情况下，p所指的是第一个结点*/; while (p->next ) { p=p->next; j++ } return j; } 算法评价

57 ⒊查找操作 按序号查找 Get_Linklist(L,i) Lnode * Get_LinkList(LinkList L, Int i);
{ Lnode * p=L; int j=0; while (p->next !=NULL && j<i ) { p=p->next; j++; } if (j==i) return p; else return NULL; }

58 按值查找即定位 Locate_LinkList(L,x)
Lnode * Locate_LinkList( LinkList L, datatype x) /*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/ { Lnode * p=L->next; while ( p!=NULL && p->data != x) p=p->next; return p; }

59 算法评价 While循环中语句频度为 若找到结点X，为结点X在表中的序号 否则，为n

60 s->next=p->next; s->next=p->next;
⒋插入操作 后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面(在线性表两个数据元素a和b间插入x) 。 p a b x s p->next=s; s->next=p->next; s->next=p->next; p->next=s; 算法评价

61 前插结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将. s插入到. p的前面。与后插不同的是：首先要找到. p的前驱
前插结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设单链表头指针为L，操作如下： q=L; while (q->next!=p) q=q->next; /*找*p的直接前驱*/ s->next=q->next; q->next=s;

62 插入运算 Insert_LinkList(L,i,x)
2.申请、填装新结点； 3.将新结点插入，结束。 int Insert_LinkList( LinkList L, int i, datatype x) /*在单链表L的第i个位置上插入值为x的元素*/ { Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p==NULL) { printf(”参数i错”);return 0; } /*第i-1个不存在不能插入*/ else { s=malloc(sizeof(LNode)); /*申请、填装结点*/ s->data=x; s->next=p->next; /*新结点插入在第i-1个结点的后面*/ p->next=s return 1; } } 算法评价

63 q->next=q-> next -> next;
⒌删除操作 设p指向单链表中某结点，删除*p。要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。 q->next=p->next; free(p); q a b c p q->next=q-> next -> next; 显然找*p前驱的时间复杂性为O(n)。

64 若要删除*p的后继结点(假设存在)，则可以直接完成： s=p->next; p->next=s->next;
free(s); q a b c p 该操作的时间复杂性为O(1) 。

65 删除运算：Del_LinkList(L,i)
int Del_LinkList(LinkList L，int i) /*删除单链表L上的第i个数据结点*/ { LinkList p,s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p==NULL) { printf(＂第i-1个结点不存在＂);return -1; } else { if (p->next==NULL) { printf(＂第i个结点不存在＂); return 0; } else { s=p->next; /*s指向第i个结点*/ p->next=s->next; /*从链表中删除*/ free(s); /*释放*s */ return 1; } } 算法评价

66 在单链表上插入、删除一个结点，必须知道其前驱结点。
单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。

67 单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢

68 2.3.3 循环链表 对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。

69 在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。
对于单循环链表则可以从表中任意结点开始遍历整个链表；另外，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率提高。

70 循环链表(circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p->next=NULL 循环链表p或p->next=H h h 空表

71 例：对两个单循环链表H1 、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R、R2来标识，则时间性能为O(1)。

72

73 P= R–>next; /*保存第一个表的头结点指针*/
R->next=R2->next->next; /*头尾连接*/ free(R2->next); /*释放第二个表的头结点*/ R2->next=P; /*组成循环链表*/

74 2.3.4 双向链表 单链表的结点中只有一个指向其后继结点的指针域next，单链表具有单向性的缺点，找后继的时间性能是O(1)，找前驱的时间性能是O(n)；可以付出空间的代价使得找前驱的时间性达到O(1)：每个结点再加一个指向前驱的指针域。用这种结点组成的链表称为双向链表。

75 双向链表结点的定义如下： typedef struct dlnode { datatype data; struct dlnode *prior,*next; }DLNode,*DLinkList;

76 和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构。通过某结点的指针p即可以直接得到它的后继结点的指针p->next，也可以直接得到它的前驱结点的的指针p->prior。这样在有些操作中需要找前驱时，则勿需再用循环。

77 p->prior->next= p= p->next->prior
b c a p p->prior->next= p= p->next->prior

78 ①s->prior=p->prior; ②p->prior->next=s; ③s->next=p;
在双向链表中插入一个结点： 设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面。 ①s->prior=p->prior; ②p->prior->next=s; ③s->next=p; ④p->prior=s; b a P x S 上面指针操作的顺序不是唯一的，但也不是任意的，操作①必须要放到操作④的前面完成，否则*p的前驱结点的指针就丢掉了。 算法评价：T(n)=O(1)

79 p->prior->next=p->next;
在双向链表中删除指定结点： 设p指向双向链表中某结点，删除*p。 p->prior->next=p->next; b c a P p->next->prior=p->prior; 算法描述 p->prior->next=p->next; p->next->prior=p->prior; free(p); 算法评价：T(n)=O(1)

80 2.3.5 静态链表 首先看一个例子：规模较大的结构数组 sd[MAXSIZE] 中有两个链表：其中链表SL是一个带头结点的单链表，表示了线性表(a1, a2, a3, a4, a5)，而另一个单链表AV是由当前 sd 中的空结点组成的链表。 数组sd的定义如下： #define MAXSIZE … /*足够大的数*/ typedef struct {datatype data; int next; }SNode; /*结点类型*/ SNode sd[MAXSIZE]; int SL,AV; /*两个头指针变量*/

81 (ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)

82 静态链表示例 (a) 修改前的状态 (b) 修改后的状态

83 在例子中，SL是用户的线性表，AV模拟的是系统存储器中空闲结点组成的链表，当用户需要结点时，例如向线性表中插入一个元素，需自己向AV申请，而不能用系统函数malloc来申请，相关的语句为：
if(AV != -1) { t=AV; AV=sd[AV].next; } ； 所得到的结点地址(下标)存入了 t 中；不难看出当AV表非空时，摘下了第一个结点给用户。当用户不再需要某个结点时，需通过该结点的相对地址 t 将它还给AV，相关语句为： sd[t].next=AV; AV=t; 交给AV表的结点链在了AV的头部。 而不能用系统函数free来释放空间。

84 例 在带头结点的静态链表SL的第i个结点之前插入一个值为x的新结点。设静态链表的存储区域sd为全局变量。
int Insert_SList( int SL, datatype x, int i) { int p=SL, j=0; while(sd[p].next != -1 && j<i-1) {p=sd[p].next; j++;} /*找第i-1个结点*/ if(j==i-1) if(AV != -1) /*若AV表还有结点可用*/ { t=AV; AV=sd[AV].next; sd[t].data=x; /*申请、填装新结点*/ sd[t].next=sd[p].next; /*插入*/ sd[p].next=t; return 1; } /*正常插入成功返回*/ else {printf(”存储器无结点”); return 0;} /*未申请到结点，插入失败*/ else {printf(”插入的位置错误”); return -1;} /*插入位置不正确，插入失败*/ }

85 2.3.6 单链表应用举例 例1 已知单链表H，写一算法将其倒置。 算法如下： void reverse (Linklist H)
{ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p) { q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 算法评价：T(n)=O(n)

86 例2 已知单链表L，写一算法，删除其重复结点。

87 void pur_LinkList(LinkList H)
{ LNode *p,*q,*r; p=H->next; /*p指向第一个结点*/ if (p==NULL) return; while (p->next) { q=p; while (q->next) /* 从*p的后继开始找重复结点*/ { if (q->next->data==p->data) { r=q->next; /*找到重复结点，用r指向，删除*r */ q->next=r->next; free(r); } else q=q->next; } p=p->next; /*p指向下一个，继续*/ } 算法评价：T(n)=O(n2)

88 例3 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值非递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。

89 LinkList merge(LinkList A,LinkList B) /*设A、B均为带头结点的单链表*/
{ LinkList C; LNode *p,*q; p=A->next; q=B->next; free(B); C=A; C->next=NULL; /*C表的头结点*/ while (p&&q) { if (p->data<q->data) { s=p;p=p->next; } else {s=q;q=q->next;} /*从原AB表上摘下较小者*/ s->next=C->next; C->next=s; /*插入到C表的头部*/ } if (p==NULL) p=q; while (p) /* 将剩余的结点一个个摘下，插入到C表的头部*/ { s=p; p=p->next; s->next=C->next;C->next=s;} 算法评价：T(n)=O(m+n)

90 链式存储结构的特点 链式存储结构有两个优点，一个是结点空间的动态申请和动态释放，这克服了顺序表数据元素最大个数需预先确定的缺点；另一个是链式存储结构中数据元素的逻辑次序靠结点的指针域来指示，这克服了顺序表插入、删除操作算法需大量移动数据元素的缺点。

91 链式存储结构也有不足： 1．每个结点中的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重就显得很大。因此，一个线性表是用顺序存储结构还是用链式存储结构更节省存储空间资源需根据具体问题分析后确定。 2．链式存储结构是一种非随机存储结构。链式存储结构中对任一结点的操作都要首先从头指针开始依指针链查找到该结点，这增加了有些操作算法的复杂程度。

92 线性表链式存储结构小结 线性表的链式存储结构的最大特点就是逻辑上相邻的两个元素在物理位置上不相邻，这样虽然比顺序存储结构多占用空间，但是存储器中的碎片可以得到充分的利用。另外，线性表的链式存储结构只能顺序存取数据元素，不能随机存取数据元素。

93 2.4 顺序表和链表的比较 1．空间性能的比较 2．时间性能的比较 3．基于环境的考虑

94 本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点：
(1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。

95 但它也有两个缺点： 　 ⑴ 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 ⑵ 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。 链表的优缺点恰好与顺序表相反。

96 在实际中怎样选取存储结构呢？通常有以下几点考虑：
⒈ 基于存储的考虑 对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。

97 ⒉ 基于运算的考虑 如果经常做的运算是按序号访问数据元素，顺序表优于链表； 在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优于前者。

98 ⒊ 基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。 总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。