线性表是一种最简单的线性结构 线性结构的基本特征为: 线性结构 是 一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素”；

Presentation on theme: "线性表是一种最简单的线性结构 线性结构的基本特征为: 线性结构 是 一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素”；"— Presentation transcript:

1 线性表是一种最简单的线性结构 线性结构的基本特征为: 线性结构 是 一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。

2 2.1 线性表的类型定义 2.2 线性表类型的实现  顺序映象 2.3 线性表类型的实现  链式映象 2.4 一元多项式的表示

3 2.1 线性表的类型定义

4 抽象数据类型线性表的定义如下： 数据关系： ADT List {
数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } {设线性表为 (a1，a2, ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。}

5 基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 } ADT List

6 初始化操作 InitList( &L ) 操作结果： 构造一个空的线性表L。

7 结构销毁操作 DestroyList( &L ) 初始条件： 操作结果： 线性表 L 已存在。 销毁线性表 L。

8 引用型操作: 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( ))

9 ListEmpty( L ) （线性表判空） 初始条件： 操作结果： 线性表L已存在。 若L为空表，则返回 TRUE，否则FALSE。

10 ListLength( L ) （求线性表的长度） 初始条件： 操作结果： 线性表L已存在。 返回L中元素个数。

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

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

13 GetElem( L, i, &e ) 操作结果： （求线性表中某个数据元素） 线性表L已存在， 且 1≤i≤LengthList(L)。
初始条件： 操作结果： 线性表L已存在， 且 1≤i≤LengthList(L)。 用 e 返回L中第 i 个元素的值。

14 LocateElem( L, e, compare( ) )
（定位函数） 初始条件： 操作结果： 线性表L已存在，e为给定值， compare( )是元素判定函数。 返回L中第1个与e满足关系 compare( )的元素的位序。 若这样的元素不存在， 则返回值为0。

15 初始条件： 操作结果： （遍历线性表） 线性表L已存在， Visit() 为某个访问函数。 依次对L的每个元素调用
ListTraverse(L, visit( )) （遍历线性表） 初始条件： 操作结果： 线性表L已存在， Visit() 为某个访问函数。 依次对L的每个元素调用 函数visit( )。一旦visit( )失败，则操作失败。

16 加工型操作 ClearList( &L ) PutElem( &L, i, &e ) ListInsert( &L, i, e )
ListDelete(&L, i, &e)

17 ClearList( &L ) （线性表置空） 初始条件： 操作结果： 线性表L已存在。 将L重置为空表。

18 PutElem( &L, i, &e ) 初始条件： 操作结果： （改变数据元素的值） 线性表L已存在，
且 1≤i≤LengthList(L) 。 L中第i个元素赋值同e的值。

19 操作结果： （插入数据元素） 初始条件： 线性表L已存在， 且 1≤i≤LengthList(L)+1 。 在L的第i个元素之前插入
ListInsert( &L, i, e ) （插入数据元素） 初始条件： 操作结果： 线性表L已存在， 且 1≤i≤LengthList(L)+1 。 在L的第i个元素之前插入 新的元素e，L的长度增1。

20 ListDelete(&L, i, &e) 初始条件： 操作结果： （删除数据元素） 线性表L已存在且非空，
1≤i≤LengthList(L) 。 删除L的第i个元素，并用e返回其值，L的长度减1。

21 利用上述定义的线性表 可以实现其它更复杂的操作 例 2-1 例 2-2 例 2-3

22 例 2-1 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合A＝A∪B。

23 上述问题可演绎为： 要求对线性表作如下操作：
扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。

24 操作步骤： 1．从线性表LB中依次察看每个数据元素; GetElem(LB, i)→e 2．依值在线性表LA中进行查访;
LocateElem(LA, e, equal( )) 3．若不存在，则插入之。 ListInsert(LA, n+1, e)

25 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

26 例 2-2 已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。 仍选用线性表表示集合。

27 集合 B 集合 A 从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上 因此，算法的策略应该和例2-1相同

28 void union(List &La, List Lb) {
La_len=ListLength(La); Lb_len=ListLength(Lb); } // union InitList(La); // 构造(空的)线性表LA 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 相同的数据元素，则插入之

29 试改变结构，以有序表表示集合。 若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 ai≥ai-1 或 ai≤ai-1(i = 2,3,…, n)，则称该线性表为有序表(Ordered List)。

30 例如： （2，3，3，5，6，6，6，8，12） 对集合 B 而言， 值相同的数据元素必定相邻； 对集合 A 而言， 数据元素依值从小至大的顺序插入。 因此，数据结构改变了， 解决问题的策略也相应要改变。

