数据结构 第 2 章 线性表.ppt

《数据结构 第 2 章 线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构 第 2 章 线性表.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中1、线性表的定义和性质及基本运算线性表的定义和性质及基本运算 2、线性表的顺序存储结构线性表的顺序存储结构 3、线性表的链式存储结构线性表的链式存储结构 4、多项式的代数运算多项式的代数运算 教学内容教学内容 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中线性结构的特点：线性结构的特点：除第一个之外的数据元素均只有一个前驱除第一个之外的数据元素均只有一个前驱;存在唯一的一个被称作存在唯

2、一的一个被称作“第一个第一个”的数据元素的数据元素;除最后一个之外的数据元素均只有一个后继。除最后一个之外的数据元素均只有一个后继。数据元素的数据元素的 非空非空非空非空有限集有限集 存在唯一的一个被称作存在唯一的一个被称作“最后一个最后一个”的数据元素的数据元素;法学系法学系法学系法学系 85231018523101 国贸系国贸系 8522105工商系工商系 8523150计算机系计算机系 8521088会计系会计系 8525789统计系统计系 8528136 外语系外语系 8523026 例：例：“第一个第一个第一个第一个”数据元素数据元素数据元素数据元素 “最后一个最后一个”数据元素数据

3、元素 直接前驱直接前驱 直接后继直接后继 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中2.1 线性表的类型定义线性表的类型定义 线性表线性表(Linear_List)：由由 n(n 0)个数据元素个数据元素 a1,a2,an 组成的组成的 有限有限有限有限并且并且有序有序有序有序的序列。的序列。其中数据元素的个数其中数据元素的个数 n 定义为表的定义为表的长度长度。当当 n=0 时称为时称为空表空表。非空的线性表非空的线性表(n0)常记作：常记作：(a1,a2,ai-1,ai,ai+1,an)例例1：26 个英文字母组成的字母表：（个英文字母组成的字母

4、表：（A,B,C,Z）例例2：某校从：某校从 1978 年到年到 1983 年各种型号的计算机拥有量的变化年各种型号的计算机拥有量的变化 情况：情况：（6,17,28,50,92,188）数据元素为数字数据元素为数字 i 为数据元素为数据元素 ai 的的位序位序。这里的数据元素这里的数据元素 ai(1 i n)只是一个抽象的符号，其具体只是一个抽象的符号，其具体 含义在不同的情况下可以不同。含义在不同的情况下可以不同。数据元素为字符数据元素为字符 指线性表中的每一指线性表中的每一 个元素都有自己的个元素都有自己的 位置（位置（position）。）。数据结构数据结构 第二章第二章 线性表线性表

5、 制作：制作：计算机科学与技术学院 徐振中例例3：学生健康情况登记表：学生健康情况登记表：姓姓 名名学学 号号性性 别别年龄年龄健康情况健康情况王小林王小林790631男男18健康健康陈陈 红红790632女女20一般一般刘建平刘建平790633男男21健康健康张立立张立立790634男男17神经衰弱神经衰弱.数据元素数据元素数据元素数据元素 (结点、记录结点、记录结点、记录结点、记录)由由 5 个个数据项数据项(字段、域字段、域)组成。组成。文件文件文件文件(filefile)线性表中的数据元素可以是各种各样的，但线性表中的数据元素可以是各种各样的，但同一线性表中的同一线性表中的 元素必定具

6、有相同特性元素必定具有相同特性（属于同一数据对象）。（属于同一数据对象）。线性表中的数据元素之间存在着线性表中的数据元素之间存在着序偶关系序偶关系 。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 从以上例子可看出从以上例子可看出线性表（非空）的逻辑特征线性表（非空）的逻辑特征是：是：1、有且仅有一个开始结点、有且仅有一个开始结点 a1，它没有直接前趋，而仅有它没有直接前趋，而仅有 一个直接后继一个直接后继 a2，a1 叫叫表头元素表头元素表头元素表头元素；2、有且仅有一个终端结点、有且仅有一个终端结点 an，它没有直接后继，而仅有它没有直接后继，而仅有

