第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示.

Presentation on theme: "第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示."— Presentation transcript:

1 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示

2 本章重点难点 重点: (1) 线性表ADT顺序存储实现中的基本操作及相关算法；(2)ADT链式存储实现中基本操作及相关算法；(3)双向链表的基本操作及相关算法；(4)循环链表的特点、基本操作及相关算法。 难点: 线性表ATD的设计和实现，线性表ADT链式存储实现，包括双向链表、循环链表的基本操作和有关算法。

3 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示

4 2.1 线性表的类型定义 线性表的定义 线性表是n 个类型相同数据元素的有限序列， 通常记作（a1, a2, a3, …, an ）。 线性结构的基本特征为: (1) 集合中必存在唯一的一个“第一元素”； (2) 集合中必存在唯一的一个“最后元素”; (3)除最后元素在外，均有唯一的后继； (4)除第一元素之外，均有唯一的前驱。

5 见下页 2.1 线性表的类型定义 线性结构的基本特征为: ADT List {
2.1 线性表的类型定义 线性结构的基本特征为: 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 } 基本操作： 见下页 }ADT List

6 2.1 线性表的类型定义 基本操作 InitList( &L ) //构造一个空的线性表L。 DestroyList( &L ) //销毁L ListEmpty( L ) //判断L是否空 ListLength( L ) //求L的长度 PriorElem( L, cur_e, &pre_e ) //求前驱的值 NextElem( L, cur_e, &next_e ) //求后继的值

7 2.1 线性表的类型定义 基本操作 GetElem( L, i, &e ) //取i位置的值 LocateElem( L, e, compare( ) ) //在线性表中查找e ListTraverse(L, visit( )) //遍历线性表 ClearList( &L ) //清空线性表 ListInsert( &L, i, e ) //在i位置插入e ListDelete(&L, i, &e) //删除i位置的元素

8 2.1 线性表的类型定义 基本操作的应用 用定义过的基本操作实现例2-1，例2-2 例 2-1 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合A＝A∪B。

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

