《线性表顺序表》PPT课件.ppt

《《线性表顺序表》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《线性表顺序表》PPT课件.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章第二章第二章 线性表线性表线性表线性表 线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储及实现 顺序表和单链表的比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：学生成绩登记表学生成绩登记表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构姓姓 名名英语英语数据结构数据结构高数高数学号学号丁一丁一9678870101李二李二8790780102张三张三6786860103孙红孙红6981960104王冬王冬8774660105每

2、行是一个数据元素每行是一个数据元素数据元素之间的关系是数据元素之间的关系是1:11:1的线性关系的线性关系职工工资登记表职工工资登记表2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构姓姓 名名岗位津贴岗位津贴基本工资基本工资奖金奖金职工号职工号丁一丁一6002782000101李二李二3001901000102张三张三3001861000103孙红孙红5002182000104王冬王冬3001901000105每行是一个数据元素每行是一个数据元素数据元素之间的关系是数据元素之间的关系是1:11:1的线性关系的线性关系线性表：线性表：简称表，是简称表，是n（n0）

3、个具有）个具有相同类型相同类型的数据的数据元素的元素的有序（前后次序）序有序（前后次序）序列列。线性表的长度：线性表的长度：线性表中数据元素的个数。线性表中数据元素的个数。空表：空表：长度等于零的线性表，长度等于零的线性表，记为：记为：L=()。非空表非空表记为：记为：L（a1,a2,ai-1,ai,an)2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的定义线性表的定义其中，其中，ai（1in）称为数据元素；）称为数据元素；下角标下角标 i 表示该元素在线性表中的位置或序号表示该元素在线性表中的位置或序号。a1a3a4ana22.1 2.1 线性表的逻辑

4、结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的图形表示线性表的图形表示线性表线性表（a1,a2,ai-1,ai,an)的图形表示如下：的图形表示如下：a1a3a4ana22.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的特性线性表的特性1.有限性：线性表中数据元素的个数是有穷的。有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素顺序性：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系，即，即ai-1是是ai的直接前

5、驱，的直接前驱，ai是是ai-1的的直接后继；直接后继；a1 无前驱，无前驱，an无后继，其它每个元素有且无后继，其它每个元素有且仅有一个直接前驱和一个直接后继。仅有一个直接前驱和一个直接后继。线性表的抽象数据类型定义线性表的抽象数据类型定义ADT List Data 线性表中的数据元素具有相同类型，线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系 Operation InitList 前置条件前置条件：表不存在：表不存在 输入输入：无：无 功能功能：表的初始化：表的初始化 输出输出：无无 后置条件后置条件：建一个空表：建一个空表2.1 2.1 线性表的逻辑

6、结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构DestroyList 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：销毁表：销毁表 输出输出：无：无 后置条件后置条件：释放表所占用的存储空间：释放表所占用的存储空间Length 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：求表的长度：求表的长度 输出输出：表中数据元素的个数：表中数据元素的个数 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义（续）线性表的抽象数据类型定义（续）Get 前置条件前置条件：表已存在

7、：表已存在 输入输入：元素的序号：元素的序号i 功能功能：在表中取序号为：在表中取序号为i的数据元素的数据元素 输出输出：若：若i合法，返回序号为合法，返回序号为i的元素值，否则抛出异常的元素值，否则抛出异常 后置条件后置条件：表不变：表不变Locate 前置条件前置条件：表已存在：表已存在 输入输入：数据元素：数据元素x 功能功能：在线性表中查找值等于：在线性表中查找值等于x的元素的元素 输出输出：若查找成功，返回：若查找成功，返回x在表中的序号，否则返回在表中的序号，否则返回0 后置条件后置条件：表不变：表不变2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构

8、线性表的抽象数据类型定义线性表的抽象数据类型定义Insert前置条件前置条件：表已存在：表已存在输入输入：插入：插入i；待插待插x功能功能：在表的第：在表的第i个位置处插入一个新元素个位置处插入一个新元素x输出输出：若插入不成功，抛出异常：若插入不成功，抛出异常 后置条件后置条件：若插入成功，表中增加一个新元素：若插入成功，表中增加一个新元素Delete前置条件前置条件：表已存在：表已存在输入输入：删除位置：删除位置i功能功能：删除表中的第：删除表中的第i个元素个元素 输出输出：若删除成功，返回被删元素，否则抛出异常：若删除成功，返回被删元素，否则抛出异常 后置条件后置条件：若删除成功，表中减

