Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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)理解一元多项式的表示方法及相加算法,提高自己用线性表解决实际问题的应用水平。


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

Similar presentations


Ads by Google