31 void purge(List &La, List Lb) {
InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i++) { } } // purge GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给 e if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } // La中不存在和 e 相同的数据元素，则插入之

32

33 // 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; }

34 } // merge_list void MergeList(List La, List Lb, List &Lc) {
// 本算法将非递减的有序表 La 和 Lb 归并为 Lc } // merge_list 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 不空

35 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 表中剩余元素

36 2.2 线性表类型 的实现----顺序映象

37 顺序映象 —— 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系<x,y>。 最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。

38 用一组地址连续的存储单元 依次存放线性表中的数据元素 a1 a2 … ai-1 ai … an 线性表的起始地址 称作线性表的基地址

39 以“存储位置相邻”表示有序对<ai-1，ai> 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量↑
所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址

40 ElemType *elem; // 存储空间基址
顺序映像的 C 语言描述 #define LIST_INIT_SIZE // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { } SqList; // 俗称 顺序表 ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位)

41 线性表的基本操作在顺序表中的实现 InitList(&L) // 结构初始化 LocateElem(L, e, compare()) // 查找 ListInsert(&L, i, e) // 插入元素 ListDelete(&L, i) // 删除元素

42 O(1) Status InitList_Sq( SqList& L ) { // 构造一个空的线性表
L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType)); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE return OK; 算法时间复杂度： O(1)

43 e = 例如：顺序表 23 75 41 38 54 62 17 p p p p p p 可见，基本操作是： 将顺序表中的元素
L.listsize L.elem L.length p p p p p p 可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。 i 8 1 4 1 2 3 e = 38 50

44 // 在顺序表中查询第一个满足判定条件的数据元素，
int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { // 在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回 0 } // LocateElem_Sq i = 1; // i 的初值为第 1 元素的位序 p = L.elem; // p 的初值为第 1 元素的存储位置 while (i <= L.length && !(*compare)(*p++, e)) ++i; (*compare)(*p++, e) if (i <= L.length) return i; else return 0; 算法的时间复杂度为： O( ListLength(L) )

45 ListInsert(&L, i, e)的实现：
线性表操作 ListInsert(&L, i, e)的实现： 首先分析: 插入元素时， 线性表的逻辑结构发生什么变化？

46 … an a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai e
(a1, …, ai-1, e, ai, …, an) <ai-1, ai> <ai-1, e>, <e, ai> a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai … an e 表的长度增加

47 算法时间复杂度为: O( ListLength(L) ) …… // 在顺序表L的第 i 个元素之前插入新的元素e,
Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1 } // ListInsert_Sq …… q = &(L.elem[i-1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入e ++L.length; // 表长增1 return OK; 元素右移 算法时间复杂度为: O( ListLength(L) )

48 考虑移动元素的平均情况: 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：
若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：

