2

Size: px

Start display at page:

Download "2"

科蒯
5 years ago
Views:

1 孙猛年 9 月 18 日

2 课程主页 : 作业通过 course.pku.edu.cn 提交 2

3 线性表的概念和抽象数据类型顺序表示链接表示 3

4 4

5 线性表 ( 简称为表 ) 是零个或多个元素的有穷序列列线性表的逻辑结构 : L =(k 0,k 1,...,k n 1 ) L =< K,R> 其中 K = {k 0,k 1,...,k n 1 },R={< k i,k i+1 > 0 apple i apple n 2} i 称为元素 k i 的索引或下标表中的元素又称表目 5

6 表中所含元素的个数称为表的长度 ; 长度为零的表称为空表 ; 称为第一个元素 ; k 0 k n 1 称为最后一个元素 ; 是的前驱 ; k i (0 apple i apple n 2) k i+1 是的后继 k i+1 k i 6

7 作为一种包含元素 ( 可以没有, 也可以有许多 ) 的数据结构, 通常都需要提供一些标准操作, 例例如 : 创建和销毁这种数据结构 ( 的实例例 ); 判断一个数据结构是否空 ( 没有元素 ), 如果数据结构的容量量有限制, 还需判断它是否满 ( 不不能再加入新元素 ); 向结构中加入元素或从中删除元素 ; 访问结构里里的元素 7

8 从作用看, 数据结构的操作可以分为三类 : 构造操作 : 构造出该数据结构的一个新实例例访问操作 : 从已有数据结构中提取某些信息, 但不不创建新结构, 也不不修改被操作的结构变动操作 : 修改已有的数据结构 8

9 假设 List 表示一个线性表类型,DataType 表示其元素的类型, 元素的下标用 position 类型的量量表示 ; 则可以说明如下 : List list; DataType x; position p; 9

10 ADT List is operations List createnulllist ( void ) /* 创建并且返回一个空线性表 */ int insertpre ( List list, position p, DataType x ) /* 在 list 中 p 位置前插入值为 x 的元素 */ int insertpost ( List list, position p, DataType x ) /* 在 list 中 p 位置后插入值为 x 的元素 */ int deletev (List list, DataType x ) /* 在 list 中删除一个值为 x 的元素 */ int deletep (List list, position p ) /* 在 list 中删除位置为 p 的元素 */ Position locate ( List list, DataType x ) /* 在 list 中查找值为 x 的元素的位置 */ int isnull ( List list ) /* 判别 list 是否为空线性表 */ end ADT List; 10

11 线性表的实现主要考虑两方面的情况计算机内存的特点, 以及保存元素和元素顺序信息的需要重要操作的效率其中使用最频繁的操作通常是 :( 定位 ) 元素访问, 元素加入, 元素删除, 元素遍历元素遍历就是依次访问表里里的所有 ( 或一批 ) 元素操作效率与访问元素的个数有关遍历所有元素的操作, 希望其复杂性不不超过 O(n) 加入 / 删除 / 访问元素的操作效率与表的实现结构有关基于各方面考虑, 人们提出了了两种基本实现模型将表元素顺序存放在的一大块连续的存储区里里, 这样实现的表也称为顺序表 ( 或连续表 ), 元素顺序有自然的表示将表元素存放在通过链接构造起来的一系列列存储块里里 ( 链接表 ) 11

12 采用顺序存储是表示线性表最简单的方法将线性表中的元素依次存储在一片相邻的存储区域中元素之间逻辑上的相邻关系通过元素在计算机内物理理位置上的相邻关系来表示逻辑上相邻存储位置相邻顺序表示的线性表也称顺序表 12

13 一般情况下表元素所需存储量量相同, 因此顺序表中任一元素的位置都可简单计算出来, 存取操作可以在 O(1) 时间内完成线性表的首地址或基地址 k 0 loc(k 0 ) 顺序表中的存储位置假定顺序表中每个元素占用 c个存储单元下标为 i的元素的存储位置为 : k i loc(k i )=loc(k 0 )+i c 13

14 14

15 如果表中要保存的元素的情况复杂, 大小不不一, 或者还有复杂的内部结构, 可以采用链接方式, 在表中保存元素链接 ( 链接的大小相同 ) 存储地址 Loc(a 0 ) Loc(a 0 )+c Loc(a 0 )+i*c Loc(a 0 )+(n-1)*c 数据元素 k 0 k 1 k i k n-1 c 是链接的大小元素另外表示, 为另外的简单元素或复杂结构 15