7、 一个直接前趋一个直接前趋 an-1，an 叫叫表尾元素表尾元素表尾元素表尾元素；3、其余的内部结点、其余的内部结点 ai(2 i n-1)都有且仅有一个直接都有且仅有一个直接 前趋前趋 ai 1 和一个直接后继和一个直接后继 ai+1。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中ADT List 抽象数据类型抽象数据类型线性表线性表的定义的定义：参看：参看 P19。数据对象：数据对象：D ai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,aiD,i=2,.,n 基本操作基本操作：（：（线性表的基本操作很多，为讨论

8、方便起见，在线性表的基本操作很多，为讨论方便起见，在 此将它归为四类。此将它归为四类。）结构初始化结构初始化 任何数据结构在被使用之前都必须进行任何数据结构在被使用之前都必须进行“初始化初始化”，它类似，它类似 于编程中使用的变量都必须先有定义。于编程中使用的变量都必须先有定义。InitList(&L)操作结果：操作结果：构造一个空的线性表构造一个空的线性表 L。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 销毁结构销毁结构 任何数据结构不再使用时都必须进行任何数据结构不再使用时都必须进行“结构销毁结构销毁”，其实质，其实质 为为“释放释放”它所占有的

9、存储空间。它所占有的存储空间。DestroyList(&L)初始条件：初始条件：线性表线性表 L 已存在。已存在。操作结果：操作结果：销毁线性表销毁线性表 L。引用型操作引用型操作 ListEmpty(L)初始条件：初始条件：线性表线性表 L 已存在。已存在。操作结果：操作结果：若若 L 为空表，则返回为空表，则返回 TRUE，否则返回否则返回 FALSE。操作的结果不改变线性表中的数据元操作的结果不改变线性表中的数据元 素，也不改变数据元素之间的关系。素，也不改变数据元素之间的关系。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 ListLength(

10、L)初始条件：初始条件：线性表线性表 L 已存在。已存在。操作结果：操作结果：返回返回 L 中元素个数。中元素个数。若若 cur_e 是线性表是线性表 L 中第一个数据元素，中第一个数据元素，则它的前驱则它的前驱 pre_e 为为 “空元素空元素”。NextElem(L,cur_e,&next_e)初始条件：初始条件：线性表线性表 L 已存在。已存在。操作结果：操作结果：若若 cur_e 是是 L 中的数据元素，则用中的数据元素，则用 next_e 返回返回 它的后继，否则操作失败，它的后继，否则操作失败，next_e 无定义。无定义。PriorElem(L,cur_e,&pre_e)初始条件

11、：初始条件：线性表线性表 L 已存在。已存在。操作结果：操作结果：若若 cur_e 是是 L 中的数据元素，则用中的数据元素，则用 pre_e 返回返回 它的前驱，否则操作失败，它的前驱，否则操作失败，pre_e 无定义。无定义。若若 cur_e 是线性表是线性表 L 中中 最后一个数据元素，则最后一个数据元素，则 它的后继它的后继 next_e 为为“空空 元素元素”。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 GetElem(L,i,&e)初始条件：初始条件：线性表线性表 L 已存在，已存在，1iLengthList(L)。操作结果：操作结果：用

12、用 e 返回返回 L 中第中第 i 个元素的值。个元素的值。此操作通常称为此操作通常称为“定位函数定位函数”，这是一种广义的定位函数写，这是一种广义的定位函数写 法，以法，以 compare()作为判定的条件，参数作为判定的条件，参数 e 和线性表中数据元和线性表中数据元 素具有相同类型。较多场合是以素具有相同类型。较多场合是以“相等相等相等相等”作为判定条件，此时可作为判定条件，此时可 省略省略省略省略函数参数，且操作结果为：若线性表中存在与函数参数，且操作结果为：若线性表中存在与 e 值相同的值相同的 数据元素，则返回第一个这样的元素在表中的位序，否则返回数据元素，则返回第一个这样的元素在

