Chapter2_线性表

1、第第2章章 线性表线性表王建芳王建芳计算机科学与技术学院计算机科学与技术学院河南理工大学河南理工大学 WIN-TC是一个是一个TC2 WINDOWS平台开发工具。平台开发工具。该软件使用该软件使用TC2为内核，提供为内核，提供WINDOWS平台的平台的开发界面，因此也就支持开发界面，因此也就支持WINDOWS平台下的功平台下的功能，例如剪切、复制、粘贴和查找替换等。而且能，例如剪切、复制、粘贴和查找替换等。而且在功能上也有它的独特特色例如语法加亮、在功能上也有它的独特特色例如语法加亮、C内内嵌汇编、自定义扩展库的支持等。并提供一组相嵌汇编、自定义扩展库的支持等。并提供一组相关辅助工具令你在编程

2、过程中更加方便。关辅助工具令你在编程过程中更加方便。 wintc不能编不能编windows应用程序，它只能编控制应用程序，它只能编控制台应用程序。台应用程序。2 众所周知众所周知TC是是DOS下的下的Text界面，所以界面，所以WIN-TC 和和 TC 属于是同一个编译器不同界面而已。属于是同一个编译器不同界面而已。 而而VC是微软公司提供的功能强大的是微软公司提供的功能强大的Window平台平台开发工具，支持开发工具，支持C,C+等语言，可以开发等语言，可以开发DOS和和Window平台的程序。而平台的程序。而TC只能开发只能开发DOS平台下平台下的程序，现多用来教学。的程序，现多用来教学。

3、3 DEV CPP DEV C+是一个是一个C+编译器编译器,遵循的是遵循的是GCC标准的编译器。现在的标准的编译器。现在的DEV C+支持最新支持最新的的C+和和C语言标准。语言标准。 而而turbo C2.0是是DOS时代的遗物了。很老了，一些新标准时代的遗物了。很老了，一些新标准并不支持，并不支持， 4 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数据结构的

4、三个方面数据结构的三个方面： 1 问题提出问题提出 一条记录有学号和成绩两个数据项，依一条记录有学号和成绩两个数据项，依次输入数据建立一个有序表（按成绩由次输入数据建立一个有序表（按成绩由大到小）。其中输入的数据如下（学号大到小）。其中输入的数据如下（学号，成绩）：，成绩）：(1,70),(2,85),(3,75), (1,70),(2,85),(3,75), (4,90),(5,60),(6,80),(7,76),(8,50)(4,90),(5,60),(6,80),(7,76),(8,50)等等。等等。 2 问题分析问题分析 可用结构体数组来存储记录。可用结构体数组来存储记录。 但数组一般

5、固定长度，分配多大空间才合适？但数组一般固定长度，分配多大空间才合适？ 如何实现每输入一条记录都保持有序？如何实现每输入一条记录都保持有序？ 如果需要增加其它功能，如删除、修改、查询、如果需要增加其它功能，如删除、修改、查询、排序，如何实现？排序，如何实现？ 如果数组长度不固定，如何动态分配数组空间？如果数组长度不固定，如何动态分配数组空间？ 如果记录还有姓名、课程等数据项，应如何修改如果记录还有姓名、课程等数据项，应如何修改程序？程序？ 8第第2章章 线性表线性表2.1 线性表的类型定义线性表的类型定义 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 线性表的链式表示与实现线性

6、表的链式表示与实现 2.4 一元多项式的表示及相加一元多项式的表示及相加 92.1 线性表的类型定义线性表的类型定义 线性结构：第线性结构：第2章至第章至第4章将讨论章将讨论“线性表线性表”、“栈栈”、“队列队列”、“串串” 线性结构特点：有线性结构特点：有“头头”元素元素有有“尾尾”元素元素，中，中间的元素有间的元素有“前驱前驱”元素元素和和“后继后继”元素元素 线性表是一个数据元素的线性表是一个数据元素的有序（次序）集有序（次序）集(1)集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；(2)集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；(3)除最后

7、元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；(4)除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。 102.1 线性表的类型定义线性表的类型定义抽象数据类型抽象数据类型线性表线性表的定义如下：的定义如下：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 为为 a