49 if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法
if (L.length >= L.listsize) { // 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) exit(OVERFLOW); // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 }

50 例如：ListInsert_Sq(L, 5, 66) q = &(L.elem[i-1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; p q p p p L.length-1 66 42 56 87

51 ListDelete(&L, i, &e)的实现：
线性表操作 ListDelete(&L, i, &e)的实现： 首先分析： 删除元素时， 线性表的逻辑结构发生什么变化？

52 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an
<ai-1, ai>, <ai, ai+1> <ai-1, ai+1> a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an 表的长度减少

53 算法时间复杂度为: Status ListDelete_Sq (SqList &L, int i, ElemType &e) {
if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法 p = &(L.elem[i-1]); // p 为被删除元素的位置 e = *p; // 被删除元素的值赋给 e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; // 表长减1 return OK; 元素左移 算法时间复杂度为: O( ListLength(L))

54 考虑移动元素的平均情况: 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：
若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：

55 例如：ListDelete_Sq(L, 5, e)
p = &(L.elem[i-1]); q = L.elem+L.length-1; for (++p; p <= q; ++p) *(p-1) = *p; q p p p p L.length-1 56 87

56 2.3 线性表类型 的实现---链式映象

57 一、单链表 二、结点和单链表的 C 语言描述 三、线性表的操作在单链表中的实现 四、一个带头结点的单链表类型 五、其它形式的链表 六、有序表类型

58 用一组地址任意的存储单元存放线性表中的数据元素。
一、单链表 用一组地址任意的存储单元存放线性表中的数据元素。 以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象) 以“结点的序列”表示线性表  称作链表

59 a1 a2 … ... an ^ 头指针 头指针 空指针  以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。
线性表为空表时， 头结点的指针域为空 头指针 空指针 头结点 a a … an ^  以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。

60 LinkList L； // L 为单链表的头指针
二、结点和单链表的 C 语言描述 Typedef struct LNode { ElemType data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; LinkList L； // L 为单链表的头指针

61 三、单链表操作的实现 GetElem(L, i, e) // 取第i个数据元素 ListInsert(&L, i, e) // 插入数据元素
ListDelete(&L, i, e) // 删除数据元素 ClearList(&L) // 重置线性表为空表 CreateList(&L, n) // 生成含 n 个数据元素的链表

62 线性表的操作 GetElem(L, i, &e) 在单链表中的实现: L 21 18 30 75 42 56 ∧ p p p j 3 2 1

63 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 I 。
单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 I 。 令指针 p 始终指向线性表中第 j 个数据元素。

64 while (p && j<i) { p = p->next; ++j; }
Status GetElem_L(LinkList L, int i, ElemType &e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L p = L->next; j = 1; // p指向第一个结点，j为计数器 while (p && j<i) { p = p->next; ++j; } // 顺指针向后查找，直到 p 指向第 i 个元素 // 或 p 为空 if ( !p || j>i ) return ERROR; // 第 i 个元素不存在 e = p->data; // 取得第 i 个元素 return OK; 算法时间复杂度为: O(ListLength(L))

65 线性表的操作 ListInsert(&L, i, e)
在单链表中的实现： 有序对 <ai-1, ai> 改变为 <ai-1, e> 和<e, ai> ai-1 ai-1 ai e

66 可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。

67 …… O(ListLength(L)) 算法的时间复杂度为:
Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L p = L; j = 0; while (p && j < i-1) { p = p->next; ++j; } // 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; // i 大于表长或者小于1 …… O(ListLength(L)) 算法的时间复杂度为:

68 s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s->data = e;
s->next = p->next; p->next = s; // 插入 return OK; p ai-1 ai-1 ai e s

69 线性表的操作ListDelete (&L, i, &e)在链表中的实现:
有序对<ai-1, ai> 和 <ai, ai+1> 改变为 <ai-1, ai+1> ai-1 ai-1 ai ai+1

70 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。
q = p->next; p->next = q->next; e = q->data; free(q); p q ai-1 ai-1 ai ai+1

71 算法的时间复杂度为: O(ListLength(L))
Status ListDelete_L(LinkList L, int i, ElemType &e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete_L p = L; j = 0; while (p->next && j < i-1) { p = p->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; 算法的时间复杂度为: O(ListLength(L))

72 操作 ClearList(&L) 在链表中的实现:
void ClearList(&L) { // 将单链表重新置为一个空表 while (L->next) { p=L->next; L->next=p->next; } } // ClearList free(p); 算法时间复杂度： O(ListLength(L))

73 如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。

74 操作步骤： 例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。 一、建立一个“空表”； 二、输入数据元素an， 建立结点并插入；

75 O(Listlength(L)) void CreateList_L(LinkList &L, int n) {
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; // 插入 } O(Listlength(L)) 算法的时间复杂度为:

76 回顾 2.1 节中三个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？

77 例2-1 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); if (!LocateElem(La, e, equal( )) ListInsert(La, ++La_len, e); }//for } // union 例2-1 算法时间复杂度 控制结构： 基本操作： for 循环 GetElem, LocateElem 和 ListInsert 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)×ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)×ListLength(Lb) )

78 例2-2 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e);
void purge(List &La, List Lb) { InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } }//for } // purge 例2-2 算法时间复杂度 控制结构： 基本操作： for 循环 GetElem 和 ListInsert 当以链式映像实现抽象数据类型线性表时为: O( ListLength2(Lb) ) 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(Lb) )

79 例2-3 算法时间复杂度 控制结构： 基本操作： 三个并列的while循环 GetElem, ListInsert
void 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)) { GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListInsert(Lc, ++k, bj); ++j; } } … … 例2-3 算法时间复杂度 控制结构： 基本操作： 三个并列的while循环 GetElem, ListInsert 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)+ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength 2(La)+ListLength 2(Lb) )

80 用上述定义的单链表实现线性表的操作时， 存在的问题： 1．单链表的表长是一个隐含的值； 2．在单链表的最后一个元素之后插入元素时， 需遍历整个链表； 3．在链表中，元素的“位序”概念淡化，结点的 “位置”概念加强。 改进链表的设置： 1．增加“表长”、“表尾指针” 和 “当前位置的 指针” 三个数据域； 2．将基本操作中的“位序 i ”改变为“指针 p ”。

81 四、一个带头结点的线性链表类型 typedef struct LNode { // 结点类型 ElemType data;
struct LNode *next; } *Link, *Position; Status MakeNode( Link &p, ElemType e ); // 分配由 p 指向的值为e的结点，并返回OK， // 若分配失败，则返回 ERROR void FreeNode( Link &p ); // 释放 p 所指结点

82 typedef struct { // 链表类型 Link head, tail; // 分别指向头结点和
// 最后一个结点的指针 int len; // 指示链表长度 Link current; // 指向当前被访问的结点 //的指针，初始位置指向头结点 } LinkList;

83 链表的基本操作: {结构初始化和销毁结构} Status InitList( LinkList &L );
// 尾指针和当前指针均指向头结点， // 表长为零。 O(1) Status DestroyList( LinkList &L ); // 销毁线性链表 L，L不再存在。 O(n)

84 {引用型操作} Status ListEmpty ( LinkList L ); //判表空
O(1) int ListLength( LinkList L ); // 求表长 O(1) Status Prior( LinkList L ); // 改变当前指针指向其前驱 O(n) Status Next ( LinkList L ); // 改变当前指针指向其后继 O(1) ElemType GetCurElem ( LinkList L ); // 返回当前指针所指数据元素 O(1)

85 Status LocatePos( LinkList L, int i );
O(n) Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType)); // 若存在与e 满足函数compare( )判定关系的元 // 素，则移动当前指针指向第1个满足条件的 // 元素的前驱，并返回OK; 否则返回ERROR O(n) Status ListTraverse(LinkList L, Status(*visit)() ); // 依次对L的每个元素调用函数visit() O(n)

