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

《《数据结构》陈慧南 第02章》由会员分享，可在线阅读，更多相关《《数据结构》陈慧南 第02章（70页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,南京邮电大学计算机学院,,陈慧南 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

2、(,,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,

3、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,之后插

4、入,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 ,,c

5、lass,,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 顺序存储结构,顺序存储表示,,,是用一组地址连续的存储单元依次存储线性表中元素。,,,,顺序表,,顺序,表示的线性表称为

6、顺序表,,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，,就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。,南京邮电

7、大学计算机学院,,陈慧南 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

8、,南京邮电大学计算机学院,,陈慧南 2006年9月,,,,……,,private://,私有数据,,,int maxLength,; //,顺序表的最大长度,,,T *elements; //,动态一维数组的指针,,};,,,,,南京邮电大学计算机学院,,陈慧南 2006年9月,,动态存储分配,,构造函数，构建一个空,线性,表,,,template ,,SeqList,::,SeqList,(,int mSize,),,{,,,maxLength,=,mSize,;,,elements=new T[,maxLength,];,,n=0;,,},,,,南京邮电大学计算机学院,,陈慧南 2006年

9、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=elements[i];,,渐近时间复杂度,：,O(1),,,a,0,a,1,…,a,i,…,,a,n-1,…,0 1

10、 … i … n-1 … maxLength-1,南京邮电大学计算机学院,,陈慧南 2006年9月,,template,,bool SeqList,::Find(,int,i,T& x) const,,{,//O(1),,if (in−1){ //,对,i,进行越界检查,,,cout,<<"Out of Bounds"<<,endl,; return false;,,},,,x=elements[i];,//,通过引用参数,x,返回下标为,i,的元素,,,return true;,,},,南京邮电大学计算机学院,,陈慧南 2006年9月,,插入运算,,,Insert(i

11、,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

12、,之后插入,x,,,if (in-1) {,//,越界检查,,,cout,<<"Out Of Bounds"<<,endl,; return false;,,},,if (n==,maxLength,){ //,上溢出检查,,,cout,<<",OverFlow,"<<,endl,; return false;,,},//,从后往前逐个后移元素,,,for (,int,j=n-1;j>i;j--),elements[j+1]=elements[j];,,,,,elements[i+1]=x;n++;,,,,return true;,,},南京邮电大学计算机学院,,陈慧南 2006年9月,,删除

13、运算,,,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 fals

14、e;,,},,if (in-1) {,,,cout,<<"Out Of Bounds"<<,endl,; return false;,,,,},//,从前往后逐个前移元素,,,for (,int,j=i+1;j r(,4,);,,r.Insert(-1,x); r.Insert(-1,x);,,r.Output(,cout,); //?

15、?,请复习,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,,空单链表,,

16、,=>,NULL,指针变量的存储单元,红色为结点的指针域,南京邮电大学计算机学院,,陈慧南 2006年9月,,注意事项,,头指针,first,是指向单链表的,头结点,的指针,,最后一个结点的指针域为,，地址值为0,,逻辑上相邻的元素在物理上不一定相邻,,不能出现“断链”现象,南京邮电大学计算机学院,,陈慧南 2006年9月,,结点类,,#,include ",linearlist,.h",,template class,,SingleList,；//,超前声明,,template ,,class Node,,{,,private:,,T,element;,,Node *,link,;,,f

17、riend,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);,,,……,南京邮电大学计算机学院,

18、,陈慧南 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=fir

19、st->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 (in−1){,,,,//,对,i,进行越界检查,,,cout,<< "Out Of

20、Bounds"; return false;,,},,Node *p=first;,,for (,int,j=0; jlink;,,x=p->element; return true;,,},,南京邮电大学计算机学院,,陈慧南 2006年9月,,,插入运算,,修改两个指针域的值,插入渐近时间复杂度：,O(1),,q->link=p->link;,,p->link=q,；,,,,南京邮电大学计算机学院,,陈慧南 2006年9月,,,插入运算步骤,：,,,生成数据域为,x,的新结点，,q,指向新结点;,,从,first,开始找第,i+1,个结点，,p,指向该结点；,,将,q,插入,p,之后。,,,

21、表长加,1。,,南京邮电大学计算机学院,,陈慧南 2006年9月,,template,,bool SingleList,::Insert(,int,i,T x),,{,,if (in−1){,,,cout,<< "Out Of Bounds"; return false;,,},,Node * q=new Node;q->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,南京邮

22、电大学计算机学院,,陈慧南 2006年9月,,,,if(i>−1) {,,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,；”,语句回收结点占用的空间。,

23、,,南京邮电大学计算机学院,,陈慧南 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 Bounds"<<,endl,;,

24、,return false；,,},,Node *p=first,*q=first;,,for (,int,j=0; jlink;,南京邮电大学计算机学院,,陈慧南 2006年9月,,,if (i==0) first=first->link;//,,删除头结点,,,else {,,p=q->link;,,q->link=p->link;,,},,delete p; n--;,,return true;,,},,南京邮电大学计算机学院,,陈慧南 2006年9月,,,单链表运算的优缺点,,优点,,,单链表插入和删除只需修改一两个指针，无需移动元素。如已知前驱结点，插入删除运算的时间为,O(

25、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,::I

26、nsert(,int,i, T x),,{,,if (in−1) {,,,cout,<< "Out Of Bounds"<<,endl,; return false;,,},,Node *p=first;,,,for (,int,j=0; jlink;,,Node * q=new Node;,,q->element=x;,,,q->link=p->link;,,,,p->link=q;,,n++;return true;,,},南京邮电大学计算机学院,,陈慧南 2006年9月,,template,,bool HeaderList,::Delete(,int,i),,{,,if ( !n ) {

27、,,,cout,<<",UnderFlow,"<<,endl,; return false;,,},,if ( in−1 ) {,,,cout,<< "Out Of Bounds"<<,endl,; return false;,,},,Node *q=first, *p;,,,for (,int,j=0; jlink;,,p=q->link;,,,,q->link=p->link;,,,,delete p;,,,,n--; return true;,,},南京邮电大学计算机学院,,陈慧南 2006年9月,,2.3.3 单循环链表,南京邮电大学计算机学院,,陈慧南 2006年9月,,2.3.4

28、 双向链表,南京邮电大学计算机学院,,陈慧南 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->,rLi

29、nk,=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 多项式的算术运算,多项式相加

30、,,,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月,,多

31、项式的存储表示,,,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,项之后，函数返回新项结点的地址。,南京邮电大学计算机学院,,陈慧南 20

32、06年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,,,//,重载“<<”，输出多项式的一项,,,friend class,Poly

33、nominal,;,,};,南京邮电大学计算机学院,,陈慧南 2006年9月,,构造函数,,Term::Term(,int,c,,int,e):,coef,(c),exp(e),,{,,link=0;,,},,Term::Term(,int,c,,int,e,Term *,nxt,):,coef,(c),exp(e),,{,,link=,nxt,;,,},,Term::Term(,int,c,,int,e),,{,,coef,=c;exp=e;,,link=0;,,},南京邮电大学计算机学院,,陈慧南 2006年9月,,,InsertAfter,函数实现,,Term* Term::,Inser

34、tAfter,(,int,c,,int,e),,{,,link=new Term(c,e,link);,,,,return link;,,},,,,调用语句：,q=q->,InsertAfter,(c,e);,南京邮电大学计算机学院,,陈慧南 2006年9月,,重载输出运算符,,ostream,&operator <<(,ostream,& out, const Term&,val,),,{,//,用 -4,x^2,表示 -4,x,2,。,,if(val.,coef,= =0) return out;,,out<

35、eak;,,,,case 1:out<<"X"; break;,,default:out<<"X^"<

36、 //,多项式相加,,…,南京邮电大学计算机学院,,陈慧南 2006年9月,,private:,,,Term*,theList,;,//,单循环链表的表头指针,,,friend,ostream,& operator << (,ostream,&,,,const,Polynominal,,,friend,istream,& operator >>(,istream,&,,,,,Polynominal,,,friend,Polynominal,& operator +(,Polynominal,&,,,,,Polynominal,,,};,南京邮电大学计算机学院,,陈慧南 2006年9月,,,2.

37、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):\n"<<,endl,;,,in

38、>>c>>e;,,if (e<0) break;,,q=q->,InsertAfter,(c,e);,,},,},南京邮电大学计算机学院,,陈慧南 2006年9月,,,输出多项式,,void,Polynominal,::Output(,ostream,& out)const,,{,,bool,start=true;,,Term *p=,theList,->link;,,out<<"The,polynominal,is:\n"<<,endl,;,,for ( ;,p!=,theList,; p=p->link){,,if (!start && p->,coef,>0) out<<'+';,,st

39、art=false;,,,,out<<*p;,,,},,out<<,endl,;,,},南京邮电大学计算机学院,,陈慧南 2006年9月,,,多项式相加,南京邮电大学计算机学院,,陈慧南 2006年9月,,若,p->exp==q->exp,，,则同类项合并，令,q->,coef,=q->,coef,+p->,coef,；,如果此时有,q->,coef,==0，,则从,q(x),中删除结点*,q，,指针,q,指向原*,q,的后继，指针,p,指向下一项；否则，指针,p、q,和,q1,均后移一项。,,若,p->exp>q->exp,，,则复制*,p，,新结点插在 *,q1,与*,q,之间，指针,q1

40、,指向新结点，指针,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->expex

41、p) {,,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月,,