资源描述：
《第2章线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表本章主要内容：•线性表的定义•线性表的顺序存储结构及其基本操作•线性表的链式存储结构及其基本操作学习目的及要求：•掌握线性表的定义•掌握线性表的两种存储结构第二章线性表2.1线性表的定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示和相加2.1线性表的定义线性结构线性表栈队列串数组广义表一个数据元素的有序(次序)集。基本特征：1.集合中必存在唯一的“第一元素”2.集合中必存在唯一的“最后元素”3.除最后元素，均有唯一后继4.除第一元素，均有唯一前驱一、定义二、特点三、抽象数据类型线性表的定义2.1线性表的定义
2、一、定义线性表——是由n个具有相同特性的数据元素a1,a2,…,an组成的有限序列，记为(a1,a2,…,an)。1．数据元素的类型可以是高级语言提供的简单数据类型也可以是用户定义的任何类型。2．线性表中元素个数n为线性表的长度。n=0时，称为空表；n>0时，线性表中第i个数据元素记为ai，i为数据元素的位序。2.1线性表的定义二、特点1.线性表是个有限序列。2.线性表中的每一个数据元素的位置由该元素所在表中的序号(下标)确定的。3.除第一个元素a1外，每个数据元素有且仅有一个前驱元素；除最后一个元素an外，每个数据元素有且仅有一个后继元素。数据元素之
3、间存在着序偶关系。a1a2a3a4……an2.1线性表的定义a3的前驱a3的后继三、抽象数据类型线性表的定义ADTList{数据对象：D={ai
4、ai∈ElemSet,1≤i≤n,n≥0}数据关系：R={}
5、ai,ai+1∈D，1≤i≤n-1}2.1线性表的定义基本操作：三、抽象数据类型线性表的定义Destroylist(&L)//销毁初始条件：线性表L已存在。操作结果：销毁线性表L。InitList(&L)//初始化操作结果：构造一个空线性表L。2.1线性表的定义三、抽象数据类型线性表的定义//{引用型操作}线性表L已存在，对表结构
6、无改变Listempty(L)操作结果：判断L是否为空。ListLength(L)操作结果：返回L中数据元素个数。GetElem(L,i,&e)操作结果：用e返回第i个数据元素的值。LocateElem(L,e,compare())操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，或locate(L,x)返回L中第一个与x值相同的元素位置。2.1线性表的定义//{加工型操作}线性表已存在，表元素或结构改变ClearList(&L)操作结果：将线性表L置为空表。Putelem(&L,i,&e)操作结果：为L中第i个位置赋e值。元素之
7、间的关系改变：ListInsert(&L,i,e)操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。三、抽象数据类型线性表的定义2.1线性表的定义三、抽象数据类型线性表的定义利用上述定义的线性表可以完成其他更复杂操作。例2-1设两个线性表LA和LB分别表示两个集合A和B，现要得到一个新的集合A=A∪B(并)。此问题可演绎为对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到LA中。2.1线性表的定
8、义三、抽象数据类型线性表的定义voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中。La.len=ListLength(La);//求线性表的长度Lb.len=ListLength(Lb);for(i=1;i<=Lb.len;i++){GetElem(Lb,i,e);//取Lb中的第i个数据元素给eif(!LocateElem(La,e,equal))ListInsert(La,++La.len,e);}}该算法的时间复杂度为：O(ListLength(La)ListLength(Lb))2.
9、1线性表的定义2.2线性表的顺序表示和实现一、线性表的顺序存储结构二、线性表顺序存储结构的实现一、线性表的顺序存储结构1.顺序存储结构方式用一组地址连续的存储单元存储线性表的数据元素，又称为顺序表。a1a2aian…12…i…n…bb+Lb+2Lb+(i-1)Lb+(n-1)L两方面的内容：(1)顺序表常用数组来描述(2)设每个数据元素占用L个存储单元，则第i个数据元素的存储位置记为LOC(ai)，与其相邻元素ai-1的存储位置LOC(ai-1)的关系满足：LOC(ai)=LOC(ai-1)+L第i数据元素ai的存储位置为：LOC(ai)=LOC(a1
10、)+(i-1)*L2.2线性表的顺序表示和实现b:线性表的起始位置与b相差一个与位序成正比的常
