数据结构 第2章线性表A.ppt_第1页
数据结构 第2章线性表A.ppt_第2页
数据结构 第2章线性表A.ppt_第3页
数据结构 第2章线性表A.ppt_第4页
数据结构 第2章线性表A.ppt_第5页
已阅读5页,还剩73页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1,上堂课要点回顾,数据结构课程涉及数学、计算机硬件和计算机软件 数据结构定义指互相有关联的数据元素的集合,用D_S=( D, S ) 或 S=( D, R) 表示。 数据结构内容数据的逻辑结构、存储结构和运算 算法时空效率指标时间效率和空间效率,2,数据结构课程的内容,逻辑结构唯一 存储结构不唯一 运算的实现依赖于存储结构,3,近3周上课内容,第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表,线性结构,若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。,可表示为:(a1 , a2 , , an),线性结构的定义:,(

2、逻辑、存储和运算),4,线性结构的特点:,只有一个首结点; 只有一个尾结点; 除首结点外,其他结点有且只有一个直接前驱 除尾结点外,其他结点有且只有一个直接后继。,线性结构表达式:(a1 , a2 , , an),线性结构包括线性表、堆栈、队列、字符串、数组等等,其中,最典型、最常用的是-,线性表,简言之,线性结构反映结点间的逻辑关系是 一对一 的,见第2章,5,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例,作业,6,(a1, a2, ai-1,ai, ai1 ,, an),2.1 线性表的逻辑结构,1. 线性表的定

3、义:用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标,是元素的序号,表示元素在表中的位置,n为元素总个数,即表长,空表,线性终点,7,例1 分析26 个英文字母组成的英文表,( A, B, C, D, , Z),例2 分析学生情况登记表,数据元素都是记录; 元素间关系是线性,数据元素都是字母; 元素间关系是线性,同一线性表中的元素必定具有相同特性,8,抽象数据类型线性表的定义如下:,ADT List ,数据对象:,D ai | ai ElemSet, i=1,2,.,n, n0 ,数据关系:,R1 |ai-1 ,aiD, i=2,.,n ,基本操

4、作:,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT List,称n为线性表的表长;称n=0时的线性表为空表。,说明: 设线性表为 (a1,a2, . . . ,ai,. . . ,an),则称i为元素ai在线性表中的位序。 在抽象数据类型中定义的各种操作可以看成是基本操作,利用这些操作可以去实现更为复杂的算法。,9,InitList( ,2.根据e的值,在线性表LA中进行查找;,3.若不存在,则插入之;否则,舍弃。,GetElem(LB, i)e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e),操作步骤:,24,GetEle