8、i 在线性表中的在线性表中的位序位序。 112.1 线性表的类型定义线性表的类型定义 基本操作：基本操作： 结构初始化操作（结构初始化操作（添加添加） 结构销毁操作（结构销毁操作（删除删除） 引用型操作（引用型操作（查询查询） 加工型操作（加工型操作（修改修改）ADT List 122.1 线性表的类型定义线性表的类型定义 结构初始化操作（结构初始化操作（添加添加）InitList( &L ) 操作结果：操作结果：构造一个空的线性表构造一个空的线性表L。 结构销毁操作（结构销毁操作（删除删除）DestroyList( &L ) 初始条件：初始条件：线性表线性表 L 已存在。已存在。 操作结果：

9、操作结果：销毁线性表销毁线性表 L。 132.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e )GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( ) 142.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）ListEmpty( L )（线性表判空）（线性表判空）初始条件：初始条件：线性

10、表线性表L已存在。已存在。操作结果：操作结果：若若L为空表，则返回为空表，则返回TRUE， 否则返回否则返回FALSE。 152.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）ListLength( L ) （求线性表的长度）（求线性表的长度）初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：返回返回L中元素个数。中元素个数。 162.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询） PriorElem( L, cur_e, &pre_e )（求数据元素的前驱）（求数据元素的前驱）初始条件：初始条件：线性表线性表L已存在。已

11、存在。操作结果：操作结果：若若cur_e是是L的元素，但不是第一，的元素，但不是第一，则用则用pre_e 返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义。无定义。 172.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）NextElem( L, cur_e, &next_e )（求数据元素的后继）（求数据元素的后继）初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：若若cur_e是是L的元素，但不是最后一的元素，但不是最后一个，则用个，则用next_e返回它的后继，否则操作失返回它的后继，否则操作失败，败，next_e无定义

12、。无定义。 182.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）GetElem( L, i, &e ) （求线性表中某个数据元素）（求线性表中某个数据元素）初始条件：初始条件：线性表线性表L已存在。且已存在。且 1iListLength (L)。操作结果：操作结果：用用 e 返回返回L中第中第 i 个元素的值。个元素的值。 192.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）LocateElem( L, e, compare( ) )（定位函数）（定位函数）初始条件：初始条件：线性表线性表L已存在，已存在，e为给定值，为给定值， comp

13、are( )是元素判定函数。是元素判定函数。操作结果：操作结果：返回返回L中第中第1个个与与e满足关系满足关系compare( )的元素的位序。若这样的元素不存的元素的位序。若这样的元素不存在，则返回值为在，则返回值为0。 202.1 线性表的类型定义线性表的类型定义 引用型操作（引用型操作（查询查询）ListTraverse(L, visit( )（遍历线性表）（遍历线性表）初始条件：初始条件：线性表线性表L已存在，已存在，visit() 为某个访问为某个访问函数。函数。操作结果：操作结果：依次依次对对L的每个元素调用函数的每个元素调用函数visit( )。一旦一旦visit( )失败，则操

14、作失败。失败，则操作失败。 212.1 线性表的类型定义线性表的类型定义 加工型操作（加工型操作（修改修改）ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) 222.1 线性表的类型定义线性表的类型定义 加工型操作（加工型操作（修改修改）ClearList( &L )（线性表置空）（线性表置空）初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：将将L重置为空表。重置为空表。 232.1 线性表的类型定义线性表的类型定义 加工型操作（加工型操作（修改修改）PutElem

15、( &L, i, &e ) （改变数据元素的值）（改变数据元素的值）初始条件：初始条件：线性表线性表L已存在，且已存在，且 1iListLength (L) 。操作结果：操作结果： L中第中第i个元素赋值同个元素赋值同e的值。的值。 242.1 线性表的类型定义线性表的类型定义 加工型操作（加工型操作（修改修改） ListInsert( &L, i, e )（插入数据元素）（插入数据元素）初始条件：初始条件：线性表线性表L已存在，已存在， 且且 1iListLength (L)+1 。 操作结果：操作结果：在在L的第的第i个元素之前个元素之前插入新的元插入新的元素素e，L的长度增的长度增1。

