数据结构课件2

1、线性表的概念线性表的概念 线性表:简称为表，是零个或多个元素的有穷序列，通常可以表示成a1，a2,，an（n1）。表中所含元素的个数称为表的长度。长度为零的表称为空表。 关系：线性关系（前趋后继）线性表线性表是一种最简单的线性结构线性结构 线性结构的线性结构的基本特征基本特征: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素”3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。线性结构线性结构 是一个数据元素的是一个数据元素的

2、有序（次序）集，有序（次序）集，),(21naaa2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象抽象数据类型线性表线性表的定义如下：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

3、 在线性表中的位序位序。 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT ADT List InitListInitList( &L )( &L )操作结果：操作结果：构造一个空的线性表构造一个空的线性表 L L。初始化操作初始化操作 结构销毁操作结构销毁操作DestroyListDestroyList( &L )( &L )初始条件：初始条件：操作结果：操作结果：线性表线性表 L L 已存在。已存在。销毁线性表销毁线性表 L L。ListEmptyListEmpty( L )( L )ListLengthList

4、Length( L )( L )PriorElemPriorElem( L, cur_e, &pre_e )( L, cur_e, &pre_e )NextElemNextElem( L, cur_e, &next_e )( L, cur_e, &next_e ) GetElemGetElem( L, i, &e )( L, i, &e )LocateElemLocateElem( L, e, compare( ) )( L, e, compare( ) )ListTraverse(LListTraverse(L, visit( ), visit( )引用型操作引用型操作( (不改变原线性表的

5、内容结构不改变原线性表的内容结构) ) ListEmptyListEmpty( L )( L )初始条件：操作结果：线性表 L L 已存在。若 L L 为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength( L )初始条件：操作结果：线性表 L 已存在。返回 L 中元素个数。（求线性表的长度） PriorElemPriorElem( L, cur_e, &pre_e )( L, cur_e, &pre_e )初始条件：操作结果：线性表 L 已存在。若 cur_e 是 L 的元素，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）NextEl

6、emNextElem( L, cur_e, &next_e )( L, cur_e, &next_e )初始条件：操作结果：线性表 L 已存在。若 cur_e 是 L 的元素，则用next_e 返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）GetElemGetElem( L, i, &e )( L, i, &e ) 初始条件： 操作结果：线性表 L L 已存在，用 e 返回L L中第 i 个元素的值。（求线性表中某个数据元素）且 1iLengthList(L)1iLengthList(L)LocateElemLocateElem( L, e, compare( ) )(

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

8、性表的内容结构，函数参数改变原线性表的内容结构，函数参数传递线性表时传递的是线性表的地址传递线性表时传递的是线性表的地址 &L) ClearListClearList( &L )( &L )PutElemPutElem( &L, i, &e )( &L, i, &e )ListInsertListInsert( &L, i, e )( &L, i, e )ListDelete(&LListDelete(&L, i, &e), i, &e) ClearListClearList( &L )( &L )初始条件：操作结果：线性表 L L 已存在。将 L L 重置为空表。（线性表置空）PutElem

9、PutElem( &L, i, &e )( &L, i, &e )初始条件：初始条件：操作结果：操作结果：线性表线性表 L L 已存在，已存在，L L 中第中第 i i 个元素赋值个元素赋值 e e 。（改变数据元素的值）（改变数据元素的值）且且 1iLengthList(L)1iLengthList(L) ListInsertListInsert( &L, i, e )( &L, i, e )初始条件：操作结果：线性表 L L 已存在，在 L L 的第 i i 个元素之前插入插入新的元素 e，L 的长度增1。（插入数据元素）且 1iLengthList(L)+11iLengthList(L)

10、+1ListDelete(&LListDelete(&L, i, &e), i, &e)初始条件：操作结果：线性表 L 已存在且非空，删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。（删除数据元素）1iLengthList(L)1iLengthList(L)利用上述定义的线性表类型线性表类型 可以实现其它更复杂的操作例例 2-22-2例例 2-12-1 假设假设: :有两个集合有两个集合 A A 和和 B B 分别用两个线性表分别用两个线性表 LA LA 和和 LB LB 表示，即：线性表中的数据元素即为表示，即：线性表中的数据元素即为集合中的成员。集合中的成员。 现要求一个新

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

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

13、 Lb_len; i+) /for / unionvoid union(List &La, List Lb) 则则 归并两个“其数据元素按值非递减有序排列”的有序表 LA LA 和 LBLB，求得有序表 LC LC 。设设 LaLa = (a1, , a ai i, , an), LbLb = (b1, , b bj j, , bm)， LcLc = (c1, , c ck k, , cm+n)且且已由(a1, , ai-1)和(b1, ,bj-1) )归并得归并得 (c1, , ck-1)jijjiikbabbaac例例 2-22-2k = 1, 2, , m+n1初始化 LC 为空表；基本

14、操作：2分别从 LA和LB中取得当前元素 ai 和 bj；3若 aibj，则将 ai 插入到 LC 中，否则将 bj 插入到 LC 中；4重复 2 和 3 两步，直至 LA 或 LB 中元素 被取完为止；5将 LA 表或 LB 表中剩余元素复制插入到 LC 表中。void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 若 La 不空while

15、(j=Lb_len) / 若 Lb 不空InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb); / 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, bj); +j; while (i =

16、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 表中剩余元素表中剩余元素最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y y 的存储位置和的存储位置和 x x 的存储位置相邻的存储位置相邻。顺序映象顺序映象 以以 x x 的存储位置和的存储位置和 y y 的存储位置之间某的存储位置之间某种关系

17、表示逻辑关系种关系表示逻辑关系 用一组地址连续的存储单元依次存放线性表中的用一组地址连续的存储单元依次存放线性表中的数据元素数据元素 a a1 1 a a2 2 a ai-1i-1 a ai i a an n线性表的起始地址，线性表的起始地址，称作线性表的基地址称作线性表的基地址以“存储位置相邻存储位置相邻”表示有序对a 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(aLOC(a1 1) ) + (i-1)

18、C 基地址基地址顺序映像的顺序映像的 C C 语言描述语言描述typedef structtypedef struct SqList SqList; / ; / 俗称俗称 顺序表顺序表ElemTypeElemType * *elemelem; / ; / 存储空间基址存储空间基址intint lengthlength; / ; / 当前长度当前长度intint listsizelistsize; / ; / 当前分配的存储容量当前分配的存储容量 线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&LInitList(&L) / ) / 结构初始化结构初始化Loc

