数据结构第二章线性表

1、单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级1第二章第二章 线性表线性表2.1 线性表的类型定义线性表的类型定义 2.2 线性表的顺序表示与实现线性表的顺序表示与实现2.3 线性表的链式表示与实现线性表的链式表示与实现2.4 一元多项式的表示及相加一元多项式的表示及相加单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级2学习目标学习目标 了解线性表的逻辑结构特性是数据元素之间存在着线

2、性了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中表示这种关系的两类不同的存储结构关系。在计算机中表示这种关系的两类不同的存储结构是是顺序存储结构顺序存储结构和和链式存储结构。链式存储结构。 熟练掌握这两类存储结构的描述方法以及线性表的基本熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。操作在这两种存储结构上的实现。 能够从时间和空间复杂度的角度综合比较线性表两种存能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。储结构的不同特点及其适用场合。 结合线性表类型的定义增强对抽象数据类型的理解。结合线性表类型的定义增强对抽象

3、数据类型的理解。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级3重点难点重点难点 链表链表 指针操作和内存动态分配的编程技术；指针操作和内存动态分配的编程技术； 链表中指针链表中指针 p 和结点和结点 *p 之间的对应关系；之间的对应关系； 头结点、头指针和首元结点的不同；头结点、头指针和首元结点的不同； 循环链表、双向链表的特点。循环链表、双向链表的特点。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四

4、级第四级 第五级第五级4线性结构的特点线性结构的特点 在数据元素的在数据元素的非空有限集中非空有限集中存在唯一一个被称做存在唯一一个被称做“第一个第一个”的数据元素；的数据元素； 存在唯一一个被称做存在唯一一个被称做“最后一个最后一个”的数据元素；的数据元素；除第一个数据元素之外，每个元素都除第一个数据元素之外，每个元素都只有一个只有一个前驱前驱； 除最后一个数据元素之外，每个元素都除最后一个数据元素之外，每个元素都只有一只有一个后继个后继。 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五

5、级52.1线性表的类型定义线性表的类型定义 线性表：是线性表：是n个数据元素的个数据元素的有限序列。有限序列。 除了第一个元素没有直接前驱和最后一个元素没有直接除了第一个元素没有直接前驱和最后一个元素没有直接后继之外，其余的每个数据元素只有一个后继之外，其余的每个数据元素只有一个直接前驱直接前驱和一和一个个直接后继直接后继。niaaaa,21如例例学号姓名年龄001张三18002李四19数据元素数据元素单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级6线性表的特征线性表的特征 有穷性：由有

6、限个元素组成，元素个数有穷性：由有限个元素组成，元素个数n表长度，表长度，n=0空空表表。 设线性表为设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称称 i 为为 ai 在线性在线性表中的表中的位序位序。 有序性：线性表元素之间存在序偶关系，有序性：线性表元素之间存在序偶关系，1in时时 ai的直接前驱是的直接前驱是ai-1，a1无直接前驱无直接前驱 ai的直接后继是的直接后继是ai+1，an无直接后继无直接后继 同一性：线性表由同类数据元素组成，每一个元素都属于同同一性：线性表由同类数据元素组成，每一个元素都属于同一数据对象一数据对象单击此处编辑母版标题样式单击此处

7、编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级7线性表抽象数据类型定义：线性表抽象数据类型定义： ADT List 数据对象：数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作：基本操作：（1）InitList（&L） 操作结果：将操作结果：将L初始化为空表。初始化为空表。（2）DestroyList(&L) 初始条件：线性表初始条件：线性表L已存在。已存在。 操作结果：将操作结果：将L销毁。销毁。单击此处编辑母版标题样

8、式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级8（3）ClearList(&L) 初始条件：线性表初始条件：线性表L已存在已存在 。 操作结果：将表操作结果：将表L置为空表。置为空表。（4）EmptyList（L） 初始条件：线性表初始条件：线性表L已存在。已存在。 操作结果：如果操作结果：如果L为空表则返回真，否则返回为空表则返回真，否则返回假。假。（5）ListLength（L） 初始条件：线性表初始条件：线性表L已存在。已存在。 操作结果：如果操作结果：如果L为空表则返回为空表则返回0，否则返回，否则返