86 Status ClearList ( LinkList &L ); // 重置 L 为空表
{加工型操作} Status ClearList ( LinkList &L ); // 重置 L 为空表 O(n) Status SetCurElem(LinkList &L, ElemType e ); // 更新当前指针所指数据元素 O(1) Status Append ( LinkList &L, Link s ); // 在表尾结点之后链接一串结点 O(s) Status InsAfter ( LinkList &L, Elemtype e ); // 将元素 e 插入在当前指针之后 O(1) Status DelAfter ( LinkList &L, ElemType& e ); // 删除当前指针之后的结点 O(1)

87 Status InsAfter( LinkList& L, ElemType e ) {
// 表L中当前指针所指结点之后,并返回OK; // 否则返回ERROR。 } // InsAfter if ( ! L.current ) return ERROR; 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;

88 // 若当前指针及其后继在链表中，则删除线性链表L中当前
Status DelAfter( LinkList& L, ElemType& e ) { // 若当前指针及其后继在链表中，则删除线性链表L中当前 // 指针所指结点之后的结点，并返回OK; 否则返回ERROR。 } //DelAfter if ( !(L.current && 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;

89 利用上述定义的线性链表如何完成 线性表的其它操作 ？
利用上述定义的线性链表如何完成 线性表的其它操作 ？ 例一 Status ListInsert_L(LinkList L, int i, ElemType e) { // 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e } // ListInsert_L if (!LocatePos (L, i-1)) return ERROR; // i 值不合法，第 i-1 个结点不存在 if (InsAfter (L, e)) return OK; // 完成插入 else return ERROR;

90 Status MergeList_L(LinkList &Lc, LinkList &La,
例二 Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ，int (*compare) (ElemType,ElemType))) { // 归并有序表 La 和 Lb ,生成新的有序表 Lc, // 并在归并之后销毁La 和 Lb, // compare 为指定的元素大小判定函数 …… } // MergeList_L

91 if ( !InitList(Lc)) return ERROR; // 存储空间分配失败
LocatePos (La, 0); LocatePos (Lb, 0); // 当前指针指向头结点 if ( DelAfter( La, e)) a = e; // 取得 La 表中第一个元素 a else a = MAXC; // MAXC为常量最大值 if ( DelAfter( Lb, e)) b = e; // 取得 Lb 表中第一个元素 b else b = MAXC; // a 和 b 为两表中当前比较元素 while (!( a=MAXC && b=MAXC)) { // La 或 Lb 非空 } … … DestroyList(La); DestroyList(Lb); // 销毁链表 La 和 Lb return OK;

92 if ((*compare)(a, b) <=0) { // a≤b
InsAfter(Lc, a); if ( DelAfter( La, e1) ) a = e1; else a = MAXC; } else { // a＞b InsAfter(Lc, b); if ( DelAfter( Lb, e1) ) b = e1; else b = MAXC; }

93 五、其它形式的链表 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next;
1. 双向链表 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList;

94 2. 循环链表 a1 a2 … ... an 最后一个结点的指针域的指针又指回第一个结点的链表
和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

95 双向循环链表 空表 非空表 a a2 … an

96 双向链表的操作特点： “查询” 和单链表相同。 “插入” 和“删除”时需要同时修改两个方向上的指针。

97 插入 p ai-1 ai-1 ai ai e s s->next = p->next; p->next = s; s->next->prior = s; s->prior = p;

98 删除 ai-1 ai-1 ai ai+1 p p->next = p->next->next; p->next->prior = p;

99 六、有序表类型 ADT Ordered_List { i=1,2,…,n, n≥0 } xi-1≤ xi, i=2,3,…,n }
集合中 任意两个 元素之间 均可以 进行比较 回顾例2-2的两个算法 ADT Ordered_List { 数据对象: S = { xi|xi  OrderedSet ， i=1,2,…,n, n≥0 } 数据关系:R = {<xi-1, xi> | xi-1, xi  S, xi-1≤ xi, i=2,3,…,n }

100 … … int(*compare)(ElemType,ElemType) ) 初始条件：有序表L已存在。
基本操作： Compare是一个有序判定函数 … … LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) ) 初始条件：有序表L已存在。 操作结果：若有序表L中存在元素e，则 q指示L中第一个值为 e 的元素的位置，并返回函数值TRUE；否则 q 指示第一个大于 e 的元素的前驱的位置，并返回函数值FALSE。

101 例如: ( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 ) 若 e = 45, 则 q 指向 若 e = 88, 则 q 指向 表示值为 88 的元素应插入在该指针所指结点之后。

102 算法时间复杂度：O(n2) void union(List &La, List Lb) {// 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 算法时间复杂度：O(n2)

103 算法时间复杂度：O(n) void purge(List &La, List Lb) { // Lb为有序表
InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i++) { } } // purge GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给 e if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } // La中不存在和 e 相同的数据元素，则插入之 算法时间复杂度：O(n)

104 2.4 一元多项式的表示

105 的多项式，上述表示方法是否合适？ 一元多项式 P = (p0, p1, …，pn) S(x) = 1 + 3x10000 – 2x20000
在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 但是对于形如 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？

106 （（p1, e1）, (p2, e2), ┄, (pm,em) ） Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem
一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 < e2 < ┄ < em = n 可以下列线性表表示： （（p1, e1）, (p2, e2), ┄, (pm,em) ）

107 例如: 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示
P999(x) = 7x3 - 2x12 - 8x999 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示

108 抽象数据类型一元多项式的定义如下： ADT Polynomial { 数据对象：
数据关系： D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 }

109 基本操作： DestroyPolyn ( &P ) PrintPolyn ( &P ) 操作结果：输入 m 项的系数和指数，
CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。

110 SubtractPolyn ( &Pa, &Pb ) … … } ADT Polynomial
PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) … … } ADT Polynomial 初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。 初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。