19、ateElem(LLocateElem(L, e, compare() / , e, compare() / 查找查找ListInsert(&LListInsert(&L, i, e) / , i, e) / 插入元素插入元素ListDelete(&LListDelete(&L, i) / , i) / 删除元素删除元素Status Status InitList_Sq( SqList& L, int maxsizeInitList_Sq( SqList& L, int maxsize ) ) / InitList_Sq / InitList_Sq算法时间复杂度：算法时间复杂度：O(1)O(1

20、)L.elem = (Element L.elem = (Element * *)malloc(sizeof(maxsize)malloc(sizeof(maxsize););if (!L.elemif (!L.elem) exit(OVERFLOW);) exit(OVERFLOW);L.length = 0;L.length = 0;L.listsize = maxsizeL.listsize = maxsize; ;return OK;return OK;顺序表查找操作：在给定线性表中找元素顺序表查找操作：在给定线性表中找元素e e23 75 41 38 54 62 1723 75 41

21、 38 54 62 17L.elemL.elemL.length = 7L.length = 7L.listsizeL.listsizee =e =3838p pp pp pp pp pi i1 1 2 2 3 3 4 4 1 1 8 85050p p可见，基本操作是，将顺可见，基本操作是，将顺序表中的元素逐个和给定序表中的元素逐个和给定值值 e e 相比较。相比较。 int LocateElem_Sq(SqList L, ElemType int LocateElem_Sq(SqList L, ElemType e, e, Status ( Status (* *compare)(ElemT

22、ype, ElemTypecompare)(ElemType, ElemType) ) / LocateElem_Sq / LocateElem_Sq O( ListLength(L O( ListLength(L) ) )if (i = L.length) return i; if (i = L.length) return i; else return 0; else return 0; 算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i = 1; / i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elemp = L.elem; / p ; / p 的初值

23、为第的初值为第 1 1 元素的存储位置元素的存储位置while while (i = L.length & !(i = L.length & !(* *compare)(compare)(* *p+, e)p+, e) +i; +i;( (* *compare)(compare)(* *p+, e)p+, e)返回返回“真真”/找到满足条件的元素找到满足条件的元素线性表线性表操作操作 ListInsert(&LListInsert(&L, i, e), i, e)的实现：的实现：首先分析首先分析: :插入元素时，插入元素时，线性表的逻辑结构线性表的逻辑结构发生什么变化发生什么变化？ (a(a1

24、 1, , , a, ai-1i-1, a, ai i, , , a, an n) ) 改变为改变为a a1 1 a a2 2 a ai-1i-1 e a ai i a an na a, , 表的长度增加表的长度增加1 1(a(a1 1, , , , a ai-1i-1, e, a, e, ai i, , , a, an n) )a a1 1 a a2 2 a ai-1i-1 a ai i a an n StatusStatus ListInsert_Sq(SqList & &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为

25、1iL.length+1 / ListInsert_Sq 算法时间复杂度算法时间复杂度为为: :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;考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第假设在第 i i 个元素之前插入的概率个元素之前插入的概率 ， 则在长度为则在长度为n n 的线性表中的线性表中插入一个元素所需

26、移动元插入一个元素所需移动元素次数的期望值素次数的期望值为：为：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定在线性表中任何一个位置上进行若假定在线性表中任何一个位置上进行插入的概插入的概率率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为：为：if (L.length = L.listsizeif (L.length = L.listsize) ) return OVERFLOW; return OVERFLOW; / / 当前存储空间已满当前存储空间已满 if (i L.length+1) if (i L.length+1) return ER

27、ROR; return ERROR; / / 插入位置不合法插入位置不合法注意操作合理性检验：注意操作合理性检验：21 18 30 75 42 56 8721 18 30 75 42 56 87 21 18 30 75 21 18 30 75例如：例如：ListInsert_Sq(LListInsert_Sq(L, 5, 66), 5, 66) L.length-1L.length-10 0p pp pp pq q8787565642426666q = &(L.elemi-1); / q q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.

28、length-1); p = q; -p) for (p = &(L.elemL.length-1); p = q; -p) * *(p+1) = (p+1) = * *p;p;p p线性表操作线性表操作 ListDelete(&LListDelete(&L, i, &e), i, &e)的实现：的实现：首先分析：首先分析：删除元素时，删除元素时，线性表的逻辑结构发生什么变化？线性表的逻辑结构发生什么变化？ (a(a1 1, , , a, ai-1i-1, a, ai i, a, ai+1i+1, , , a, an n) ) 改变为改变为a ai+1i+1a an na, , a 表的长度减

29、少表的长度减少 a a1 1 a a2 2 a ai-1i-1 a ai i a ai+1 i+1 a an na a1 1 a a2 2 a ai-1i-1 (a(a1 1, , , , a ai-1i-1, a, ai+1i+1, , , a, an n) )Status ListDelete_Sq(SqList &L, int i, ElemTypeStatus ListDelete_Sq(SqList &L, int i, ElemType &e) &e) / ListDelete_Sq / ListDelete_Sqfor (+p; p = q; +p) for (+p; p = q

30、; +p) * *(p-1) = (p-1) = * *p; p; -L.length; / -L.length; / 表长减表长减1 1return OK;return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L O( ListLength(L)p = &(L.elemi-1); / p p = &(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置e = e = * *p; / p; / 被删除元素的值赋给被删除元素的值赋给 e eq = L.elem+L.length-1; / q = L.elem+L.length-1; / 表尾元素

31、的位置表尾元素的位置if (i L.length) return ERROR;if (i L.length) return ERROR; 元素左移元素左移考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：21 18 30 75 42 56 8721 18 30 75 42 56 8721 18 30 7521 18 30 7

32、5L.length-1L.length-10 0p pp pp pq q87875656p = &(L.elemi-1);p = &(L.elemi-1);q = L.elem+L.length-1;q = L.elem+L.length-1;for (+p; p = q; +p) for (+p; p next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (p & jnext; +j; while (p & jnext; +j; ifif ( ! !p | ji ) returnreturn ERROR; e = p-data; returnr

33、eturn OK;a ai-1i-1 线性表的操作 ListInsert(&L, i, e) 在单链表中的实现： 有序对有序对 a 改变为改变为 a , e 和和e, a e ea ai ia ai-1i-1 因此，在单链表中第因此，在单链表中第 i i 个结点之前进行插入的个结点之前进行插入的基本操作为基本操作为: : 找到线性表中第找到线性表中第i-1i-1个结点，然后修改其指向后个结点，然后修改其指向后继的指针。继的指针。 可见，在链表中插入结点只需要修改指针。但可见，在链表中插入结点只需要修改指针。但同时，若要在第同时，若要在第 i i 个结点之前插入元素，修改的个结点之前插入元素，修

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

35、结点ifif (! !p | | j i-1) returnreturn ERROR; / i i 大于表长或者小于大于表长或者小于1 1 s = (LinkList)malloc(sizeof(LNode);if ( s = NULL) return ERROR;s-data = e; s-next = p-next; p-next = s; / 插入return OK; eai-1aiai-1sp线性表的操作ListDeleteListDelete (&L, i, &e) (&L, i, &e)在链表中的实现:有序对有序对a 和和 a 改变为改变为 a a ai-1i-1a ai ia a

36、i+1i+1a ai-1i-1 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; delete(q);pq Status ListDelete_L(LinkList L, int i, ElemType Status ListDelete_L(LinkList L, int i, ElemType &e) &e) / / 删除以删除以 L L 为头指针为头指针( (带头结点带头结点) )的单链表中第的单链表中第 i i 个结点个结点 / Lis

37、tDelete_L / ListDelete_L算法的算法的时间复杂度时间复杂度为为: :O(ListLength(LO(ListLength(L)p = L; j = 0;p = L; j = 0;while (p-next & j next; +j; while (p-next & j next; +j; / / 寻找第寻找第 i i 个结点，并令个结点，并令 p p 指向其前趋指向其前趋q = p-next; p-next = q-next;q = p-next; p-next = q-next; / / 删除并释放结点删除并释放结点e = q-data; e = q-data; del

38、ete(q);delete(q);return OK;return OK;if (!(p-next) | j i-1) if (!(p-next) | j i-1) return ERROR; / return ERROR; / 删除位置不合理删除位置不合理操作操作 ClearList(&LClearList(&L) ) 在链表中的实现在链表中的实现: :void ClearList(&Lvoid ClearList(&L) ) / / 将单链表重新置为一个空表将单链表重新置为一个空表 while (L-next) while (L-next) p=L-next; L-next=p-next;

39、p=L-next; L-next=p-next; / ClearList / ClearListdelete(p);delete(p);算法算法时间复杂度时间复杂度：O(ListLength(LO(ListLength(L)链表是一个动态的结构，它不需要予分配空间，因链表是一个动态的结构，它不需要予分配空间，因此此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过的过程。程。例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素

40、二、输入数据元素a an n， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素a an-1n-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。void CreateList_L(LinkList &L, intvoid CreateList_L(LinkList &L, int n) n) / / 逆序输入逆序输入 n n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 / CreateList_L / CreateList_L算法的算法的时间复杂度时间复杂度为为: :O(Listle

41、ngth(LO(Listlength(L)L = (LinkList)malloc(sizeof(LNodeL = (LinkList)malloc(sizeof(LNode); L-next = NULL; ); L-next = NULL; / / 先建立一个带头结点的单链表先建立一个带头结点的单链表for (i = n; i 0; -i) for (i = n; i 0; -i) p = new LNode p = new LNode; ; scanf(&p scanf(&p-data); / -data); / 输入元素值输入元素值 p-next = L-next; L-next =

42、p; p-next = L-next; L-next = p; / / 插入插入 用上述定义的单链表实现线性表的操作时，存在的用上述定义的单链表实现线性表的操作时，存在的问题问题： 改进链表的设置：改进链表的设置：1 1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1 1增加增加“表长表长”、“表尾指针表尾指针” ” 、“当前位置的当前位置的 指针指针”和和“当前序号当前序号”四个数据域；四个数据域；2 2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3 3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概

43、念淡化，结点的 “ “位置位置”概念加强。概念加强。2 2将基本操作中的将基本操作中的“位序位序 i ”i ”改变为改变为“指针指针 p ”p ”。四、一个带头结点的线性链表类型四、一个带头结点的线性链表类型typedef struct LNodetypedef struct LNode / / 结点类型结点类型 ElemTypeElemType data; data; struct LNode struct LNode * *next;next; * *Link, Link, * *Position;Position;Status MakeNode( Link &p, ElemTypeSta

44、tus MakeNode( Link &p, ElemType e ); e ); / / 分配由分配由 p p 指向的值为指向的值为e e的结点，并返回的结点，并返回OKOK； / / 若分配失败，则返回若分配失败，则返回 ERRORERRORvoid FreeNodevoid FreeNode( Link &p ); ( Link &p ); / 释放释放 p p 所指结点所指结点typedef structtypedef struct / / 链表类型链表类型 Link head, tail;Link head, tail; / / 分别指向头结点和最后一个结点的指针分别指向头结点和最后

45、一个结点的指针 int lenint len; ; / / 指示链表长度指示链表长度 Link current;Link current; / / 指向当前被访问的结点指向当前被访问的结点 /的指针，初始位置指向头结点的指针，初始位置指向头结点 int curposint curpos; ; / / 指示当前指针位置指示当前指针位置, ,初值为初值为0 0 LinkListLinkList; ;链表的基本操作链表的基本操作: : 结构初始化和销毁结构结构初始化和销毁结构 StatusStatus InitList( LinkList & &L ); / 构造一个空的线性链表 L，其头指针、 /

46、 尾指针和当前指针均指向头结点， / 当前位置和表长为零。StatusStatus DestroyList( LinkList & &L ); / 销毁线性链表 L，L不再存在。 O(1) O(n) 引用型操作引用型操作 Status ListEmpty ( LinkListStatus ListEmpty ( LinkList L ); / L ); /判表空判表空int ListLength( LinkListint ListLength( LinkList L ); / L ); / 求表长求表长Status Prior( LinkListStatus Prior( LinkList L

47、 ); L ); / / 改变当前指针指向其前驱改变当前指针指向其前驱Status Next ( LinkListStatus Next ( LinkList L ); L ); / / 改变当前指针指向其后继改变当前指针指向其后继ElemType GetCurElem ( LinkListElemType GetCurElem ( LinkList L ); L ); / / 返回当前指针所指数据元素返回当前指针所指数据元素O(1)O(1)O(1)O(1)O(n)O(n)O(1)O(1)O(1)O(1) Status LocatePos( LinkList L, int Status Loc

48、atePos( LinkList L, int i ); i ); / / 改变当前指针指向第改变当前指针指向第i i个结点个结点Status LocateElem (LinkList L, ElemTypeStatus LocateElem (LinkList L, ElemType e, e, Status ( Status (* *compare)(ElemType, ElemTypecompare)(ElemType, ElemType);); / / 若存在与若存在与e e 满足函数满足函数compare( )compare( )判定关系的元判定关系的元 / / 素，则移动当前指针指

49、向第素，则移动当前指针指向第1 1个满足条件的个满足条件的 / / 元素的前驱，并返回元素的前驱，并返回OK; OK; 否则返回否则返回ERRORERRORStatus ListTraverse(LinkList L,StatusStatus ListTraverse(LinkList L,Status( (* *visit)();visit)(); / / 依次对依次对L L的每个元素调用函数的每个元素调用函数visit()visit()O(n)O(n)O(n)O(n)O(n)O(n) 加工型操作加工型操作 Status ClearList ( LinkListStatus ClearLis

50、t ( LinkList &L ); &L ); / / 重置重置 L L 为空表为空表Status SetCurElem(LinkList &L, ElemTypeStatus SetCurElem(LinkList &L, ElemType e ); e ); / / 更新当前指针所指数据元素更新当前指针所指数据元素Status Append ( LinkListStatus Append ( LinkList &L, Link s ); &L, Link s ); / / 在表尾结点之后链接一串结点在表尾结点之后链接一串结点Status InsAfter ( LinkList &L, E

51、lemtypeStatus InsAfter ( LinkList &L, Elemtype e ); e ); / / 将元素将元素 e e 插入在当前指针之后插入在当前指针之后Status DelAfter ( LinkList &L, ElemTypeStatus DelAfter ( LinkList &L, ElemType& e ); & e ); / / 删除当前指针之后的结点删除当前指针之后的结点 O(1) O(1)O(n)O(n) O(s) O(s) O(1) O(1) O(1) O(1)Status InsAfter( LinkList& L, ElemTypeStatus

52、 InsAfter( LinkList& L, ElemType e ) e ) / / 若当前指针在链表中，则将数据元素若当前指针在链表中，则将数据元素e e插入在线性链插入在线性链 / / 表表L L中当前指针所指结点之后中当前指针所指结点之后, ,并返回并返回OK;OK; / / 否则返回否则返回ERRORERROR。 / InsAfter / InsAfter if if ( ! L.current ) returnreturn ERROR; ifif (! MakeNode( s, e) ) return return ERROR; s-next = L.current-next;

53、L.current-next = s; L.length+; ifif (L.tail = L.current) L.tail = s; L.current = s; L.curpos+; returnreturn OK;Status DelAfter( LinkList& L, ElemTypeStatus DelAfter( LinkList& L, ElemType& e ) & e ) / / 若当前指针及其后继在链表中，则删除线性链表若当前指针及其后继在链表中，则删除线性链表L L中当前中当前 / / 指针所指结点之后的结点，并返回指针所指结点之后的结点，并返回OK; OK; 否则返

54、回否则返回ERRORERROR。 /DelAfter /DelAfterif ( !(L.current & L.current-next ) )if ( !(L.current & L.current-next ) ) return ERROR; return ERROR;q = L.current-next;q = L.current-next;L.current-next = q-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current;if (L.tail = q) L.tail = L.current;e=q-da

55、ta; L.length-;e=q-data; L.length-;FreeNode(qFreeNode(q); return OK;); return OK;Status ListInsert_L(LinkList L, int i, ElemTypeStatus ListInsert_L(LinkList L, int i, ElemType e) e) / / 在带头结点的单链线性表在带头结点的单链线性表 L L 的第的第 i i 个元素之前插入元素个元素之前插入元素 e e / ListInsert_L / ListInsert_L其它操作其它操作 if (!LocatePosif (

56、!LocatePos (L, i-1) return ERROR; (L, i-1) return ERROR; if (InsAfterif (InsAfter (L, e) return OK; (L, e) return OK; else return ERROR;else return ERROR;Status MergeList_L(LinkList &Lc, LinkListStatus MergeList_L(LinkList &Lc, LinkList &La, &La, LinkList &Lb LinkList &Lb ，int (int (* *compare)(Elem

57、Type,ElemTypecompare)(ElemType,ElemType) ) / / 归并有序表归并有序表 La La 和和 Lb Lb , ,生成新的有序表生成新的有序表 LcLc, , / / 并在归并之后销毁并在归并之后销毁La La 和和 Lb,Lb, / compare / compare 为指定的元素大小判定函数为指定的元素大小判定函数 / MergeList_L / MergeList_L例二例二if ( !InitList(Lc) return ERROR; / 存储空间分配失败while (!( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 Loc

58、atePos (La, 0); LocatePos (Lb, 0); / 当前指针指向头结点当前指针指向头结点if ( DelAfter( La, e) a = e; / 取得取得 La 表中第一个元素表中第一个元素 aelse a = MAXC; / MAXC为常量最大值if ( DelAfter( Lb, e) b = e; / 取得取得 Lb 表中第一个元素表中第一个元素 belse b = MAXC; / a 和和 b 为两表中当前比较元素为两表中当前比较元素DestroyList(La); DestroyList(Lb); / 销毁链表销毁链表 La 和和 Lbreturn OK;

59、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, e1) ) b = e1; else b = MAXC; 1. 1. 双向链表双向链表五、其它形式的链表五、其它形式的链表typedef struct DuLNodetypedef struct DuLNode ElemType ElemType data; data; struct DuLNodestruct DuL

60、Node * *prior;prior; struct DuLNodestruct DuLNode * *next;next; DuLNode, DuLNode, * *DuLinkListDuLinkList; ; 最后一个结点的指针域的指针又指回第一最后一个结点的指针域的指针又指回第一个结点的链表个结点的链表 a a1 1 a a2 2 . a . an n 2. 2. 循环链表循环链表 和单链表的差别仅在于，和单链表的差别仅在于，判别判别链表中最后一个结链表中最后一个结点的点的条件条件不再是不再是“后继是否为空后继是否为空”，而是，而是“后继是后继是否为头结点否为头结点”。约瑟夫问题约瑟