第二章-线性表演示幻灯片.pptx

第二章 线性表2.1 线性表的抽象数据类型 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.1 线性表的抽象数据类型一个线性表(Linear List) 是由n(n≧0)个数据元素(结点) 组成的有限序列。数据元素可以是一个字符、一个数或一个记录，也可以是更复杂的信息。 线性表一：26个英文字母组成的字母表（A，B，C，…，Z）。表中的数据元素是单个字母字符。线性表二：某学生五门课的成绩列表（76，87，88，80，92）。表中的数据元素是整数。线性表三：某班级学生信息表（如下表所示）。表中的数据元素是一个记录，包括姓名、学号、性别和年龄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 线性表的顺序存储结构 线性表的顺序存储是指在内存中用地址连续的一块存储空间依次存放线性表的数据元素，用这种存储形式存储的线性表称其为顺序表。假设每个数据元素占d个存储单元，且将ai的存储地址表示为Loc(ai)，则有如下关系： Loc(ai)=Loc(a1)+(i-1)*d Loc(a1)是线性表的第一个数据元素a1的存储地址，通常称作线性表的基地址。顺序表的存储结构如下图所示，其中b为线性表的基地址。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]); }2.2.3 顺序实现的算法分析1. 插入假设pi是在第i个位置插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为：pi=1/(n+1)◆插入算法的平均时间复杂度为O(n)。2. 删除假设qi是在第i个位置删除一个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为：qi=1/n◆删除算法的平均时间复杂度为O(n)。2.2.4 顺序表的应用举例【例1】 编写一算法，从顺序表中删除自第i个元素开始的k个元素。算法思路： 为保持顺序表的逻辑特性，需将i+k ~ n位置的所有元素依次前移k个位置。算法如下： int deleteK(Sqlist sq,int i,int k) { if (i1||k1||i+k-1sq.len) return 0; for (j=i+k-1;j=sq.len-1;j++) sq.data[j-k]=sq.data[j]; sq.len-=k; return 1; }// deleteK 【例2】巳知有两个按元素值递增有序的顺序表La和Lb，设计一个算法将表La和表Lb的全部元素归并为一个按元素值递增有序的顺序表Lc。算法思路：用i扫描顺序表La，用j扫描顺序表Lb。当表La和表Lb都未扫描完时，比较两者的当前元素，将较小者插入表Lc的表尾，若两者的当前元素相等，则将这两个元素依次插入表Lc的表尾。最后，将尚为扫描完的顺序表的余下部分元素依次插入表Lc的表尾。算法如下： void MergeList_Sq(SqList La, SqList Lb, SqList Lc) { int i=0,j=0,k=0;while (i La.len jLb.len)// 表La和表Lb都未扫描完时 { if (La. data[i] Lb. data [j]) { Lc.