数据结构c版第2章线性表(1).ppt

1 第2章 线性表 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： 2 2.1 线性表的逻辑结构 学生成绩登记表 姓 名英语数据结构高数学号 丁一9678870101 李二8790780102 张三6786860103 孙红6981960104 王冬8774660105 数据元素之间的关系是什么？ 3 线性表：简称表，是n（n0）个具有相同类型的数 据元素的有限序列。 线性表的长度：线性表中数据元素的个数。 空表：长度等于零的线性表，记为：L=( )。 非空表记为：L（a1, a2 , , ai-1, ai , , an) 线性表的定义 其中，ai（1in）称为数据元素； 下角标 i 表示该元素在线性表中的位置或序号，称元素 ai位于表的第 i 个位置，或称 ai是表中的第 i 个元素 。 4 a1a3a4ana2 线性表的图形表示 线性表（a1, a2 , , ai-1, ai , , an)的图形表 示如下： 5 a1a3a4ana2 线性表的特性 1.有限性：线性表中数据元素的个数是有穷的。 2.相同性：线性表中数据元素的类型是同一的。 3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在 序偶关系(ai-1, ai)，即ai-1是ai的前驱， ai是ai-1的 后继；a1 无前驱，an无后继，其它每个元素有且仅有 一个前驱和一个后继。 6 线性表的抽象数据类型定义 见教材P50 线性表ADT的几点说明 （1）对于不同的应用，线性表的基本操作是不同的； （2）复杂的操作可以通过基本操作的组合来实现； （3）对不同的应用，操作的接口可能不同。 7 顺序表线性表的顺序存储结构 例：（34, 23, 67, 43） 存储要点 用一段地址连续的存储单元 依次存储线性表中的数据元素 34236743 4 2.2 线性表的顺序存储结构及实现 8 例：（34, 23, 67, 43） 34236743 4 如何实现顺序表的内存分配？ 顺序表一维数组 9 顺序表线性表的顺序存储结构 例：（34, 23, 67, 43） 34236743 存储空间的起始位置 4 用什么属性来描述顺序表？ 顺序表的容量（最大长度） 顺序表的当前长度 10 如何描述顺序存储结构需要的三个属性？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲 表的长度 一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储 ： (1)存储空间的起始位置：数组名 data (2)顺序表的存储容量:数组长度MaxSize (3)顺序表的当前长度：length length 11 区分：“数组的长度”和“线性表的长度” 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲 表的长度 一般情况下，(a1，a2，, ai-1，ai , , an)的顺序存储 ： (1)前者确定不变 后者变化 (2)线性表的长度 /模板类 class SeqList public: SeqList( ) ; /构造函数 SeqList(T a , int n); SeqList( ) ; /析构函数 int Length( ); T Get(int i); int Locate(T x ); void Insert(int i, T x); T Delete(int i); 18 顺序表类的声明 private: T dataMaxSize; int length; ; 19 template /模板的标志 T Max(T x, T y) return x=y? x: y; int i=Max(1, 2); double x=Max(1.2, 2.5); 函数Max 要返回两个参数中的最大者，如何定义 一个具有通用功能的函数Max，支持不同类型的 参数和返回值？ 20 构造函数的作用是初始化一个对象的成员变量。 构造函数的特点: 1. 构造函数必须与类名相同； 2. 必须声明为类的公有成员函数； 3. 不可以有返回值也不得指明返回类型； 4. 构造函数可以重载。 21 构造函数的作用是什么（What）？ 什么时候（When）调用？ 由谁（Who）来调用？ What:构造函数为成员变量分配存储空间并初始化 When:在声明一个对象变量是该类的一个实例时调用 Who:由系统根据实参自动调用相应的构造函数 22 操作接口SeqList( )：创建一个空的顺序表 算法描述： SeqList:SeqList( ) length=0; 顺序表的实现无参构造函数 data length 0 23 操作接口SeqList(T a , int n)：创建一个 长度为n的顺序表 顺序表的实现有参构造函数 顺序表 数组a 3512243342 5 3512243342 24 template SeqList:SeqList(T a , int n) if (nMaxSize) throw “参数非法“; for (i=0; i=MaxSize 合理的插入位置：1ilength+1（i指的是元素的序号 ） 顺序表的实现插入 4 35122442 a1a2a3a4 0 1 2 3 4 42241233 5 什么时候不能插入？注意边界条件 30 1. 如果表满了，则抛出上溢异常; 2. 如果元素的插入位置不合理，则抛出位置 异常; 3. 将最后一个元素至第i个元素分别向后移动 一个位置； 4. 将元素x填入位置i处； 5. 表长加1； 算法描述伪代码 顺序表的实现插入 31 顺序表的实现插入 1 如果顺序表已满 ，抛出上溢异常 2 如果元素插入位 置不存在，抛出 位置异常 3 将最后一个元素 至第i个元素（i 为插入位置）向 后移动一个位置 4 将元素插入到i位 置 5 将顺序表的长度 增1 template void SeqList:Insert(int i, T x) int j; if (length=MaxSize) throw “上 溢“; if (ilength+1) throw “位置 “; for (j=length; j=i; j-) dataj=dataj-1; datai-1=x; length+; 基本语句？ 32 顺序表的实现插入 最好情况（i=n+1）： 基本语句执行0次，时间复杂度为O(1)。 最坏情况（i=1）： 基本语句执行n次，时间复杂度为O(n)。 平均情况（1in+1）： 时间复杂度为O(n)。 时间性能分析 +- + = 1 1 )=1( n i i inp+- + + = 1 1 )=1( 1 1 n i in n 2 n =O(n) 33 操作接口T Delete(int i):将线性表中的第i（1 i n)个 元素删除，并返回被删除元素的值 删除前：(a1, , ai-1,ai,ai+1,an) 删除后：(a1,ai-1,ai+1, ,an) 顺序表的实现删 除 ai-1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 34 顺序表的实现删 除 例：（35, 33, 12, 24, 42），删除i=2的数据 元素。 仿照顺序表的插入操作，完成： 1. 分析边界条件； 2. 分别给出伪代码和C+描述的算法； 3. 分析时间复杂度。 5 35 a1a2a3a4 0 1 2 3 4 422412334 a5 122442 35 1.如果顺序表已空，抛出下溢异常 2.如果元素删除位置不存在，抛出位置异常 3.取出被删除的元素 4.将下标为i，i+1n-1的元素依次移到i- 1,i,n-2的位置 5.将顺序表的长度减1，返回被删除的元素 算法描述伪代码 顺序表的实现删除 36 顺序表的实现删除 1.如果顺序表已空， 抛出下溢异常 2.如果元素删除位置 不存在，抛出位置 异常 3.取出被删除的元素 4.将下标为i， i+1n-1的元素一 次移到i-1,i,n- 2的位置 5.将顺序表的长度减 1，返回被删除的 元素 template T SeqList:Delete(int i) int x,j; if (length=0) throw “下溢“; if (ilength) throw “位置“; x=datai-1; for (j=i; j T SeqList:Get(int i) if (ilength) throw “查找位置非法“; else return datai-1; 时间复杂度？ O(1) 40 顺序表的实现按值查找 操作接口int Locate(T x ):查找值为x的元素并返回其序号 5 35 a1a2a3a4 0 1 2 3 4 42241233 a5 例：在（35, 33, 12, 24, 42） 中查找值为12的元 素，返回在表中的序号。 iii 注意序号和下标之间的关系 41 顺序表的实现按值查找 template int SeqList:Locate(T x) for (int i=0; ilength; i+) if (datai=x) return i+1 ; /下标为i的元素等于x，返回其 序号i+1 return 0; /退出循环，说明查找失败 算法描述： 时间复杂度？ 42 顺序表的实现按值查找 最好情况： 如果顺序表的第一个元素恰好就是 x ，算法只要比 较一次就行了 最坏情况： 如果顺序表的最后一个元素是 x