C与数据结构 第14次课--顺序线性表的插入、删除和顺序查找.ppt

《C与数据结构 第14次课--顺序线性表的插入、删除和顺序查找.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、首页学到现在，入门了吗？学习内容越来越难了教学主题顺序线性表的插入、删除和顺序查找教学目标通过本次课的学习，使学生掌握顺序线性表的基本操作（插入、删除以及顺序查找法）。教学重点1、顺序线性表中元素的插入2、顺序线性表中元素的删除3、顺序线性表中元素的查找（顺序查找）教学难点各种操作的实现算法教案主要内容顺序线性表的插入和删除操作顺序线性表中元素的插入顺序线性表中元素的删除有序顺序表中元素的插入顺序存储结构的优缺点顺序线性表的查找与查找有关的基本概念顺序线性表中查找的实现顺序线性表中元素的插入插入操作在顺序线性表的第i－1个数据元素和第i个数据元素之间插入一个新的数据元

2、素x，使长度为ｎ的顺序线性表（a0,…,ai-1,ai,…,an-1）变成长度为ｎ+1的顺序线性表（a0,…,ai-1,x,ai,…,an-1）。具体做法应先把元素ai,…,an-1依次向后各自移动一个位置，然后将x插在第i个位置上。插入操作示意图在顺序线性表的第i个位置插入一个元素的示意图a0a1…ai-1ai……an-101i-1in-1插入x01i-1ii+1n-1na0a1…ai-1xai…an-2an-1注意发生的变化①移动多个元素，要用到循环。②哪一个先移？顺序线性表中元素插入的实现分析看源程序(14_1)源程序流程图①表是否已满?②插入位置i是否合法?运行

3、程序(14_1)返回顺序线性表中元素的删除删除操作删除操作和插入操作类似。删除顺序线性表的第i个元素ai，使长度为ｎ的顺序线性表（a0,…,ai-1,ai,ai+1,…,an-1）变成长度为ｎ-1的顺序线性表（a0,…,ai-1,ai+1,…,an-1）。具体做法把元素ai+1,…,an-1分别向前移动一个位置即可。删除操作示意图删除顺序线性表的第i个元素ai的示意图a0a1…ai-1aiai+1……an-101i-1ii+1n-101i-1ii+1n-2n-1a0a1…ai-1ai+1ai+2…an-1注意发生的变化①移动多个元素，要用到循环。②哪一个先移？顺序线性表

4、中元素删除的实现分析看源程序(14_1)源程序流程图①表是否为空?②删除位置i是否合法？运行程序(14_1)返回有序顺序表定义元素有序（递增或递减）的顺序线性表。在有序顺序表中插入元素①要求在有序顺序表（如递增）中插入一个数据元素，使顺序表仍保持有序（递增）。②算法的重点是要找到应该插入的位置。③查找插入位置，有两种方法。方法一：通过循环，从线性表表头元素开始，依次与待插入的数据元素进行比较，直到找到一个数据元素比待插入元素大为止。方法二：通过循环，从线性表表尾元素开始，依次与待插入的数据元素进行比较，直到找到一个数据元素比待插入元素小为止。分析在有序顺序表中插入元素的

5、实现看源程序(14_2)源程序方法一的流程图运行程序(14_2)注意：创建线性表时，要有序。在有序顺序表中插入元素的实现看源程序(14_3)源程序方法二的流程图运行程序(14_3)注意：创建线性表时，要有序。返回顺序存储结构的优缺点优点1、逻辑相邻，物理相邻。2、可随机存取任一元素。3、存储空间使用紧凑。缺点1、插入、删除操作需要移动大量的元素，效率较低。2、预先分配空间需按最大空间分配，利用不充分。3、表容量难以扩充。返回与查找有关的基本概念列表：由同一类型的数据元素(或记录)构成的集合。关键字：数据元素的某个数据项，用它可以标识列表中的一个或一组数据元素。如果一个关

6、键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。查找：根据给定的关键字值，在列表中寻找与给定关键字值相同的数据元素，并返回该数据元素在列表中的位置。查找的结果：有两种，查找成功和查找失败。查找时涉及到的三类参量：①查找对象K(找什么)；②查找范围L(在哪找)；③K在L中的位置(查找的结果)。输出参量输入参量查找举例在学生成绩管理系统中，假设全部学生的成绩可以如下表所示存储在计算机中，表中每一行为一个记录，学生的学号为记录的主关键字。若给定值为0223801，则可找到学生王丽，查找是成功的。若给定

7、值为0223912，由于表中没有关键字为0223912的记录，则查找不成功。查找的方法查找的方法很多。对于不同结构的查找表，需要采用不同的查找方法。就大的方向来分，查找方法可以分为静态查找表和动态查找表。顺序表可采取的查找方法：顺序查找法，即：从顺序表的一端开始，用给定值k逐个顺序地与表中各记录的关键字比较，直到在表中找到某个记录的关键字与k值相等，表明查找成功；否则，若查遍了表中的所有记录却仍未找到与k值相等的关链字，表明查找失败。查找后，不影响表中的数据查找后，表中数据会改变返回顺序表的存储结构顺序表中数据的存储结构可描述如下：#de