10 2.1 线性表的类型定义 例2-1算法 void union(List &La, List Lb) { La_len = ListLength(La); // 求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i <= Lb_len; i++) { ……………………………. } }

11 2.1 线性表的类型定义 例2-1算法 GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素，则插入之 例2-1算法时间复杂性 O(ListLength(La)*ListLength(Lb))

12 2.1 线性表的类型定义 基本操作的应用 用定义过的基本操作实现例2-2 例 2-2 将两个“数据元素按值递增有序排列”的线性表La和Lb归并到线性表Lc，且Lc具有同样的性质。 设 La=(a1,…ai,….an) Lb=(b1,…bj,….bm) Lc=(c1,…ck,…cm+n)

13 见下页 2.1 线性表的类型定义 例2-2算法 void MergeList(List La, List Lb, List &Lc) {
2.1 线性表的类型定义 例2-2算法 void MergeList(List La, List Lb, List &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 不空 见下页

14 2.1 线性表的类型定义 例2-2算法 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;

15 2.1 线性表的类型定义 例2-2算法 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 表中剩余元素

16 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示

17 存储线性表，就是要保存至少两类信息： (1) 线性表中的数据元素； (2) 线性表中数据元素的顺序关系；
2.2 线性表的顺序表示和实现 存储线性表，就是要保存至少两类信息： (1) 线性表中的数据元素； (2) 线性表中数据元素的顺序关系； 如何在计算机中存储线性表？ 如何在计算机中实现线性表的 基本操作？

18 2.2 线性表的顺序表示和实现 线性表的顺序表示的定义 以数据元素x 的存储位置和数据元素 y 的存储位置之间的某种关系表示逻辑关系<x,y>。 线性表的顺序表示最简单的一种顺序映象方法是：令x的存储位置和y 的存储位置相邻。

19 2.2 线性表的顺序表示和实现 线性表的顺序表示图示 用一组地址连续的存储单元依次存放线性表中的数据元素 a1 a … ai ai … an 线性表的起始地址 称作线性表的基地址

20 2.2 线性表的顺序表示和实现 数据元素地址之间的关系 以“存储位置相邻”表示有序对<ai-1，ai>时， ai-1和ai的地址关系如下： LOC(ai) = LOC(ai-1) + C C为一个数据元素所占存储量 所有数据元素的存储位置均取决于第一个数据元素的存储位置。 LOC(ai) = LOC(a1) + (i-1)×C ↑基地址

21 2.2 线性表的顺序表示和实现 顺序表示的实现 #define LIST_INIT_SIZE // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { } SqList; // 俗称 顺序表 ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位)

22 2.2 线性表的顺序表示和实现 基本操作的实现 Status InitList_Sq( SqList &L ) { // 构造一个空的线性表 } // InitList_Sq L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType)); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK;

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

24 2.2 线性表的顺序表示和实现 插入操作过程示意图 a1 a2 … ai-1 ai ai+1 an a1 a2 … ai-1 ai ai+1
2.2 线性表的顺序表示和实现 插入操作过程示意图 a1 a2 … ai-1 ai ai+1 an a1 a2 … ai-1 ai ai+1 an a1 a2 … ai-1 e ai+1 an

25 2.2 线性表的顺序表示和实现 插入操作算法 Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 在顺序表L的第 i 个元素之前插入新的元素e } // 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;

26 if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法
2.2 线性表的顺序表示和实现 插入操作算法 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; }

27 O(n) 2.2 线性表的顺序表示和实现 插入算法时间复杂性分析
2.2 线性表的顺序表示和实现 插入算法时间复杂性分析 设在第i个元素之前插入的概率为pi，则在长度为n的线性表中插入一个元素时所需平均移动元素次数为： 若假定在任何一个位置上插入元素的概率相同，则平均移动次数为： O(n)

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

29 2.2 线性表的顺序表示和实现 删除操作过程示意图 a1 a2 … ai-1 ai ai+1 an a1 a2 … ai-1 ai+1 an

30 2.2 线性表的顺序表示和实现 删除操作过程示意图 Status ListDelete_Sq (SqList &L, int i, ElemType &e) { } // ListDelete_Sq 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;

31 2.2 线性表的顺序表示和实现 删除操作时间复杂性分析 设删除第i个元素的概率为pi，则在长度为n的线性表中删除一个元素时所需平均移动次数为： 若假定在任何一个位置上删除元素的概率相同，则平均移动次数为： O(n)

32 2.2 线性表的顺序表示和实现 顺序表的优缺点 (1) 优点    a.节省存储空间; b.对线性表中第i个结点的操作易于实现; c.容易查找一个结点的前驱和后继。 (2)缺点 a.插入和删除操作比较困难; b.建立空表时，较难确定所需的存储空间。

33 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示

34 2.3 线性表的链式表示和实现 单链表 静态链表 循环链表 双向链表

35 单链表 链表的定义 一个线性表由若干个结点组成，每个结点至少含有两个域：数据域(信息域)和指针域(链域)，由这样的结点形成存储的线性表称作链表。 单链表结构示意图 … a1 a2 an ^

36 … 2.3.1 单链表 单链表结构示意图 结构特点 逻辑次序和物理次序 相同； 不一定
单链表 单链表结构示意图 … a1 a2 an ^ 结构特点 逻辑次序和物理次序 相同； 元素之间的逻辑关系用 表示；需要额外空间存储元素之间的关系; 是不是随机存储结构？ 不一定 指针 不是

37 … 2.3.1 单链表 头指针的概念 在链式存储结构中以第一个结点的存储地址作为线性表的基地址，通常称它为头指针。
单链表 头指针的概念 在链式存储结构中以第一个结点的存储地址作为线性表的基地址，通常称它为头指针。 … a1 a2 an ^ 线性表的最后一个数据元素没有后继，因此最后一个结点中的"指针"是一个特殊的值 "NULL"，通常称它为"空指针"。

38 … 2.3.1 单链表 头结点的概念 在单链表上设置一个结点，它本身不存放数据，它的指针域指向第一个元素的地址。 头结点的作用
单链表 头结点的概念 在单链表上设置一个结点，它本身不存放数据，它的指针域指向第一个元素的地址。 … a1 a2 an ^ 头结点的作用 使对第一个元素的操作与对其它元素的操作保持一致。

39 单链表 单链表的C语言实现 Typedef struct LNode { ElemType data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; LinkList L； // L 为单链表的头指针

40 单链表 单链表操作的实现 GetElem_L(LinkList L, int i, ElemType &e) //查找第i个结点，将第i个结点的值存入e 查找过程 (1)从第一个结点p开始，j=1开始记数； (2)当p->next不为空时，转向下一个继续记数; (3)直到j=i或p->next为空。

41 单链表 GetElem_L算法 Status GetElem_L(LinkList L, int i, ElemType &e) { } p = L->next; j = 1; // p指向第一个结点，j为计数器 while (p && j<i) { p = p->next; ++j; } if ( !p) return ERROR; // 第 i 个元素不存在 e = p->data; // 取得第 i 个元素 return OK;

42 单链表 单链表操作的实现 Status ListInsert_L(LinkList L, int i, ElemType e) // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e 插入过程 (1)查找第i-1个结点p； (2)生成结点s,存入e; (3)s->netx=p->next, p->next=s;

43 单链表 ListInsert_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 ) return ERROR; // i 大于表长或者小于1 ……

44 单链表 ListInsert_L算法 s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s->data = e; s->next = p->next; p->next = s; // 插入 return OK; ListInsert_L算法的时间杂性 O(ListLength(L))

45 单链表 单链表操作的实现 ListDelete_L(LinkList L, int i, ElemType &e) // L 为带头结点的单链表的头指针，本算法 // 删除链表中第i 个结点，值储入 e 删除过程 (1) 查找第i-1个结点p； (2) q=p->netx,p->next=q->next (3) free(q)

46 单链表 ListDelete_L算法 Status ListDelete_L(LinkList L, int i, ElemType &e) { } // ListDelete_L p = L; j = 0; while (p->next && j < i-1) { p = p->next; ++j; } if (!(p->next) ) return ERROR; // 删除位置不合理 q = p->next; p->next = q->next; e = q->data; free(q); return OK;

47 单链表 单链表应用举例 例 2-3 将两个“数据元素按值递增有序排列”的线性表La和Lb归并到线性表Lc，且Lc具有同样的性质。 设 La=(a1,…ai,….an) Lb=(b1,…bj,….bm) Lc=(c1,…ck,…cm+n)

48 单链表 例2-3算法 Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) ｛LinkList pa=La->next,pb=Lb->next,pc=Lc=La; while(pa&&pb) { if(pa->data<=pb->data) {pc->next=pa;pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; free(Lb); } // MergeList_L

49 单链表 链表的优缺点 (1) 优点    a. 插入和删除时间复杂性低; b.不需预先分配空间。 (2)缺点 a.指针占用存储空间，增加了内存负担。

50 2.3 线性表的链式表示和实现 单链表 静态链表 循环链表 双向链表

51 静态链表 静态链表的引入 链表具有不需事先分配存储空间，插入和删除操作时间复杂性低等优点，但实现链表必须能够对内存地址进行操作，但直接对内存地址进行操作是很多高级语言不具备的功能，为了在不具备地址操作的高级语言上实现链表的功能，引入了静态链表。 静态链表的概念 定义一个较大的结构数组作为备用结点空间(即存储池)，当申请结点时，从存储池中取出一个结点，当释放结点时，将结点归还存储池内。

52 space[1],space[3],space[5], space[6].
静态链表 存储池 space 静态链表示意图 1 2 3 4 5 6 7 8 9 10 9 zhao 3 qian 4 sun 5 li 7 zhou 6 wu zheng 8 wang 10 静态链表的第一个结点位置是一个下标： 左图中有两个静态链表 第一个以1开头。 space[1],space[3],space[5], space[6]. 第二个以2开头 space[2],space[4],space[7], space[8]. data域 cur域

53 静态链表 静态链表的C语言实现 //----线性表的静态单链表存储结构----// #define MAXSIZE //链表的最大长度 typedef struct { ElemType data; int cur; //游标 } component, SLinkList[MAXSIZE]; SLinkList space;

54 静态链表 静态链表模拟可用空间初始化 //----初始化----// void InitSpace_SL(SLinkList &space) { for (i=0;i<MAXSIZE-1;++i) space[i].cur=i+1; space[MAXSIZE-1].cur=0; }

55 静态链表 静态链表模拟申请空间的实现 //----申请空间----// int Malloc_SL(SLinkList &space) { i = space[0].cur; if (space[0].cur) space[0].cur = space[i].cur; return i; }

56 静态链表 静态链表模拟释放空间的实现 //----回收结点----// void Free_SL(SLinkList &space,int K) { space[k].cur=space[0].cur; space[0].cur=k; }

57 静态链表 静态链表插入算法 Status ListInsert_L(int L, int i, ElemType e) { // L 为静态链表的第一个结点位置，本算法 // 在链表中第i 个结点之前插入新的元素 e } p =L; j = 0; while (p && j < i-1) { p =space[p].cur; ++j; } if (!p) return ERROR; ……

58 静态链表 静态链表插入算法 s = Malloc_SL(space) // 生成新结点 space[s].data = e; space[s].cur =space[p].cur; space[p].cur = s; // 插入新结点 return OK; 静态链表插入算法时间复杂性 O(ListLength(L))

59 2.3 线性表的链式表示和实现 单链表 静态链表 循环链表 双向链表

60 循环链表 循环链表的概念 单链表最后一个结点的指针域没有利用，如果使其指向指向头指针（头结点），则首尾构成一个循环，称作循环链表。 循环链表示意图 … a1 a2 an head

61 … 2.3.3 循环链表 循环链表的优点 从表中任一结点出发均可找到表中其它结点。 讨论：在循环链表中多采用尾指针？为什么？
循环链表 循环链表的优点 … a1 a2 an head 从表中任一结点出发均可找到表中其它结点。 讨论：在循环链表中多采用尾指针？为什么？ 结论：如果采用尾指针，则查找第一个结点和最后一个结点都容易。

62 循环链表 单链表和循环链表操作比较 设两个链表La=(a1,a2,...,an)和Lb=(b1,b2,...bm)，讨论如下问题： (1) La、Lb都是带头结点的单链表，如何实现将Lb接在La之后？时间复杂度是多少？ (2) La、Lb都是带头结点头指针的单循环链表，如何实现将Lb接在La之后还形成一个循环链表？时间复杂度是多少？ (3) La、Lb都是带头结点尾指针的单循环链表，如何实现将Lb接在La之后还形成一个循环链表？时间复杂度是多少？

63 循环链表 单链表和循环链表操作比较 结论： (1) La、Lb都是带头结点的单链表，Lb接在La之后，时间复杂度是 O(length(La))。 (2) La、Lb都是带头结点头指针的单循环链表，实现将Lb接在La之后还形成一个循环链表，时间复杂度是多少 O(length(La)+length(Lb))。 (3) La、Lb都是带头结点尾指针的单循环链表，实现将Lb接在La之后还形成一个循环链表，时间复杂度是 O(1)。

64 一个链表的每一个结点含有两个指针域：一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。
2.3.3 双向链表 双向链表的概念 一个链表的每一个结点含有两个指针域：一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。 双向链表结构示意图 ^ a1 a2 … ^ head

65 2.3.3 双向链表 双向链表的C语言实现 //类型定义 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; } DuLNode,*DuLinkList;

66 2.3.3 双向链表 双向链表中地址关系 在双向链表中： p->prior指向p的前驱，p->next指向p的后继 以下都是p结点的地址： p->next->prior 和 p->prior->next 双向链表的操作特点： “查询” 和单链表相同。 “插入” 和“删除”时需要同时修改两个方向上的指针。

67 2.3.3 双向链表 双向链表的插入算法 Status ListInsert_Dul(DuLinkList &L, int i ,ElemType e) { if(!(p=GetElemP_DuL(L,i))) return error; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) s->data=e; s->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s; return OK; }

68 2.3.3 双向链表 双向链表的删除算法 Status ListDelete_Dul(DuLinkList &L,int i ,ElemType &e) { if(!(p=GetElemP_DuL(L,i))) return error; e=p->data; p->prior->next=p->next; p->next->prior=p->prior; free(p); return OK; }

69 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示

70 2.4 一元多项式的表示 一元多项式的讨论 讨论一元多项式用什么方式存储比较合适？ 结论：一元多项式既可以用顺序表存储，也可以用链表存储，在用顺序表存储时，如果是稀疏多项式则浪费空间严重，用链式存储比较好。

71 见下页 2.4 一元多项式的表示 一元多项式的抽象数据类型 ADT Polynomial { 数据对象：
2.4 一元多项式的表示 一元多项式的抽象数据类型 ADT Polynomial { 数据对象： 数据关系： } 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中的指数值 } 基本操作： 见下页

72 2.4 一元多项式的表示 一元多项式的基本操作 CreatPolyn ( &P, m ) //存储多项式 DestroyPolyn ( &P ) //销毁多项式 PrintPolyn ( &P ) //打印输出多项式 PolynLength( P ) //求多项式的项数 AddPolyn ( &Pa, &Pb ) //两个多项式相加 SubtractPolyn ( &Pa, &Pb )//两个多项式相减 ……

73 2.4 一元多项式的表示 一元多项式类型的C语言实现 typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType; typedef LinkList polynomial; // 用带表头结点的有序链表表示多项式

74 本章小结 熟练掌握： (1)线性表的逻辑结构特性和线性表的(ADT)设计； (2)线性表的顺序存储结构和链式存储结构两种实现方式和基本操作；
(3)双向链表的插入和删除等基本操作及相关算法; (4)循环链表的特点及相关操作; (5)理解一元多项式的表示方法及相加算法，提高自己用线性表解决实际问题的应用水平。