16 struct SeqList{ int MAXNUM; /* 顺序表中可以存放元素的个数 */ int n; /* 实际存放线性表中元素的个数,n MAXNUM */ DataType *element; /* element[0],,element[n- 1] 存放线性表中的元素 */ }; typedef struct SeqList *PSeqList; 如果 palist 是个 PSeqList 类型的指针变量, 则 : palist->maxnum: 顺序表中可以存放元素的个数 ; palist->n: 顺序表中实际元素的个数 ; palist->element[0],,palist->element[palist->n-1]: 顺序表中各个元素 16

17 17

18 创建空顺序表判断表是否为空在顺序表中求某元素的下标顺序表的插入顺序表的删除 18

19 PSeqList createnulllist_seq(int m) { /* 创建新的顺序表 */ PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList)); if (palist!=null){ palist->element = (DataType*)malloc(sizeof(DataType)*m); if (palist->element){ palist->maxnum=m; palist ->n = 0; /* 空表长度为 0 */ return palist ; } else free palist; } printf( Out of space!!\n ); /* 存储分配失败 */ return NULL; } 19

20 int isnulllist_seq(pseqlist palist) { /* 判别 palist 所指顺序表是否为空表 */ return ( palist->n == 0 ); } 20

21 int locate_seq(pseqlist palist, DataType x) { /* 求 x 在 palist 所指顺序表中的下标 */ int q; for ( q=0; q<palist->n ; q++) if ( palist->element[q] == x) return q ; return -1; } 21

22 int insertpre_seq(pseqlist palist, int p, DataType x) k 0 k 0 k 0 k 1 k 1 k 1 p k 2 3 p p x k 3 k 2 k 2 2 k 4 k 3 k 3 1 k 4 k 4 n=5 n=6 22

23 int insertpre_seq(pseqlist palist, int p, DataType x) { /* 在 palist 所指顺序表中下标为 p 的元素之前插元素 x */ int q; if ( palist->n >= palist-> MAXNUM ) { /* 溢出 */ printf( Overflow!\n ); return 0 ; } if (p<0 p>palist->n ) { /* 不存在下标为 p 的元素 */ printf( Not exist! \n ); return 0 ; } for(q=palist->n - 1; q>=p; q--) /* 插位置及之后的元素均后移个位置 */ palist->element[q+1] = palist->element[q]; palist->element[p] = x; /* 插元素 x */ palist->n = palist->n + 1; /* 元素个数加 1 */ return 1 ; } 23

24 int deletep_seq(pseqlist palist, int p) k 0 k 0 k 1 k 1 p k 2 1 p k 3 k 3 k 4 2 k 4 k 5 3 k 5 n=6 n=5 24

25 int deletep_seq(pseqlist palist, int p) { /* 在 palist 所指顺序表中删除下标为 p 的元素 */ int q; if ( p<0 p>palist->n 1 ) {/* 不存在下标为 p 的元素 */ printf( Not exist!\n ); return 0 ; } for(q=p; q<palist->n-1; q++) /* 被删除元素之后的元素均前移个位置 */ palist->element[q] = palist->element[q+1]; palist->n = palist->n - 1; /* 元素个数减 1 */ return 1 ; } 25

26 int deletev_seq(pseqlist palist, DataType x) 在 palist 所指顺序表中, 删除一个值为 x 的元素, 返回删除成功与否的标志实现的算法只要首先调用locate_seq(palist, x), 在 palist 所指顺序表中寻找一个值为 x 的元素的下标, 假设为 p, 然后调用deleteP_seq(palist, p ) 即可 26

27 在有 n 个元素的线性表里里下标为 i 的元素前插入一个元素需要移动 n-i 个元素, 删除下标为 i 的元素需要移动 n-i-1 个元素若在下标为 i 的位置插入和删除元素的概率分别是 P i 和 P i, 则插入时平均移动元素数为 : 删除时平均移动元素数为 : M i = M d = nx (n i)p i i=0 n 1 X (n i 1)Pi 0 考虑在不不同的下标位置上插入和删除元素的概率相等 i=0 P i = 1 n ; P 0 i = 1 n +1 27

28 顺序表插入和删除操作的平均时间代价和最坏时间代价都是 O(n) 两种特殊情况 : 表后端插入 / 删除的时间代价为 O(1) 根据元素值的定位操作 (locate_seq), 需顺序与表中元素比较, 当定位的概率平均分布在表的所有元素上时, 一次定位平均需要和 n/2 个元素进行行比较, 时间代价为 O(n) 特殊情况 : 如果顺序表中的元素按照值的升 ( 降 ) 序排列列, 则可使用二分法使得定位操作的时间代价减少到 O(log 2 n) 28

29 链接表示 : 实现线性表的另一种存储结构不不连续的存储单元不不要求逻辑关系相邻的两个元素在物理理位置上也相邻存储附加信息通过增加指针来显式地指示元素之间的逻辑关系和后继元素的位置基于链接技术实现的线性表称为链接表或链表 k 1 k 0 k 3 29

