数据结构线性表

1、2021/8/141本章学习要点本章学习要点 1.1.了解线性表逻辑结构的特征了解线性表逻辑结构的特征; ; 2.2.重点掌握线性表的顺序存储结构和链式存储结构，重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如它们如何表达线性表中数据元素之间的结构关系；如何用何用C C语言描述它们的类型定义；语言描述它们的类型定义； 3.3.掌握在顺序存储结构下，线性表的基本操作的算掌握在顺序存储结构下，线性表的基本操作的算法；法； 4.4.掌握在链式存储结构下，线性表的基本操作算法；掌握在链式存储结构下，线性表的基本操作算法； 5.5.能够从时间复杂度的角度，比较线

2、性表两类存储能够从时间复杂度的角度，比较线性表两类存储结构不同特点及适用场合；结构不同特点及适用场合；第第2 2章章 线性表线性表2021/8/142线性结构的线性结构的基本特征基本特征为为: :线性结构线性结构是一个数据元素的是一个数据元素的有序（次序）集合。有序（次序）集合。1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。2021/8/1432.1 线性表的类型定义线性

3、表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象2021/8/1442.1 线性表的类型定义线性表的类型定义线性表线性表是是n n 个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，通常记作（通常记作（a a1 1, a, a2 2, a, a3 3, , ,a,an n ）。）。 姓名姓名 电话号码电话号码 蔡颖蔡颖 6321444463214444 陈红陈红 6321777763217777 刘建平刘建平 6321666663216666 王小林王小林 6321

4、888863218888 张力张力 6321555563215555 .例例1、数学中的数列（、数学中的数列（11，13，15，17，19，21）例例2、英文字母表（、英文字母表（A, B, C, D, E Z ）。）。例例3、某单位的电话号码簿。、某单位的电话号码簿。一、线性表的逻辑结构一、线性表的逻辑结构电话号码簿是数据元素电话号码簿是数据元素的有限序列，每一数据的有限序列，每一数据元素包括两个数据项，元素包括两个数据项，一个是用户姓名，一个一个是用户姓名，一个是对应的电话号码。是对应的电话号码。2021/8/145说明：说明：设A=（a1,a2,.,ai-1,ai,ai+1,an）是一线

5、性表，则 1 1、线性表的数据元素可以是各种各样的，但线性表的数据元素可以是各种各样的，但同一线同一线性表中性表中的元素必须是的元素必须是同一类型同一类型的；的；2 2、在表中在表中ai-1ai-1领先于领先于aiai，aiai领先于领先于ai+1ai+1，称，称ai-1ai-1是是aiai的的直接前趋直接前趋，ai+1ai+1是是aiai的的直接后继直接后继；3 3、在线性表中，除第一个元素和最后一个元素之外在线性表中，除第一个元素和最后一个元素之外，其他元素都，其他元素都有且仅有有且仅有一个一个直接前趋直接前趋，有且仅有一个，有且仅有一个直接直接后继后继。4 4、线性表中元素的个数线性表中

6、元素的个数n n称为线性表的称为线性表的长度长度，n=0n=0时时称为称为空表空表；5 5、aiai是线性表的第是线性表的第i i个元素，称个元素，称i i为数据元素为数据元素aiai的的位位序。序。2021/8/146二、线性表的抽象数据类型定义二、线性表的抽象数据类型定义：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作：基本操作：结构初始化操作结构初始化操作结构销毁操作结构销毁操作引用型操作引用型操作加工型操作加工型操作 ADT List2021/8/147 I

7、nitList( &L )操作结果：操作结果：构造一个空的线性表L。初始化操作 结构销毁操作DestroyList( &L )初始条件：初始条件：线性表 L 已存在。操作结果：操作结果：销毁线性表 L。2021/8/148引用型操作: ListEmpty( L )/ 线性表判空线性表判空初始条件：初始条件：线性表L已存在。操作结果：操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength( L ) /求线性表的长度求线性表的长度初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：返回返回L中元素个数。中元素个数。 PriorElem( L,

8、cur_e, &pre_e ) /求元素的前驱）求元素的前驱）初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：若若cur_e是是L的元素，但不是第一个，的元素，但不是第一个，则用则用pre_e 返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义。无定义。2021/8/149 NextElem( L, cur_e, &next_e ) /求元素的后继求元素的后继初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：若若cur_e是是L的元素，但不是最后一的元素，但不是最后一个，则用个，则用next_e 返回它的后继，否则