16、252.1 线性表的类型定义线性表的类型定义 加工型操作（加工型操作（修改修改）ListDelete(&L, i, &e)（删除数据元素）（删除数据元素）初始条件：初始条件：线性表线性表L已存在且非空，已存在且非空， 1iLengthList(L) 。操作结果：操作结果：删除删除L的第的第i个元素，并用个元素，并用e返回其值，返回其值，L的长度减的长度减1。 262.1 线性表的类型定义线性表的类型定义 利用上述定义的利用上述定义的线性表线性表可以实现其它更复杂可以实现其它更复杂的操作的操作 事物可从简单演化为复杂，复杂中包含简单。事物可从简单演化为复杂，复杂中包含简单。例如，生物的多样性、社

17、会的自然性例如，生物的多样性、社会的自然性 哲学意义上哲学意义上万物发展的原动力万物发展的原动力：物质之间的：物质之间的相互作用相互作用 内因内因(内部元素之间的作用内部元素之间的作用)通过通过外因外因(外部数外部数据之间的作用据之间的作用)表现出来表现出来 272.1 线性表的类型定义线性表的类型定义例例 2-1 假设假设:有两个集合有两个集合 A 和和 B 分别用两个线分别用两个线性表性表 LA 和和 LB 表示，即：线性表中的数据元表示，即：线性表中的数据元素即为集合中的成员。现欲求一个新的集合素即为集合中的成员。现欲求一个新的集合AAB。上述问题可演绎为：上述问题可演绎为：要求对线性表

18、做如下操作：要求对线性表做如下操作： 扩大线性表扩大线性表 LA，将存在于线性表，将存在于线性表LB 中而中而不存在于线性表不存在于线性表 LA 中的数据元素插入到线性中的数据元素插入到线性表表 LA 中去。中去。 282.1 线性表的类型定义线性表的类型定义操作步骤：操作步骤：1从线性表从线性表LB中依次察看每个数据元素中依次察看每个数据元素;GetElem(LB, i, &e)2依值在线性表依值在线性表LA中进行查访中进行查访;LocateElem(LA, e, equal( )3若不存在，则插入之。若不存在，则插入之。ListInsert(&LA, n+1, e) 292.1 线性表的类

19、型定义线性表的类型定义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 (!LocateElem(La, e, equal( ) ) ListInsert(&La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 / union 302.

20、1 线性表的类型定义线性表的类型定义例例 2-2 已知一个非纯集合已知一个非纯集合 B，试构造一个纯集，试构造一个纯集合合 A，使，使 A中只包含中只包含 B 中所有值各不相中所有值各不相 同的数同的数据元素。据元素。仍选用线性表表示集合。仍选用线性表表示集合。 312.1 线性表的类型定义线性表的类型定义集合集合 B集合集合 A从集合从集合 B 取出物件放入集合取出物件放入集合 A要求集合要求集合A中中同样物件不能有两件以上同样物件不能有两件以上因此，因此，算法的策略应该和例算法的策略应该和例2-1相同相同 322.1 线性表的类型定义线性表的类型定义void union(List &La,

21、 List Lb) InitList(&La); / 构造构造(空的空的)线性表线性表LA 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, equal( ) ) ListInsert(&La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 / union 332.1 线性表的类型定义线性表

22、的类型定义试改变结构，以试改变结构，以有序表有序表表示集合。表示集合。若线性表中的数据元素相互之间可以比较，并且数据若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或或 aiai-1(i = 2,3, n) 则称该线性表为则称该线性表为有序表有序表(Ordered List)。 例如：例如： （2，3，3，5，6，6，6，8，12） 对集合对集合 B 而言，值相同的数据元素必定相邻；而言，值相同的数据元素必定相邻； 对集合对集合 A 而言，数据元素依值从小至大的顺序插入。而言，数据元素依值从小

23、至大的顺序插入。 数据结构改变了，解决问题的策略也相应要改变。数据结构改变了，解决问题的策略也相应要改变。 342.1 线性表的类型定义线性表的类型定义void purge(List &La, List Lb) InitList(&LA); La_len = ListLength(La); / 求线性表的长度求线性表的长度 Lb_len =ListLength(Lb); for (i = 1; i b时，时，c=b 362.1 线性表的类型定义线性表的类型定义void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表本算法将非递减的有序表

24、La 和和 Lb 归并为归并为 Lc InitList(&Lc); / 构造空的线性表构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) / La 和和 Lb 均非空均非空 while (i=La_len) / 若若 La 不空不空 while (j=Lb_len) / 若若 Lb 不空不空 / merge_list 372.1 线性表的类型定义线性表的类型定义 / La 和和 Lb 均非空均非空 / i = j = 1,

25、 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, bj); +j; 382.1 线性表的类型定义线性表的类型定义 while (i = La_len) / 当当La不空时不空时 GetElem(La, i+, &ai); ListInsert(&Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j

26、 = Lb_len) / 当当Lb不空时不空时 GetElem(Lb, j+, &bj); ListInsert(&Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素 392.2 线性表的顺序表示和实现线性表的顺序表示和实现 顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置之间某种关的存储位置之间某种关系表示逻辑关系系表示逻辑关系。 最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y 的存储位置和的存储位置和 x 的的存储位置相邻存储位置相邻。 用一组用一组地址连续地址连续的存储单元的存储单元依次存放依次存放线性表线性表中的数据元素中的数

27、据元素 402.2 线性表的顺序表示和实现线性表的顺序表示和实现 用一组用一组地址连续地址连续的存储单元的存储单元依次存放依次存放线性表线性表中的数据元素中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的称作线性表的基地址基地址 412.2 线性表的顺序表示和实现线性表的顺序表示和实现 以以“存储位置相邻存储位置相邻”表示有序对表示有序对 即：即： LOC(ai) = LOC(ai-1) + C 所有数据元素的存储位置均取决于第一个数所有数据元素的存储位置均取决于第一个数据元素的存储位置据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)

28、C一个数据元素所占存储量一个数据元素所占存储量基地址基地址 422.2 线性表的顺序表示和实现线性表的顺序表示和实现顺序映像的顺序映像的 C 语言描述语言描述#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量线性表存储空间的分配增量typedef struct ElemType *elem; / 存储空间基址存储空间基址 int length; / 当前长度当前长度 int listsize; / 当前分配的存储容量当前分配的存储容量 / (以以sizeof(

29、ElemType)为单位为单位 SqList; / 俗称俗称 顺序表顺序表 432.2 线性表的顺序表示和实现线性表的顺序表示和实现 线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i, &e) / 删除元素删除元素 442.2 线性表的顺序表示和实现线性表的顺序表示和实现Status InitList_Sq( SqList &L ) / 构造一个空的线性表构造一个空的线性

