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

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

1、学习提要2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加2.5顺序表与链表的比较第二章线性表学习提要理解线性结构的基本特点理解线性表的基本概念和抽象数据类型的定义。掌握线性表的顺序和链式存储结构的描述方法、基本操作（查找、插入和删除等）和各种算法的时间复杂度分析.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。线性结构的特点在数据元素的非空有限集中存在唯一的一个被称做“第一个”的数据元素；存在唯一一个被称做“最后一个”的数据元素；

2、除第一个数据元素之外，每个元素都只有一个前驱；除最后一个数据元素之外，每个元素都只有一个后继。定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素2.1线性表的类型定义(LinearList)2.1线性表的类型定义(LinearList)特征：元素个数n—表长度，n=0空表1

3、ai∈ElemSet,i

4、=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{

5、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}2、线性表的抽象数据类型基本操作：（1）结构初始化InitList(L)操作结果：构造一个空的线性表L。（2）销毁结构DestroyList(L)初始条件：线性表L已存在。操作结果：销毁线性表L。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为

6、空表。（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。（5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。（7）GetData(L,i)操作前提：表L存在，且i值合法，即1≤i≤ListLength（L）。操作结果：返回线性表L中第i个元素的值。（8）In

7、sList(L,i,e)操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。（9）DelList(L,i,&e)操作前提：表L已存在且非空，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。}ADTLinearList2.2线性表的顺序表示与实现1、顺序表的定义和特点定义将线性表中的元素相继存放在一个连续的存储空间中。253457164809012345data用物理位置来表示逻辑结

8、构。LOC(ai+1)=LOC(ai)+k;LOC(ai)=LOC(a1)+(i-1)*k特点：随机存取的存储结构。只要确定了存储线性表的起始位置，线性表中的任一数据元素可随机存取。图2.2顺序表存储示意图2.2线性表的顺序表示与实现2、线性表的顺序存储结构＃defineMAXSIZE=线性表可能达到的最大长度typedefstruct{ElemTypeelem［MAXSIZE］/*线性表占用的数组空间*/intlast；/*记录线性表中最后一个元素在数组elem［］中的位置（下标值），空表置为-1*/}SeqLis

9、t；2.2顺序表类型的实现3、顺序线性表的操作顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。⑴初始化操作2.2顺序表类型的实现3、顺序线性表的操作顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。(2)从线性表中查找具有给定值的第一个元素：intLocate(SeqListL，ElemTypee){i=0;while((i<=L.last)&&(L.elem［i］!=e))/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/i++;if(i<=L.last

10、)return(i+1);elsereturn(-1);/*若没找到，则返回空序号*/}此算法的时间复杂度为:O(ListLength(L))平均比较次数为：(n+1)/22.2顺序表类型的实现3、顺序线性表的操作顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。(3)在线性表中指定位置前插入一个元素：插入元素时，线性表