13、表中的位序，否则返回 函数值为函数值为 0。LocateElem(L,e,compare()初始条件：初始条件：线性表线性表 L 已存在，已存在，compare()是元素判定函数。是元素判定函数。操作结果：操作结果：返回返回 L 中第中第 1 个与个与 e 满足关系满足关系 compare()的元的元 素的位序。若这样的元素不存在，则返回素的位序。若这样的元素不存在，则返回 0。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 ListTraverse(L,visit()初始条件：初始条件：线性表线性表 L 已存在，已存在，visit()为元素的访问函数。

14、为元素的访问函数。操作结果：操作结果：依次对依次对 L 的每个元素调用函数的每个元素调用函数 visit()。一旦一旦 visit()失败，则操作失败。失败，则操作失败。visit()亦为函数参数，常见的情况是亦为函数参数，常见的情况是“依次输出表中元素的依次输出表中元素的依次输出表中元素的依次输出表中元素的 值值值值”，同样在这种情况下，通常的写法也是，同样在这种情况下，通常的写法也是省略省略省略省略函数参数。函数参数。加工型操作加工型操作 操作的结果或修改表中的数据操作的结果或修改表中的数据 元素，或修改元素之间的关系元素，或修改元素之间的关系 ClearList(&L)初始条件：初始条件

15、：线性表线性表 L 已存在。已存在。操作结果：操作结果：将将 L 重置为空表。重置为空表。在对线性表在对线性表 L 进行进行 ClearList(L)操作之后，仅是删除表中操作之后，仅是删除表中 所有元素，在以后的程序中仍可对它进行某些所有元素，在以后的程序中仍可对它进行某些“合法合法”操作，如操作，如 判空、插入等。但在进行了判空、插入等。但在进行了 DestroyList(L)操作之后，线性表操作之后，线性表 L 不再存在，即不能在以后的程序中再引用它。不再存在，即不能在以后的程序中再引用它。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 PutEl

16、em(&L,i,e)初始条件：初始条件：线性表线性表 L 已存在，已存在，1iLengthList(L)。操作结果：操作结果：L 中第中第 i 个元素赋值为个元素赋值为 e 的值。的值。ListInsert(&L,i,e)初始条件：初始条件：线性表线性表 L 已存在，已存在，1iLengthList(L)+1。操作结果：操作结果：在在 L 的第的第 i 个元素之前插入新的元素个元素之前插入新的元素 e，L 的长度增的长度增 1。ListDelete(&L,i,&e)初始条件：初始条件：线性表线性表 L 已存在且非空，已存在且非空，1iLengthList(L)。操作结果：操作结果：删除删除 L

17、 的第的第 i 个元素，并用个元素，并用 e 返回其值，返回其值，L 的长度减的长度减 1。ADT List 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 上述各个操作目前还无法在程序设计中加以引用。上述各个操作目前还无法在程序设计中加以引用。但如果已经实现了上述定义的线性表类型，那么在应用问题的但如果已经实现了上述定义的线性表类型，那么在应用问题的 求解中就可以用这些操作实现应用问题的算法设计。求解中就可以用这些操作实现应用问题的算法设计。注注 例例2-1：已知集合已知集合 A 和和 B，求这两个集合的并集，使，求这两个集合的并集，使 AAB，且且

18、B 不再单独存在不再单独存在。要在计算机中求解，首先要确定要在计算机中求解，首先要确定“如何表示集合如何表示集合如何表示集合如何表示集合”。用线性表表示集合用线性表表示集合 以线性表以线性表 LA 和和 LB 分别表示集合分别表示集合 A 和和 B，两个线性表的，两个线性表的 数据元素分别为集合数据元素分别为集合 A 和和 B 中的成员。中的成员。由此，上述集合求并的问题便可演绎为：由此，上述集合求并的问题便可演绎为：扩大线性表扩大线性表 LA，将存在于线性表将存在于线性表 LB 中而不存在于线性中而不存在于线性 表表 LA 中的数据元素插入到线性表中的数据元素插入到线性表 LA 中去。中去。

19、数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中思路：思路：1从从 LB 中中取出取出取出取出一个数据元素；一个数据元素；2依值在依值在 LA 中进行中进行查询查询查询查询；3.若不存在，则若不存在，则插入插入插入插入之。之。重复上述三步直至重复上述三步直至 LB 中的数据元素取完为止。中的数据元素取完为止。ListInsert(&LA,n+1,e)GetElem(LB,i,&e)LocateElem(LA,e,equal()其中的每一步能否利用线性表类型中定义的基本操作来其中的每一步能否利用线性表类型中定义的基本操作来 完成呢完成呢？ListDelete

20、(&LB,i,&e)数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度求线性表的长度 for(i=1;i=Lb_len;i+)GetElem(Lb,i,&e);/取取 Lb 中第中第 i 个数据元素赋给个数据元素赋给 e if(!LocateElemLocateElem (La,e,equal()ListInsert(&La,+La_len,e);/La 中不存在和中不存在和 e 相同的数据元素，则插入

21、之相同的数据元素，则插入之 DestroyList(LB);/销毁线性表销毁线性表 LB /union 假设执行时间与表长无关假设执行时间与表长无关 执行时间与表长成正比执行时间与表长成正比执行时间与表长成正比执行时间与表长成正比 时间复杂度：时间复杂度：O(ListLength(La)ListLength(Lb)算法算法 2.1 ListDelete(&LB,i,&e)数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中例例2-2：归并两个归并两个“其数据元素按值非递减有序排列的其数据元素按值非递减有序排列的”线性表线性表 La 和和 Lb，求得线性表求得线

22、性表 Lc 也具有同样特性。也具有同样特性。设设 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)思路：思路：1分别从分别从 La 和和 Lb 中取得当前元素中取得当前元素 ai 和和 bj；2若若 ai bj，则将则将 ai 插入到插入到 Lc 中，否则将中，否则将 bj 插入到插入到 Lc 中。中。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中void MergeList(List La,List Lb,List&Lc)InitList(&Lc);i=j=1;k=0

23、;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)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);假设执行时

24、间与表长无关假设执行时间与表长无关 时间复杂度：时间复杂度：O(ListLength(La)+ListLength(Lb)算法算法 2.2 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 在实际的程序设计中在实际的程序设计中要引用要引用线性表的基本操作，线性表的基本操作，必须必须先实现先实现先实现先实现线性表类型。线性表类型。确确 定定 存存 储储 结结 构构 实实 现现 基基 本本 操操 作作 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中2.2 线性表的顺序表示和实现线性表的顺序表示和实现 在计算机中用一组在计

25、算机中用一组地址连续地址连续地址连续地址连续的存储单的存储单 元元依次存储依次存储依次存储依次存储线性表的各个数据元素，线性表的各个数据元素，称作称作 线性表的线性表的顺序存储结构顺序存储结构或或顺序映象顺序映象。用这用这 种方法存储的线性表称作种方法存储的线性表称作顺序表顺序表。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中例如：线性表例如：线性表 (1,2,3,4,5,6)的存储结构：的存储结构：1 2 3 4 5 6 是是是是一个典型的一个典型的线形表顺序存储结构线形表顺序存储结构线形表顺序存储结构线形表顺序存储结构。不是不是不是不是一个一个线形表

26、顺序存储结构线形表顺序存储结构线形表顺序存储结构线形表顺序存储结构。1 2 3 4 5 6 依次存储，地址连续依次存储，地址连续 中间中间没有空出存储单元。没有空出存储单元。存储结构：存储结构：地址不连续地址不连续 中间中间存在空的存储单元。存在空的存储单元。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中顺序表中元素存储位置的计算：顺序表中元素存储位置的计算：假设线性表的每个元素需占假设线性表的每个元素需占 l 个存储单元，个存储单元，则第则第 i+1 个数据个数据 元素的存储位置和第元素的存储位置和第 i 个数据元素的存储位置之间满足关系：个数据元素的

27、存储位置之间满足关系：LOC(ai+1)=LOC(ai)+l 由此，所有数据元素的存储位置均可由第一个数据元素的存由此，所有数据元素的存储位置均可由第一个数据元素的存 储位置得到：储位置得到：LOC(ai)=LOC(a1)+(i-1)l 线性表的第线性表的第 1 个数据元素个数据元素 a1 的存储位置，称作的存储位置，称作线性表的线性表的起起 始位置始位置或或基地址基地址。基地址基地址基地址基地址a1 a2 ai-1 ai ai+1 an 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中线性表顺序存储结构的图示：线性表顺序存储结构的图示：存储地址存储地址

28、内存状态内存状态 数据元素在线数据元素在线 性表中的位序性表中的位序 a1 a2 ai an LOC(a1)LOC(a1)+l LOC(a1)+(i-1)l LOC(a1)+(n-1)l 1 2 i n 顺序表的特点：顺序表的特点：以物理位置相邻表示逻辑关系。以物理位置相邻表示逻辑关系。以物理位置相邻表示逻辑关系。以物理位置相邻表示逻辑关系。任一元素均可随机存取。任一元素均可随机存取。任一元素均可随机存取。任一元素均可随机存取。（优点）（优点）LOC(a1)+n l LOC(a1)+(maxlen-1)l 空闲空闲 顺序表在机器内顺序表在机器内 存中的物理状态存中的物理状态本课程在本课程在高级

29、语高级语高级语高级语 言层次言层次言层次言层次讨论数据讨论数据 结构的实现方法结构的实现方法 需用需用高级语言已高级语言已 经实现的数据类经实现的数据类 型型描述存储结构描述存储结构 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中用一维数组用一维数组 表示顺序表表示顺序表 类型相同类型相同 用一变量表示顺序表的长度属性用一变量表示顺序表的长度属性 线性表长可变（删除）线性表长可变（删除）顺序表（元素）顺序表（元素）地址连续地址连续 随机存取随机存取 依次存放依次存放 数组（元素）数组（元素）数组长度不可动态定义数组长度不可动态定义#define LIST

30、_INIT_SIZE 100 /线性表存储空间的初始分配量线性表存储空间的初始分配量 typedef struct ElemType elemLIST_INIT_SIZE;int length;/当前长度当前长度 SqList;一维数组的定义方式：一维数组的定义方式：类型说明符类型说明符 数组名数组名 常量表达式常量表达式 说明：常量表达式中可以包含常量和说明：常量表达式中可以包含常量和 符号常量，不能包含变量。即符号常量，不能包含变量。即C 不允不允 许对数组的大小作动态定义。许对数组的大小作动态定义。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 考

31、虑到线性表因插入元素而使存储空间不足的问题，应考虑到线性表因插入元素而使存储空间不足的问题，应允许允许 数组容量进行动态扩充数组容量进行动态扩充。#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量线性表存储空间的分配增量typedef struct ElemType *elem;/数组指针，指示线性表的基地址数组指针，指示线性表的基地址 int length;/当前长度当前长度 int listsize;/当前分配的存储容量当前分配的存储容量(以以sizeof(

32、ElemType)为单位为单位)SqList;C 语言中的数组下标从语言中的数组下标从“0”开始，因此若开始，因此若 L 是是 Sqlist 类型的顺序表，则表中第类型的顺序表，则表中第 i 个元素是个元素是 L.elemi-1。注意注意 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中Status InitList_Sq(Sqlist&L)/构造一个空的顺序表构造一个空的顺序表 L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/存储分

33、配失败存储分配失败 L.lengh=0;/空表长度为空表长度为 0 L.listsize=LIST_INIT_SIZE;/初始存储容量初始存储容量 return OK;/InitList_Sq 初始化操作：初始化操作：为顺序表分配一预定义大小的数组空间，并将线性表的当前长度设为为顺序表分配一预定义大小的数组空间，并将线性表的当前长度设为 0。函数的类型函数的类型 顺序表基本操作的实现顺序表基本操作的实现 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中771 2 3 4 5 6 线性表的插入运算是指在表的第线性表的插入运算是指在表的第 i(1 i n+1)

34、个位置上，插个位置上，插 入一个新结点入一个新结点 b，使长度为使长度为 n 的线性表的线性表 (a1,ai 1,ai,an)变成长度为变成长度为 n+1 的线性表的线性表 (a1,ai 1,b,ai,an)1 2 3 4 5 6 71 2 3 4 5 6 5 671 2 3 4 5 67算法思想：算法思想：1）检查）检查 i 值是否超出所允许的范围值是否超出所允许的范围(1 i n+1)，若超出，则进若超出，则进 行行“超出范围超出范围”错误处理；错误处理；2）将线性表的第）将线性表的第 i 个元素和它后面的所有元素均后移一个位置；个元素和它后面的所有元素均后移一个位置；3）将新元素写入到空

35、出的第）将新元素写入到空出的第 i 个位置上；个位置上；4）使线性表的长度增）使线性表的长度增 1。插入插入操作：操作：数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中Status ListInsert_Sq(SqList&L,int i,ElemType e)if(i L.length+1)return ERROR;/插入位置不合法插入位置不合法 if(L.length=L.listsize)/当前存储空间已满，增加分配当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCR

36、EMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败存储分配失败 L.elem=newbase;/新基址新基址 L.listsize+=LISTINCREMENT;/增加存储容量增加存储容量 q=&(L.elemi-1);/q 指示插入位置指示插入位置 for(for(p p=&(L.elemL.length-1);=&(L.elemL.length-1);p p=q q;-;-p p)*()*(p p+1)=*+1)=*p p;/插入位置及之后的元素右移插入位置及之后的元素右移插入位置及之后的元素右移插入位置及之后的元素右移 *

37、q=e;/插入插入e +L.length;/表长增表长增 1 return OK;/ListInsert_sq 算法算法 2.4 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中插入算法的时间复杂度分析：插入算法的时间复杂度分析：问题规模问题规模问题规模问题规模是表的长度，设它的值为是表的长度，设它的值为 n。算法的时间主要花费在向后移动元素的算法的时间主要花费在向后移动元素的 for 循环语句上。该语循环语句上。该语 句的循环次数为句的循环次数为 (n i+1)。由此可看出，所需移动结点的次由此可看出，所需移动结点的次 数不仅依赖于表的长度数不仅依赖于表

38、的长度 n，而且还与插入位置而且还与插入位置 i 有关。有关。当插入位置在表尾当插入位置在表尾(i=n+1)时，不需要移动任何元素时，不需要移动任何元素；这是最这是最 好情况，其时间复杂度好情况，其时间复杂度 O(1)。当插入位置在表头当插入位置在表头(i=1)时，所有元素都要向后移动，循环语时，所有元素都要向后移动，循环语 句执行句执行 n 次，这是最坏情况，其时间复杂度次，这是最坏情况，其时间复杂度 O(n)。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中 算法的平均时间复杂度：算法的平均时间复杂度：设设 pi 为在第为在第 i 个元素之前插入一个元

39、个元素之前插入一个元 素的概率，则在长度为素的概率，则在长度为 n 的线性表中插入一个元素时所需移动的线性表中插入一个元素时所需移动 元素次数的期望值为元素次数的期望值为 假设假设假设假设在表中任何位置在表中任何位置(1 i n+1)上插入结点的机会是均等的，上插入结点的机会是均等的，则则则则 由此可见，由此可见，在顺序表上做插入运算，平均要移动表上一半元在顺序表上做插入运算，平均要移动表上一半元 素。素。当表长当表长 n 较大时，算法的效率相当低。算法的平均时间复杂较大时，算法的效率相当低。算法的平均时间复杂 度为度为 O(n)。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算

40、机科学与技术学院 徐振中 删除操作删除操作 线性表的删除运算是指将表的第线性表的删除运算是指将表的第 i(1 i n)个结点删除，个结点删除，使长度为使长度为 n 的线性表的线性表 (a1,ai 1,ai,an)变成长度为变成长度为 n-1 的线性表的线性表 (a1,ai 1,ai+1,an)61 2 3 4 5 641 2 3 4 5 61算法思想：算法思想：1)检查检查 i 值是否超出所允许的范围值是否超出所允许的范围(1 i n)，若超出，则进若超出，则进 行行“超出范围超出范围”错误处理；错误处理；2)将线性表的第将线性表的第 i 个元素后面的所有元素均前移一个位置；个元素后面的所有元