111 一元多项式的实现： 结点的数据元素类型定义为: typedef OrderedLinkList polynomial;
// 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType;

112 Status CreatPolyn ( polynomail &P, int m ) {
// 输入m项的系数和指数，建立表示一元多项式的有序链表P } // CreatPolyn InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); // 设置头结点的数据元素 for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项 } return OK; scanf (e.coef, e.expn); if (!LocateElem ( P, e, (*cmp)()) ) if ( !InsAfter ( P, e ) ) return ERROR; 注意: 1.输入次序不限; 2.指数相同的项只能输入一次。

113 // 利用两个多项式的结点构成“和多项式” Pc = Pa＋Pb … …
Status AddPolyn ( polynomial &Pc, polynomial &Pa, polynomial &Pb) { // 利用两个多项式的结点构成“和多项式” Pc = Pa＋Pb … … if (DelAfter(Pa, e1)) a=e1.expn else a=MAXE; if (DelAfter(Pb, e2)) b=e2.expn else b=MAXE; while (!(a=MAXE && b=MAXE)) { } } // AddPolyn

114 switch (*cmp(e1, e2)) { case -1: { // 多项式PA中当前结点的指数值小 … … break; } case 0: { // 两者的指数值相等 e1.coef= a.coef + b.coef ; if ( a.coef != 0.0 ) InsAfter(Pc, e1); … … break; } case 1: { //多项式PB中当前结点的指数值小

115 本章小结 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。