9、操作失败，返回它的后继，否则操作失败，next_e无定义。无定义。GetElem( L, i, &e ) /求线性表中某个数据元素求线性表中某个数据元素初始条件：初始条件：线性表线性表L存在且存在且1iLengthList(L)。操作结果：操作结果：用用 e 返回返回L中第中第 i 个元素的值。个元素的值。2021/8/1410LocateElem( L, e, compare( ) ) /定位函数定位函数初始条件：初始条件：表表L已存在，已存在，e为给定值，为给定值，compare( )是元素判定函数。是元素判定函数。操作结果：操作结果：返回返回L中第中第1个与个与e满足关系满足关系

10、compare( )的元素的位序。若这样的元素不存在，则返回值的元素的位序。若这样的元素不存在，则返回值为为0。 ListTraverse(L, visit( ) /遍历线性表遍历线性表初始条件：初始条件：线性表线性表L已存在，已存在，visit() 为某个访问为某个访问函数。函数。操作结果：操作结果：依次对依次对L的每个元素调用函数的每个元素调用函数visit( )。一旦一旦visit( )失败，则操作失败。失败，则操作失败。2021/8/1411ClearList( &L ) /线性表置空线性表置空初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：将将L重置为空

11、表。重置为空表。加工型操作 PutElem( &L, i, &e ) /改变数据元素的值改变数据元素的值初始条件：初始条件：表表L已存在，且已存在，且1iLengthList(L) 。操作结果：操作结果：L中第中第i个元素赋值同个元素赋值同e的值。的值。2021/8/1412 ListInsert( &L, i, e ) /插入数据元素插入数据元素初始条件：初始条件：线性表线性表L已存在，已存在， 且且 1iLengthList(L)+1 。操作结果：操作结果：在在L的第的第i个元素之前插入新的元素个元素之前插入新的元素e，L的长度增的长度增1。ListDelete(&

12、amp;L, i, &e) /删除数据元素删除数据元素初始条件：初始条件：线性表线性表L已存在且非空，已存在且非空， 1iLengthList(L) 。操作结果：操作结果：删除删除L的第的第i个元素，并用个元素，并用e返回其值，返回其值，L的长度减的长度减1。2021/8/1413用线性表的基本操作实现其它更复杂的操作实例用线性表的基本操作实现其它更复杂的操作实例例例 2-12-1假设有两个集合集合 A A 和和 B B 分别用两个线性表线性表 LA LA 和和 LB LB 表示，现要求一个新的集合现要求一个新的集合A AABAB。解题思路：解题思路：扩大线性表扩大线性表 LALA，将

13、存在于线性表，将存在于线性表LB LB 中而不存在于线性表中而不存在于线性表 LA LA 中的数据元素插中的数据元素插入到线性表入到线性表 LA LA 中去。以下是算法。中去。以下是算法。2021/8/1414 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 = Li

14、stLength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union2021/8/1415例例 2-22-2已知线性表已知线性表LALA和和LBLB中的元素按值非递减中的元素按值非递减有序，现要求将它们归并成一个新的线性表有序，现要求将它们归并成一个新的线性表LCLC，且且LCLC的元素也按值非递减有序。的元素也按值非递减有序。解题思路：解题思路：建立空线性表建立空线性表 LCLC，将，将LALA、LBLB表中的表中的元素逐个插入到元素逐个插入到LCLC中，插入规则为：在中，插入规

15、则为：在LALA、LB LB 中分别设立指针中分别设立指针i i、j j，比较，比较i,ji,j位置上的元素位置上的元素（设它们分别为（设它们分别为a,b)a,b)。则。则C C 继续往下比较继续往下比较 以下是算法。以下是算法。后移，时插入当后移，时插入当jbbaiaba2021/8/1416void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i