9、少一个元素：若删除成功，表中减少一个元素2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义Empty 前置条件前置条件：表已存在：表已存在 输入输入：无：无 功能功能：判断表是否为空：判断表是否为空 输出输出：若是空表，返回：若是空表，返回1，否则返回，否则返回0 后置条件后置条件：表不变：表不变ADT List进一步说明进一步说明:（1 1）线性表的基本操作根据实际应用而定；）线性表的基本操作根据实际应用而定；（2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用

10、，操作的接口可能不同。对不同的应用，操作的接口可能不同。2.1 2.1 线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67,43）34236743存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67

11、,43）34236743存储空间存储空间 10用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度 42.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构例：例：（34,23,67,43）34236743 10如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组和两一维数组和两个整型变量个整型变量 4如何求得任意元素的存储地址？如何求得任意元素的存储地址？0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度

12、2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表一般情况下，一般情况下，(a1，a2，,ai-1，ai,an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)Loc(aLoc(ai i)表示数据元素表示数据元素a ai i的地址的地址 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度Loc(ai)=Loc(a1)+(i-1)c随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表顺序表一般情况下，一般情况下，(a1，a2，,ai-1，ai,an)的顺

13、序存储：的顺序存储：cLoc(ai)Loc(a1)数据元素数据元素a ai i地址的计算地址的计算公式公式2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现存储存储结构是数据及其逻辑结构在计算机中的表示；结构是数据及其逻辑结构在计算机中的表示；存取存取结构是在一个数据结构上对查找操作的时间性结构是在一个数据结构上对查找操作的时间性能的一种描述。能的一种描述。存储结构和存取结构存储结构和存取结构 “顺序表是一种顺序表是一种顺序存储、随机存取顺序存储、随机存取的的存储存储结构结构”的含义为：在顺序表这种存储结构上进行的查找操的含义为：在顺序表这种存储结构上进行的查找操作，其时间性能为作，

14、其时间性能为O(1)。顺顺序序表表类类型型的的描描述述顺序表类型的示意图顺序表类型的示意图12.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现34236743 10 4分析：这是一个结构体类型，由分析：这是一个结构体类型，由3 3个数据成员组成个数据成员组成(1)(1)一维数组，存放线性表的元素一维数组，存放线性表的元素(2)(2)总容量总容量(数组的数组的长度数组的数组的长度)(3)(3)线性表的长度线性表的长度给出上述顺序表类型的定义：给出上述顺序表类型的定义：#define MAXSIZE 100typedef struct listElemType elemMAXSIZE;/

15、*ElemType 为数据元素类型*/int listsize;int length;SqList;SqList L,*p=&L;L的数据成员如何表示的数据成员如何表示（1）L.elemi,L.length,L.listsize（2）p-elemi,p-length,p-listsize 顺顺序序表表类类型型的的描描述述顺序表类型的示意图顺序表类型的示意图22.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现分析：这是一个结构体类型，由分析：这是一个结构体类型，由3 3个数据成员组成个数据成员组成(1)(1)指针变量，存放一维数组的首地址指针变量，存放一维数组的首地址(2)(2)总容量

16、总容量(数组的长度数组的长度)(3)(3)线性表的长度线性表的长度34236743 10 4 给出上述结构体类型的定义：给出上述结构体类型的定义：typedef struct listElemType*elem;/*连续空间的申请由初始化完成连续空间的申请由初始化完成*/int listsize;int length;SqList;操作接口：操作接口：int InitSqlist(SqList&L)2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现初始化（方案初始化（方案1）？L初始化前顺序表类型变量初始化前顺序表类型变量L L的存储空间示意图的存储空间示意图

17、？n 0L调用初始化操作之后调用初始化操作之后L L的存储空间示意图的存储空间示意图n n为符号常量为符号常量MAXSIZEMAXSIZE算法描述：算法描述：int InitSqlist(SqList&L)L.listsize=MAXSIZE;L.length=0;return 1;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现初始化（方案初始化（方案1）操作接口：操作接口：int InitSqlist(SqList&L,int n)2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现初始化（方案初始化（方案2）?L调用初始

18、化操作之前调用初始化操作之前L L的存储空间示意图的存储空间示意图?n 0 L调用初始化操作之后调用初始化操作之后L L的存储空间示意图的存储空间示意图算法描述：算法描述：int InitSqlist(SqList&L,int n)L.elem=new ElemTypen;if(L.elem=NULL)printf(“空间分配失败空间分配失败”);exit(0);L.listsize=n;L.length=0;return 1;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现初始化（方案初始化（方案2）操作接口操作接口 int InsertSqlist(Sq

19、List&L,int i,ElemType x)插入前：插入前：(a1,ai-1,ai,an)插入后：插入后：(a1,ai-1,x,ai,an)顺序表的实现顺序表的实现插入插入2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化33例：例：（35，12，24，42），），在在i=2的位置上插入的位置上插入33。表满：表满：length=listsize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素

20、的序号）指的是元素的序号）2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入 435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件1.如果表满了，则抛出如果表满了，则抛出上溢上溢异常异常;2.如果元素的插入位置不合理，则抛出如果元素的插入位置不合理，则抛出位置位置异常异常;3.将最后一个元素至第将最后一个元素至第i个元素分别向后移动一个位置；个元素分别向后移动一个位置；4.将元素将元素x填入位置填入位置i处；处；5.表长加表长加1；算法描述算法描述伪代码伪代码2.2 线性表的顺

21、序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入int InsertSqlist(SqList&L,int i,ElemType x)if(L.length=L.listsize)printf()printf(上溢上溢);return 0;if(iL.length+1)printf(位置非法位置非法);return 0;for(j=length;j=i;j-)-)L.elemj=L.elemj-1;L.elemi-1=x;L.length+;return 1;算法描述算法描述C描述描述2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现

