第二章线性表复习

1、1线性表线性表是一种最简单的线性结构线性结构22.1 线性表的逻辑结构线性表的逻辑结构2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象32.1 线性表的逻辑结构线性表的逻辑结构4（a1, a2, ai-1，ai, ai1 ，, an）n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点1.定义：定义：

2、线性表是由线性表是由n（n0）个数据元素（结）个数据元素（结点）点）a1，a2，an组成的有限序列。组成的有限序列。5【例【例1】26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z）【例【例2】某校从】某校从2000年到年到2005年各种型号的年各种型号的计算机拥有量的变化情况计算机拥有量的变化情况()。 （150，236，321，400，500，600）数据元素数据元素ai（1in）只是个抽象符号，其）只是个抽象符号，其具体含义在不同情况下可以不同。具体含义在不同情况下可以不同。6【例【例3】学生健康情况登记表。】学生健康情况登记表。姓姓 名名学学 号号性性 别别年龄年龄 健

3、康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经衰弱神经衰弱 . . .72.2.线性表逻辑结构特征线性表逻辑结构特征( (非空有限集非空有限集) )(1)集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；(2)集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素”(3)除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；(4)除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。线性结构是线性结构是

4、一个数据元素的有序（次序）集一个数据元素的有序（次序）集83.3.抽象数据类型线性表的定义抽象数据类型线性表的定义ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称称 n 为线性表的为线性表的表长表长; 称称 n=0 时的线性表为时的线性表为空表空表。数据关系：数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称称 i 为为 ai 在线性表中的在线性表中的位序位序。9 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作

5、引用型操作 加工型操作加工型操作 ADT List10 InitList( &L )操作结果：操作结果：构造一个空的线性表构造一个空的线性表L。初始化操作初始化操作11 结构销毁操作结构销毁操作DestroyList( &L )初始条件：初始条件：线性表线性表 L 已存在。已存在。销毁线性表销毁线性表 L。操作结果：操作结果：12ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare(

6、) )ListTraverse(L, visit( )引用型操作引用型操作13加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) 143.3.组合基本运算，实现复杂运算组合基本运算，实现复杂运算 例例 2-2 (构造构造A)例例 2-3(归并归并A.B)例例 2-1 (AAB)15 假设假设: :有两个集合有两个集合 A 和和 B 分别用分别用两个线性表两个线性表 LA 和和 LB 表示，即：表示，即：线性表中的数据元素即为集合中的线性表中的数据元素即为集合中的成员。

7、成员。 现要求一个新的集合现要求一个新的集合AAB。【例【例 2-1】 16 要求对线性表作如下操作：要求对线性表作如下操作：扩大线性表扩大线性表 LA，将存在于线性表，将存在于线性表LB 中而不存在于线性表中而不存在于线性表 LA 中的中的数据元素插入到线性表数据元素插入到线性表 LA 中去。中去。上述问题可演绎为：上述问题可演绎为：171从线性表从线性表LB中依次察看每个数据元素中依次察看每个数据元素;2依值在线性表依值在线性表LA中进行查访中进行查访; 3若不存在，则插入之。若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) List

8、Insert(LA, n+1, e)操作步骤：操作步骤：18 GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListLength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len;

9、 i+) / union19 已知一个非纯集合已知一个非纯集合 B，试构造一个，试构造一个纯集合纯集合 A，使，使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的数据元素。同的数据元素。仍选用仍选用线性表线性表表示集合表示集合【例【例 2-2】20集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同21void purge(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); / purge

10、GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = Lb_len; i+) InitList(La); / 构造(空的)线性表LA22若线性表中的数据元素相互之间可以比若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递较，并且数据元素在线性表中依值非递减或非递增有序排列，即减或非递增有序排列，即

11、a ai iaai-1i-1 或或 a ai iaai-1i-1(i = 2,3, n)(i = 2,3, n)，则称该线性，则称该线性表为表为有序表有序表(Ordered List)(Ordered List)。试改变结构，以试改变结构，以有序表有序表表示集合。表示集合。23例如例如：（2，3，3，5，6，6，6，8，12）对集合 B 而言， 值相同的数据元素必定相邻值相同的数据元素必定相邻对集合 A 而言， 数据元素依值从小至大的顺序插入数据元素依值从小至大的顺序插入因此，数据结构改变了，数据结构改变了， 解决问题的策略也相应要改变。解决问题的策略也相应要改变。24void purge_o

