数据结构第二章线性表ppt课件.ppt

《数据结构第二章线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、顺序表(SequentialList)***多项式抽象数据类型(PolynomialADT)单链表(SinglyLinkedList)循环链表(CircularList)***多项式及其相加双向链表(DoublyLinkedList)***稀疏矩阵第二章线性表2.2顺序表(SequentialList)顺序表的定义和特点定义n（0）个表项的有限序列（a1,a2,…,an）ai是表项，n是表长度。特点顺序存取遍历逐项访问从前向后从后向前从两端向中间最常用且最简单的一种数据结构，是n个数据元素的有限序列。如（6，10，13，18，20，

2、50，100，200）在稍微复杂的线性表中，数据元素可以由记录组成，同一线性表中的元素必须是同一类型的，一般记为：（a1，a2，…，ai–1，ai，ai+1，…，an）n为线性表的长度，n=0时称为空表，元素在线性表中的位置，仅取决于其序号顺序表(SeqList)类的定义templateclassSeqList{private:Type*data;//顺序表存储数组intMaxSize;//最大允许长度intlast;//当前最后元素下标public:SeqList(intMaxSize=defaultSize)

3、;~SeqList(){delete[]data;}intLength()const{returnlast+1;}intFind(Type&x)const;intIsIn(Type&x);intInsert(Type&x,inti);intRemove(Type&x);intNext(Type&x);intPrior(Type&x);intIsEmpty(){returnlast==-1;}intIsFull(){returnlast==MaxSize-1;}Type&Get(inti){returni<0

4、

5、i>last？NULL:

6、data[i];}}顺序表部分公共操作的实现templateSeqList::SeqList(intsz){//构造函数if(sz>0){MaxSize=sz;last=-1;data=newType[MaxSize];}}templateintSeqList::Find(Type&x)const{//搜索函数：在表中从前向后顺序查找xinti=0;while(i<=last&&data[i]!=x)i++;if(i>last)return-1;elsereturni

7、;}顺序搜索图示x=48x=50搜索成功若搜索概率相等，则搜索不成功数据比较n次表项的插入templateintSeqList::Insert(Type&x,inti){//在表中第i个位置插入新元素xif(i<0

8、

9、i>last+1

10、

11、last==MaxSize-1)return0;//插入不成功else{last++;for(intj=last;j>i;j--)data[j]=data[j-1];data[i]=x;return1;//插入成功}}表项的删除template

12、e>intSeqList::Remove(Type&x){//在表中删除已有元素xinti=Find(x);//在表中搜索xif(i>=0){last--;for(intj=i;j<=last;j++)data[j]=data[j+1];return1;//成功删除}return0;//表中没有x}顺序表的应用：集合的“并”运算templatevoidUnion(SeqList&LA,SeqList&LB){intn=LA.Length();intm=LB.Length();f

13、or(inti=0;ivoidIntersection(SeqList&LA,SeqList&LB){intn=LA.Length();intm=LB.Length();inti=0;while(i

14、Find(x);//在LB中搜索它if(k==-1){LA.Remove(x);n--;}elsei++;//未找到在LA中删除它}}顺序表的应用：集合的“交”运算**2.3多项式(Polynomial)n阶多项式Pn(