9、回表中的元素个数。表中的元素个数。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级9（6）GetItem(L,i,&e) 初始条件：初始条件： 表表L已存在，已存在，1=i=ListLength(L)。 操作结果：操作结果： 用用e返回返回L中第中第i个元素的值。个元素的值。（7）LocateElem(L,e) 初始条件：初始条件： 表表L已存在，已存在，e为合法元素值。为合法元素值。 操作结果：操作结果： 如果如果L中存在元素中存在元素e，则将，则将“当前指针当前指针”指向第一个这样的元

10、素指向第一个这样的元素e所在位置并返回真，否则返所在位置并返回真，否则返回假。回假。（8）ListInsert(&L,i,e) 初始条件：表初始条件：表L已存在，已存在，e为合法元素值且为合法元素值且1iListLength(L)+1。 操作结果：在操作结果：在L中第中第i个位置之前插入新的数据元素个位置之前插入新的数据元素e，L的长度加的长度加1。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级10（9）ListDelete(&L,i,&e) 初始条件：表初始条件：表L已存在且非空已存在

11、且非空 ，1iListLength(L)。 初始条件：删除初始条件：删除L的第的第i个数据元素，并用个数据元素，并用e返回其值，返回其值，L的长度减的长度减1。ADT List 利用上述定义的线性表类型，可以实现其它更复杂的利用上述定义的线性表类型，可以实现其它更复杂的操作，例如：归并、拆分、复制、排序操作，例如：归并、拆分、复制、排序单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级11算法举例：算法举例：例例2-1 假设有两个集合假设有两个集合A和和B分别用两个线性表分别用两个线性表LA

12、和和LB表示表示（即：线性表中的数据元素即为集合中的成员），现要求一个新（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合的集合AAB。要求对线性表作如下操作：扩大线性表。要求对线性表作如下操作：扩大线性表LA，将存在于线性表将存在于线性表LB中而不存在于线性表中而不存在于线性表LA中的数据元素插入到中的数据元素插入到线性表线性表LA中去。中去。(注：注： 并集，属于并集，属于A或者属于或者属于B) 思路：思路： 1从线性表从线性表LB中依次取得每个数据元素中依次取得每个数据元素; GetElem(LB, i)e 2依值在线性表依值在线性表LA中进行查访中进行查访; LocateE

13、lem(LA, e, equal( ) ) 3. 若不存在，则插入之。若不存在，则插入之。 ListInsert(LA, n+1, e)算法实现：算法实现：void union(List &La, List Lb) / 将所有在线性表将所有在线性表Lb中但不在中但不在La中的数据元素插入到中的数据元素插入到La中中 La_len = ListLength(La); Lb_len = ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e

