第二章 线性表.

Presentation on theme: "第二章 线性表."— Presentation transcript:

1 第二章 线性表

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

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

4 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } { 称 n 为线性表的表长;
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 {结构初始化} 操作结果：构造一个空的线性表 L。 初始条件：A[]中存在线性表的 n 个 数据元素。 操作结果：构造一个含 n 个数据元素
InitList( &L ) 操作结果：构造一个空的线性表 L。 CreateList( &L, A[], n) 初始条件：A[]中存在线性表的 n 个 数据元素。 操作结果：构造一个含 n 个数据元素 的线性表 L。

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

8 PriorElem( L, cur_e, &pre_e )
{引用型操作} 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 若 L 为空表，则返回 TRUE，否则FALSE。
ListEmpty( L ) （线性表判空） 初始条件： 操作结果： 线性表 L 已存在。 若 L 为空表，则返回 TRUE，否则FALSE。 ListLength( L ) （求线性表的长度） 初始条件： 操作结果： 线性表 L 已存在。 返回线性表 L 中元素个数。

10 NextElem( L, cur_e, &next_e )（求后继）
PriorElem( L, cur_e, &pre_e )（ 求前驱） 初始条件： 操作结果： 线性表 L 已存在。 若 cur_e 是 L 中的元素，则以 pre_e 带回它的前驱，否则操作失败，pre_e无定义。 NextElem( L, cur_e, &next_e )（求后继） 初始条件： 操作结果： 线性表 L 已存在。 若cur_e是 L 中的元素，则以 next_e带回它的后继，否则操作失败，next_e无定义。

11 LocateElem( L, e, compare( ) )（定位函数）
GetElem( L, i, &e )（ 求线性表中某个元素） 初始条件： 操作结果： 且1≤i≤LengthList(L)。 线性表 L 已存在 以 e 带回 L 中第 i 个数据元素值。 LocateElem( L, e, compare( ) )（定位函数） 初始条件： 操作结果： 线性表 L 已存在,compare()为判定函数。 返回 L 中第 1 个与 e 满足关系 compare( )的元素的位序，若不存在这样的元素，则返回 0。

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

13 {加工型操作} ClearList( &L ) ( 线性表置空 ) PutElem( &L, i, &e ) ( 改变数据元素的值 ) ListInsert( &L, i, e ) ( 插入数据元素 ) ListDelete( &L, i, &e ) ( 删除数据元素 )

14 初始条件： 操作结果： 线性表 L 已存在。 将 L 重置为空表。 PutElem( &L, i, e ) 初始条件： 操作结果：
ClearList( &L ) 初始条件： 操作结果： 线性表 L 已存在。 将 L 重置为空表。 PutElem( &L, i, e ) 初始条件： 操作结果： 线性表 L 已存在， 且 1≤i≤LengthList(L)。 L 中第 i 个元素赋值和 e 相同。

15 初始条件： 操作结果： 初始条件： 操作结果： ,1≤i≤LengthList(L)+1。 线性表 L 已存在
ListInsert( &L, i, e ) 初始条件： 操作结果： ,1≤i≤LengthList(L)+1。 线性表 L 已存在 在 L 的第 i 个元素之前插入新的元素e, L 的长度增 1。 ListDelete( &L, i, e ) 初始条件： 操作结果： 线性表 L 已存在 ,1≤i≤LengthList(L)。 删除 L 中第 i 个元素，并以 e 带回其值, L 的长度减 1。

16 例 2-1 现要求一个新的集合A＝A∪B。 即:需对线性表作如下操作：
假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合A＝A∪B。 即:需对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。

17 操作步骤： 1．取得线性表 LB 中一个数据元素; ListDelete(Lb, 1, e); 2．依值在线性表 LA 中进行查访;
LocateElem(LA, e, equal( )); 3．若不存在，则插入之。 ListInsert(LA, n+1, e); ( n 表示线性表 LA 当前长度)

18 // La中不存在和 e 相同的数据元素，则插入之
void union(List &La, List Lb) { // 将线性表Lb中所有在线性表La中不存在的数据元素 // 插入到线性表La中 La_len = ListLength(La); // 求线性表La的长度 while (!ListEmpty(Lb)) { ListDelete(Lb, 1, e); // 删除Lb中第1个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之 }//while } // union

19 例 2-2 已知一个“非纯集合” B，试构造一个纯集合A，使 A 中只包含 B 中所有值各不相同的数据元素。
若仍然以线性表表示集合，则算法的策略应该和例一基本相同,差别是什么？ 1.集合 A 的初态是“空集” 2.不破坏集合 B

20 void purge(List &La, List Lb) {
La_len=0; Lb_len=ListLength(Lb); } // pugre InitList(La); // 构造(空的)线性表LA for (i = 1; i <= Lb_len; i++) { }//for GetElem(Lb, i, e); // 取Lb中第 i 个数据元素赋给 e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之

21 例 2-3 判别两个集合是否相等。 集合相等的条件是:两者所含元素个数相同，且所有对应元素都相等。
仍以线性表表示集合，并假设这两个集合是“纯集合”。 则算法的策略为:在两个线性表的长度相等的前提下，只要判别一个表中的元素在另一个表中都存在即可。

22 ……… bool isEqual(List LA, List LB) { // 若线性表LA和LB不仅长度相等，且所含数据
// 元素也相同，则返回 TRUE, 否则返回 FALSE }//isEqual La_len = Listlength(LA); Lb_len = Listlength(LB); if ( La_len != Lb_len ) return FALSE; // 两表的长度不等 else { } ………

23 while ( i<= La_len && found ) {
return found; i = 1; found = TRUE; GetElem(LA, i, e); // 取得LA中一个元素 if (LocateElem(LB, e, equal( )) i++; // 依次处理下一个 else found = FALSE; // LB中没有和该元素相同的元素

24 一、顺序表 ---线性表的顺序映象 二、顺序表中基本操作的实现 三、顺序表的其它操作举例

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

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

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

28 顺序表的 C 语言描述 typedef struct { ElemType *elem; // 存储空间基址
// 存储结构 typedef struct { } SqList; // 俗称 顺序表 ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) // 基本操作接口

29 void purge(SqList &La, SqList Lb) {
// 构造顺序表La，使其只包含Lb中所有值不 //相同的数据元素, 算法不改变顺序表Lb bool b; int Lb_len = Listlength(Lb); // 求线性表Lb的长度 InitList(La, Lb_len); // 创建一个空的线性表La int La_len = 0; for (i = 1; i <= Lb_len; i++) { // 依次处理Lb中每个元素 }//for } //purge

30 b = GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) { ++La_len; b = ListInsert(La, La_len, e); // 当 La中不存在和 e 值相同的数据 //元素时进行插入 }

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

32 O(1) Status InitList( SqList& L, int maxsize ) {
L.elem = new ElemType[maxsize]; // 为顺序表分配大小为 maxsize 的数组空间 if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = maxsize; return OK; 算法时间复杂度： O(1)

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

34 // 在顺序表中查询第一个满足判定条件的数据元素，
int LocateElem(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { // 在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回 0 } // LocateElem 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) )

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

36 … 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 表的长度增加

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

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

39 if (i < 1 || i > L.length+1) return ERROR;
// 插入位置不合法 if (L.length >= L.listsize) return OVERFLOW; // 当前存储空间已满

40 例如：ListInsert(L, 5, 66) for (j=L.length-1; j >=pos-1; --j) L.elem[j+1]= L.elem[j]; j j j 4 L.length-1 66 42 56 87

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

42 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 表的长度减少

43 算法时间复杂度为: Status ListDelete (SqList &L, int i, ElemType &e) {
if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法 for (j = pos; j<L.length; ++j) L.elem[j-1] = L.elem[j]; // 被删除元素之后的元素左移 --L.length; // 表长减1 return TRUE; 元素左移 算法时间复杂度为: O( ListLength(L))

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

45 例如：ListDelete(L, 5, e) for (j=pos; j<L.length; ++j) L.elem[j-1] = L.elem[j]; j j j 5 L.length-1 56 87 63

46 例 2-4 算法 1 算法 2 试设计一个算法，用尽可能少的辅助空间将顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表
(a1, a2, …, am, b1, b2, …, bn ) 改变成 (b1, b2, …, bn, a1, a2, …, am ) 。 算法 1 从 b1开始，从原地删除之后插入到 a1 之前直至 bn。 算法 2 进行三次“逆转顺序表”的操作。

47 j i j i j i a b c d e f g 1 2 3 4 5 1 2 a b a 3 b a c b d c c e d d f

48 算法的时间复杂度为: O(m+n) void invert( ElemType &R[]，int s， int t )
// 本算法将数组 R 中下标自 s 到 t 的元素逆置， // 即将（Rs, Rs+1, …, Rt-1, Rt ） // 改变为（Rt, Rt-1, …, Rs+1, Rs ） void exchange ( SqList &A; int m ) { // 本算法实现顺序表中前 m 个元素 // 和后 n 个元素的互换 n = A.length – m; invert( A.elem, 0, A.length ); invert( A.elem, 0, n-1 ); invert( A.elem, n, m+n-1 ); } // exchange 算法的时间复杂度为: O(m+n)

49 for ( i=0; j = m; j<A.length; i++,j++ ) {
void exchange( SqList &A, int m ) { // 实现顺序表 A 中前 m 个元素和后 n 个元素互换 } exchange for ( i=0; j = m; j<A.length; i++,j++ ) { } x = A.elem[j]; for ( k=j; k>i; k-- ) A.elem[j] = A.elem[j-1]; A.elem[i] = x; 算法的时间复杂度 为: O(mn)

50 例 2-5 算法 1 算法 2 试编写算法，删除顺序表中“多余” 的数据元素 。
从 a1开始，检查在它之后的数据元素，如有和它相等的，则从表中删除之。 算法 1 回顾例2-2的算法，试按“构造”一个新的顺序表的思想来进行，设想这两个表“共享”一个存储空间。 算法 2

51 i i j j j j 5 2 3 4 7 3 3 4 2 5 7 4 7 5 5 4 3 4 3 3 L.length-1 L.length-1 L.length-1 L.length-1 5 2 3 4 7 5 2 3 4 7 k k i i k k i k i k i i i i i i i i i

52 算法的时间复杂度为: O(L.length3)
void purge(SqList &L ){// 删除顺序表 L 中冗余元素   for (i=0; i<L.length-1; ++i) {// 顺序考察表中每个元素 j=i+1; while ( j< L.length ) }//for }//purge if ( L.elem[j] != L.elem[i] ) ++j; else { for ( k=j+1; k<L.length; ++k ) L.elem[k-1] = L.elem[k]; // 移动元素 --L.length; // 修改表长 }//else 算法的时间复杂度为: O(L.length3)

53 算法的时间复杂度为: O(L.length2)
void purge(SqList &L ) { // 删除顺序表 L 中的冗余元素  k = -1; // k 指示新表的表尾 for ( i=0; i<L.length; ++i ) // 顺序考察表中每个元素 }//for L.length = k+1; // 修改表长 }//purge 算法的时间复杂度为: O(L.length2)

54 j=0; while(j<=k && L.elem[j]!=L.elem[i]) ++j; // 在新表中查询是否存在 // 和L.elem[i]相同的元素 if ( k==-1 || j>k ) // k=-1 表明当前考察的是第一个元素 L.elem[++k] = L.elem[i];

55 一、单链表 ---线性表的链式映象 二、单链表中基本操作的实现 三、单链表的其它操作举例 四、其它形式的链表结构

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

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

58 LinkList L； // L 为单链表的头指针
单链表的 C 语言描述 // 存储结构 Typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } *LinkList; LinkList L； // L 为单链表的头指针

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

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

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

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

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

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

65 …… O(ListLength(L)) 算法的时间复杂度为:
Status ListInsert(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert 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)) 算法的时间复杂度为:

66 if ( s == NULL) return ERROR; s->data = e;
s = new LNode; // 生成新结点 if ( s == NULL) return ERROR; s->data = e; s->next = p->next; p->next = s; // 插入 return OK; p ai-1 ai-1 ai e s

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

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

69 算法的时间复杂度为: O(ListLength(L))
Status ListDelete(LinkList L, int i, ElemType &e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete 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; delete(q); return OK; 算法的时间复杂度为: O(ListLength(L))

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

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

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

73 L = new LNode; L->next = NULL;
// 先建立一个带头结点的单链表 p = new LNode; scanf(&p->data); // 输入元素值 p->next = L->next; L->next = p; // 插入 a p b p c p d p e p L ∧ ∧ ∧

74 O(Listlength(L)) void CreateList(LinkList &L, int n) {
L = new LNode; L->next = NULL; // 先建立一个带头结点的单链表 for (i = n; i > 0; --i) { p = new LNode; scanf(&p->data); // 输入元素值 p->next = L->next; L->next = p; // 插入 } O(Listlength(L)) 算法的时间复杂度为:

75 试设计算法，将单链表中前 m 个结点和后 n 个结点进行互换，即将线性表 (a1, a2, …, am, b1, b2, …, bn ) 改变成 (b1, b2, …, bn, a1, a2, …, am ) 。 例 2-6 算法设计: 将 (b1, b2, …, bn )从链表的当前位置上删除之后再插入 a1 到之前，并将 am设为表尾。

76 … ta->next=NULL; tb->next = L->next; L->next = hb; ta hb
am b1 b2 bn L … ∧ ∧ ∧ ta->next=NULL; tb->next = L->next; L->next = hb;

77 算法的时间复杂度为: void exchange( SLink &L, int m ) { // 互换链表中前 m 个和后 n 个结点
ta = L; i = 0; while ( ta && i<m ) { // 查询结点 am ta = ta->next; i++; }// while }//exchange if ( ta && ta->next ) { // m < 表长 hb = ta->next; tb = hb; while (tb->next) tb = tb->next; // 查询表尾 bn }//if 修改指针 算法的时间复杂度为: O(ListLength(L))

78 例 2-7 试编写算法，删除单链表中“多余” 的数据元素 。 算法一 对链表中当前考察的每个元素，删除它之后的“值相同”的结点; 算法二
将新表中尚未存在的“值相同”的结点插入到新的链表中。

79 算法时间复杂度: O(ListLength2(n)) void purge( SLink &L ) { // 删除链表中的“冗余”元素
p = L->next; while ( p ) { // p 指向当前被考察的结点 q = p; while (q->next) // 考察 q 所指后继结点 if (q->next->data <> p->data) q = q->next; else // 修改指针并释放结点空间 { s = q->next; q->next = s->next; delete s; } p = p->next; }// while p }//purge 算法时间复杂度: O(ListLength2(n))

80 void purge( SLink &L ) { // 删除链表中“冗余”元素
p = L->next; L->next = NULL; // 设新表为空表 while ( p ) { // p 指向当前被考察的结点 q = L->next; succ = p->next; // 指向*p的后继 while (q && q->data <> p->data) q = q->next; // 查询是否已存在值相同的结点 if ( q ) delete p; else // 插入新表(倒插)，修改指针 { p->next = L->next; L->next = p; } p = succ; // 继续考察下一个结点 }// while p }//purge 算法时间复杂度: O(ListLength2(n))

81 循环链表 a1 a2 … ... an 最后一个结点的指针域的指针又指回第一个结点的链表
和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 有时还可以将头指针设成指向尾结点。

82 ->next; ha = ta->next; void exchange( SLink &L, int m ) {
// 互换 链表中前 m 个和后 n 个结点 ta = L; i = 0; while ( ta && i<m ) { // 查询结点 am ta = ta->next; i++; }// while if ( ta && ta->next ) { // m < 表长 hb = ta->next; tb = hb; while (tb->next) tb = tb->next; // 查询表尾 bn 修改指针 }//if }//exchange 循环 ->next; ha = ta->next; ta->next = L->next; L->next = ha; ta->next->next = hb; L = ta;

83 双向链表 双向链表通常以循环链表的形式出现 struct DuLNode *prior; // 指向前驱的指针域
typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList; 双向链表通常以循环链表的形式出现

84 双向循环链表 空表 非空表 a a … an

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

86 删除 ai-1 ai-1 ai ai+1 p q p->next = q->next;
p->next->prior = p; delete q;

87 一、有序表类型 二、有序链表类型举例 三、一元稀疏多项式类型的定义 四、一元稀疏多项式类型的实现

88 ADT Ordered_List { i=1,2,…,n, n≥0 } xi-1≤ xi, i=2,3,…,n }
集合中任意两个元素 之间均可以进行比较 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 } 基本操作: } ADT Ordered_List

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

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

91 例 2-8 试以有序表表示集合，编写算法“从非纯集合构造纯集合” 。 例如：B =（2，3，3，5，6，6，6，8，12）
A =（2，3，5，6，8，12） 对集合 B 而言，值相同的数据元素必定相邻; 对集合 A 而言，数据元素依值从小至大的顺序插入。 可见，数据结构改变了， 解决问题的策略也应作相应地改变。

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

93 算法的时间复杂度为: O(L.length2)
void purge_Sq(SqList &L ) { // 删除顺序表 L 中的冗余元素  k = -1; // k 指示新表的表尾 for ( i=0; i<L.length; ++i ) // 顺序考察表中每个元素 }//for L.length = k+1; // 修改表长 }//purge_Sq 算法的时间复杂度为: O(L.length2)

94 L.elem[i] != L.elem[k] ) j=0; while(j<=k && L.elem[j]!=L.elem[i])
if ( k==-1 || j>k ) // k=-1 表明当前考察的是第一个元素 L.elem[++k] = L.elem[i]; L.elem[i] != L.elem[k] )

95 算法的时间复杂度为: O(L.length2)
void purge_L( SLink &L ) { // 删除链表中“冗余”元素 p = L->next; L->next = NULL; // 设新表为空表 while ( p ) { // p 指向当前被考察的结点 q = L->next; succ = p->next; while (q && q->data <> p->data) q = q->next; // 查询有否值相同的结点 if ( q ) delete p; else // 插入新表，修改指针 { p->next = L->next; L->next = p; } p = succ; }// while p }//purge_L ra = L; while ( p ) { // p 指向当前被考察的结点 q = L->next; succ = p->next; if ( ra <> L && p->data == ra->data ) delete p; ra->next = p; ra = p; ra->next = NULL; 算法的时间复杂度为: O(L.length2)

96 例 2-9 试编写算法，以有序表表示集合，试求C=AB 。 算法策略分析: 设 La = (a1, …, ai, …, an),
Lb = (b1, …, bj, …, bm) Lc = (c1, …, ck, …, cm+n) 且已由 (a1, …, ai-1) 和 (b1, …,bj-1) 归并得 (c1, …, ck-1) 则 k = 1, 2, …, m+n

97 操作步骤： 1．初始化 LC 为空表； 2．分别从 LA和LB中取得当前元素 ai 和 bj；
3．若 ai≤bj，则将 ai 插入到 LC 中，否则将 bj 插入到 LC 中(相等时只取一个)； 4．重复 2 和 3 两步，直至 LA 或 LB 中元素 被取完为止； 5．将 LA 表或 LB 表中剩余元素复制插入到 LC 表中。

98 } // merge_list void MergeList(List La, List Lb, List &Lc) {
// 本算法将非递减的有序表 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 算法时间复杂度: O(La_len+Lb_len)

99 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { // 将 ai 插入到 Lc 中 ListInsert(Lc, ++k, ai); ++i; if (ai==bj) ++j; } else { // 将 bj 插入到 Lc 中 ListInsert(Lc, ++k, bj); ++j;

100 … … … … void union_OL( LinkList &La，LinkList &Lb ) { { } } // union_OL
// La 和 Lb 分别为表示集合 A 和 B 的循环链表的头指 // 针，求 C=A∪B，操作完成之后，La为表示集合C //的循环链表的头指针，集合A和B的链表不再存在 pa = La->next->next; // pa 指向 A 中当前结点 pb = Lb->next->next; // pb 指向 B 中当前结点 rc = La->next; // rc 指向 C 当前的表尾结点 while ( pa!=La->next && pb!=Lb->next ) { } } // union_OL … … … … if ( pb == Lb->next ) rc->next = pa; // 链接 A 剩余段 else { } delete pb; // 释放 B 表的表头 // 链接 B 的剩余段

101 if ( pa->data < pb->data ) { // 链接 A 的结点
rc->next = pa; rc = pa; pa = pa->next; if (pa->data == pb->data) { qb = pb; pb = pb->next; delete qb; } else { // 链接B的结点 rc->next = pb; rc = pb; pb = pb->next; } rc->next = pb; pb = Lb->next; Lb->next = La->next; La = Lb; // pb 指向 B 的头结点并构成 C 的循环链

102 线性表的基本操作在两种存储结构中的时间性能比较:
基 本 操 作 顺序表 链表 InitList(&L) DestroyList(&L) ListEmpty(L) ListLength(L) PreElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) GetElem(L, i, &e) LocateElem(L, e, compare()) O(1) O(1) O(1) O(n) O(1) O(1) O(1) O(n) O(1) O(n) O(1) O(1) O(1) O(n) O(n) O(n)

103 1. 链表是一种动态分配空间的存储结构，能更有效地利用存储空间;
基 本 操 作 顺序表 链表 ListTraverse( L, visit() ) ClearList( &L ) PutElem( &L, i, &e ) ListInsert( &L, i , e ) LiseDelete( &L, i ) O(n) O(n) O(1) O(n) O(1) O(n) O(n) O(n) O(n) O(n) 链表结构的特点: 1. 链表是一种动态分配空间的存储结构，能更有效地利用存储空间;

104 2. 链表中以“指针”指示元素的后继，因此在插入或删除元素时不需要移动元素，但在基本操作中显示不出它的优势;
3. 由于链表是“顺序存取”的结构，给随机存取元素和在表尾插入等操作带来不便; 引起问题的原因: 1. 链表的长度是隐含值，给线性表的某些操作带来不便; 2. 在链表中，数据元素在线性表中的位序不明确，取而代之的是结点的“位置”;

105 // 结构定义 typedef struct LNode { // 结点结构 ElemType data;
struct LNode *next; } *SLink; typedef struct { // 链表结构 SLink head, // 指向有序链表中的头结点 tail, // 指向有序链表中最后一个结点 curPtr; // 指向操作的当前结点 int len, // 指示有序链表的长度 curpos; // 指示当前指针所指结点的位序 } OrderedLinkList;

106 // 基本操作接口(函数声明) bool InitList(OrderedLinkList &L ){
// L.head = NULL 并返回FALSE，否则返回TRUE L.head = new LNode; if ( L.head) { // 链表构建成功 L.tail = L.curPtr = L.head; L.len = L.curpos = 0; return TRUE; } else { L.head = NULL; return FALSE; } }//InitList

107 bool GetPos (OrderedLinkList L, int pos ){
// 若1≤pos≤LengthList(L)，则移动当前指针 // 指向第pos个结点且返回函数值为TRUE, //否则不移动当前指针且返回函数值为FALSE if (pos<1 || pos>L.len) return FALSE; if (pos < L.curpos ) { L.curPtr = L.head->next; L.curpos = 1; } while ( L.curpos < pos ) { L.curPtr = L.curPtr->next; ++L.curpos; } return TRUE; }

108 bool LocateElem (OrderedLinkList L, ElemType e,
int (*compare)(ElemType, ElemType)) { // 若有序链表L中存在和e相同的数据元素，则当前 // 指针指向第1个和e相同的结点，并返回TRUE， // 否则当前指针指向第一个大于e的元素的前驱， // 并返回FALSE L.current = L.head; L.curpos = 0; while (L.current->next && compare(e,L.current->next->data)>0) { L.current = L.current->next; L.curpos ++; // 指针后移，继续查询 }

109 if (L.current->next &&
compare(e,L.current->next->data)==0) { // 查到和e相同元素，当前指针后移 L.current = L.current->next; L.curpos++; return TRUE; } else return FALSE; // 当前指针所指后继元素大于e // 查找不成功 }//LocateElem

110 bool InsAfter ( LinkList &L, ElemType e ){ // 在有序链表L中当前指针所指结点之后插入一个元
s = new LNode; if (!s) return FALSE; s->data = e; s->next = L.curPtr->next; L.curPtr->next = s; if (L.tail == L.curPtr) L.tail = s; // 若新结点插入在尾结点之后，则修改尾指针 L.curPtr = s; ++L.curpos; // 移动当前指针 ++L.len; return TRUE; // 表长增 1 }

111 bool DelAfter( LinkList &L, ElemType& e ) { // 若当前指针所指非单链表L中最后一个结点，则删除
//并返回TRUE，否则不进行删除操作且返回FALSE if (L.curPtr == L.tail ) return FALSE; p = L.curPtr->next; e = p->data; L.curPtr->next = p->next; // 修改当前结点的指针 if (L.tail == p) L.tail = L.curPtr; // 删除尾结点时修改尾指针 delete p ; --L.len; // 释放被删结点, 表长减1 return TRUE; }// DelAfter

112 的多项式，上述表示方法是否合适？ S(x) = 1 + 3x10000 – 2x20000 一元多项式 在计算机中，可以用一个线性表来表示:
P = (p0, p1, …，pn) 但是对于形如 在第一章曾做过多项式求值的题，由于多项式中各项指数是从0起，并逐项增1，因此很自然地只需要用一个一维数组存储多项式的各项系数，记得所编函数中有两个参数a[]和n，它实际上是一个用顺序存储结构表示的线性表，因此也可以采用链表存储各项系数。 在有的数学问题中可能出现这样的多项式，当然也可以用通常所用方法实现，但由于它中间缺了好多项，即存在很多系数为0的项，此时仍用一维数组存储系数的话，不仅浪费空间，而且浪费时间，例如在求值的过程中就进行了很多和“0”相加或相乘的运算。 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？

113 （（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) ） 称这类含有很多“零系数项”的多项式为稀疏多项式，这是它的一般书写形式。 为了节省时间和空间，即不存储“零值的系数”，我们可以用这样一个线性表来表示，由于加上了“指数” ，明确了每个非零系数所对应的指数，自然就可以省缺存储“0”系数项。 下面将这样的多项式作为线性表的一种应用进行讨论。

114 抽象数据类型一元多项式的定义如下： 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中的指数值 }

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

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

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

118 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.指数相同的项只能输入一次

119 // 本函数实现多项式求和 Pc = Pa＋Pb，并销毁Pa和Pb … …
Status AddPolyn ( polynomial &Pc, polynomial &Pa, polynomial &Pb) { // 本函数实现多项式求和 Pc = Pa＋Pb，并销毁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 … … … …

120 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中当前结点的指数值小

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