5、m(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素,则插入之,25,已知一个非纯集合B(B中有值相同的数据元素),试构造一个纯集合 A ,使 A 中只包含 B 中所有值各不相同的数据元素。,仍选用线性表表示集合。,例 2-2,例2-3,26,集合 B,集合 A,从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上,因此,算法的策略应该和例2-1相同,27,void union(List / union,Get

6、Elem(Lb, i, e); / 取Lb中第 i 个元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的元素,则插入之,for (i = 1; i = Lb_len; i+) ,28,若线性表中的数据元素相互之间可以比较,并且数据元素在线性表中依值非递增或非递减有序排列,即有 aiai-1 或 aiai-1(i = 2,3, n),则称该线性表为有序表(Ordered List)。,已知线性表LA和LB是非递减有序表,现要求将LA和LB归并为一个新的线性表LC,且LC仍是非递减

7、有序表。,例2-3,29,例如:LA=(3,5,8,12) LB=(2,6,8,9,12,15,20),则LC=(2,3,5,6,8,8,9,12,12,15,20) 如何得到LC? 先设LC为空表 将LA或LB中的元素逐个插入到LC中。 LC=( ),2, 3, 5, 6, 8, 8, 9, 12, 12, 15, 20,30,void MergeList(List La, List Lb, List / 构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb);,while (i = La_l

8、en) GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; ,32,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); / 插入

9、Lb 表中剩余元素,33,练:判断下列叙述的正误:,数据的逻辑结构是指数据元素之间的逻辑关系,是用户按使用需要建立的。 线性表的逻辑结构定义是唯一的,不依赖于计算机。 数据结构是指相互之间存在一种或多种关系的数据元素的全体。 线性结构反映结点间的逻辑关系是一对一的。 一维向量是线性表,但二维或N维数组不是。 “同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,34,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示 2.2.2 顺序表的实现与运算效率分析,本节小结,作 业,35,最简单的一种顺序表示方法是: 令y和x的存储位置相邻。,顺序表示,

10、用x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系。,2.2.1 线性表的顺序表示,36,用一组地址连续的存储单元, 依次存放线性表中的数据元素。,a1 a2 ai-1 ai an,线性表的起始地址, 称作线性表的基地址。,线性表的顺序表示(续),37,线性表顺序存储特点,1. 逻辑上相邻的数据元素,其物理上也相邻; 若已知表中首元素在存储器中的位置,则其他元素存放位置亦可求出(利用数组下标)。计算方法是(参见存储结构示意图): 设首元素a1的存放地址为LOC(a1)(称为首地址), 设每个元素占用存储空间(地址长度)为L字节, 则表中任一数据元素的存放地址为: LOC(ai) = L

11、OC(a1) + L *(i-1) LOC(ai+1) = LOC(ai)+L,注意:C语言中的数组的下标从0开始, 即:Vn的有效范围是V0Vn-1,38,线性表的顺序存储结构示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,39,顺序映像的 C 语言描述(常称为顺序表),typedef struct SqList; /三个核心成份被定义成一个结构,#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量 #define LISTINCREMENT

12、 10 / 线性表存储空间的分配增量,ElemType *elem; / 存储空间基地址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),40,2.2.2 顺序表的实现与运算效率分析,InitList( if (!L.elem) exit(OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE return OK;,42,顺序表的查找 例如,在顺序表中查找元素38和50,e =,38,i,1,2,3,4,1,8,50,可见,基本操作是: 将顺序表中的元素

13、逐个和给定的值 e 进行比较。,上述过程的实现代码如下:,43,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType x, ElemType y) / 在顺序表中查询第一个满足判定条件的数据元素, / 若存在,则返回它的位序,否则返回 0 / LocateElem_Sq,O( ListLength(L) ),算法的时间复杂度为:,i = 1; / i 的初值为第1元素的位序 p = L.elem; /p的初值为第1元素的存储位置,while (i = L.length ,if (i = L.length) retu

14、rn i; else return 0;,44,线性表操作(插入操作) ListInsert( if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基地址 L.listsize += LISTINCREMENT; / 增加存储容量 ,关于插入算法的省略部分的描述如下: if (i L.length+1) return ERROR; / 插入位置不合法,48,例如:ListInsert_Sq(L, 5, 66) 在线性表L中第5个位置上插入66的过程如下:,L.length-1,0,87,56,42,66,q = ,49,考虑移

15、动元素的平均情况:,假设在第 i 个元素之前插入的概率为pi , 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为:,若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:,50,线性表上删除操作 ListDelete( p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK;,算法时间复杂度为:,O( ListLength(L),p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,元素左移,53,L.length-1,0,

16、87,56,p = ,例如:ListDelete_Sq(L, 5, e) 删除线性表L的第5个数据元素,54,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 qi , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为:,若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:,55,1.线性表顺序存储结构的特征: 逻辑上相关联的数据元素在物理上也相邻; 相邻两个数据元素间,其存储位置相差一个常数。,本节小结,2. 能够进行随机访问; LOC(ai) = LOC(a1) + (i-1)C,3.插入或删除数据元素时,通常要移动相应的数据元素。,56,2

17、.2 线性表的顺序表示和实现,2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.2.3 顺序表的运算效率分析,本节小结,作 业,57,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素,可通过数组Vn来实现。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义:,顺序存储方法:,简言之,逻辑上相邻,物理上也相邻,58,线性表顺序存储特点:,1. 逻辑上相邻的数据元素,其物理上也相邻; 若已知表中首元素在存储器中的位置,则其他元素存放位置亦可求出(利用数组下标)。计算方法是(参见存储结构示意图):

18、 设首元素a1的存放地址为LOC(a1)(称为首地址), 设每个元素占用存储空间(地址长度)为L字节, 则表中任一数据元素的存放地址为: LOC(ai) = LOC(a1) + L *(i-1) LOC(ai+1) = LOC(ai)+L,注意:C语言中的数组的下标从0开始, 即:Vn的有效范围是V0Vn-1,59,线性表的顺序存储结构示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,60,一个一维数组,下标的范围是到,每个数组元素用相邻的个字节存储。存储器按字节编址,设存储

19、数组元素的第一个字节的地址是,则的第一个字节的地址是,113,例1,因此:LOC( M3 ) = 98 + 5 (4-1) =113,解:地址计算通式为:,LOC(ai) = LOC(a1) + L *(i-1),61,用数组V来存放26个英文字母组成的线性表(a,b,c,z),写出在顺序结构上生成和显示该表的C语言程序。,#include #include void build(int V, int n) /*字母线性表的生成,即建表操作*/ int i; V0=a; for(i=1;i=n-1;i+) Vi=Vi-1+1; ,核心语句: 法1 Vi= Vi-1+1; 法2 Vi=a+i;

20、法3 Vi=97+i;,例2,62,void main(void) /*主函数,字母线性表的生成和输出*/ int n=26; /* n是表长,是数据元素的个数,而不是V的 实际下标*/ int v30; build(v, n); display(v, n); ,void display(int V, int n) /*字母线性表的显示,即读表操作*/ int i; for(i=0;i=n-1;i+) printf(%c,vi); printf(n); ,执行结果: a b c d e f g h i j k l m n o p q r s t u v w x y z,63,2.2.2 顺序表

21、的实现(或操作),回忆:数据结构基本运算操作有: 修改、插入、删除、查找、排序,1) 修改 通过数组的下标便可访问某个特定元素并修改之。,核心语句: Vi=x;,显然,顺序表修改操作的时间效率是T(n)=O(1),64,2)插入 在线性表的第i个位置前插入一个元素,实现步骤: 将第n至第i 位的元素向后移动一个位置; 将要插入的元素写到第i个位置; 表长加1。 注意:事先应判断: 插入位置i 是否合法?表是否已满? 应当有1in+1 或 i=1,n+1,for (j=n;j=i;j-) aj+1=aj; ai=x; n+;,/ 元素后移一个位置,/ 插入x,/ 表长加1,核心语句:,65,在线

22、性表的第i个位置前插入一个元素的示意图如下:,a1 a2 ai-1 ai an,66,实现步骤: 将第i 至第n 位的元素向前移动一个位置; 表长减1。 注意:事先需要判断,删除位置i 是否合法? 应当有1in 或 i=1, n,3)删除 删除线性表的第i个位置上的元素,for (j=i+1;j=n;j+) aj-1=aj; n-;,/ 元素前移一个位置,/ 表长减1,核心语句:,67,删除顺序表中某个指定的元素的示意图如下:,ai+1,an,表的长度减少,68,2.2.3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上,因此 计算时间复杂度的基本操作(最深层语句频度) T(n)=

23、O (移动元素次数) 移动元素的个数取决于插入或删除元素的位置.,思考: 若插入在尾结点之后,则根本无需移动(特别快); 若插入在首结点之前,则表中元素全部要后移(特别慢); 若要考虑在各种位置插入(共n+1种可能)的平均移动次数,该如何计算?,讨论1:若在长度为 n 的线性表的第 i 位前 插入一元素,则向后移动元素的次数f(n)为: f(n) =,n i + 1,时间效率分析:,69,讨论2:若在长度为n的线性表上删除第i位元素,向前移动元素的次数f(n)为: f(n) =,思考:若删除尾结点,则根本无需移动(特别快); 若删除首结点,则表中元素全部要前移(特别慢); 若要考虑在各种位置删

24、除(共n种可能)的平均移动次数,该如何计算?,n i,可以证明: 插入、删除操作平均需要移动一半元素(n/ 2) 插入、删除算法的平均时间复杂度为:O(n),显然,顺序表的空间复杂度S(n)=O(1) (没有占用辅助空间),70,证明:假定在每个元素位置上插入x的可能性都一样(即概率P相同),则应当这样来计算平均执行时间: 将所有位置的执行时间相加,然后取平均。 若在首结点前插入,需要移动的元素最多,后移n次; 若在a1后面插入,要后移n-1个元素,后移次数为n-1; 若在an-1后面插入,要后移1个元素; 若在尾结点an之后插入,则后移0个元素; 所有可能的元素移动次数合计: 0+1+n =

25、 n(n+1)/2,所以平均移动次数为:n(n+1)/2(n+1)n/2O(n),共有多少种插入形式?连头带尾有n+1种,同理可证:顺序表删除一元素的时间效率为: T(n)=(n-1)/2 O(n),71,教材P25算法2.5也是对执行效率的推导:,假定在表中任意位置插入、删除元素都是等概率的, 插入概率p(i)=1/(n+1) ,删除概率q(i)=1/n ,则:,插入操作时间效率(平均移动次数),删除操作时间效率(平均移动次数),72,本节小结,线性表顺序存储结构特点:逻辑关系上相邻的两个元素在物理存储位置上也相邻; 优点:可以随机存取表中任一元素; 缺点:在插入,删除某一元素时,需要移动大量元素。 为克服这一缺点,我们引入另一种存储形式:,链式存储结构,见2.3节,73,2.3 线性表的链式表示和实现,2.3.1 链表的表示 2.3.2 链表的实现 2.3.3 链表的运算效率分析,本节小结,作 业,74,2.3.

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论