第2课--线性表与其顺序存储结构.ppt

* * 线性表顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此可以 随机存取 其中的任意元素。 但是，顺序存储结构也有一些不方便之处，主要表现在： （1）数据元素集最大个数需预先确定(静态结构)，使得高级程序设计语言编译系统需预先分配相应的存储空间； （2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。 顺序结构小结： * * 教学目的：掌握线性表的概念和类型定义 教学重点：线性表的顺序存储结构和链式存储结构 教学难点：链表的操作 第2章 线性表 * * 线性表（Linear list）是最简单且最常用的一种数据结构。这种结构逻辑上具有下列特点： 存在一个唯一的没有前驱的数据元素——称为表头 ； 存在一个唯一的没有后继的数据元素——称为表尾 ； 其它数据元素均有且仅有一个直接前驱和一个直接后继. 本章学习导读 * * 1.线性表的概念和类型定义 2.线性表的顺序存储结构及算法实现 3. 补充: C语言中结构体操作 教学重点：线性表的插入、删除操作 本课内容 * * 线性表由一组具有相同属性的数据元素构成。数据元素的含义很广泛，在不同的具体情况下，可以有不同的含义。 1 . 线性表的定义 线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。 当n=0时称为空表，即不含有任何元素。 2.1 线性表的基本概念 * * 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188） 例3、学生统计表 * * 从以上例子可看出,线性表的特点： （1）有穷性：线性表长度是有限的； （2）有序性：元素之间是有顺序限制的，并且用直接前驱和后继来描述； （3）同型性：所有元素是同一数据类型； （4）抽象性：数据元素的类型没有具体定义，只是给出一个抽象说明（DataType)。即可以是简单类型，也可以是复杂的构造类型； （5）原子性：数据元素整体上作为一个独立的存储对象，不再分解为更小的数据单位进行存储。 * * 2.2 线性表的顺序结构及实现 线性表的顺序存储结构可以有静态结构和动态结构两种不同的方式。 顺序存储结构的特点：在内存中用地址连续的存储单元按照数据元素的逻辑顺序、依次“一个接一个”地存放线性表的所有数据元素，通过物理位置的相邻来表示元素之间的逻辑关系。 所谓静态结构指：线性表所占的存储空间是在编译时就确定的，且一经分配不再改变。 动态结构指：线性表所需的存储空间可以在运行时分配， 并且能够根据需要增加或释放。 * * 线性链的基本操作 创建一个线性表 向表中插入一个元素 删除一个元素 获取指定元素 求链表长度 输出链表所有元素 * * 在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组data[MaxLen]来存储数据元素，为保存线性表的长度需定义一个整型变量length。线性表的第l，2，…，n个元素分别存放在此数组下标为0，1，…，length-1数组元素中，如下图所示 * * 一个线性表的顺序存储结构需要两个分量描述，为体现数组data和length之间的内在联系，通常将它们定义在一个结构类型中。 可用下述类型sqList定义来描述顺序表(重点)： #define MaxLen 100 //线性表的容量 typedef struct { DataType data[MaxLen]; //定义存储表元素的数组 int length; //线性表的实际长度 } sqList; typedef int DataType //元素类型DataType简化为int型 2.2.1 线性表的顺序静态结构及实现 * * 1．初始化表操作