第2章-线性表PPT.pptx

第二章 线性表;2.1 线性表的抽象数据类型 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 ;2.1 线性表的抽象数据类型;线性表三：某班级学生信息表（如下表所示）。表中的数据元素是一个记录，包括姓名、学号、性别和年龄4个数据项。; 一个线性表可记为： （a1,a2, …,ai-1,ai,ai+1, …,an），n ≥0 ? 其中，n为表的长度，当n=0时，称为空表。 称i为ai在线性表中的位序。 表中ai-1领先于ai，称ai-1是ai的直接前驱， ai+1是ai的直接后继。 线性表的抽象数据类型定义 （参见教材） 返回本章目录 ;2.2.1 顺序表的类型定义 #define MAXSIZE 100 // 顺序表的容量 typedef struct { ElemType data[MAXSIZE]; // 存放顺序表的元素 int len; // 顺序表的实际长度 }SqList; ◆MAXSIZE为顺序表的容量，表示线性表实际可能达到的最大长度。 ◆len表示顺序表当前的长度。;2.2.2 线性表基本运算在顺序表上的实现 C语言中数组的下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.data[i-1]。 ? 1. 初始化线性表运算 void InitList(SqList sq) { sq.len=0; } 2.求线性表长度运算 int ListLength (SqList sq) { return(sq.len); };3.求线性表中第i个元素运算 ElemType GetElem(SqList sq,int i) { if (i1|| isq.len) // i 值不合法 return 0; else return(sq.data[i-1]); } ;4.按值查找运算 int LocateElem(SqList sq, ElemType e) { int i=0; while (isq.len) (sq.data[i]!=e) i++; // 将表中元素逐个与e比较 if (i=sq.len) return 0; else return i+1; };5. 插入元素运算 int ListInsert(SqList sq ,int i, ElemType e) { int j; if (i1||isq.len+1) return 0; // i 值不合法 for (j=sq.len;j=i;j--) // 插入位置及之后的元素右移 sq.data[j]= sq.data[j-1]; sq.data[i-1]=e; // 插入e sq.len++; // 表长增1 return 1; };6. 删除元素运算 int ListDelete (SqList sq ,int i) { int j; if (i1||isq.len) return 0; // i 值不合法 for (j=i;jsq.len;j++) // 被删除元素之后的元素左移 sq.data[j-1]= sq.data[j]; sq.len--; // 表长减1 return 1; };2.2.3 顺序实现的算法分析 1. 插入 假设pi是在第i个位置插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为：;2. 删除 假设qi是在第i个位置删除一个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为： ;2.2.4 顺序表的应用举例 【例1】 编写一算法，从顺序表中删除自第i个元素开始的k个元素。 算法思路： 为保持顺序表的逻辑特性，需将i+k ~ n位置的所有元素依次前移k个位置。算法如下： int deleteK(Sqlist sq,int i,int k) {