数据结构CC版第2章 了解线性表.pptx

《数据结构CC版第2章 了解线性表.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（C语言版）项目二了解线性表线性表是线性结构的抽象，其本质特征是元素之间只有一维的位置关系。在本项中，通过2个工作任务，向读者展示线性表的基础知识，应用线性对数值进行排序。目录任务一利用顺序表对数据进行升序排序任务二使用单链表对数据进行升序排序利用顺序表对数据进行升序排序准备知识利用顺序表对数据进行升序排序线性表概述线性表的抽象数据类型和基本操作线性表的顺序存储结构1.线性表概述1.线性表概述线性表是最基本、最简单、也是最常用的一种数据结构。线性表(LinearList)是由n(n≥0)个相同类型的数据元素构成的有限序列。线性

2、表(List)简记为L，是一个二元组，其形式定义为：L=(D,R)其中，D是数据元素的有限集合，R是数据元素之间关系的有限集合。知识点链接对于这个定义应该注意两个概念：一是“有限”，指的是线性表中的数据元素的个数是有限的，线性表中的每一个数据元素都有自己的位置(Position)。二是“相同类型”，指的是线性表中的数据元素都属于同一种类型。2.线性表的抽象数据类型和基本操作2.线性表的抽象数据类型和基本操作线性表中数据元素可以是简单数据类型，也可以是复杂的数据类型。例如表1-1企业员工信息表，数据元素(DataElements)由若干

3、数据项(DataItem)组成，描述员工的一些属性，包括姓名、性别、出生年月、家庭住址等。线性表的基本操作包括：（1）初始化：若线性表不存在，则创建一个新的线性表。（2）求长度：求线性表的表长。若线性表存在，返回线性表中所有数据元素的个数。（3）清空表：若线性表存在且有数据元素，则从线性表中清除所有数据元素，线性表为空。该操作通常用于顺序表。（4）判断是否为空：假设线性表存在，如果线性表为空则返回真，否则返回假。（5）附加：若线性表存在，则将值为item的新元素添加到线性表的末尾。（6）插入：在线性表中第i个元素之后（或之前）插入一个

4、新的元素。若线性表存在且插入位置正确，则在线性表中插入一个新元素，表长加1。2.线性表的抽象数据类型和基本操作2.线性表的抽象数据类型和基本操作（7）删除元素：删除线性表中的第i个元素。若线性表存在不为空且删除位置正确，则在线性表中删除一个元素，返回删除后的数据元素，表长减1。（8）取表元：取线性表中的第i个元素。若线性表存在且数据元素位置正确，则返回线性表中某个数据元素。（9）按值查找：若线性表存在，则在线性表中查找数据元素，其结果返回在线性表中首次出现的数据元素的序号，称为查找成功；否则返回一个特殊值，表示查找失败。（10）销毁线

5、性表：若线性表已存在，清空所有结点并将线性表空间释放。该操作通常用于链式表。2.线性表的抽象数据类型和基本操作2.线性表的抽象数据类型和基本操作3.线性表的顺序存储结构3.线性表的顺序存储结构线性表的顺序存储是用一组地址连续的存储单元依次存放线性表中的各个元素，使线性表中在逻辑结构上相邻的元素，在物理存储单元中也是相邻的，通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦

6、相邻。设线性表中有n个元素，每个数据元素需占用相同的存储单元(设为k个)，第一个元素的存储地址作为存放元素的起始位置，也称为基地址。如下图所示给出了线性表的顺序存储结构示意。线性表顺序存储结构拓展提高：计算机高级语言中的数组在内存中占用的存储空间就是一组连续的存储区域，具有随机存取的特点。所以，数组天生具有表示顺序表的数据存储区域的特性。任务实施张瑶是某公司科技公司的程序员，接到主管任务，她需要使用顺序表编写程序。要求能够对数据表中的数值从小到大进行排序。利用顺序表对数据进行升序排序任务一：利用顺序表对数据进行升序排序任务分析：理解牢

7、记！由于线性表顺序表是通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。在进行数值排序时，能够按照下标进行相邻比较。因此，张瑶决定使用顺序表来完成此任务。任务一：利用顺序表对数据进行升序排序任务实施利用顺序表对数据进行升序排序有数据类型为整型的顺序表La和Lb，其数据元素均按从小到大的升序排列，张瑶编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。算法思路：依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给Lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下

8、的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。按升序合并两个顺序表的算法C语言实现如下：/*---------------------------------------------------