14、if(!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同相同的数据元素，则插入之的数据元素，则插入之 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级12算法举例：算法举例： 例例2-2 归并两个归并两个“其数据元素按值非递减有序排列其数据元素按值非递减有序排列”的有序表的有序表 La 和和 Lb，求得有序表，求得有序表 Lc 也具有同样特性。也具有同样特性。问题分析：问题分析： La =

15、(a1, , ai, , an), Lb = (b1, , bj, , bm), Lc = (c1, , ck, , cm+n) 且已由且已由(a1, , ai-1)和和(b1, ,bj-1)归并得归并得 (c1, , ck-1)jijjiikbabbaack = 1, 2, , m+n单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级13算法基本思路算法基本思路初始化初始化 Lc 为空表；为空表；分别从分别从 La和和Lb中取得当前元素中取得当前元素 ai 和和 bj ； GetElem(

16、La, i, ai); GetElem(Lb, j, bj); 若若 aibj，则将，则将 ai 插入到插入到 Lc 中，否则将中，否则将 bj 插插入到入到 Lc 中；中； ListInsert(Lc, +k, ai); ListInsert(Lc, +k, bj); 重复重复 2 和和 3 两步，直至两步，直至 La 或或 Lb 中元素中元素 被取完为止；被取完为止；将将 La 表或表或 Lb表中剩余元素复制插入到表中剩余元素复制插入到Lc 表表中。中。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四

17、级 第五级第五级14void MergeList(List La, List Lb, List &Lc) InitList(Lc); i = j = 1; k = 0; 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; 单击

18、此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级15 while (i = La_len) GetElem(La, i+, ai);ListInsert(Lc, +k, ai); while (j = Lb_len) GetElem(Lb, j+, bj);ListInsert(Lc, +k, bj); / MergeList算法的时间复杂度算法的时间复杂度：O( ( ListLength(La) +ListLength(Lb)） 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑

19、母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级162.2 线性表的顺序表示和实现线性表的顺序表示和实现 顺序映象顺序映象 线性表的顺序存储是指线性表的顺序存储是指用一组地址连续的存储用一组地址连续的存储单元单元依次存储线性表中的各个元素。依次存储线性表中的各个元素。20 31 45 34 25 35 1 2 3 4 5 6 data用物理位置来表示逻辑结构。用物理位置来表示逻辑结构。 LOC(ai+1)=LOC(ai)+l ; LOC(ai)=LOC(a1)+(i-1)*l 特点：特点：是一种是一种随机存随机存取取的存储结构，的存储结构，只要确定了

20、起只要确定了起始位置，就可始位置，就可以访问表中的以访问表中的任何一个元素。任何一个元素。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级1720 12 33 45 35 54 23 65 76 78 1 2 3 4 5 6 7 8 9 10l l l l l l l l l l LOC(ai) = LOC(ai-1)+l = arr+(i-1)*larr+(i-1)*larr单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级

21、第三级第三级 第四级第四级 第五级第五级18线性表顺序存储结构的线性表顺序存储结构的 C语言定义语言定义#define LIST_INIT_SIZE 100#define LISTINCREAMENT 10typedef struct ElemType *elem； /* 线性表占用的数组空间。线性表占用的数组空间。*/ int length； /*线性表的长度线性表的长度*/ int listsize； /*当前分配的存储容量当前分配的存储容量(以以sizeof(ElemType)为单位为单位) /* SqList； elemlengthlistsizeSqListElemType单击此处编

22、辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级19顺序线性表的操作顺序线性表的操作l 顺序表容易实现访问操作，可随机存取元素。但插入顺序表容易实现访问操作，可随机存取元素。但插入和删除操作需要移动元素。和删除操作需要移动元素。 初始化操作初始化操作 算法思想：构造一个空表。算法思想：构造一个空表。 设置表的起始位置、表长及可用空间。设置表的起始位置、表长及可用空间。0100La.019899单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第

23、二级 第三级第三级 第四级第四级 第五级第五级20初始化操作实现初始化操作实现Status InitList_Sq(SqList &L) /构造一个空的线性表构造一个空的线性表 L.elem=(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType); if (! L.elem) exit(OVERFLOW); /存储分配失败存储分配失败 L.length=0; /空表长度为空表长度为0 L.listsize= LIST_INIT_SIZE; /初始存储容量初始存储容量 return OK; /InitList_Sq 单击此处编辑母版标题样式单击此处

24、编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级21（2）线性表的顺序表插入操作）线性表的顺序表插入操作 ListInsert(&L, i, e) 分析：分析：“插入元素插入元素”使线性表的逻辑结构发生什么变使线性表的逻辑结构发生什么变化？假设在线性表的第化？假设在线性表的第i个元素之前插入一个元素个元素之前插入一个元素e。插入元素时，线性表的逻辑结构由插入元素时，线性表的逻辑结构由 (a1,ai-1, ai,an) (a1, , ai-1, e, ai, , an), a1 a2 ai-1 ai ana1 a2 ai-

25、1 ai ean单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级22ListInsert(&La, 4, 29)221)(1)(1 0)1(11)(11=nnnnnn1inn1ni1AMN20 38 46 18 40 39 78 1 2 3 4 5 6 7 8La78平均移动次数：平均移动次数：39401829单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级23算法的基本思想算法的基本

26、思想检查检查i i值是否超出所允许的范围值是否超出所允许的范围（1in+11in+1），若超出，则进行），若超出，则进行“超出范超出范围围”错误处理；错误处理；将线性表的第将线性表的第i i个元素和它后面的所有元素个元素和它后面的所有元素均向后移动一个位置；均向后移动一个位置；将新元素写入到空出的第将新元素写入到空出的第i i个位置上；个位置上；使线性表的长度增使线性表的长度增1 1。 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级24Status ListInsert_Sq(SqLis

27、t &L, int i, ElemType e) / 在顺序表在顺序表L的第的第 i 个元素之前插入新的元素个元素之前插入新的元素e, / i 的合法范围为的合法范围为 1iL.length+1 ElemType *p,*q; if (i L.length+1) return ERROR; / 插入位置不合法插入位置不合法 if (length = listsize) . q = &(L.elemi-1); / q 指示插入位置指示插入位置 for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元

28、素右移 *q = e; / 插入插入e + length; / 表长增表长增1 return OK;/ ListInsert_Sq newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType); If(!newbase) return OVERFLOW;/当前存储空间已满当前存储空间已满 elem=newbase; listsize+=LISTINCREMENT; 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第

29、四级第四级 第五级第五级25（3）线性表的顺序表删除操作）线性表的顺序表删除操作 ListDelete(&La, i, &e) 分析：分析： “删除元素删除元素” 线性表的逻辑结构发生什么变线性表的逻辑结构发生什么变化？假设删除线性表的第化？假设删除线性表的第i个元素保存在变量个元素保存在变量e中。中。删除元素时，线性表的逻辑结构由删除元素时，线性表的逻辑结构由 (a1,ai-1, ai,an) (a1, , ai-1, ai+1, , an)a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 ai+1 ean ai单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版

30、文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级26ListDelete(&La, 4, &e)20 38 46 18 40 39 78 1 2 3 4 5 6 7 8La78平均移动次数：平均移动次数：3940e18ninnnninn1AMN2121)(1)(1=单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级27算法的基本思想算法的基本思想检查检查i i值是否超出所允许的范围（值是否超出所允许的范围（1in1in），），若超出，则进行若超出，则进

31、行“超出范围超出范围”错误处理；错误处理；将线性表的第将线性表的第i i个元素后面的所有元素均向个元素后面的所有元素均向前移动一个位置；前移动一个位置；使线性表的长度减使线性表的长度减1 1。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级28 Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表在顺序线性表L中删除第中删除第i个元素，并用个元素，并用e返回其值。返回其值。 / i的合法值为的合法值为1iListLengt

32、h_Sq(L) if (i L.length) return ERROR; / 删除位置不合法删除位置不合法 p = &(L.elemi-1); / p为被删除元素的位置为被删除元素的位置 e = *p; / 被删除元素的值赋给被删除元素的值赋给e q = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置 for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移被删除元素之后的元素左移 - - L.length; return ok; 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式

33、第二级第二级 第三级第三级 第四级第四级 第五级第五级29（4）线性表的顺序表查找操作）线性表的顺序表查找操作 LocateElem_Sq (La, e) Status LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 int i; ElemType *p; i= 1; p=L.elem; while (i = L.length &

34、!(* compare(*p+, e) +i; if (i = L.length) return i; else return 0; / LocateElem_Sq 此算法的时间复杂度为此算法的时间复杂度为: O( ListLength(L) ) 平均比较次数为：平均比较次数为：(n+1)/2单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级30例如：顺序表例如：顺序表23 75 41 38 54 62 17L.elemL.length = 7L.listsizee =38pppppi1 2

35、 3 4 1 850p可见，基本操作是，可见，基本操作是，将顺序表中的元素将顺序表中的元素逐个和给定值逐个和给定值 e e 相比较。相比较。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级31顺序存储结构的优缺点顺序存储结构的优缺点 优点优点 逻辑相邻，物理相邻逻辑相邻，物理相邻 可随机存取任一元素可随机存取任一元素 存储空间使用紧凑存储空间使用紧凑 缺点缺点 插入、删除操作需要移动大量的元素插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分预先分配空间需按最大空间

36、分配，利用不充分 表容量难以扩充表容量难以扩充单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级32顺序表的合并问题顺序表的合并问题 例例1、已知顺序表、已知顺序表LA和和LB中的数据元素按值非递减中的数据元素按值非递减有有序排列序排列，现要将，现要将LA和和LB归并为一个新表归并为一个新表LC，且，且LC中的数据元素仍按非值递减有序排序。中的数据元素仍按非值递减有序排序。 例如：例如：LA（3,5,8,9） LB（2,6,8,9,11,15,20） 则则LC（2,3,5,6,8,8,9,1

37、1,11,15,20）85398210111520papbpc2356 688910111520单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级33void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+ Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType

38、);If(!Lc.elem) exit(OVERFLOW);pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb) *pc+=*pa+;else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+;while(pbdata 表示表示p指向结点的指向结点的数据域数据域(*p).next p-next 表示表示p指向结点的指向结点的指针域指针域LinkListLNodeLNodenextdata单击此处编辑母版标题样式单击此处编辑母版标题

39、样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级39 生成一个生成一个LNode型新结点：型新结点： p=(LinkList)malloc(sizeof(LNode); 系统回收系统回收p结点：结点： free(p) 单链表特点单链表特点: 它是一种动态结构，整个存储空间为多个链表共用它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间不需预先分配空间 指针占用额外存储空间指针占用额外存储空间 插入、删除方便插入、删除方便 不能随机存取，查找速度慢不能随机存取，查找速度慢单击此处编辑母版标题样式单击此处编辑母版标题样式 单

40、击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级40单链表基本操作的实现单链表基本操作的实现GetElem(L, i, &e) / 取第取第i个数据元素个数据元素ListInsert(&L, i, e) / 插入数据元素插入数据元素ListDelete(&L, i, &e) / 删除数据元素删除数据元素CreateList_L(&L, n) / 创建线性表创建线性表单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级41（1）单链表查找操作

41、）单链表查找操作 GetElem(L, i, &e)Lpj12 32017406034 实现实现GetElem(L, 3, &e) 实现实现GetElem(L, 6, &e)4 5单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级42算法的基本思想算法的基本思想令令p为指针变量，首先指向第一个结点，变为指针变量，首先指向第一个结点，变量量j为计数器；为计数器；依次向后查找，循环结束的条件，依次向后查找，循环结束的条件，p为空或为空或者者j=i。如果如果p为空为空 或或 ji，出错。，出错。找

42、到了，用找到了，用e返回第返回第i个元素。个元素。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级43算法实现算法实现 Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 p = L-next; / p指向第一个结点指向第一个结点 j = 1; / j为计数器为计数器 while (p & jnext; +j; if ( !p | ji ) re

43、turn ERROR; e = p-data;/ 取得第取得第 i 个元素个元素 return OK; / GetElem_L单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级44（2）单链表的插入操作）单链表的插入操作 ListInsert(&L, i, e) 分析：分析：“插入元素插入元素”使线性表的逻辑结构和物理结构使线性表的逻辑结构和物理结构发生什么变化？假设在线性表的第发生什么变化？假设在线性表的第i个元素之前插入一个元素之前插入一个元素个元素e。 (a1,ai-1, ai,an)

44、 (a1, , ai-1, e, ai, , an), ai-1anaia1Le单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级45第第i个元素之前插入元素个元素之前插入元素es = (LinkList)malloc(sizeof(LNode);/ 生成新结点生成新结点s-data = e; s-next = p-next; p-next = s；ai( (插入前插入前) () (插入后插入后) )aiai-1peai-1sp单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母

45、版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级46单链表插入操作单链表插入操作 ListInsert ( &L, i, e ) Lpj122017406034 实现实现ListInsert (L, 3, 10 )10s单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级47/ 带头结点的单链表带头结点的单链表L中第中第 i 个位置之前插入元素个位置之前插入元素 eLNode *p,*s; int j;p = L; j = 0;while ( p &

46、jnext; +j; if ( ! p | j i-1 ) return ERROR; s = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新结点生成新结点s-data = e; / 使新结点数据域的值为使新结点数据域的值为 es-next = p-next; / 将新结点插入到单链表将新结点插入到单链表 L 中中p-next = s; / 修改第修改第 i-1 个结点指针个结点指针return OK; / ListInsert_LStatus ListInsert_L ( LinkList &L, int i, ElemType e ) 时间复

47、杂度：时间复杂度： T(n)=O(n)单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级48（3）单链表的删除操作单链表的删除操作 ListDelete(&L, i, &e) 分析：分析：“删除元素删除元素”使线性表的物理结构发生什么变使线性表的物理结构发生什么变化？化？ai-1anaia1Lai+1单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级49删除第删除第i个元素，并保存数据到元

48、素个元素，并保存数据到元素e中中 q = p-next; / 用指针用指针 q 指向被删除结点指向被删除结点 p-next = q-next; / 删除第删除第 i 个结点个结点*e=ai;free(q);pqpai+1aiai-1aie单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级50单链表的删除操作单链表的删除操作 ListDelete(&L, i, &e)Lpj122017406034 实现实现ListDelete(&L, 3, &e)q单击此处编辑母版标题样式单击此处编辑母版标题

49、样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级51/ 删除第删除第 i 个元素，并由个元素，并由 e 返回其值返回其值LNode *p,*q;int j;p = L; j = 0;while ( p-next & jnext; +j; if ( !(p-next) | j i-1 ) return ERROR; / 删除位置不合理删除位置不合理 q = p-next; / 用指针用指针 q 指向被删除结点指向被删除结点p-next = q-next; / 删除第删除第 i 个结点个结点e = q-data; / 取出第取出第 i

50、个结点数据域值个结点数据域值free (q); / 释放第释放第 i 个结点个结点return OK; / LinkDelete_LStatus ListDelete_L ( LinkList L, int i, ElemType &e )时间复杂度：时间复杂度： T(n)=O(n)单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级52 （4）创建单链表）创建单链表 CreateList_L(&L, n)Lp2017406034 已知线性表（已知线性表（20，17，40，60，34） 头插法

51、创建带有头结点的单链表。头插法创建带有头结点的单链表。pppp单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级53头插法头插法 创建单链表创建单链表执行的语句组为:snextLnext；Lnexts；L(a) 建空表c1ss 指向新申请的结点sdatac1(b) 申请新结点并赋值Lci 1s(c) 插入第一个结点Lc2c1cic1s(d) 插入第 i个元素单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第

52、四级 第五级第五级54CreateList_L(LinkList &L, int n) L = (LinkList) malloc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof (LNode) ); scanf( &s-data); s-next = L-next; L-next = s; 头插法头插法 创建单链表创建单链表单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级5

53、5void CreateList_L ( LinkList &L, int n ) / 输入输入 n 个数据元素的值，建立带头结点的单链表个数据元素的值，建立带头结点的单链表 L LNode *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-ne

54、xt; L-next = p; / CreateList_L单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级56 （4）创建单链表）创建单链表 CreateList_L(&L, n)Lp2017 已知线性表（已知线性表（20，17，40，60） 尾插法创建带有头结点的单链表。尾插法创建带有头结点的单链表。 思考：算法如何实现？思考：算法如何实现？pq40p60p单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第

55、四级第四级 第五级第五级57用尾插法建立线性单链表用尾插法建立线性单链表r s； r 始终指向单链表的表尾L(a) 建空表c1ss 指向新申请的结点空间s data c1(b) 申请新结点并赋值Lc1s(c) 插入第一个结点Lc2c1rrr next s；(d) 插入第二个结点sr单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级58用尾插法建立线性单链表用尾插法建立线性单链表CreateList_L(LinkList &L, int n) tail = L = (LinkList) mal

56、loc( sizeof (LNode) ); L-next = NULL; for( i=n; i0; -i) s = (LinkList) malloc( sizeof(LNode) ); scanf( &s-data); s-next = NULL; tail-next = s; tail = s; 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级59线性表的合并问题线性表的合并问题 例例1、已知线性表、已知线性表Lc和和Lb中的数据元素按值非递减中的数据元素按值非递减有有序排列序排列

57、，现要将，现要将Lc和和Lb归并为一个新的链表归并为一个新的链表Lc，且，且Lc中的数据元素仍按非值递减有序排序。中的数据元素仍按非值递减有序排序。 例如：例如：La（3,5,8,11） Lb（2,6,9,15,20）La11853Lb2015962pcpbpaLc单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级60void MergeList_L ( LinkList &La, LinkList &Lb, LinkList &Lc ) / 归并归并 La 和和 Lb 得到新的单链表得到新

58、的单链表 Lc ，Lc 的元素也按非递减排列的元素也按非递减排列LNode *pa, *pb, *pc;pa = La-next; pb = Lb-next;Lc = pc = La; / 用用 La 的头结点作为的头结点作为 Lc 的头结点的头结点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; / 插入剩余段插入剩余段free (Lb); / 释放释放 Lb 的

59、头结点的头结点 / MergeList_L单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级612.3.2 循环链表循环链表 循环链表是单链表的变形。循环链表是单链表的变形。 循环链表最后一个结点的指针域不为循环链表最后一个结点的指针域不为NULLNULL，而是指向，而是指向了表的前端。了表的前端。 为简化操作，在循环链表中往往加入为简化操作，在循环链表中往往加入头结点头结点。 循环链表的特点是：循环链表的特点是：只要知道表中某一结点的地址，只要知道表中某一结点的地址，就可搜寻到所有其他结点

60、的地址。就可搜寻到所有其他结点的地址。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级62循环链表示例循环链表示例带头结点的循环链表带头结点的循环链表 a1a2a3anHanHa2a1H( (空表空表) )( (非空表非空表) )单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级63H31481557搜索搜索15 pppH31481557搜索搜索25 pppp p思考整个搜索算法的条件是