《数据结构——第二章线性表》由会员分享，可在线阅读，更多相关《数据结构——第二章线性表（81页珍藏版）》请在金锄头文库上搜索。
1、数据结构 第二章,主讲人:陈频,第二章 线性表,2.1 线性表的逻辑结构（掌握） 2.2 线性表的顺序存储及实现（掌握） 2.3 线性表的链接存储及实现（掌握） 2.4 顺序表和单链表的比较（掌握） 2.5 线性表的其他存储及实现（了解） 2.6 应用举例（理解）,知识结构图,线性表,逻辑结构,存储结构,基 本 概 念,抽类 象型 数定 据义,顺 序 存 储 结 构,链 接 存 储 结 构,其 他 存 储 方 法,（1）线性表定义 （2）逻辑特征,（1）ADT定义 （2）基本操作,（1）顺序表的特点 （2）顺序表类定义 （3）基本操作的 实现及时间性能,（1）单链表的特点 （2）单链表类定义
2、（3）基本操作的 实现及时间性能,（1）循环链表 （2）双链表 （3）静态链表 （4）间接寻址,比较,引言,珍珠序列,线性表应用的一个实例,学生成绩登记表,2.1 线性表的逻辑结构,姓 名,英语,数据结构,高数,学号,丁一,96,78,87,0101,李二,87,90,78,0102,张三,67,86,86,0103,孙红,69,81,96,0104,王冬,87,74,66,0105,1.线性表：简称表，是n（n0）个具有相同类型的数据元素的有限序列。 2.线性表的长度：线性表中数据元素的个数。 3.空表：长度等于零的线性表，记为：L=( )。 4.非空表记为：L（a1, a2 , , ai-
3、1, ai , , an),2.1 线性表的逻辑结构,2.1.1线性表的定义,其中，ai（1in）称为数据元素； 下角标 i 表示该元素在线性表中的位置或序号 。,2.1 线性表的逻辑结构,线性表的图形表示,线性表（a1, a2 , , ai-1, ai , , an)的图形表示如下：,2.1 线性表的逻辑结构,线性表的特性,1.有限性：线性表中数据元素的个数是有穷的。,2.相同性：线性表中数据元素的类型是同一的。,2.1.2线性表的抽象数据类型定义,ADT List Data线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系 Operation InitList 前置条件：表不存在输
4、入：无功能：表的初始化输出： 无后置条件：建一个空表,2.1 线性表的逻辑结构,DestroyList前置条件：表已存在输入：无功能：销毁表输出：无后置条件：释放表所占用的存储空间 Length 前置条件：表已存在输入：无功能：求表的长度输出：表中数据元素的个数 后置条件：表不变,2.1 线性表的逻辑结构,Get前置条件：表已存在输入：元素的序号i功能：在表中取序号为i的数据元素输出：若i合法，返回序号为i的元素值，否则抛出异常后置条件：表不变 Locate前置条件：表已存在输入：数据元素功能：在线性表中查找值等于的元素输出：若查找成功，返回在表中的序号，否则返回0后置条件：表不变,2.1 线
5、性表的逻辑结构,Insert前置条件：表已存在输入：插入i；待插功能：在表的第i个位置处插入一个新元素输出：若插入不成功，抛出异常后置条件：若插入成功，表中增加一个新元素 Delete前置条件：表已存在输入：删除位置i功能：删除表中的第i个元素输出：若删除成功，返回被删元素，否则抛出异常后置条件：若删除成功，表中减少一个元素,2.1 线性表的逻辑结构,Empty前置条件：表已存在输入：无功能：判断表是否为空输出：若是空表，返回1，否则返回0后置条件：表不变 endADT,进一步说明: （1）线性表的基本操作根据实际应用是而定； （2）复杂的操作可以通过基本操作的组合来实现； （3）对不同的应用
6、，操作的接口可能不同。,2.1 线性表的逻辑结构,2.2 线性表的顺序存储结构及实现,2.2.1顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,2.2 线性表的顺序存储结构及实现,2.2.1顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,用什么属性来描述顺序表？,数组,2.2 线性表的顺序存储结构及实现,2.2.1顺序表线性表的顺序存储结构,例：（34, 23, 67, 43）,34,23,67,43,4,如何实现顺序表的内存分配？,如何求得任意元素的存储地址？,0 i-2 i-1 n-1 Ma-1,a
7、1,ai-1,ai,an,空闲,长度,2.2 线性表的顺序存储结构及实现,顺序表存储示意图:,一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储：,Loc(ai)=Loc(a1) + (i -1)c,随机存取：在O(1)时间内存取数据元素,2.2 线性表的顺序存储结构及实现,存储结构是数据及其逻辑结构在计算机中的表示； 存取结构是在一个数据结构上对查找操作的时间性能的一种描述。,存储结构和存取结构,“顺序表是一种随机存取的存储结构”的含义为：在顺序表这种存储结构上进行的查找操作，其时间性能为O(1)。,顺序表类的声明,const int MaSize=100; templa
8、te /模板类 class SeqList public:SeqList( ) ; /构造函数SeqList(T a , int n); SeqList( ) ; /析构函数int Length( ); /求长度T Get(int i); /按位查找int Locate(T ); /按值查找void Insert(int i, T ); /插入T Delete(int i); /删除void PrintList(); /遍历 private:T dataMaSize; /数组int length; /长度 ;,2.2 线性表的顺序存储结构及实现,构造函数,构造函数的作用是初始化一个对象的成员变
9、量。 构造函数的特点: 1. 构造函数必须与类名相同； 2. 必须声明为类的公有成员函数； 3. 不可以有返回值也不得指明返回类型； 4. 构造函数可以重载。,构造函数的作用是什么（What）？ 什么时候（When）调用？ 由谁（Who）来调用？,析构函数,析构函数用于在一个对象被撤消时删除其成员变量，其标志是在类的名字前面加上“”。 析构函数特点: 1.析构函数没有参数和返回值; 2.一个类只能有一个析构函数; 3. 析构函数不允许重载。,析构函数的作用是什么（What）？ 什么时候（When）调用？ 由谁（Who）来调用？,操作接口：SeqList( ),算法描述： SeqList:Seq
10、List( ) length=0; ,2.2 线性表的顺序存储结构及实现,1.顺序表的实现无参构造函数,0,创建一个空的顺序表!,操作接口：SeqList(T a , int n),1.顺序表的实现有参构造函数,2.2 线性表的顺序存储结构及实现,5,35,12,24,33,42,创建一个长度为n的具有给定数组元素的顺序表!,template SeqList:SeqList(T a , int n) if (nMaSize) throw “参数非法“;for (i=0; i=MaSize 合理的插入位置：1ilength+1（i指的是元素的序号）,2.2 线性表的顺序存储结构及实现,2.顺序表
11、的实现插入,4,35,12,24,42,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,什么时候不能插入？,1. 如果表满了，则抛出上溢异常; 2. 如果元素的插入位置不合理，则抛出位置异常; 3. 将最后一个元素至第i个元素分别向后移动一个位置； 4. 将元素填入位置i处； 5. 表长加1；,算法描述伪代码,2.2 线性表的顺序存储结构及实现,2.顺序表的实现插入,template void SeqList:Insert(int i, T ) if (length=MaSize) throw “上溢“;if (ilength+1) throw “位置“;for (j=le
12、ngth; j=i; j-)dataj=dataj-1; /元素后移datai-1=;length+; ,算法描述C+描述,2.2 线性表的顺序存储结构及实现,2.顺序表的实现插入,基本语句？,最好情况（ i=n+1）：基本语句执行0次，时间复杂度为O(1)。 最坏情况（ i=1）：基本语句执行n+1次，时间复杂度为O(n)。 平均情况（1in+1）：时间复杂度为O(n)。,时间性能分析,2.2 线性表的顺序存储结构及实现,2.顺序表的实现插入,操作接口： T Delete(int i) 删除前：(a1, , ai-1,ai,ai+1,an) 删除后：(a1,ai-1,ai+1, ,an),3
13、.顺序表的实现删 除,2.2 线性表的顺序存储结构及实现,ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,例：（35, 33, 12, 24, 42），删除i=2的数据元素。,2.2 线性表的顺序存储结构及实现,3.顺序表的实现删 除,5,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,12,24,42,35,什么时候不能插入？,表空：length=0 合理的删除位置：1ilength（i指的是元素的序号）,1. 如果表空，则抛出下溢异常; 2. 如果元素的插入位置不合理，则抛出位置异常; 3. 取出被删元素； 4.
14、将被删后的元素开始依次向前移动； 5. 表长减1,返回被删元素值；,算法描述伪代码,2.2 线性表的顺序存储结构及实现,3.顺序表的实现删除,template void SeqList:Delete(int i) if (length=0) throw “下溢“;if (ilength) throw “位置“; = datai-1;for (j=i; jlength; j+)dataj-1=dataj; /元素前移length-;return ; ,算法描述C+描述,2.2 线性表的顺序存储结构及实现,3.顺序表的实现删除,基本语句？,最好情况（ i=n）：基本语句执行0次，时间复杂度为O(1)。 最坏情况（ i=1）：基本语句执行n次，时间复杂度为O(n)。 平均情况（1in）：时间复杂度为O(n)。,
