数据结构c++版第2章线性表-1.ppt

顺序表中的查找操作 两种查找方法 按位置查找，即查找指定位置上的元素 按值查找，即查找指定的值在顺序表中的位置 顺序表的实现——插入 最好情况（i=n+1）： 基本语句执行0次，时间复杂度为O(1)。 最坏情况（i=1）： 基本语句执行n次，时间复杂度为O(n)。 平均情况（1≤i≤n+1）： 时间复杂度为O(n)。 时间性能分析 ? + - + = 1 1 )= 1 ( n i i i n p ? + - + + = 1 1 )= 1 ( 1 1 n i i n n 2 n =O(n) 操作接口T Delete(int i):将线性表中的第i（1 ≤i ≤n)个元素删除，并返回被删除元素的值 删除前：(a1, …, ai-1,ai,ai+1,…,an) 删除后：(a1,…,ai-1,ai+1, …,an) 顺序表的实现——删 除 ai-1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 顺序表的实现——删 除 例：（35, 33, 12, 24, 42），删除i=2的数据 元素。 仿照顺序表的插入操作，完成： 1. 分析边界条件； 2. 分别给出伪代码和C++描述的算法； 3. 分析时间复杂度。 5 35 a1 a2 a3 a4 0 1 2 3 4 42 24 12 33 4 a5 12 24 42 1.如果顺序表已空，抛出下溢异常 2.如果元素删除位置不存在，抛出位置异常 3.取出被删除的元素 4.将下标为i，i+1…n-1的元素依次移到i-1,i,…n-2的位置 5.将顺序表的长度减1，返回被删除的元素 算法描述——伪代码 顺序表的实现——删除 顺序表的实现——删除 1.如果顺序表已空，抛出下溢异常 2.如果元素删除位置不存在，抛出位置异常 3.取出被删除的元素 4.将下标为i，i+1…n-1的元素一次移到i-1,i,…n-2的位置 5.将顺序表的长度减1，返回被删除的元素 template class T T SeqListT::Delete(int i) {int x,j; if (length==0) throw 下溢; if (i1 || ilength) throw 位置; x=data[i-1]; for (j=i; jlength; j++) data[j-1]=data[j]; length--; return x; } 基本语句？ 顺序表的实现——删除 最好情况（i=n）： 基本语句执行0次，时间复杂度为O(1)。 最坏情况（i=1）： 基本语句执行n-1次，时间复杂度为O(n)。 平均情况（1≤i≤n）： 时间复杂度为O(n)。 时间性能分析 * 第2章 线性表 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： 2.1 线性表的逻辑结构 学生成绩登记表 姓 名 英语 数据结构 高数 学号 丁一 96 78 87 0101 李二 87 90 78 0102 张三 67 86 86 0103 孙红 69 81 96 0104 王冬 87 74 66 0105 数据元素之间的关系是什么？ 线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。 线性表的长度：线性表中数据元素的个数。 空表：长度等于零的线性表，记为：L=( )。 非空表记为：L＝（a1, a2 , …, ai-1, ai , …, an) 线性表的定义 其中，ai（1≤i≤n）称为数据元素； 下角标 i 表示该元素在线性表中的位置或序号，称元素 ai位于表的第 i 个位置，或称 ai是表中的第 i 个元素。 a1 a3 a4 an a2 线性表的图形表示 线性表（a1, a2 , …, ai-1, ai , …, an)的图形表示如下： a1 a3 a4 an a2 线性表的特性 1.有限性：线性表中数据元素的个数是有穷的。 2.相同性：线性表中数据元素的类型是同一的。 3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1, ai)，即ai-1是ai的前驱， ai是ai-1的后继；a1 无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。 线性表的抽象数据类型定义 见教材P50 线性表ADT的几点说明 （1）对于不同的应用，线性表的基本操作是不同的； （2）复杂的操作可以通过基本操作的组合来实现； （3）对不同的应用，操作的接口可能不同。 顺序表——线性表的顺序存储结构 例：（34, 23