16、=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);代码见下页（代码见下页（1）代码见下页（代码见下页（2）代码见下页（代码见下页（3）2021/8/1417 / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(

17、Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素代码（代码（1）代码（代码（2）代码（代码（3）2021/8/1418例一和例二的算法时间复杂度分析：例一和例二的算法

18、时间复杂度分析：上述算法中基本操作上述算法中基本操作GetElemGetElem和和ListInstertListInstert的执行时间，它们与表长无关，的执行时间，它们与表长无关，LocateElemLocateElem与表与表长成正比。长成正比。所以例一的时间复杂度为：所以例一的时间复杂度为：O(ListLength(LA) ListLength(LB)例二的时间复杂度为：例二的时间复杂度为：O(ListLength(LA)+ ListLength(LB)2021/8/14192.2 线性表的实现线性表的实现 顺序映象顺序映象 用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的

19、数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址2021/8/1420以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素所占存储量 所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址2021/8/1421顺序映像的顺序映像的 C 语言描述语言描述typedef struct SqList; / 俗称俗称 顺序表顺序表#define LIST_

20、INIT_SIZE 80 / 线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量线性表存储空间的分配增量ElemType *elem; / 存储空间基址存储空间基址int length; / 当前长度当前长度int listsize; / 当前分配的存储容量当前分配的存储容量 (以以sizeof(ElemType)为单位为单位)2021/8/1422线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compar

21、e() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素2021/8/1423Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度： O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEre

22、turn OK;2021/8/1424顺序表中查找数据元素23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。2021/8/1425 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回

23、0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;2021/8/1426ListInsert(&L, i, e)的实现：分析分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变

24、化发生什么变化？2021/8/1427 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an), ea1 a2 ai-1 ai ana1 a2 ai-1 aian表的长度增加2021/8/1428 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq 算法时间复杂度算法时间复杂度为为: :O( ListLength(L) )q = &(L.elemi-

25、1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表长增1return OK; /此处可对参数进行合法性检测，见下张幻灯片此处可对参数进行合法性检测，见下张幻灯片2021/8/1429if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (E

26、lemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量/对参数进行检测对参数进行检测if (i L.length+1) return ERROR; /插入位置不合法插入位置不合法2021/8/1430考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：ip11) 1(niiisinpE11)

27、 1(11niisinnE2n 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：2021/8/143121 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p2021/8/1432操作ListDelete(&L, i, &e)的实现：

28、?删除元素时，线性表的逻辑结构发生什么变化？2021/8/1433 (a1, , ai-1, ai, ai+1, , an) 改变为改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 2021/8/1434Status ListDelete_Sq(SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移被删除元素之后的元素左移-L.length; / 表

29、长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置e = *p; / 被删除元素的值赋给被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 删除位置不合法删除位置不合法元素左移元素左移2021/8/1435考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第假设删除第 i 个元素的概率为个元素的概率为 , 则在长度则在长度为为n

30、的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素移动元素次数的期望值次数的期望值为：为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除若假定在线性表中任何一个位置上进行删除的的概率概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为：为：2021/8/143621 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p next = NULL; return OK;/ Ini

31、tList_L 线性表的初始化操作线性表的初始化操作InitList_L (LinkList &L) 功能：功能： 建立带头结点的空线性链表建立带头结点的空线性链表L L参数：参数： L L为线性链表的头指针为线性链表的头指针主要步骤：调用主要步骤：调用malloc()malloc()分配一结点的空间分配一结点的空间, ,并将其地址赋值给并将其地址赋值给L L；2021/8/1441三单链表操作的实现三单链表操作的实现GetElem(L, i, e) /取第取第i i个数据元素个数据元素ListInsert(&L, i, e) /插入数据元素插入数据元素ListDelete(&

32、amp;L, i, e) /删除数据元素删除数据元素ClearList(&L) /重置线性表为空表重置线性表为空表CreateList(&L, n) /创建含创建含n n个元素的链表个元素的链表2021/8/1442L1.单链表中GetElem(L, i, &e)的实现:211830754256pppj1 2 3 单链表是一种顺序存取的结构，要找单链表是一种顺序存取的结构，要找第第 i 个数据元个数据元素，必须先找到素，必须先找到第第 i-1 个数据元素，通过移动指针个数据元素，通过移动指针p，比较比较 j 和和 i，令指针，令指针 p 始终指向线性表中第始终指向线性表

33、中第 j 个数据个数据元素。元素。 2021/8/1443 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 个元素个元素 /

34、或或 p p 为空为空if ( !p | ji ) / 第第 i i 个元素不存在个元素不存在 return ERROR; e = p-data; / 取得第取得第 i i 个元素个元素return OK;2021/8/1444ai-1 2.单链表中ListInsert(&L, i, e)的实现：有序对有序对 a 改变为改变为 a , e 和和e, a eaiai-1由上图可见，在链表中插入结点只需要修改指针。由上图可见，在链表中插入结点只需要修改指针。若要在第若要在第 i 个结点之前插入元素，修改的是第个结点之前插入元素，修改的是第 i-1 个结点的指针。个结点的指针。基本操作基本操

35、作:找到线性表中第找到线性表中第i-1i-1个结个结点，然后修改其指向后继的指针。点，然后修改其指向后继的指针。2021/8/1445 Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)s = (LinkList) malloc ( sizeof (LNode); / / 生成新结点生成新结点s

36、-data = e; s-next = p-next; p-next = s; / 插入return OK;p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 i-1 个结点个结点if (!p | j i-1) return ERROR; / i / i 大于表长或者小于大于表长或者小于1 1 2021/8/14463.单链表中ListDelete (&L, i, &e)的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-12021/8/1447 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作

37、为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq2021/8/1448 Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以删除以 L L 为头指针为头指针( (带头结点带头结点) )的单链表中第的单链表中第 i i 个结点个结点 / ListDelete_L算法的算法的时间复杂度时间复杂度为: O(ListLength(L)p = L; j

38、 = 0;while (p-next & j next; +j; / / 寻找第寻找第 i i 个结点，并令个结点，并令 p p 指向其前趋指向其前趋if (!(p-next) | j i-1) return ERROR; / / 删除位置不合理删除位置不合理q = p-next; p-next = q-next; /删除并释放结点删除并释放结点e = q-data; free(q);return OK;2021/8/14494.单链表中ClearList(&L) 的实现:void ClearList(&L) / 将单链表重新置为一个空表 while (L-next)

39、p=L-next; L-next=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)2021/8/1450链表是一个动态的结构，链表是一个动态的结构，从线性表得到单链表从线性表得到单链表它不需要预分它不需要预分配空间，因此生成链表的过程是一个结点配空间，因此生成链表的过程是一个结点“逐个插入逐个插入” 的过程。的过程。例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，建立带头结点的单链个数据元素的值，建立带头结点的单链表。表。一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三

40、、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。ananan-12021/8/1451void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (L

41、inkList) malloc (sizeof (LNode); scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入2021/8/1452线性链表归并操作算法（直接对原链表进行操作）线性链表归并操作算法（直接对原链表进行操作）算法算法 2.12void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) /已知单链线性表La和Lb的元素按值非递减排列/归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列pa=La-next; pb=

42、Lb-next;Lc=pc=La; /用La的头结点作为Lc的头结点while(pa & pb)If (pa-datadata) 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的头结点/MergeList_L2021/8/1453四四 静态链表静态链表1. 1. 静态链表的概念静态链表的概念用一维数组来实现线性链表，用一维数组表示的线用一维数组来实现线性链表，用一维数组表示的线性链表，称为静态链表。性链表，称为静态链表。2. 2. 静态链

43、表的类型定义静态链表的类型定义SLinkList：数组的类型名；数组的类型名；SLinkList类型的数组变量是结构数组，每一数组分量包括两个类型的数组变量是结构数组，每一数组分量包括两个域：域：data用于存储线性表元素；用于存储线性表元素；cur用于存储直接后继元素在数用于存储直接后继元素在数组中的位置（下标）。组中的位置（下标）。#define MAXSIZE 1000 / 链链表的最大长度表的最大长度typedef struct ElemType data; int cur; component, SLinkListMAXSIZE;2021/8/1454静态链表图示静态链表图示0123

44、45678910 3 7 a4 0 5 a3 2 6 8 a1 9 10 a2 4 0 a a4 4a a3 3a a1 1a a2 2 0101010141020101010121014101610181020102210241026线性链表图示线性链表图示数组数组下标下标地址地址静态链表与静态链表与线性链表线性链表的区别？的区别？2021/8/1455012345678910 1ZHAO 2QIAN 3SUN 4LI 9ZHOU 6WU 7ZHENG 8WANG 0SHI 5012345678910 1ZHAO 2QIAN 3SUN 4LI 5ZHOU 6WU 7ZHENG 8WANG 0

45、 插入前3. 3. 静态链表插入操作图示静态链表插入操作图示在在LiLi后面后面插入插入SHISHI 插入后2021/8/1456012345678910 1ZHAO 2QIAN 4SUN 4LI 5 ZHOU 6WU 7ZHENG 8WANG 0012345678910 1ZHAO 2QIAN 3SUN 4LI 5ZHOU 6WU 7ZHENG 8WANG 0 删除前删除sun删除后4. 4. 静态链表删除插入操作图示静态链表删除插入操作图示2021/8/14575. 5. 静态链表的空间管理静态链表的空间管理初始化：void InitSpace_SL(Slinklist &spac

46、e) for(i=0;inext = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入若插入若P P定位在定位在i i的前驱上的前驱上2021/8/1464ai-1pxai插入操作算法插入操作算法（算法（算法2.18）Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)/在带头结点的双链循环线性表在带头结点的双链循环线性表L中第中第i个位置之前插入元素个位置之前插入元素e，1i表长表长+1 if(!p=GetElemP_DuL(L,i) /在在L中确定第中确定

47、第i个元素的位置指针个元素的位置指针p return ERROR; /p=NULL，即第，即第i个元素不存在个元素不存在 if (!(s=(DuLinkList)malloc(sizeof(DuLNode) /为新结点分配空间为新结点分配空间 return ERROR; s-data=e; s-prior=p-prior; p-prior-next=s; / 完成插入完成插入图示中的图示中的 s-next=p; p-prior=s; /完成插入完成插入图示中的图示中的 return OK;/LinstInsert_DuL 2021/8/1465ai-1删除若删除若P P定位在定位在i i的前驱

48、上的前驱上aiai+1p-next = p-next-next;p-next-prior = p;pai-12021/8/1466删除操作算法删除操作算法（算法（算法2.19）Status ListDelete_DuL(DuLinkList &L, int i, ElemType&e)/删除带头结点的双链循环线性表删除带头结点的双链循环线性表L的第的第i个元素，个元素，i的合法值为的合法值为1i表长表长if(!p=GetElemP_DuL(L,i) /在在L中确定第中确定第i个元素的位置指针个元素的位置指针p return ERROR; /p=NULL，第，第i个元素不存在个元

49、素不存在 e = p-data; p-prior-next=p-next; /完成删除完成删除图示中的图示中的 p-next-prior=p-prior; /完成删除完成删除图示中的图示中的 free(p); return OK;/LinstDelete_DuL aiai+1pai-12021/8/1467七一个带头结点的线性链表类型七一个带头结点的线性链表类型typedef struct LNode / 结点类型结点类型 ElemType data; struct LNode *next; *Link, *Position;Status MakeNode( Link &p, Elem

50、Type e ); / 分配由 p 指向的值为e的结点，并返回OK， / 若分配失败，则返回 ERRORvoid FreeNode( Link &p ); / 释放 p 所指结点2021/8/1468typedef struct / 链表类型链表类型 Link head, tail; / 分别指向头结点和 / 最后一个结点的指针 int len; / 指示链表长度 Link current; / 指向当前被访问的结点 /的指针，初始位置指向头结点 LinkList;2021/8/1469链表的基本操作链表的基本操作: : 结构初始化和销毁结构结构初始化和销毁结构 Status Init

51、List( LinkList &L ); / 构造一个空的线性链表 L，其头指针、 / 尾指针和当前指针均指向头结点， / 表长为零。Status DestroyList( LinkList &L ); / 销毁线性链表 L，L不再存在。 O(1) O(n)2021/8/1470 引用型操作引用型操作 Status ListEmpty ( LinkList L ); /判表空int ListLength( LinkList L ); / 求表长Status Prior( LinkList L ); / 改变当前指针指向其前驱Status Next ( LinkList L );

52、 / 改变当前指针指向其后继ElemType GetCurElem ( LinkList L ); / 返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1)2021/8/1471Status LocatePos( LinkList L, int i ); / 改变当前指针指向第i个结点Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType); / 若存在与e 满足函数compare( )判定关系的元素， / 则移动当前指针指向第1个满足条件的元素的 /前驱，并返回OK; 否则返回

53、ERRORStatus ListTraverse(LinkList L, Status(*visit)() ); / 依次对L的每个元素调用函数visit()O(n)O(n)O(n)2021/8/1472 加工型操作加工型操作Status ClearList ( LinkList &L ); / 重置 L 为空表Status SetCurElem(LinkList &L, ElemType e ); / 更新当前指针所指数据元素Status Append ( LinkList &L, Link s ); / 在表尾结点之后链接一串结点Status InsAfter (

54、LinkList &L, Elemtype e ); / 将元素 e 插入在当前指针之后Status DelAfter ( LinkList &L, ElemType& e ); / 删除当前指针之后的结点 O(1)O(n) O(s) O(1) O(1)2021/8/1473Status InsAfter( LinkList& L, ElemType e ) / 若当前指针在链表中，则将数据元素e插入在线性链 / 表L中当前指针所指结点之后,并返回OK; / 否则返回ERROR。 / InsAfter if ( ! L.current ) return ERRO

55、R; if (! MakeNode( s, e) ) return ERROR; s-next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;2021/8/1474Status DelAfter( LinkList& L, ElemType& e ) / 若当前指针及其后继在链表中，则删除线性链表L中当前 / 指针所指结点之后的结点，并返回OK; 否则返回ERROR。 /DelAfterif ( !(L.current &

56、; L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current;e=q-data; FreeNode(q);return OK;2021/8/1475例一例一Status ListInsert_L(LinkList L, int i, ElemType e) / 在带头结点的单链线性表在带头结点的单链线性表 L 的第的第 i 个元素之前插入元素个元素之前插入元素 e / ListInsert_L利用上述定义的线性链表如何完成线性表的其它

57、操作利用上述定义的线性链表如何完成线性表的其它操作 if (!LocatePos (L, i-1) return ERROR; / i 值不合法，第 i-1 个结点不存在if (InsAfter (L, e) return OK; / 完成插入else return ERROR;2021/8/1476Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ，int (*compare) (ElemType,ElemType) / 归并有序表 La 和 Lb ,生成新的有序表 Lc, / 并在归并之后销毁La

58、 和 Lb, / compare 为指定的元素大小判定函数 / MergeList_L例二例二2021/8/1477if ( !InitList(Lc) return ERROR; / 存储空间分配失败while (!( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 LocatePos (La, 0); LocatePos (Lb, 0); / 当前指针指向头结点当前指针指向头结点if ( DelAfter( La, e) a = e; / 取得取得 La 表中第一个元素表中第一个元素 aelse a = MAXC; / MAXC为常量最大值if ( DelAfte

59、r( Lb, e) b = e; / 取得取得 Lb 表中第一个元素表中第一个元素 belse b = MAXC; / a 和和 b 为两表中当前比较元素为两表中当前比较元素DestroyList(La); DestroyList(Lb); / 销毁链表销毁链表 La 和和 Lbreturn OK;2021/8/1478 if (*compare)(a, b) =0) / ab InsAfter(Lc, a); if ( DelAfter( La, e1) ) a = e1; else a = MAXC; else / ab InsAfter(Lc, b); if ( DelAfter( Lb

60、, e1) ) b = e1; else b = MAXC; 2021/8/14792.4 一元多项式的表示一元多项式的表示nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？2021/8/1480 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：其中：pi 是指数为ei 的项的非零系数， 0 e

61、1 e2 em = n可以下列线性表表示：（p1, e1）, (p2, e2), , (pm,em) ）例如例如: P999(x) = 7x3 - 2x12 - 8x999可用线性表( (7, 3), (-2, 12), (-8, 999)表示2021/8/1481ADT Polynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值中的指数值a