数据结构 第2章 线性表.ppt

《数据结构 第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构2.4复杂性分析2.5堆栈2.6队列2.1线性表的定义和基本操作1.线性表的定义[例1]英文字母表（A,B,C,……,Z)整数序列（1,78,9,12,10)[例2]某班学生健康情况登记表。学号姓名性别年龄健康情况01张军男18一般02陈红女17良好03陈军男19神经衰弱……………问题：这些线性表中的数据元素是什么？表中每个数据元素由什么域组成？线性表的定义：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。通常用(a0，a1，…，an1)表示一个线性表，n0(正整数)，a

2、k表示结点，0kn1；当n0时，线性表中无结点，被称为空表；当n1时，称a0为线性表的头结点(简称表头)，称an1为线性表的尾结点(简称表尾)，ai为ai+1的前驱结点，ai+1为ai的后继结点，其中0in1；当n1时，线性表中仅有一个结点a0，a0既是表头又是表尾。线性表的逻辑结构：线性结构线性表记为(a0,a1,…,an1)n0()空表n03线性表的基本操作（1）创建一个线性表；(2)确定线性表的长度；（3）确定线性表是否为空；（4）存取线性表中第k个结点的字段值；（5）查找指定字段值在表中的位置；（6）删除表中第k个结点；(7)在表中第k个结点后插入一个

3、新结点。第二章线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构2.4复杂性分析2.5堆栈2.6队列2.2线性表的顺序存储结构顺序存储：按逻辑顺序将线性表的结点依次存放在一组地址连续的字节中。顺序存储的线性表也称为顺序表。顺序表的特点：逻辑顺序与物理顺序相同。包含4个结点的线性表A[4]在内存中的表示，其中每个结点占2个连续的字节，第一个结点A[0]的首地址为302图2.1线性表的顺序存储线性表A[2]308306304302A[0]A[1]A[3]实现顺序存储的最有效方法是使用一维数组。例如：线性表(a0，a1，…,an-1),可以使用数

4、组a[n]来存放。空闲区a0a1an-1akb+cb+k*cbb+(n-1)*c……01n-1kLoc(a[k])=Loc(a[0])+k*c顺序表的类声明templateclassLinearList{private:intMaxSize;//顺序表的最大长度intlength;//顺序表的实际长度T*element;//存储顺序表的数组public:LinearList(intMaxListSize=10);//构造函数，最大长度默认为10~LinearList(){delete[]element;}//析构函数boolIsEmpty()const{returnle

5、ngth==0;}//判断表是否为空boolIsFull()const{returnlength==MaxSize;}//判断表是否为满intLength()const{returnlength;}//返回表的长度boolFind(intk,T&item)const;//存取：将下标为k的结点的字段值赋给itemintSearch(constT&item)const;//查找：在表中查找字段值为item的结点并返回其下标voidDelete(intk,T&item);//删除：删除下标为k的结点并将其字段值赋给itemvoidInsert(intk,constT&item);//插入

6、：在下标为k的结点后插入字段值为item的结点};顺序存储的线性表的基本运算1、插入[例]在顺序表（12,13,21,24,28,30,42,77）中，插入元素25。此时，线性表的逻辑结构发生什么变化？位置关系发生变化长度增1序号元素341527861213212428304277插入25序号元素341527861213252124283042779//采用ADL算法描述语言描述算法算法Insert(A,k,item)/*在下标为k的结点后插入值为item的结点*/I1.[插入合法？]IF(k0ORklength-1ORlength=MaxSize)THEN(PRINT“插入不合法”

7、.RETURN).I2.[插入]FORilength-1TOk1STEP-1DOA[i1]A[i].A[k1]item.lengthlength1.▌13时间复杂性分析：插入操作的基本运算是：元素移动Dn中有多少种可能的输入呢？n+1种(n+1个位置可以发生插入)设插入成功且插入到各位置的概率相同：1/(n+1)则期望复杂性为：E(n)=(n+(n-1)+……+1+0)/(n+1)=n/22、删除[例]在顺序表(12