41、素均前移一个位置；3)使线性表的长度减使线性表的长度减 1。61 2 3 4 55 62 3 4 5 6数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中Status ListDelete_Sq(SqList&L,int i,ElemType&e)if(i L.length)return ERROR;/删除位置不合法删除位置不合法 p=&(L.elemi-1);/p为被删除元素的位置为被删除元素的位置 e=*p;/被删除元素的值赋给被删除元素的值赋给 e q=L.elem+L.length-1;/表尾元素的位置表尾元素的位置 for(+for(+p p;p

42、p=q q;+;+p p)*()*(p p-1)=*-1)=*p p;/被删除元素之后的元素左移被删除元素之后的元素左移被删除元素之后的元素左移被删除元素之后的元素左移 -L.length;/表长减表长减 1 return OK;/ListInsert_sq 算法算法 2.5 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中删除算法的复杂度分析：删除算法的复杂度分析：问题规模问题规模问题规模问题规模是表的长度，设它的值为是表的长度，设它的值为 n。算法的时间主要花费在向前移动元素的算法的时间主要花费在向前移动元素的 for 循环语句上。该语循环语句上。该语

43、 句的循环次数为句的循环次数为(n i)。由此可看出，所需移动结点的次数不由此可看出，所需移动结点的次数不 仅依赖于表的长度仅依赖于表的长度 n，而且还与删除位置而且还与删除位置 i 有关。有关。当删除位置在表尾当删除位置在表尾(i=n)时，不需要移动任何元素时，不需要移动任何元素；这是最好这是最好 情况，其时间复杂度情况，其时间复杂度 O(1)。当删除位置在表头当删除位置在表头(i=1)时，有时，有 n-1 个元素要向前移动，循环个元素要向前移动，循环 语句执行语句执行 n-1 次，这是最坏情况，其时间复杂度次，这是最坏情况，其时间复杂度 O(n)。数据结构数据结构 第二章第二章 线性表线性