30 最简单的链表表示 : 只为每个数据元素关联一个链接, 表示后继关系每个结点包括两个域数据域 : 存放元素本身信息指针域 : 存放其后继结点的存储位置元素链接最后一个元素的指针不不指向任何结点, 称为空指针, 在图示中用表示, 在算法中用 NULL 表示指向链表中第一个结点的指针, 称为这个链表的头指针在单链表里里, 与表里里的 n 个元素对应的 n 个结点通过指针形成一条结点链从表里里的任一个结点都可以找到保存下一个元素的结点 30

31 存储地址数据域指针域 100 D B 113 表头变量 h C F 100 NULL A E 119 h 实际中不不需要关心结点的具体存储地址, 只关心表的逻辑结构 A B C D E F 31

32 struct Node; /* 单链表结点类型 */ typedef struct Node * PNode; /* 结点指针类型 */ struct Node { /* 单链表结点结构 */ DataType info; PNode link; }; typedef struct Node * LinkList ; /* 单链表类型 */ LinkList llist; /*llist 是个链表的头指针 */ 32

33 假设 llist 是某单链表的头指针, 类型是 LinkList, 存储结构如下所示, 当单链表为空表时,llist 的值为 NULL llist 为方便便运算实现, 可以在单链表的第一个结点之前另加一个头结点辅助结点, 不不属于表的内容 k 0 k 1 k n-1 Λ 可以不不存信息, 也可以保存与整个表相关的信息, 如元素个数 Link 域指向表的第一个实际结点 llist 头结点 k 0 k 1 k n-1 Λ 33

34 如果没有, 在表头进行行插入 / 删除时需要修改链表头指针, 在其它位置插入 / 删除时修改其前驱结点的 link, 两种操作需要分别处理理引进头结点使得这两种操作的实现可以统一处理理, 因为表中每个元素都链接在另一个结点的 link 域重点关注带头结点的单链表的操作实现算法 llist k 0 k 1 k n-1 Λ llist 头结点 k 0 k 1 k n-1 Λ 34

35 /* 创建一个带头结点的空单链表 */ LinkList createnulllist_link(void) { LinkList llist; } /* 申请表头结点空间 */ llist=(linklist)malloc(sizeof(struct Node)); if (llist!=null) llist->link=null; else printf( Out of space!\n ); /* 创建失败 */ return llist; 操作正常完成后的状态 : llist 35

36 int isnulllist_link(linklist llist) { return (llist->link==null); } /* 因为 llist 指向头结点, 总是非空, 所以算法中只要检查 llist->link 是否为空即可 */ 36

37 /* 在带头结点的单链表 llist 中找第一个值为 x 的结点存储位置 */ PNode locate_link(linklist llist, DataType x) { PNode p; } if(llist==null) return NULL; /* 找不不到时返回空指针 */ p=llist->link; while (p!=null&&p->info!=x)p=p->link; return p; 37

38 llist info link p k 0 k 1 k i-1 k i k n-1 Λ p->link=q; q->link=p->link; q x 插入算法示意 38

39 int insertpost_link (LinkList llist, PNode p, DataType x) { PNode q=(pnode)malloc(sizeof(struct Node)); /* 申请新结点 */ } if (q==null) { printf(ʺout of Space!\nʺ) ; return 0; } else { } q->info =x; q->link=p->link; p->link=q; return 1; 注意指针更更新次序 39

40 PNode locatepre_link (LinkList llist, PNode p) { PNode p1; if(llist==null) return NULL; p1=llist; while(p1!=null && p1->link!=p) p1=p1->link; return p1; } 40

41 llist info link p q k 0 k 1 k i x k i+2 k n-1 Λ p->link=p->link->link 41

42 int deletev_link(linklist llist, DataType x) { PNode p, q; p = llist; if(p==null) return 0 ; while( p->link!= NULL && p->link->info!= x ) } p = p->link; /* 找值为 x 的结点的前驱结点的存储位置 */ if( p->link == NULL ) { /* 没找到值为 x 的结点 */ printf( Not exist!\n ); return 0 ; } else { } q = p->link; /* 找到值为 x 的结点 */ p->link = q->link; /* 删除该结点 */ free( q ); return 1 ; 42

43 在有 n 个结点的单链表中查找第 i 个结点时, 必须从链表的第一个结点开始往下查找, 所需的时间与 i 的大小成正比, 最坏情况下要查找 n 个结点, 平均情况下需要查找 n/2 个结点, 因此时间复杂度为 O(n) 在单链表中找第一个值为 x 的结点存储位置 ; 在单链表中,p 所指结点前面插入值为 x 的新结点 ; 以及在单链表中删除第一个值为 x 的结点等算法的时间复杂度均为 O(n) 43

