数据结构第二章线性表.

顺序表(SequentialList)***多项式抽象数据类型(PolynomialADT)单链表(SinglyLinkedList)循环链表(CircularList)***多项式及其相加双向链表(DoublyLinkedList)***稀疏矩阵2.2顺序表(SequentialList)顺序表的定义和特点定义n（0）个表项的有限序列（a1,a2,…,an）ai是表项，n是表长度。特点顺序存取遍历逐项访问从前向后从后向前从两端向中间最常用且最简单的一种数据结构，是n个数据元素的有限序列。如（6，10，13，18，20，50，100，200）在稍微复杂的线性表中，数据元素可以由记录组成，同一线性表中的元素必须是同一类型的，一般记为：（a1，a2，…，ai–1，ai，ai+1，…，an）n为线性表的长度，n=0时称为空表，元素在线性表中的位置，仅取决于其序号顺序表(SeqList)类的定义templateclassTypeclassSeqList{private:Type*data;//顺序表存储数组intMaxSize;//最大允许长度intlast;//当前最后元素下标public:SeqList(intMaxSize=defaultSize);~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){returni0||ilast？NULL:data[i];}}顺序表部分公共操作的实现templateclassTypeSeqListType::SeqList(intsz){//构造函数if(sz0){MaxSize=sz;last=-1;data=newType[MaxSize];}}templateclassTypeintSeqListType::Find(Type&x)const{//搜索函数：在表中从前向后顺序查找xinti=0;while(i=last&&data[i]!=x)i++;if(ilast)return-1;elsereturni;}顺序搜索图示x=48x=50搜索成功若搜索概率相等，则搜索不成功数据比较n次iniicpACN10=212)(11)2(111)(1=10nnnnnninACNni221)(1)(10)1(11)(11=0nnnnnninnAMNni表项的插入templateclassTypeintSeqListType::Insert(Type&x,inti){//在表中第i个位置插入新元素xif(i0||ilast+1||last==MaxSize-1)return0;//插入不成功else{last++;for(intj=last;ji;j--)data[j]=data[j-1];data[i]=x;return1;//插入成功}}表项的删除102121)(11)(1=ninnnninnAMNtemplateclassTypeintSeqListType::Remove(Type&x){//在表中删除已有元素xinti=Find(x);//在表中搜索xif(i=0){last--;for(intj=i;j=last;j++)data[j]=data[j+1];return1;//成功删除}return0;//表中没有x}顺序表的应用：集合的“并”运算templateclassTypevoidUnion(SeqListType&LA,SeqListType&LB){intn=LA.Length();intm=LB.Length();for(inti=0;im;i++){Typex=LB.Get(i);//在LB中取一元素intk=LA.Find(x);//在LA中搜索它if(k==-1)//若未找到插入它{LA.Insert(n+1,x);n++;}}}templateclassTypevoidIntersection(SeqListType&LA,SeqListType&LB){intn=LA.Length();intm=LB.Length();inti=0;while(in){Typex=LA.Get(i);//在LA中取一元素intk=LB.Find(x);//在LB中搜索它if(k==-1){LA.Remove(x);n--;}elsei++;//未找到在LA中删除它}}顺序表的应用：集合的“交”运算iniinnnxaxaxaxaaxP02210)(**2.3多项式(Polynomial)n阶多项式Pn(x)有n+1项。系数a0,a1,a2,…,an指数0,1,2,…,n。按升幂排列classPolynomial{public:Polynomial();//构造函数intoperator!();//判是否零多项式CoefficientCoef(Exponente);ExponentLeadExp();//返回最大指数PolynomialAdd(Polynomialpoly);PolynomialMult(Polynomialpoly);floatEval(floatx);//求值}多项式(Polynomial)的抽象数据类型#includeiostream.hclasspower{doublex;inte;doublemul;public:power(doubleval,intexp);doubleget_power(){returnmul;}};创建power类，计算x的幂power::power(doubleval,intexp){//按val值计算乘幂x=val;e=exp;mul=1.0;if(exp==0)return;for(;exp0;exp--)mul=mul*x;}main(){powerpwr(1.5,2);coutpwr.get_power()“\n”;}多项式的存储表示第一种：private:(静态数intdegree;组表示)floatcoef[maxDegree+1];Pn(x)可以表示为：pl.degree=npl.coef[i]=ai,0in第二种：private:(动态数intdegree;组表示)float*coef;Polynomial::Polynomial(intsz){degree=sz;coef=newfloat[degree+1];}以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如P101(x)=3+5x50-14x101,不经济。第三种：classPolynomial;classterm{//多项式的项定义friendPolynomial;private:floatcoef;//系数intexp;//指数};classPolynomial{//多项式定义public:……private:statictermtermArray[MaxTerms];//项数组staticintfree;//当前空闲位置指针//termPolynomial::termArray[MaxTerms];//intPolynomial::free=0;intstart,finish;//多项式始末位置}A(x)=2.0x1000+1.8B(x)=1.2+51.3x50+3.7x101两个多项式存放在termArray中两个多项式的相加结果多项式另存扫描两个相加多项式，若都未检测完：若当前被检测项指数相等，系数相加。若未变成0，则将结果加到结果多项式。若当前被检测项指数不等，将指数小者加到结果多项式。若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。PolynomialPolynomial::Add(PolynomialB){PolynomialC;inta=start;intb=B.start;C.start=free;floatc;while(a=finish&&b=B.finish)Switch(compare(termArray[a].exp,termArray[b].exp)){//比较对应项指数case‘=’://指数相等c=termArray[a].coef+termArray[b].coef;if(c)NewTerm(c,termArray[a].exp);a++;b++;break;case'':NewTerm(termArray[b].coef,termArray[b].exp);b++;break;case'':NewTerm(termArray[a].coef,termArray[a].exp);a++;}for(;a=finish;a++)//a未检测完时NewTerm(termArray[a].coef,termArray[a].exp);for(;b=B.finish;b++)//b未检测完时NewTerm(termArray[b].coef,termArray[b].exp);C.finish=free-1;returnC;}在多项式中加入新的项voidPolynomial::NewTerm(floatc,inte){//把一个新的项加到多项式C(x)中if(free=maxTerms){coutToomanytermsinpolynomials”endl;return;}termArray[free].coef=c;termArray[free].exp=e;free++;}3.1.1单链表(SinglyLinkedList)特点每个元素(表项)由结点(Node)构成。线性结构结点可以不连续存储表可扩充datalink单链表的存储映像3.1.2单链表的类定义多个类表达一个概念(单链表)。链表结点(ListNode)类链表(List)类定义方式复合方式嵌套方式classList;//复合类定义classListNode{//链表结点类friendclassList;//链表类为其友元类private:intdata;//结点数据,整型ListNode*link;//结点指针};classList{//链表类public://链表公共操作………private:ListNode*first,*last;//表头和表尾指针};classList{//链表类定义(嵌套方式)public://链表操作………private:classListNode{//嵌套链表结点类public:intdata;ListNode*link;};ListNode*first,*last;//表头和表尾指针};3.1.3单链表中的插入与删除插入第一种情况：在第一个结点前插入newnode-link=first;first=newnode;（插入前）（插入后）firstnewnodenewnodefirst(插入前)(插入后)第二种情况：在链表中间插入newnode→link=p→link;p→link=newnode；第三种情况：在链表末尾插入newnode→link=p→link;(或者newnode→link=NULL;)p→link=last=newnode；(插入前)(插入后)intList::Insert(constintx,constinti){//在链表第i个结