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

1、,首页,学到现在，入门了吗？,学习内容越来越难了,教案,主要内容,顺序线性表的插入和删除操作 顺序线性表中元素的插入 顺序线性表中元素的删除 有序顺序表中元素的插入 顺序存储结构的优缺点 顺序线性表的查找 与查找有关的基本概念 顺序线性表中查找的实现,顺序线性表中元素的插入,插入操作 在顺序线性表的第i1个数据元素和第i个数据元素之间插入一个新的数据元素x，使长度为的顺序线性表（a0, , ai-1, ai, , an-1）变成长度为+1的顺序线性表（a0, , ai-1, x, ai, , an-1）。 具体做法 应先把元素ai,an-1依次向后各自移动一个位置，然后将x插在第i个位置上。,

2、插入操作示意图,在顺序线性表的第i个位置插入一个元素的示意图,插入x,注意发生的变化, 移动多个元素，要用到循环。 哪一个先移？,顺序线性表中元素插入的实现,分析,看源程序(14_1),源程序,流程图, 表是否已满? 插入位置i 是否合法?,运行程序(14_1),返回,顺序线性表中元素的删除,删除操作 删除操作和插入操作类似。删除顺序线性表的第i个元素ai，使长度为的顺序线性表（a0, , ai-1, ai, ai+1, , an-1）变成长度为-1的顺序线性表（a0, , ai-1, ai+1, , an-1）。 具体做法 把元素ai+1, , an-1分别向前移动一个位置即可。,删除操作示

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

4、，从线性表表尾元素开始，依次与待插入的数据元素进行比较，直到找到一个数据元素比待插入元素小为止。,分析,在有序顺序表中插入元素的实现,看源程序(14_2),源程序,方法一的流程图,运行程序(14_2),注意：创建线性表时，要有序。,在有序顺序表中插入元素的实现,看源程序(14_3),源程序,方法二的流程图,运行程序(14_3),注意：创建线性表时，要有序。,返回,顺序存储结构的优缺点,优点 1、逻辑相邻，物理相邻。 2、可随机存取任一元素。 3、存储空间使用紧凑。 缺点 1、插入、删除操作需要移动大量的元素，效率较低。 2、预先分配空间需按最大空间分配，利用不充分。 3、表容量难以扩充。,返回

5、,与查找有关的基本概念,列表：由同一类型的数据元素(或记录)构成的集合。 关键字：数据元素的某个数据项，用它可以标识列表中的一个或一组数据元素。 如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。 查找：根据给定的关键字值，在列表中寻找与给定关键字值相同的数据元素，并返回该数据元素在列表中的位置。 查找的结果：有两种，查找成功和查找失败。 查找时涉及到的三类参量： 查找对象K(找什么)； 查找范围L(在哪找)； K在L中的位置(查找的结果)。,输出参量,输入参量,查找举例,在学生成绩管理系统中，假设全部学生的成

6、绩可以如下表所示存储在计算机中，表中每一行为一个记录，学生的学号为记录的主关键字。,若给定值为0223801，则可找到学生王丽，查找是成功的。 若给定值为0223912，由于表中没有关键字为0223912的记录，则查找不成功。,查找的方法,查找的方法很多。对于不同结构的查找表，需要采用不同的查找方法。 就大的方向来分，查找方法可以分为静态查找表和动态查找表。 顺序表可采取的查找方法：顺序查找法，即：从顺序表的一端开始，用给定值k逐个顺序地与表中各记录的关键字比较，直到在表中找到某个记录的关键字与k值相等，表明查找成功；否则，若查遍了表中的所有记录却仍未找到与k值相等的关链字，表明查找失败。,查

7、找后，不影响表中的数据,查找后，表中数据会改变,返回,顺序表的存储结构,顺序表中数据的存储结构可描述如下： #define MAXSIZE 100 typedef struct node int key; /* 关键字域 */ /* 其它域 */ Elemtype ; typedef struct sequence Elemtype rMAXSIZE ; /* 数组域 */ int len ; /* 表长域 */ Seq; Seq list;,类型定义,变量定义,顺序表中顺序查找的实现,看源程序(14_4),源程序,流程图,运行程序(14_4),顺序表中顺序查找算法的改进,如果允许在表的最后增设一个虚拟记录（要查找的关键字值放入其中，只要不引起数组r的下标溢出即可）作为循环控制的边界，则算法中的循环控制条件可以减少一个，而得到较快的顺序查找算法。,顺序表中顺序查找的改进算法,看源程序(14_5),源程序,流程图,运行程序(14_5),有序顺序表的顺序查找,看源程序(14_6),源程序,流程图,运行程序(14_6),顺序线