《数据结构》陈慧南 第02章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京邮电大学计算机学院,陈慧南 2006年9月,*,数据结构,Data Structures in C+,南京邮电大学计算机学院,陈慧南 2006年9月,第2章 线性表,南京邮电大学计算机学院,陈慧南 2006年9月,2.1 线性表,ADT,2.2,线性表的顺序表示,2.3 线性表的链接表示,2.4 多项式的算术运算,南京邮电大学计算机学院,陈慧南 2006年9月,2.1 线性表,ADT,南京邮电大学计算机学院,陈慧南 2006年9月,线性表的定义,线性表是,n(,0),个元素,a,0,a,1,a,n-1,的线性序列，记为: (,a,0,a,1,a,n-1,)。,其中,n,是线性表中元素的个数，称为,线性表的长度,；,n=0,时称为,空表,。,a,i,是表中下标为,i,的元素（,i=0,1,n-1），,称,a,i,是,a,i,+1,的,直接前驱元素,，,a,i,+1,是,a,i,的,直接后继元素。,线性表是,动态数据结构,，它的表长可以改变。,南京邮电大学计算机学院,陈慧南 2006年9月,线性表,ADT,ADT,LinearList,数据：,0个或多个元素的线性序列（,a,0,a,1,.,a,n-1,），,其最大允许长度为,MaxListSize,。,运算：,Create()：,创建一个空线性表。,Destroy()：,撤消一个线性表。,IsEmpty,()：,若线性表空，则返回,true；,否则返回,false。,Length()：,返回表中元素个数。,南京邮电大学计算机学院,陈慧南 2006年9月,Find(i,x)：,在,x,中返回表中下标为,i,的元素,a,i,。,若不存在，则返回,false，,否则返回,true。,Search(x)：,若,x,不在表中，则返回-1，否则返回,x,在表中的下标。,Insert(i,x)：,在元素,a,i,之后插入,x。,若,i=-1，,则,x,插在第一个元素,a,0,前。若插入成功，则返回,true，,否则返回,false。,Delete(i)：,删除元素,a,i,。,若删除成功，则返回,true，,否则返回,false。,Update(i,x)：,将元素,ai,的值修改为,x。,若修改成功，则返回,true，,否则返回,false。,Output(out)：,把表送至输出流, / 插入,x,到表：,（,a,0,a,1,.,a,n-1,）,南京邮电大学计算机学院,陈慧南 2006年9月,线性表类,template ,class,LinearList,public:,virtual,bool,Find(,int,i,T,virtual,bool,Insert(,int,i,T x)=0;,virtual,bool,Delete(,int,i)=0;,protected:,int,n;,/,线性表的长度,;,南京邮电大学计算机学院,陈慧南 2006年9月,2.2 线性表的顺序表示,南京邮电大学计算机学院,陈慧南 2006年9月,2.2.1 顺序存储结构,顺序存储表示,是用一组地址连续的存储单元依次存储线性表中元素。,顺序表,顺序,表示的线性表称为顺序表,a,0,a,1,a,i,a,n-1,0 1 i n-1 maxLength-1,南京邮电大学计算机学院,陈慧南 2006年9月,地址计算公式,若已知顺序表中每个元素占,k,个存储单元，第一个元素,a,0,在计算机内存中的首地址是,loc(a,0,)，,则表中任意一个元素,a,i,在内存中的存储地址,loc(,a,i,),为,loc(,a,i,)=loc(a,0,)+i*k,随机存取结构,只要给定,loc(a,0,),和,k，,就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。,南京邮电大学计算机学院,陈慧南 2006年9月,2.2.2 顺序表类,顺序表类,template ,class,SeqList,:public,LinearList,public: /,公有函数,SeqList,(,int mSize,);,SeqList,() ,d,elete elements,;,bool,Find(,int,i,T,int,Search(T x) const;,bool,Insert(,int,i,T x);,bool,Delete(,int,i);,SingleList,LinearList,SeqList,南京邮电大学计算机学院,陈慧南 2006年9月,private:/,私有数据,int maxLength,;/,顺序表的最大长度,T *elements;/,动态一维数组的指针,;,南京邮电大学计算机学院,陈慧南 2006年9月,动态存储分配,构造函数，构建一个空,线性,表,template ,SeqList,:,SeqList,(,int mSize,),maxLength,=,mSize,;,elements=new T,maxLength,;,n=0;,南京邮电大学计算机学院,陈慧南 2006年9月,析构函数，撤消一个顺序表,template ,SeqList,: ,SeqList,(),delete elements;,南京邮电大学计算机学院,陈慧南 2006年9月,2.2.3 线性表运算实现,搜索运算,Find(i,x):,查找下标为,i,的元素,a,i,。,在,x,中返回表中下标为,i,的元素,a,i,(,即表中,第,i+1,个元素)。如果不存在，则返回,false，,否则返回,true。,x=elementsi;,渐近时间复杂度,：,O(1),a,0,a,1,a,i,a,n-1,0 1 i n-1 maxLength-1,南京邮电大学计算机学院,陈慧南 2006年9月,template,bool SeqList,:Find(,int,i,T& x) const,/O(1),if (in1) /,对,i,进行越界检查,cout,Out of Bounds,endl,; return false;,x=elementsi;,/,通过引用参数,x,返回下标为,i,的元素,return true;,南京邮电大学计算机学院,陈慧南 2006年9月,插入运算,Insert(i,x)：,在表中下标为,i,的元素,a,i,后插入,x。,若,i=-1，,则将新元素,x,插在最前面。若插入成功，返回,true；,南京邮电大学计算机学院,陈慧南 2006年9月,插入运算的平均时间复杂度,分析：设顺序表长度为,n，,共有,n+1,个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即,P,i,=1/(n+1)，,在位置,i（i=-1,0,n-1）,后插入一个元素要移动,n-i-1,个元素。,南京邮电大学计算机学院,陈慧南 2006年9月,template,bool SeqList,:Insert(,int,i,T x),/,在元素,a,i,之后插入,x,if (in-1) ,/,越界检查,cout,Out Of Bounds,endl,; return false;,if (n=,maxLength,)/,上溢出检查,cout,OverFlow,i;j-),elementsj+1=elementsj;,elementsi+1=x;n+;,return true;,南京邮电大学计算机学院,陈慧南 2006年9月,删除运算,Delete(i)：,删除元素,a,i,。,南京邮电大学计算机学院,陈慧南 2006年9月,删除运算的平均时间复杂度,分析:,设顺序表长度为,n,则删除元素,a,i,（i=0,n-1）,要移动,n-i-1,元素。若删除表中每个元素的概率是相等的，即,Q,i,=1/n，,南京邮电大学计算机学院,陈慧南 2006年9月,template ,bool SeqList,:Delete(,int,i),/,删除元素,a,i,if (!n) /,下溢出检查,cout,UnderFlow,endl,; return false;,if (in-1) ,cout,Out Of Bounds,endl,; return false;,/,从前往后逐个前移元素,for (,int,j=i+1;jn;j+),elementsj-1=elementsj;,n-; return true;,南京邮电大学计算机学院,陈慧南 2006年9月,void main(),int,x=10;,SeqList, r(,4,);,r.Insert(-1,x); r.Insert(-1,x);,r.Output(,cout,); /?,请复习,C+，,理解这一函数,南京邮电大学计算机学院,陈慧南 2006年9月,线性表的顺序存储表示的优缺点,优点：,随机存取；,存储空间利用率高。,缺点：,插入、删除效率低；,必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大。,南京邮电大学计算机学院,陈慧南 2006年9月,2.3,线性表的链接表示,南京邮电大学计算机学院,陈慧南 2006年9月,2.3.1,单链表,链接存储表示,单链表的结点结构,单链表结构,element,link,a,0,a,1,a,2,a,n-1,first,非空单链表,first,空单链表,=,NULL,指针变量的存储单元,红色为结点的指针域,南京邮电大学计算机学院,陈慧南 2006年9月,注意事项,头指针,first,是指向单链表的,头结点,的指针,最后一个结点的指针域为,，地址值为0,逻辑上相邻的元素在物理上不一定相邻,不能出现“断链”现象,南京邮电大学计算机学院,陈慧南 2006年9月,结点类,#,include ,linearlist,.h,template class,SingleList,；/,超前声明,template ,class Node,private:,T,element;,Node *,link,;,friend,class,SingleList,;,;,element,link,南京邮电大学计算机学院,陈慧南 2006年9月,单链表类,template ,class,SingleList,:public,LinearList,public:,SingleList,() first=NULL; n=0; ,SingleList,();,bool,Find(,int,i,T,int,Search(T x) const;,bool,Insert(,int,i,T x);,bool,Delete(,int,i);,南京邮电大学计算机学院,陈慧南 2006年9月,.,private:,Node* first;,;,顺序表类,SeqList,、,单链表类,SingleList,是抽象线性表类,LinearList,类的,派生类。,SingleList,LinearList,SeqList,Node,friend,南京邮电大学计算机学院,陈慧南 2006年9月,构造函数,SingleList,() first=NULL; n=0; ,析构函数,template ,SingleList,: ,SingleList,(),Node *p;,while (first),p=first-link;,delete first;,first=p;,南京邮电大学计算机学院,陈慧南 2006年9月,搜索运算,必须从头指针开始沿链逐个计数查找，称为,顺序查找,搜索运算的平均、最坏的渐近时间复杂度：,O(n),南京邮电大学计算机学院,陈慧南 2006年9月,template,bool SingleList,:Find(,int,i,T& x)const, /,在(,a,0,a,1,.,a,n,1,),中找下标为,i,的元素,a,i,if (in1),/,对,i,进行越界检查,cout,element; return true;,南京邮电大学计算机学院,陈慧南 2006年9月,插入运算,修改两个指针域的值,插入渐近时间复杂度：,O(1),q-link=p-link;,p-link=q,；,南京邮电大学计算机学院,陈慧南 2006年9月,插入运算步骤,：,生成数据域为,x,的新结点，,q,指向新结点;,从,first,开始找第,i+1,个结点，,p,指向该结点；,将,q,插入,p,之后。,表长加,1。,南京邮电大学计算机学院,陈慧南 2006年9月,template,bool SingleList,:Insert(,int,i,T x),if (in1),cout,element=x;,Node *p=first;/,找,a,i,元素所在的结点,p,for (,int,j=0; jlink;,first,a,0,a,1,a,2,a,n-1,非空单链表,first,空单链表,p,p,p,i=2,南京邮电大学计算机学院,陈慧南 2006年9月,if(i1) ,q-link=p-link;/,新结点,q,插在,p,之后,p-link=q;,else ,q-link=first; /,新结点,q,插在头结点之前,first=q;,n+; return true;,/,删除结点,p,是指删除指针变量,p,所指示的结点*,p。,南京邮电大学计算机学院,陈慧南 2006年9月,单链表的删除,只需修改一个指针,“,q-link=p-link,”，,但还需使用“,delete p,；”,语句回收结点占用的空间。,南京邮电大学计算机学院,陈慧南 2006年9月,单链表的步骤,从,first,开始找第,i+1,个结点，,p,指向该结点，,q,指向,p,之前驱结点;,从单链表中删除,p；,释放,p,之空间；,表长,减1。,南京邮电大学计算机学院,陈慧南 2006年9月,template,bool SingleList,:Delete(,int,i),if ( !n ) ,cout,UnderFlow,endl,;,return false;,if ( in-1 ) ,cout, Out Of Boundslink;/,删除头结点,else ,p=q-link;,q-link=p-link;,delete p; n-;,return true;,南京邮电大学计算机学院,陈慧南 2006年9月,单链表运算的优缺点,优点,单链表插入和删除只需修改一两个指针，无需移动元素。如已知前驱结点，插入删除运算的时间为,O(1),可以动态分配结点空间，线性表的长度只受内存大小限制。,缺点,查找运算费时，只能顺序查找，不能随机查找,南京邮电大学计算机学院,陈慧南 2006年9月,2.3.2 带表头结点的单链表,请区分“表头结点”和“头结点”,南京邮电大学计算机学院,陈慧南 2006年9月,template,HeaderList,:,HeaderList,(),Node *first=new Node;,first-link=NULL;,n=0;,南京邮电大学计算机学院,陈慧南 2006年9月,template,bool HeaderList,:Insert(,int,i, T x),if (in1) ,cout, Out Of Boundselement=x;,q-link=p-link;,p-link=q;,n+;return true;,南京邮电大学计算机学院,陈慧南 2006年9月,template,bool HeaderList,:Delete(,int,i),if ( !n ) ,cout,UnderFlow,endl,; return false;,if ( in1 ) ,cout, Out Of Boundslink;,q-link=p-link;,delete p;,n-; return true;,南京邮电大学计算机学院,陈慧南 2006年9月,2.3.3 单循环链表,南京邮电大学计算机学院,陈慧南 2006年9月,2.3.4 双向链表,南京邮电大学计算机学院,陈慧南 2006年9月,结点类,template class,DoubleList,;/,超前声明,template ,class,DNode,private:,T element;,DNode, *,lLink, *,rLink,;,friend,DoubleList,;,;,南京邮电大学计算机学院,陈慧南 2006年9月,插入操作的核心步骤如下：,（,1,）,DNode, *q=new,DNode,;,q-element=x;,（,2,）,q-,lLink,=p-,lLink,; q-,rLink,=p;,p-,lLink,-,rLink,=q; p-,lLink,=q;,错误：,p-,lLink,-,rLink,=q； q-,lLink,=p-,lLink,;,q-,rLink,=p; p-,lLink,=q;,南京邮电大学计算机学院,陈慧南 2006年9月,删除操作的核心步骤如下：,（,1,）,p-,lLink,-,rLink,=p-,rLink,;,p-,rLink,-,lLink,=p-,lLink,;,（,2,）,delete p;,南京邮电大学计算机学院,陈慧南 2006年9月,2.4 多项式的算术运算,多项式相加,p(,x,)=3,x,14,8,x,8,+6,x,2,+2,q(,x,)=2,x,10,+4,x,8,6,x,2,q,(,x,),p(,x,)+q(,x,),结果：,q,(,x,) =3,x,14,+2,x,10,4,x,8,+2,南京邮电大学计算机学院,陈慧南 2006年9月,多项式的逻辑结构：视为线性表,p(x)=3x,14,-8x,8,+6x,2,+2,数据元素,(,coef,exp),表示多项式项,coef,x,exp,，,coef,是该项的系数，,exp,是变元,x,的指数。,南京邮电大学计算机学院,陈慧南 2006年9月,多项式的存储表示,p(x)=3x,14,-8x,8,+6x,2,+2,( (,3,14)，(-8,8)，(6,2)，(2,0) ),顺序表示,线性表长度事先难以确定；,算术运算需插入和删除元素。,南京邮电大学计算机学院,陈慧南 2006年9月,多项式的链接表示,多项式的项,南京邮电大学计算机学院,陈慧南 2006年9月,2.4.1,项结点类,项结点类,Term*,I,nsertAfter,（,int,c,int,e）,构造一个新项（,c,e）,结点，插在*,this,项之后，函数返回新项结点的地址。,南京邮电大学计算机学院,陈慧南 2006年9月,class Term,public:,Term(,int,c,int,e); /,构造函数1,Term(,int,c,int,e,Term*,nxt,); /,构造函数2,Term*,InsertAfter,(,int,c,int,e);,private:,int coef,;,int,exp;,Term *link;,friend,ostream,& operator,(,ostream,/,重载“,InsertAfter,(c,e);,南京邮电大学计算机学院,陈慧南 2006年9月,重载输出运算符,ostream,&operator (,ostream,& out, const Term&,val,),/,用 -4,x2,表示 -4,x,2,。,if(val.,coef,=0) return out;,outval.,coef,;,switch(val.exp),case 0:break;,case 1:outX; break;,default:outXval.exp; break;,return out;,南京邮电大学计算机学院,陈慧南 2006年9月,2.4.3,多项式的,C+,类,class,Polynominal,public:,Polynominal,();,Polynominal,();,void,AddTerms,(,istream, /,建立多项式链表,void Output(,ostream, /,输出多项式,void,PolyAdd,(,Polynominal, /,多项式相加,南京邮电大学计算机学院,陈慧南 2006年9月,private:,Term*,theList,;,/,单循环链表的表头指针,friend,ostream,& operator (,istream,&,Polynominal,friend,Polynominal,& operator +(,Polynominal,&,Polynominal,;,南京邮电大学计算机学院,陈慧南 2006年9月,2.4.4,多项式类的实现,构造函数,Polynominal,:,Polynominal,(),theList,=new Term(0,1);,theList,-link=,theList,;,南京邮电大学计算机学院,陈慧南 2006年9月,2.4.5 多项式的输入和输出,输入多项式,void,Polynominal,:,AddTerms,(,istream,& in),Term* q=,theList,;,int,c,e;,for(;),cout,Input a term(,coef,exp):nce;,if (e,InsertAfter,(c,e);,南京邮电大学计算机学院,陈慧南 2006年9月,输出多项式,void,Polynominal,:Output(,ostream,& out)const,bool,start=true;,Term *p=,theList,-link;,outThe,polynominal,is:nlink),if (!start & p-,coef,0) out+;,start=false;,out*p;,outexp=q-exp,，,则同类项合并，令,q-,coef,=q-,coef,+p-,coef,；,如果此时有,q-,coef,=0，,则从,q(x),中删除结点*,q，,指针,q,指向原*,q,的后继，指针,p,指向下一项；否则，指针,p、q,和,q1,均后移一项。,若,p-expq-exp,，,则复制*,p，,新结点插在 *,q1,与*,q,之间，指针,q1,指向新结点，指针,q,不动，而指针,p,指向下一项。,若,p-expexp,，,则将,q,指示的当前项保留在,q(x),中，所以令指针,q1,和,q,后移一项，指针,p,不动。,南京邮电大学计算机学院,陈慧南 2006年9月,void,Polynominal,:,PolyAdd,(,Polynominal,& r),/,将多项式,r,加到多项式,this,上,Term* q,*q1=,theList,*p;,p=r.,theList,-link;,q=q1-link;,while (p-exp=0) ,while (p-expexp) ,q1=q; q=q-link;,南京邮电大学计算机学院,陈慧南 2006年9月,if(p-exp=q-exp) ,q-,coef,=q-,coef,+p-,coef,;,if(q-,coef,=0) ,q1-link=q-link; delete(q);,q=q1-link;,else ,q1=q; q=q-link;,else q1=q1-,InsertAfter,(p-,coef,p-exp);,p=p-link;,/while (p-exp=0),南京邮电大学计算机学院,陈慧南 2006年9月,