数据结构60771.ppt

第2章 线性表 第2章 线性表 第2章 线性表 教学内容 2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 线性表的应用举例 2.1 线性表的逻辑结构 2.1.1 线性表的定义 线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式： L=( a1, a2,...,ai-1,ai,ai+1,...,an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 特点：除了a1 ， an 外，ai（2=i=n-1)都有一个前驱和后继。（ai-1 ， ai+1）。例如：26个英文字母。 线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。 举例 La=（34，89，765，12，90，-34，22） 数据元素类型为int。 Ls=(?Hello?,?World?, ?China?, ?Welcome?) 数据元素类型为string。 Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结构类型： struct bookinfo{ int No; //图书编号 char *name; //图书名称 char *auther; //作者名称 ...; } 2.1.2 线性表的基本操作 线性表初始化：Init_List(L) 求线性表的长度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_List(L,x) 插入操作：Insert_List(L,i,x) 删除操作：Delete_List(L,i) 2.2 线性表的顺序存储结构 2.2.1 线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示： 其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai+1)=LOC(a1)+(i-1)*L 顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致； （2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。 在C语言中，实现线性表的顺序存储结构的类型定义 #define MAXSIZE 100 //线性表的最大长度 typedef struct { datatype data[MAXSIZE]; int last; } SeqList; 2.2.2 典型操作的算法实现 初始化线性表L SeqList *init_SeqList( ) { SeqList *L; L=malloc(sizeof(SeqList)); L-last=-1; return L; } 插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为： 删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：