第3章-线性表

数据结构与算法电子工业出版社数据结构与算法作者：胡明王红梅出版社：电子工业出版社邮箱：[e-mail]数据结构与算法电子工业出版社第3章线性表线性表的逻辑结构线性表的存储结构及实现应用实例本章的基本内容是：数据结构与算法电子工业出版社3.1引言数据元素之间的关系是什么？数据结构与算法电子工业出版社3.1引言数据元素之间的关系是什么？现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？数据结构与算法电子工业出版社3.1引言约瑟夫环问题设n(n0)个人围成一个环，n个人的编号分别为1，2，……，n，从第1个人开始报数，报到m时停止报数，报m的人出环，再从他的下一个人起重新报数，报到m时停止报数，报m的出环，……，如此下去，直到所有人全部出环为止。当任意给定n和m后，求n个人出环的次序。n=5,m=3时的出圈次序：约瑟夫环问题的数据模型是一种典型的环状线性结构。如何存储这种环形结构并求解约瑟夫环的出环次序呢？数据结构与算法电子工业出版社线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)3.2线性表的逻辑结构线性表的定义其中，ai（1≤i≤n）称为数据元素；下角标i表示该元素在线性表中的位置或序号。数据结构与算法电子工业出版社a1a3a4ana23.2线性表的逻辑结构线性表的特性1.有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1,ai)，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。数据结构与算法电子工业出版社线性表的抽象数据类型定义ADTListData线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系OperationInitList前置条件：表不存在输入：无功能：表的初始化输出：无后置条件：建一个空表3.2线性表的逻辑结构数据结构与算法电子工业出版社DestroyList前置条件：表已存在输入：无功能：销毁表输出：无后置条件：释放表所占用的存储空间Length前置条件：表已存在输入：无功能：求表的长度输出：表中数据元素的个数后置条件：表不变3.2线性表的逻辑结构线性表的抽象数据类型定义数据结构与算法电子工业出版社Get前置条件：表已存在输入：元素的序号i功能：在表中取序号为i的数据元素输出：若i合法，返回序号为i的元素值，否则抛出异常后置条件：表不变Locate前置条件：表已存在输入：数据元素x功能：在线性表中查找值等于x的元素输出：若查找成功，返回x在表中的序号，否则返回0后置条件：表不变3.2线性表的逻辑结构线性表的抽象数据类型定义数据结构与算法电子工业出版社Insert前置条件：表已存在输入：插入i；待插x功能：在表的第i个位置处插入一个新元素x输出：若插入不成功，抛出异常后置条件：若插入成功，表中增加一个新元素Delete前置条件：表已存在输入：删除位置i功能：删除表中的第i个元素输出：若删除成功，返回被删元素，否则抛出异常后置条件：若删除成功，表中减少一个元素3.2线性表的逻辑结构线性表的抽象数据类型定义数据结构与算法电子工业出版社Empty前置条件：表已存在输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0后置条件：表不变ADT进一步说明:（1）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。3.2线性表的逻辑结构线性表的抽象数据类型定义数据结构与算法电子工业出版社3.3线性表的存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素数据结构与算法电子工业出版社顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度3.3线性表的存储结构及实现数据结构与算法电子工业出版社顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434如何实现顺序表的内存分配？顺序表一维数组3.3线性表的存储结构及实现数据结构与算法电子工业出版社0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：数组的长度Max线性表的长度Length数组的长度大于等于当前线性表的长度3.3线性表的存储结构及实现数据结构与算法电子工业出版社顺序表存储结构的定义3.3线性表的存储结构及实现数据结构与算法电子工业出版社如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)3.3线性表的存储结构及实现数据结构与算法电子工业出版社0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度Loc(ai)=Loc(a1)+(i-1)×c随机存取：在O(1)时间内存取数据元素一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)3.3线性表的存储结构及实现数据结构与算法电子工业出版社存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对查找操作的时间性能的一种描述。存储结构和存取结构“顺序表是一种随机存取的存储结构”的含义为：在顺序表这种存储结构上进行的查找操作，其时间性能为O(1)。3.3线性表的存储结构及实现数据结构与算法电子工业出版社操作接口：voidInitList(SeqList&L)算法描述：voidSeqList(SeqList&L){L.length=0;}顺序表的实现——初始化顺序表datalength03.3线性表的存储结构及实现数据结构与算法电子工业出版社操作接口：voidCreat(SeqList&L,DataTypea[],intn)顺序表的实现——建立顺序表顺序表数组a3512243342535122433423.3线性表的存储结构及实现数据结构与算法电子工业出版社voidCreat(SeqList&L,DataTypea[],intn){if(nMaxSize){printf(参数非法);exit(-1);}for(i=0;in;i++)L.data[i]=a[i];L.length=n;}算法描述：3.3线性表的存储结构及实现顺序表的实现——建立顺序表数据结构与算法电子工业出版社操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x,ai,…,an)顺序表的实现——插入ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化3.3线性表的存储结构及实现数据结构与算法电子工业出版社33例：（35，12，24，42），在i=2的位置上插入33。表满：length=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序号）顺序表的实现——插入435122442a1a2a3a401234422412335什么时候不能插入？注意边界条件3.3线性表的存储结构及实现数据结构与算法电子工业出版社1.如果表满了，则抛出上溢异常;2.如果元素的插入位置不合理，则抛出位置异常;3.将最后一个元素至第i个元素分别向后移动一个位置；4.将元素x填入位置i处；5.表长加1；算法描述——伪代码顺序表的实现——插入3.3线性表的存储结构及实现数据结构与算法电子工业出版社voidInsert(SeqList&L,inti,DataTypex){if(L.length=MaxSize){printf(上溢);exit(-1);}if(i1||ilength+1){printf(位置);exit(-1);}for(j=L.length;j=i;j--)//j表示元素序号L.data[j]=L.data[j-1];L.data[i-1]=x;L.length++;}算法描述——C描述顺序表的实现——插入基本语句？3.3线性表的存储结构及实现数据结构与算法电子工业出版社最好情况（i=n+1）：基本语句执行0次，时间复杂度为O(1)。最坏情况（i=1）：基本语句执行n+1次，时间复杂度为O(n)。平均情况（1≤i≤n+1）：时间复杂度为O(n)。时间性能分析顺序表的实现——插入+-+=11)=1(niiinp+-++=11)=1(11niinn2n=O(n)3.3线性表的存储结构及实现数据结构与算法电子工业出版社操作接口：DataTypeDelete(inti)删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)顺序表的实现——删除ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化3.3线性表的存储结构及实现数据结构与算法电子工业出版社例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出伪代码和C描述的算法；3.分析时间复杂度。顺序表的实现——删除535a1a2a3a401234422412334a51224423.3线性表的存储结构及实现数据结构与算法电子工业出版社顺序表的实现——按位查找操作接口：DataTypeGet(inti)0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲n算法描述：DataTypeGet(SeqList&L,inti){if(i1&&iL.length){printf(查找位置非法);exit(-1);}elsereturnL.data[i-1];}时间复杂度？3.3线性表的存储结构及实现数据结构与算法电子工业出版社顺序表的实现——按值查找操作接口：intLocate(DataTypex)535a1a2a3a40123442241233a5例：在（35,33,12,24,42）中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系3.3线性表的存储结构及实现数据结构与算法电子工业出版社intLocate(SeqList&L,DataTypex){for(i=0;iL.length;i++)if(L.data[i]==x)returni+1;//返回序号i+1return0;//退出循环，说明查找失败}顺序表的实现——按值查找算法描述：时间复杂度？3.3线性表的存储结构及实现数据结构与算法电子工业出版社顺序表的优缺点顺序表的优点：⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；⑵随机存取：可以快速地存取表中任一位置的元素。顺序表的缺点：⑴插入和删除操作需要移动大量元素；⑵表的容量难以确定，表的容量难以扩充；⑶造成存储空间的碎片。3.3线性表的存储结构及实现数据结构与算法电子工业出版社单链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。单链表静态存储分配顺序表事先确定容量链表动态存储分配运行时分配空间连续不连续零散分布3.3线性表的存储结构及实现数据结构与算法电子工业出版社0200020803000325…………存储特点：1.逻辑次序和物理次序不一定相同。2.元素之间的逻辑关系用指针表示。例：(a1,a2,a3,a4)的存储示意图单链表a10200a20325a30300a4∧3.3线性表的存储结构及实现数据结构与算法电子工业出版社单链