44 单链表并非只有一种设计, 可以根据需要和认识修改设计, 例例如前面实现的一个缺点是尾端加入操作的效率低实际中可能经常需要频繁地在表的两端加入元素一种可能是采用下面的结构, 给表对象增加一个对表尾结点的指针 : 这样, 在尾端加入元素, 也能做到 O(1) 注意 : 新设计的链表与前面单链表结构近似, 结构变化应该只影响到表的变动操作, 非变动操作不不需要修改有可能重用前面定义吗? ^ 44

45 将单链表的最后一个结点的指针不不设置为空, 而是指向头一个结点, 这样就得到循环链表循环链表未增加新的存储空间, 但从任一结点出发都能访问所有结点 clist k 0 k 1 k n-1 操作经常要访问修改首结点和末结点, 让表头指针指向循环链表末结点, 可以方便便对表头表尾的操作 clist k 0 k 1 k n-1 45

46 循环链表插入第一个元素时需要特别处理理 : clist k 0 考虑带头结点的循环链表 : clist k 0 k 1 k n-1 46

47 可以采用与单链表一样的数据类型定义创建链表的操作需要修改如有头结点的链表 : llist = (LinkList) malloc( sizeof( Node ) ); if ( llist!= NULL ) llist->link = llist; return llist; 无头结点的表插入第一个结点时, 也需建立循环链接判断空表的操作 ( 有头结点的表 ): return llist->link = llist; 其他操作基本上可以照搬单链表的操作根据所采用的设计, 可能需要做些小调整 47

48 单链表找指定结点的前驱结点比较困难可以设计双链表来克服单链表的这个缺点每个结点都设后继指针和前驱指针, 既可以找到后继也可以直接找到前驱双链表结点结构示意与带有头尾指针的双链表 llink info rlink dlist head rear Λ k 0 k 1 k n-2 k n-1 Λ 48

49 struct DoubleNode; /* 双链表结点 */ typedef struct DoubleNode * PDoubleNode; /* 结点指针类型 */ struct DoubleNode{ /* 双链表结点结构 */ DataType info; PDoubleNode llink, rlink; }; struct Doublelist{ /* 双链表类型 */ PDoubleNode head; /* 指向第一个结点 */ PdoubleNode rear; /* 指向最后一个结点 */ }; 49

50 如果要删除指针变量量 p 所指的结点, 只需要修改该结点的前驱的 rlink 和后继的 llink: if(p -> llink!= NULL) p -> llink -> rlink = p -> rlink; if(p -> rlink!= NULL) p -> rlink -> llink = p -> llink; 50

51 在 p 所指的结点后插入一个新结点, 首先申请一个新结点 q=(pdoublenode)malloc(sizeof(struct DoubleNode)); 修改 p 所指结点的 rlink 和原后继结点的 llink: q -> llink = p; q -> rlink = p -> rlink; p -> rlink -> llink = q; p -> rlink = q; 51

52 顺序存储结构的优点 : 元素之间的逻辑关系是通过存储位置直接反映的, 顺序存储结构中只需存放数据元素自身的信息, 因此, 存储密度大空间利利用率高 ; 元素的位置可以用元素的下标通过简单的解析式计算出来, 因此可以随机存取顺序存储结构的缺点 : 元素的插入和删除运算可能需要移动许多其它元素的位置, 一些长度变化较大的线性表必须按最大需要的空间分配存储 52

53 链接存储结构的优点 : 不不用预先按最大需要分配连续空间 ; 线性表的插入和删除只需修改指针域, 而不不需移动其它元素链接存储结构的缺点 : 每个结点中的指针域需额外占用存储空间, 存储密度小 ; 链接存储结构是一种非随机存储结构, 查找任一结点都要从头指针开始, 沿指针域一个一个地搜索, 这增加了了有些算法的时间代价 53

54 时间代价和空间代价始终是数据结构与算法设计的最主要因素, 然而它们往往是相互对立的一个好的设计总是在时间代价和空间代价之间作出一个好的权衡, 而这种权衡的标准需要根据实际计算机的资源情况和求解问题的特点来确定顺序表和单链表是两种最简单的数据结构, 但是它们的应用非常广泛 54

55 本讲讨论的线性表和随后几讲要讨论的串串栈与队列列都属于线性结构它们之间的区别, 主要是操作的不不同, 所以分别属于几种不不同抽象数据类型的实现 55

Microsoft Word - 专升本练习2：线性表.doc

Microsoft Word - 专升本练习2：线性表.doc 第二章线性表一选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率插入一个元素时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C.