30、表 L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType) ); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE return OK; / InitList_Sq算法时间复杂度：算法时间复杂度：O(1) 452.2 线性表的顺序表示和实现线性表的顺序表示和实现例如：顺序表例如：顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可见，基本操

31、作是：可见，基本操作是：将顺序表中的元素逐将顺序表中的元素逐个和给定值个和给定值 e 相比较。相比较。 462.2 线性表的顺序表示和实现线性表的顺序表示和实现int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 i = 1; / i 的初值为第的初值为第 1 元素的位序元素的位序 p = L.elem; / p 的初值为第的初

32、值为第 1 元素的存储位置元素的存储位置 while (i = L.length & !(*compare)(*p+, e) i +; if (i = L.length) return i; else return 0; / LocateElem_Sq 算法的算法的时间复杂度时间复杂度为：为：O( ListLength(L) ) 472.2 线性表的顺序表示和实现线性表的顺序表示和实现 线性表操作线性表操作ListInsert(&L, i, e)的实现的实现 首先分析首先分析: 插入元素时，线性表的逻辑结构插入元素时，线性表的逻辑结构发生什么变化发生什么变化？ 482.2 线性表的顺序表示和实

33、现线性表的顺序表示和实现 (a1, , ai-1, ai, , an) 改变为改变为 (a1, , ai-1, e, ai, , an), a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的长度增加表的长度增加 492.2 线性表的顺序表示和实现线性表的顺序表示和实现 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表在顺序表L的第的第 i 个元素之前插入新的元素个元素之前插入新的元素e, / i 的合法范围为的合法范围为 1iL.length+1 q = &(L.elemi-1); / q 指示插入位置指示插

34、入位置 for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移 *q = e; / 插入插入e +L.length; / 表长增表长增1 return OK; / ListInsert_Sq 算法算法时间复杂度时间复杂度为为: O( ListLength(L) ) 502.2 线性表的顺序表示和实现线性表的顺序表示和实现11) 1(niiisinpE11) 1(11niisinnE 若假定在线性表中任何一个位置上进行若假定在线性表中任何一个位置上进行插入的概插入的概率率都是都是相等相等的，

35、则的，则移动元素的期望值移动元素的期望值为为：2n 假设在第假设在第 i 个元素之前插入的概率为个元素之前插入的概率为 ， 则在长度为则在长度为n 的线性表中的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：为：ip 512.2 线性表的顺序表示和实现线性表的顺序表示和实现if (i L.length+1) return ERROR; / 插入位置不合法插入位置不合法if (L.length = L.listsize) / 当前存储空间已满，增加分配当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.

36、listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败存储分配失败 L.elem = newbase; / 新基址新基址 L.listsize += LISTINCREMENT; / 增加存储容量增加存储容量 522.2 线性表的顺序表示和实现线性表的顺序表示和实现21 18 30 75 42 56 8721 18 30 75例如：例如：ListInsert_Sq(&L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置

37、指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p 532.2 线性表的顺序表示和实现线性表的顺序表示和实现 线性表操作线性表操作ListDelete(&L, i, &e)的实现的实现 首先分析首先分析: 删除元素时，线性表的逻辑结构删除元素时，线性表的逻辑结构发发生什么变化生什么变化？ 542.2 线性表的顺序表示和实现线性表的顺序表示和实现 (a1, , ai-1, ai, ai+1, , an) 改变为改变为 (a1, , ai-1, ai+1, , an)ai+1an, 表的长度减少表的长度减少a1 a2 ai-1

38、ai ai+1 ana1 a2 ai-1 552.2 线性表的顺序表示和实现线性表的顺序表示和实现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 (+p; p = q; +p) *(p-1) = *p; / 被删除元素

39、之后的元素左移被删除元素之后的元素左移 -L.length; / 表长减表长减1 return OK; / ListDelete_Sq 算法算法时间复杂度时间复杂度为为: O( ListLength(L) 562.2 线性表的顺序表示和实现线性表的顺序表示和实现考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第假设删除第 i 个元素的概率为个元素的概率为 , 则在长度为则在长度为n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元移动元素次数的期望值素次数的期望值为：为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除的若假定在线

40、性表中任何一个位置上进行删除的概率概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为：为： 572.2 线性表的顺序表示和实现线性表的顺序表示和实现21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; / p指向第一个结点，指向第一个结点，j为计数器为计数器 while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p 指向第指向第 i 个元素，或个元素，或 p 为空为空 if

41、 ( !p | ji ) return ERROR; / 第第 i 个元素不存在个元素不存在 e = p-data; / 取得第取得第 i 个元素个元素 return OK; / GetElem_L 算法算法时间复杂度时间复杂度为为: O(ListLength(L) 662.3 线性表的链式表示与实现线性表的链式表示与实现ai-1 线性表的操作线性表的操作 ListInsert_L(&L, i, e) 在单链表中的实现在单链表中的实现： 有序对有序对 a 改变为改变为 a , e 和和e, a eaiai-1 672.3 线性表的链式表示与实现线性表的链式表示与实现 可见，在链表中插入结点只需

42、要修改指针。可见，在链表中插入结点只需要修改指针。但同时，若要在第但同时，若要在第 i 个结点之前插入元素，个结点之前插入元素，修改的是第修改的是第 i-1 个结点的指针。个结点的指针。 因此，在单链表中第因此，在单链表中第 i 个结点之前进行插入个结点之前进行插入的基本操作为的基本操作为: 找到线性表中第找到线性表中第i-1个结点，然后修改其指向个结点，然后修改其指向后继的指针。后继的指针。 682.3 线性表的链式表示与实现线性表的链式表示与实现Status ListInsert_L(LinkList &L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法

43、为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e p = L; j = 0; while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点 if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 / LinstInsert_L 算法的算法的时间复杂度时间复杂度为为:O(ListLength(L) 692.3 线性表的链式表示与实现线性表的链式表示与实现s = (LinkList) malloc ( sizeof (LNode); / 生成新结点生成新结点s-d

44、ata = e; s-next = p-next; p-next = s; / 插入插入return OK; eai-1aiai-1sp 702.3 线性表的链式表示与实现线性表的链式表示与实现线性表的操作线性表的操作ListDelete _L(&L, i, &e)在链表在链表中的实现中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 712.3 线性表的链式表示与实现线性表的链式表示与实现Status ListDelete_L(LinkList &L, int i, ElemType &e) / 删除以删除以 L 为头指针为头指针(带头结点带头结点)的单链表中第的单链表

45、中第 i 个结点个结点 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; free(q); return OK; / ListDelete_L算法的算法的时间复杂度时间复杂度为为: O(ListLength(L) 722.3 线性表的链式表示与实现线性表的链式表示与实

46、现 在单链表中删除第在单链表中删除第 i 个结点的基本操作为个结点的基本操作为:找到线找到线性表中第性表中第i-1个结点，修改其指向后继的指针。个结点，修改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq 732.3 线性表的链式表示与实现线性表的链式表示与实现 如何得到单链表如何得到单链表? 链表是一个动态的结构，它不需要预先分配链表是一个动态的结构，它不需要预先分配空间，因此空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐逐个插入个插入” 的过程。的过程。 742.3 线性表的

47、链式表示与实现线性表的链式表示与实现例如：逆位序输入例如：逆位序输入 n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a1为止。为止。 752.3 线性表的链式表示与实现线性表的链式表示与实现void CreateList_L(LinkList &L, int n) / 逆序输入逆序输入 n 个数据

48、元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带头结点的单链表先建立一个带头结点的单链表 for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 输入一个元素值输入一个元素值 p-next = L-next; L-next = p; / 插入插入 / CreateList_L算法的算法的时间复杂度时间复杂度为为: O(Listlength(L) 762.3 线性

49、表的链式表示与实现线性表的链式表示与实现 最后一个结点的指针域的指针又指回第一个结的链表最后一个结点的指针域的指针又指回第一个结的链表 a1 a2 . an 循环链表循环链表 和单链表的差别仅在于，和单链表的差别仅在于，判别判别链表中最后一个链表中最后一个结点的结点的条件条件不再是不再是“后继是否为空后继是否为空”，而是，而是“后继后继是否为头结点是否为头结点”。 772.3 线性表的链式表示与实现线性表的链式表示与实现 双向链表双向链表typedef struct DuLNode ElemType data; / 数据域数据域 struct DuLNode *prior; / 指向前驱的指针

50、域指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域指向后继的指针域 DuLNode, *DuLinkList; 782.3 线性表的链式表示与实现线性表的链式表示与实现 双向链表的操作特点：双向链表的操作特点：“查询查询”和单链表相同。和单链表相同。“插入插入” 和和“删除删除”时需要同时修改两个方向上的时需要同时修改两个方向上的指针。指针。 792.3 线性表的链式表示与实现线性表的链式表示与实现双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an 802.3 线性表的链式表示与实现线性表的链式表示与实现ai-1删除删除aiai+1p-next

51、 = p-next-next;p-next-prior = p;pai-1 812.3 线性表的链式表示与实现线性表的链式表示与实现ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入 822.3 线性表的链式表示与实现线性表的链式表示与实现 用上述定义的单链表实现线性表的操作时，存在用上述定义的单链表实现线性表的操作时，存在以下以下问题问题：1.1.单链表的表长是一个隐含的值；单链表的表长是一个隐含的值；2.2.在单链表的最后一个元素之后插入元素时，需遍在单链表的最后一个元素之后插入元素时，

52、需遍历整个链表；历整个链表； 在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的“位置位置”概念加强。概念加强。 改进链表的设置：改进链表的设置：1.1.增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前位置的指针当前位置的指针” 三个数据域；三个数据域；2.2.将基本操作中的将基本操作中的“位序位序 i i ”改变为改变为“指针指针 p p ”。 832.3 线性表的链式表示与实现线性表的链式表示与实现 一个带头结点的线性链表类型一个带头结点的线性链表类型typedef struct LNode / 结点类型结点类型 ElemType data; struct LNode *next; *Link, *Position;typedef struct / 链表类型链表类型 Link head, tail; / 分别指向头结点和分别指向头结点和 / 最后一个结点的指针最后一个结点的指针 int len; / 指示链表长度指示链表长