12、rder(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge_order GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，

13、则插入之25则则 归并两个归并两个“其数据元素按值非递减有序其数据元素按值非递减有序排列排列”的有序表的有序表 LA 和和 LB，求得有序表，求得有序表 LC 也具有同样特性。也具有同样特性。设设 La = (a1, , ai, , an) Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)jijjiikbabbaac【例【例 2-3】k = 1, 2, , m+n261初始化初始化 LC 为空表；为空表；基本操作：基本操作：2分别从分别从 LA和和LB中取得当前元素中取得当前元素 ai 和和 bj；3若若 aibj，则将，则将 ai 插入到插入到 LC

14、 中，否则将中，否则将 bj 插入到插入到 LC 中；中；4重复重复 2 和和 3 两步，直至两步，直至 LA 或或 LB 中元素中元素 被取完为止；被取完为止；5将将 LA 表或表或 LB 表中剩余元素复制插入到表中剩余元素复制插入到 LC 表中。表中。27 / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, b

15、j); +j; 28void MergeList(List La, List Lb, List &Lc) InitList(Lc); / 构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); / merge_listwhile (i = La_len) & (j = Lb_len) / La 和 Lb 均不空 while (i=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空29 while (i = La_len) GetElem(La, i+, ai

16、); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素 while (j = Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素302.2 线性表的顺序线性表的顺序 表示和实现表示和实现31 1.定义：定义：用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素。 a1 a2 ai-1 ai an线性表的起始地址线性表的起始地址，称作线性表的基地址基地址2.2.1 线性表的顺序存储结构线性表的顺序存储结构322.实现：可用实现：可用C/C+的一维数组实现的一维数组实现a

17、1a2an01n-112n内存单元内存单元数组下标数组下标元素序号元素序号m-1333结点结点ai 的存储地址的存储地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置。第一个数据元素的存储位置。 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址34【例【例1 1】一个大小为一个大小为1010的一维数组的一维数组A A，每个，每个数组元素用相邻的数组元素用相邻的8 8个字节个字节存储。假设存存储。假设存

18、储数组元素储数组元素AA 的第一个字节的地址是的第一个字节的地址是1020，则，则A6A6的第一个字节的地址是的第一个字节的地址是 1068LOC(a6 ) = LOC(a1 )+8*(6-0) = 1020 + 8 (6-0) =1068解：解：地址计算通式为：地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）35#define MAXNUM typedef structSqlist；4.4.顺序存储结构顺序存储结构（1 1）静态分配静态分配的顺序存储结构的顺序存储结构Elemtype elemMAXNUM; int length;36静态顺序表：静态顺序表：lengt

19、helemMAXNUM3 2 6 5 8 96例如例如 ：MAXNUM=1237（2 2）动态分配动态分配的顺序存储结构的顺序存储结构typedef struct SqList; / 俗称 顺序表顺序表const int LIST_INIT_SIZE = 80 ; / 线性表存储空间的初始分配量ElemType *elem; / 存储空间基址存储空间基址int listsize; / 当前分配的存储容量int length; /当前长度38动态顺序表动态顺序表*elem length listsize例如例如 ：742000H2000H 4 72000H3578392.2.2顺序表的基本操作顺

20、序表的基本操作InitList(&L) / 结构初始化LocateElem(L, e, compare() / 查找ListInsert(&L, i, e) / 插入元素ListDelete(&L, i,&e) / 删除元素/(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType) /free(T)Status ListCreate_Sq(SqList &L,int n)40Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = new E

21、lemTypeLIST_INIT_SIZE;if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK;1.1.初始化初始化动态分配内存动态分配内存设置顺序表的大小设置顺序表的大小41例如：在顺序表中查找元素例如：在顺序表中查找元素23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p2.2.查找元素查找元素42 int LocateElem_Sq(SqList L, ElemType e) / 在顺序表中查询第一

22、个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while (i = L.length & (*p+!=e) +i;if (i = L.length) return i;else return 0;43线性表操作 Lis

23、tInsert(&L, i, e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？3.3.插入元素插入元素44 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加表的长度增加14521 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.

24、elemL.length-1); p = q; -p) *(p+1) = *p;p*q = e; 实现步骤：实现步骤：移动元素移动元素插入元素插入元素46L.length = L.listsize / 当前存储空间已满，不能插入i L.length+1 / 插入位置不合法 l事先应判断事先应判断: 插入位置插入位置i 是否合法是否合法?l表是否已满表是否已满?注意：注意：47 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / ListInsert_Sq 算法时间复杂度算法时间复杂度为为:

25、 :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表长增表长增1return OK;if(iL.length+1) return ERROR;元素右移元素右移if(L.length = L.listsize ) return OVERFLOW ;48考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第假设在第 i 个

26、元素之前插入的概率为个元素之前插入的概率为 ， 则在长度为则在长度为n 的线性表中的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：为：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定在线性表中任何一个位置上进行若假定在线性表中任何一个位置上进行插入插入的概率的概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：49线性表操作 ListDelete(&L, i, &e)的实现：首先分析：首先分析：删除元素时，删除元素时，线性表的逻辑结构发生什么变化？线性表的逻辑结构发生什么变化？4.4.删除元素删除元素50 (

27、a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少表的长度减少1a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 5121 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p = q; +p) *(p-1) = *p; 例如：ListDelete_Sq(L, 5, e) p实现步骤：实现步骤：移动元素移动元素52 (L.length = 0) / 当

28、前存储空间为空，不能删除(i L.length) / 删除位置不合法 l事先应判断事先应判断: 删除位置删除位置i 是否合法是否合法?l表是否为空表是否为空?注意：注意：53Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 删除元素删除元素-L.length; / 表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置为被删

29、除元素的位置e = *p; / 被删除元素的值赋给被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; 元素左移元素左移if ( L.length=0) return ERROR; 54考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第假设删除第 i 个元素的概率为个元素的概率为 , 则在长度为则在长度为n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素次数的期望值移动元素次数的期望值为：为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表

30、中任何一个位置上进行删除若假定在线性表中任何一个位置上进行删除的的概率概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：55typedef int ElemType ; Status ListCreate_Sq(SqList &L,int n) /创建顺序表 / ListCreate_Sqreturn OK;for(int i=1;ix;L.elemi-1=x;+L.length ;5.5.创建顺序表创建顺序表562.2.32.2.3利用上述定义的顺序结构利用上述定义的顺序结构 可以实现其它更复杂的操作可以实现其它更复杂的操作例例 2-5 (逆置顺序表逆置顺序表)例例 2-

31、6(调整顺序调整顺序)例例 2-4 (归并归并A、B)57则则 归并两个归并两个“其数据元素按值非递减有序其数据元素按值非递减有序排列排列”的有序表的有序表 LA 和和 LB，求得有序表，求得有序表 LC 也具有同样特性。也具有同样特性。（用顺序表实现）（用顺序表实现）设设 La = (a1, , ai, , an) Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)jijjiikbabbaac【例【例 2-4】k = 1, 2, , m+n58LA（1，3，4，9 ， 10）LB（2，5，6，7，8） LC(1，2，3 ， 4，5，6，7，8，9，10

32、)Legth=5 Legth=5 Legth=10例如：例如：5913942567PaPa_lastPb_lastPbLaLb8LcPc1234567810910算算法法思思路路 ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa = La-elem; pa_last = La-elem+La-length-1; pb = Lb-elem;pb_last = Lb-elem+Lb-length-1;Lc-listsize = Lc-length = La-length+Lb-length;if (*pa = *pb) *pc+ = *pa+; else *pc+

33、 = *pb+;pa = pa_last & pb = pb_last 第二步归并第二步归并（将（将剩余元素插入到剩余元素插入到Lc末尾末尾）第一步第一步归并结束归并结束第二步第二步归并结束归并结束60 while(iLA.length) & (jLB.length)if(LA.elemi=LB.elemj)LC.elemk=LA.elemi;i+;k+;else LC.elemk=LB.elemj;j+;k+; void Merge_sq(SqList &LC,SqList LA,SqList LB) i=0,j=0,k=0; LC.length =LA.length+LB.length;6

34、1 while(jLB.length) LC.elemk=LB.elemj;j+;k+;while(iLA.length) LC.elemk=LA.elemi;i+;k+; / Merge_sq62设有一个顺序表设有一个顺序表A，包含，包含n个数据元素。个数据元素。编写一个算法，将顺序表编写一个算法，将顺序表A逆置，逆置，只允许在原表的存储空间外再增加只允许在原表的存储空间外再增加一个附加的工作单元。一个附加的工作单元。【例【例 2-5 】63LA（21，62，8，9，11，25，20） LA（20，25，11，9，8，62，21）逆置后：逆置后： i逆置前：逆置前： j附加单元附加单元tem

35、pLA（20，62，8，9，11，25，21） tempLA(i); LA(i)=LA(j);LA(j)=temp i j64 temp=L.elemi; L.elemi=L.elemn-i-1; L.elemn-i-1=temp; for( i =0; i m; +i)void invert_sq( SqList &L) n=L.length;i=0,m=n/2; / invert_sq65设有一个顺序表设有一个顺序表A，包含，包含n个数据元个数据元素。调整顺序表素。调整顺序表A，使其左边的所，使其左边的所有元素均小于有元素均小于0，使其右边的所有，使其右边的所有元素均大于元素均大于0。【例

36、【例 2-6】66LA（-62，-8，-25，20，9，8，21）调整前：调整前：LA（21，-62，8，9，-8，-25，20） iLB（ ）xy调整后：调整后：LB（ 21）yxLA（21，-62，8，9，-8，-25，20） iLB（-62 21）yxLA（21，-62，8，9，-8，-25，20） i与与0比较比较67 if(LA.elemi0)LB.elemx=LA.elemi;x+; /前置前置 else LB.elemy=LA.elemi; y-; for (i = 0; i n; i+) void adjust_sq(SqList &LA) InitList_Sq(LB); n

37、=LA.length; x=0;y=n-1; / adjust_sqfor(i=0;in;+i)LA.elemi=LB.elemi; DestroyList(LB);68优点：优点：l逻辑相邻，物理相邻逻辑相邻，物理相邻l可随机存取任一元素可随机存取任一元素l存储空间使用紧凑存储空间使用紧凑缺点：缺点：l插入、删除操作需要移动大量的元素插入、删除操作需要移动大量的元素l预先分配空间需按最大空间分配，利预先分配空间需按最大空间分配，利用不充分用不充分l表容量难以扩充表容量难以扩充顺序存储结构的优缺点顺序存储结构的优缺点692.3.1 单链表单链表2.3.2 2.3.2 单向循环链表单向循环链表2

38、.3.3 双链表双链表2.3.4 双向循环链表双向循环链表2.3线性表的链式存储结构线性表的链式存储结构701.概述概述用一组用一组地址任意地址任意的存储单元存放线性表的存储单元存放线性表中的数据元素。中的数据元素。2.3.1 单链表单链表以以元素元素(数据元素的映象数据元素的映象) + 指针指针(指示后继元素存储位置指示后继元素存储位置) = 结点结点 数据域数据域 指针域指针域结点结构结点结构数据域：元素本身信息数据域：元素本身信息指针域：指示直接后继的存储位置指针域：指示直接后继的存储位置71ZHAOQIANSUNLIZHOUWUZHENGWANGH例例 线性表线性表 (ZHAO,QIA

39、N,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域数据域指针域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址存储地址1713192531374331H头指针头指针72 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。1a头结点头结点 a1 a2 . an 头指针头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针以“结点的序列结点的序列”表示线性表 称作链表链表h空表空表单链表的一般图示法单链表的一般图示法73上例链表的逻辑结构示意图有以下上例链表的逻

40、辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：区别： 无头结点无头结点 有头结点有头结点74 typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList; 2.2.结点和单链表的结点和单链表的 C 语言描述语言描述LinkList L； / L 为单链表的头指针为单链表的头指针数据域数据域 指针域指针域结点结构结点结构753.单链表的运算单链表的运算GetElem(L,

41、i, e) / 取第取第i i个数据元素个数据元素ListInsert(&L, i, e) / 插入插入数据元素数据元素ListDelete(&L, i, e) / 删除删除数据元素数据元素ClearList(&L) / 重置线性表为空表重置线性表为空表CreateList(&L, n) / 生成含生成含 n 个数据元素的链表个数据元素的链表76(1)(1)单链表元素的读取单链表元素的读取GetElem(L, i, &e)L 1p5j=1假设假设 i=2jij=j+1=2j=i找到！找到！77L 1p5j=1jij=j+1=2ji假设假设 i=4j=j+1=3ji假设假设 i=0没找到！没找到

42、！非法位非法位置置79 Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 / GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p = L-next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空if ( !p | ji )

43、return ERROR; / 第第 i i 个元素不存在个元素不存在e = p-data; / 取得第取得第 i i 个元素个元素return OK;80 (2)插入操作 ListInsert(&L, i, e)xsbapabps-next=p-next;p-next=s;插入前插入前插入后插入后81 因此，在单链表中第因此，在单链表中第 i i 个结点之前个结点之前进行插入的基本操作为进行插入的基本操作为: : 找到线性表中第找到线性表中第i-1i-1个结点，然后修个结点，然后修改其指向后继的指针。改其指向后继的指针。算法思路算法思路：在链表中插入结点只需要修：在链表中插入结点只需要修改指

44、针。但同时，若要在第改指针。但同时，若要在第 i 个结点之个结点之前插入元素，修改的是第前插入元素，修改的是第 i-1 个结点的个结点的指针。指针。82 Status ListInsert_L(LinkList &L, int i, ElemType e) / L 为带头结点的单链表的头指针，为带头结点的单链表的头指针， / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结

45、点个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 83s = new LNode; / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入return OK;84(3) 删除操作删除操作ListDelete (&L, i, &e)cabpq = p-next;qp-next=q-next;delete q;85 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。算法思路

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

47、delete q;return OK;87(4)清空操作 ClearList(&L)void ClearList(&L) / 将单链表重新置为一个空表 while (L-next) p=L-next; L-next=p-next; / ClearListDelete p;算法时间复杂度：O(ListLength(L)88（5）如何从线性表得到单链表？）如何从线性表得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要预分配空间，因此预分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入”的过程。的过程。89头插法思路：头插法思路：L datanex

48、tpdatanextpp-next=L-nextL-next=p(1)(1)建立一个建立一个“空表空表”；(2)(2)输入数据元素输入数据元素an，建立结点并插入；，建立结点并插入；(3)(3)输入数据元素输入数据元素an-1，建立结点并插入；，建立结点并插入；(4)(4)依次类推，直至输入依次类推，直至输入a a1 1为止。为止。逆位序输入逆位序输入该方法生成链表的结点次序与输入顺序相反。该方法生成链表的结点次序与输入顺序相反。90void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的

49、算法的时间复杂度时间复杂度为:O(Listlength(L)L = new LNode;L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = new LNode; cin p-data; / 输入元素值 p-next = L-next; L-next = p; / 插入91尾插法思路（正位序输入尾插法思路（正位序输入 ）：）：L datanextppdatanextp-next=L-nextL-next=pp-next=L-next-nextL-next-next=pL-next-next-.-next ?92尾插法思路：尾插法思路：L

50、datanextpspdatanextp-next=s-nexts-next=p注意：注意：采用尾插法建表，生成的链表中结点采用尾插法建表，生成的链表中结点的次序和输入顺序一致。的次序和输入顺序一致。必须增加一个尾指针必须增加一个尾指针s,s,使其始终指向使其始终指向当前链表的尾结点。当前链表的尾结点。93void CreateList_L(LinkList &L, int n) / 正序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = new LNode;L-next = NULL; S=L;/

51、建立带头结点/尾指针的单链表for (i = 1; i p-data; / 输入元素值 p-next = S-next; S-next = p;S=p;/ 插入94则则 归并两个归并两个“其数据元素按值非递减有序其数据元素按值非递减有序排列排列”的有序表的有序表 LA 和和 LB，求得有序表，求得有序表 LC 也具有同样特性。也具有同样特性。（用单链表实现）（用单链表实现）设设 La = (a1, , ai, , an) Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)jijjiikbabbaac【例【例 2-7】链表的应用。】链表的应用。k = 1,

52、 2, , m+n95算法分析：算法分析：搜索：搜索：需要两个指针搜索两个链表；需要两个指针搜索两个链表；比较：比较：比较结点数据域中数据的大小；比较结点数据域中数据的大小；插入：插入：将两个结点中数据小的结点插入将两个结点中数据小的结点插入新链表。新链表。963 5 8 11 2 6 7 129 PaPa、PbPb用于搜索用于搜索LaLa和和LbLb， PcPc指向新链表当前结点指向新链表当前结点LaLbPbPaLc Pc=不需要重建结点空间，只要修改指针即可不需要重建结点空间，只要修改指针即可97void MergeList_L(LinkList La, LinkList Lb,LinkL

53、ist &Lc) /合并两个有序表合并两个有序表 / MergeList_Lpa = La-next; pb = Lb-next; / p指向第一个结点Lc=pc=La;while (pa & pb) if(pa-data data ) pc-next =pa;pc=pa;pa=pa-next ;else pc-next =pb;pc=pb;pb=pb-next ;pc-next =pa?pa:pb;98假如假如 x=3 y=6算法思路：算法思路：138459LP qqq【例【例2-8】设计一个算法，要求删除线性表设计一个算法，要求删除线性表中介于中介于x和和y之间的数据。之间的数据。99vo

54、id del_LQ(LinkList L,int x,int y) / del_LQ p=L; while (p-next) if (p-next-data=x&p-next-datanext; p-next=q-next; delete(q); else p=p-next; 100单链表的特点：单链表的特点：1它是一种动态结构，整个存储空间为它是一种动态结构，整个存储空间为多个链表共用。多个链表共用。2指针占用额外存储空间指针占用额外存储空间。3在链表中，元素的在链表中，元素的“位序位序”概念淡化，概念淡化，结点的结点的 “位置位置”概念加强。概念加强。4不能随机存取，查找速度慢不能随机存取

55、，查找速度慢,但是插入、但是插入、删除操作很方便删除操作很方便。1011.定义：最后一个结点的指针域的指针又指回第一个结点的链表，使链使链表构成环状。表构成环状。 a1 a2 . an 带头结点的单循环链表h空表空表2.3.2 单向循环链表单向循环链表102特点：特点：从表中任一结点出发均可找到表从表中任一结点出发均可找到表中其他结点，提高查找效率。中其他结点，提高查找效率。单循环链表单循环链表 a1 a2 . an 带头结点的单循环链表103typedef struct LNode ElemType data;struct LNode* next; LNode, *CircleLinkLis

56、t; 2.存储结构（和单链表相同）存储结构（和单链表相同）104与单链表基本一致与单链表基本一致, ,它们仅在它们仅在循环终止条循环终止条件上有所不同件上有所不同。 3.3.基本操作基本操作单链表：单链表： p=NULLp=NULL或或p-next=NULLp-next=NULL循环链表：循环链表：p=L p=L 或或p-next=Lp-next=L105头插法头插法L datanextpdatanextpL-next = p;（1 1） 单向循环链表创建单向循环链表创建p-next = L-next; 106头插法头插法void CreatListF(CircleLinkList &L) /

57、 CreatListF char ch; L=new LNode; /头指针头指针 L-next=L; /链表开始为空链表开始为空 ch=getchar(); /读入第读入第1个字符个字符 while(ch!=n) p=new LNode; /生成新结点生成新结点 p-data=ch; p-next= L-next; L-next =p; ch=getchar(); /读入下一字符读入下一字符 107尾插法尾插法L datanextprpdatanextp-next =Lr-next = p;108尾插法尾插法void CreatListR(CircleLinkList &L) / Creat

58、ListR L=new LNode; /头指针头指针 L-next=L; /链表开始为空链表开始为空 r=L; /设置尾指针初值设置尾指针初值 ch=getchar(); /读入第读入第1个字符个字符 while(ch!=n) p=new LNode; p-data=ch; p-next=L; /将新结点插到将新结点插到r之后之后 r-next=p; r=p;/尾指针指向新表尾尾指针指向新表尾 ch=getchar(); /读入下一字符读入下一字符 /endwhile109（2 2）单向循环链表元素的读取）单向循环链表元素的读取L 1p5j=1假设假设 i=2jij=j+1=2j=i找到！找到

59、！110L 1p5j=1jij=j+1=2ji假设假设 i=4j=j+1=3ji假设假设 i=0没找到！没找到！112xsbapabps-next=p-next;p-next=s;插入前插入前插入后插入后（3 3）单向循环链表的插入（同单链表）单向循环链表的插入（同单链表）113cabpq = p-next;qp-next=q-next;delete q;（4 4）单向循环链表的删除（同单链表）单向循环链表的删除（同单链表）1142.3.3双向链表双向链表L空双向链表：空双向链表：非空双向链表：非空双向链表：LABbcapp-prior-next= p= p-next-prior;priord

60、atanext115结构定义结构定义typedef struct DBLNode ElemType data; / 数据域 struct DBLNode *prior; / 指向前驱的指针域 struct DBLNode *next; / 指向后继的指针域 DBLNode, *DBLinkList;priordatanext1162.3.4双向循环链表双向循环链表L空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;1171.结构定义结构定义typedef struct DBLNode ElemType data; / 数据域 stru