44、表 制作：制作：计算机科学与技术学院 徐振中 算法的平均时间复杂度：算法的平均时间复杂度：设设 qi 为删除第为删除第 i 个元素的概率，则在个元素的概率，则在 长度为长度为 n 的线性表中删除一个元素时所需移动元素次数的期望的线性表中删除一个元素时所需移动元素次数的期望 值为值为 假设在表中任何位置假设在表中任何位置(1 i n)删除结点的机会是均等的，则删除结点的机会是均等的，则 由此可见，由此可见，在顺序表上做删除运算，平均在顺序表上做删除运算，平均约约约约要移动表上一半要移动表上一半 元素。元素。当表长当表长 n 较大时，算法的效率相当低。算法的平均时间复较大时，算法的效率相当低。算法

45、的平均时间复 杂度为杂度为 O(n)。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度求线性表的长度 for(i=1;i=Lb_len;i+)GetElem(Lb,i,&e);/取取 Lb 中第中第 i 个数据元素赋给个数据元素赋给 e if(!LocateElemLocateElem (La,e,equal()ListInsert(&La,+La_len,e);/La 中不存在和中不存在和 e 相同

46、的数据元素，则插入之相同的数据元素，则插入之 DestroyList(LB);/销毁线性表销毁线性表 LB /union 算法算法 2.1 void union(SqList&La,SqList Lb)for(i=1;i=Lb_len;i+)i=0;i Lb.length;i+)e=Lb.elemi;/取取 Lb 中第中第 i 个数据元素赋给个数据元素赋给 e sign=1;for j=0;j La.length;j+)if(La.elemj=e)sign=0;break;if(sign)La.elemLa.length=e;La.length+;数据结构数据结构 第二章第二章 线性表线性表