22、插入插入基本语句基本语句？最好最好情况（情况（i=n+1）：）：基本语句执行基本语句执行0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（i=1）：）：基本语句执行基本语句执行n次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：）：时间复杂度为时间复杂度为O(n)。时间性能分析时间性能分析2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现插入插入+-+=11)=1(niiinp+-+=11)=1(11niinn2n=O(n)操作接口：操作接口：int DeleteSqlist(SqList&L,int i,ElemTyp

23、e&x)删除前：删除前：(a1,ai-1,ai,ai+1,an)删除后：删除后：(a1,ai-1,ai+1,an)顺序表的实现顺序表的实现删删 除除2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化例：（例：（35,33,12,24,42），），删除删除i=2的数据元素。的数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1.分析边界条件；分析边界条件；2.分别给出伪代码和分别给出伪代码和C描述的算

24、法；描述的算法；3.分析时间复杂度。分析时间复杂度。2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现删除删除 535a1a2a3a40 1 2 3 4422412334a5122442顺序表的实现顺序表的实现按位查找按位查找操作接口：操作接口：int GetSqlist(SqList L,int i)2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 n算法描述：算法描述：int GetSqlist(SqList L,int i)if(i=1&i=L.length)ret

25、urn i-1;else return-1;时间复杂度时间复杂度？O(1)顺序表的实现顺序表的实现按值查找按值查找操作接口：操作接口：int LocateSqlist(SqList L,ElemType x)2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现 535a1a2a3a40 1 2 3 442241233a5例：在（例：在（35,33,12,24,42）中查找值为中查找值为12的元素，的元素，返回在表中的序号。返回在表中的序号。iii注意序号和下标之间的关系注意序号和下标之间的关系int LocateSqlist(SqList L,ElemType x)for(i=0;iL

26、.length;i+)if(L.elem(L.elemi=x)return i+1;return 0;2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现顺序表的实现顺序表的实现按值查找按值查找算法描述：算法描述：时间复杂度时间复杂度？最好情况：最好情况：O(1)最差情况：最差情况：O(n)平均情况：平均情况：O(n)顺序表的优缺点顺序表的优缺点 顺序表的优点：顺序表的优点：无需为表示表中元素之间的逻辑关系而增加额外的无需为表示表中元素之间的逻辑关系而增加额外的存储空间；存储空间；随机存取：可以快速地存取表中任一位置的元素。随机存取：可以快速地存取表中任一位置的元素。顺序表的缺点：顺序表的缺点：插入和删除操作需要移动大量元素；插入和删除操作需要移动大量元素；表的容量难以确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充；2.2 线性表的顺序存储结构及实现线性表的顺序存储结构及实现