47、制作：制作：计算机科学与技术学院 徐振中作业作业 2.10、2.11、2.21、2.25 选择题部分选择题部分 1、一个线性表第一个元素的存储地址是、一个线性表第一个元素的存储地址是 100，每个元素的长度，每个元素的长度 为为 2，则第则第 5 个元素的地址是个元素的地址是()。（A）110（B）108（C）100（D）120 2、向一个有、向一个有 127 个元素的顺序表中插入一个新元素并保持原来个元素的顺序表中插入一个新元素并保持原来 顺序不变，平均要移动（顺序不变，平均要移动（）个元素。）个元素。（A）64（B）63（C）63.5（D）7 数据结构数据结构 第二章第二章 线性表线性表

48、制作：制作：计算机科学与技术学院 徐振中2.3 线性表的链式表示和实现线性表的链式表示和实现 顺序表的特点：顺序表的特点：以物理位置相邻表示逻辑关系。以物理位置相邻表示逻辑关系。以物理位置相邻表示逻辑关系。以物理位置相邻表示逻辑关系。任一元素均可随机存取。任一元素均可随机存取。任一元素均可随机存取。任一元素均可随机存取。顺序表的优点：顺序表的优点：顺序表的缺点：顺序表的缺点：进行插入和删除操作时，需移动大量的元素。进行插入和删除操作时，需移动大量的元素。进行插入和删除操作时，需移动大量的元素。进行插入和删除操作时，需移动大量的元素。为避免元素的移动，我们介绍线性表的另一种存储方式，为避免元素的

49、移动，我们介绍线性表的另一种存储方式，链式存储结构链式存储结构，简称为，简称为链表链表(Linked List)。数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中2.3.1 线性链表线性链表 用一组物理位置任意的存储单元来存放线性表的数据元素。用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的，甚至是零散这组存储单元既可以是连续的，也可以是不连续的，甚至是零散 分布在内存中的任意位置上的。因此，链表中元素的逻辑次序和分布在内存中的任意位置上的。因此，链表中元素的逻辑次序和 物理次序不一定相同。物理次序不一定相同

50、。链表的链表的存储方式存储方式 数据结构数据结构 第二章第二章 线性表线性表 制作：制作：计算机科学与技术学院 徐振中链链链链顺序表顺序表存储地址存储地址 存储状态存储状态 0031 赵赵 0033 钱钱 0035 孙孙 0037 李李 0039 周周 0041 吴吴 0043 郑郑 0045 王王 链表链表 存储地址存储地址 存储状态存储状态 0001 李李 0007 钱钱 0013 孙孙 0019 王王 0025 吴吴 0031 赵赵 0037 郑郑 0043 周周 0043 0013 0001 NULL 0037 0007 0019 0025头指针头指针 H 0031 指针域指针域 数据