数据结构讲义

数据结构王源2016年9月第2章线性表

2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算实验二、链表及其应用

2.1线性表ADT线性表的定义线性表是n(0)个元素a0,a1,…,an-1的线性序列，记为:(a0,a1,…,an-1)。其中n是线性表中元素的个数，称为线性表的长度；n=0时称为空表。

ai是表中下标为i的元素（i=0,1,…,n-1），称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。

线性表ADTADTLinearList{数据：

0个或多个元素的线性序列（a0,a1,...,an-1），其最大允许长度为MaxListSize。运算：

Create()：创建一个空线性表。

Destroy()：撤消一个线性表。

IsEmpty()：若线性表空，则返回true；否则返回false。

Length()：返回表中元素个数。

Find(i,x)：在x中返回表中下标为i的元素ai。若不存在，则返回false，否则返回true。Search(x)：若x不在表中，则返回-1，否则返回x在表中的下标。Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。若插入成功，则返回true，否则返回false。Delete(i)：删除元素ai。若删除成功，则返回true，否则返回false。Update(i,x)：将元素ai的值修改为x。若修改成功，则返回true，否则返回false。Output(out)：把表送至输出流}//插入x到表：（a0,a1,...,an-1）

线性表类template<classT>classLinearList{public:……virtualboolFind(inti,T&x)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;……protected:

intn;//线性表的长度};

2.2线性表的顺序表示

2.2.1顺序存储结构顺序存储表示是用一组地址连续的存储单元依次存储线性表中元素。顺序表顺序表示的线性表称为顺序表

a0a1…ai

…

an-1

…01…i…n-1…maxLength-1

地址计算公式

若已知顺序表中每个元素占k个存储单元，第一个元素a0在计算机内存中的首地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为

loc(ai)=loc(a0)+i*k

随机存取结构只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。2.2.2顺序表类顺序表类template<classT>classSeqList:public

LinearList<T>{public://公有函数

SeqList(intmSize);

~SeqList(){delete[]elements;}boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……SingleListLinearListSeqList

……private://私有数据

intmaxLength; //顺序表的最大长度

T*elements; //动态一维数组的指针};

动态存储分配构造函数，构建一个空线性表

template<classT>SeqList<T>::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}

析构函数，撤消一个顺序表template<classT>SeqList<T>::~SeqList(){delete[]elements;}2.2.3线性表运算实现搜索运算

Find(i,x):

查找下标为i的元素ai。在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回

false，否则返回true。x=elements[i];渐近时间复杂度：O(1)

a0a1…ai

…

an-1

…01…i…n-1…maxLength-1

template<classT>boolSeqList<T>::Find(inti,T&x)const{//O(1)if(i<0||i>n−1){ //对i进行越界检查

cout<<"OutofBounds"<<endl;returnfalse;}

x=elements[i];//通过引用参数x返回下标为i的元素

returntrue;}

插入运算

Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；

插入运算的平均时间复杂度分析：设顺序表长度为n，共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，在位置i（i=-1,0,…,n-1）后插入一个元素要移动n-i-1个元素。

template<classT>boolSeqList<T>::Insert(inti,Tx){//在元素ai之后插入xif(i<-1||i>n-1){//越界检查

cout<<"OutOfBounds"<<endl;returnfalse;}if(n==maxLength){ //上溢出检查

cout<<"OverFlow"<<endl;returnfalse;}//从后往前逐个后移元素

for(intj=n-1;j>i;j--)elements[j+1]=elements[j];

elements[i+1]=x;n++; returntrue;}

删除运算

Delete(i)：删除元素ai。

删除运算的平均时间复杂度分析:

设顺序表长度为n,则删除元素ai（i=0,…,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，

template<classT>boolSeqList<T>::Delete(inti){//删除元素ai

if(!n){ //下溢出检查

cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){ cout<<"OutOfBounds"<<endl;returnfalse;}//从前往后逐个前移元素

for(intj=i+1;j<n;j++)elements[j-1]=elements[j];

n--;returntrue;}

voidmain(){intx=10;SeqList<int>r(4);r.Insert(-1,x);r.Insert(-1,x);r.Output(cout);//??请复习C++，理解这一函数}线性表的顺序存储表示的优缺点

优点：随机存取；存储空间利用率高。缺点：插入、删除效率低；必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大。2.3线性表的链接表示2.3.1单链表链接存储表示单链表的结点结构单链表结构elementlinka0a1a2an-1…first∧非空单链表first空单链表=>NULL指针变量的存储单元红色为结点的指针域

注意事项头指针first是指向单链表的头结点的指针最后一个结点的指针域为，地址值为0逻辑上相邻的元素在物理上不一定相邻不能出现“断链”现象

结点类#include"linearlist.h"template<classT>classSingleList；//超前声明template<classT>classNode{private:Telement;Node<T>*link;friendclassSingleList<T>;};elementlink

单链表类template<classT>classSingleList:publicLinearList<T>{public:SingleList(){first=NULL;n=0;}~SingleList();boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);……

…….private:

Node<T>*first;};

顺序表类SeqList、单链表类SingleList是抽象线性表类LinearList类的派生类。SingleListLinearListSeqListNodefriend

构造函数

SingleList(){first=NULL;n=0;}析构函数

template<classT>SingleList<T>::~SingleList(){Node<T>*p;while(first){p=first->link;deletefirst;first=p;}}33/244单链表的类定义小结使用面向对象方法，要把数据与操作一起定义和封装，用多个类表达一个单链表。

链表结点(ListNode)类链表(SList)类定义方式（多种方式）

复合方式嵌套方式

继承方式结构方式34/244

classSList;

//复合方式

classListNode{

//链表结点类

friendclassSList;

//链表类为其友元类

private:

intdata;

//结点数据,整型

ListNode*link;//结点指针

};classSList{ //链表类

private:ListNode*first;//表头指针

};复合方式的类定义35/244classSList{//嵌套方式private:

classListNode{//嵌套链表结点类

public:

intdata;

ListNode*link;

};ListNode*first;

//表头指针public:

//链表操作………};嵌套方式的类定义36/244//链表类和链表结点类定义(继承方式)classListNode{

//链表结点类

protected:

intdata;

ListNode*link;

};classSList:public

classListNode{//链表类,继承链表结点类的数据和操作

private:ListNode*first;//表头指针};继承方式的类定义37/244在复合方式中，链表结点类中声明链表类是它的友元类，这样可以“奉献”它的私有成员给链表类。这种方式灵活。在嵌套方式中，链表结点类是链表类的私有成员，这样限制了链表结点类的应用范围。在继承方式中，链表类声明为链表结点类的派生类，这在实现上是可行的。但在逻辑上是有问题的，如三角形is多边形（继承关系）链表is链表结点（显然概念不准确）

搜索运算必须从头指针开始沿链逐个计数查找，称为顺序查找

搜索运算的平均、最坏的渐近时间复杂度：O(n)

template<classT>boolSingleList<T>::Find(inti,T&x)const{//在(a0,a1,...,an−1)中找下标为i的元素aiif(i<0||i>n−1){ //对i进行越界检查

cout<<"OutOfBounds";returnfalse;}Node<T>*p=first;for(intj=0;j<i;j++)p=p->link;x=p->element;returntrue;}

插入运算修改两个指针域的值插入渐近时间复杂度：O(1)q->link=p->link;p->link=q；

插入运算步骤：生成数据域为x的新结点，q指向新结点;

从first开始找第i+1个结点，p指向该结点；将q插入p之后。

表长加1。

template<classT>boolSingleList<T>::Insert(inti,Tx){if(i<−1||i>n−1){cout<<"OutOfBounds";returnfalse;}Node<T>*q=newNode<T>;q->element=x; Node<T>*p=first; //找ai元素所在的结点pfor(intj=0;j<i;j++)p=p->link;firsta0a1a2an-1…∧非空单链表first空单链表pppi=2

if(i>−1){q->link=p->link; //新结点q插在p之后

p->link=q;}else{q->link=first;//新结点q插在头结点之前

first=q;}n++;returntrue;}//删除结点p是指删除指针变量p所指示的结点*p。

单链表的删除

只需修改一个指针“q->link=p->link”，但还需使用“deletep；”语句回收结点占用的空间。

单链表的步骤

从first开始找第i+1个结点，p指向该结点，q指向p之前驱结点;

从单链表中删除p；释放p之空间；

表长减1。

template<classT>boolSingleList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){cout<<"OutOfBounds"<<endl;returnfalse；}Node<T>*p=first,*q=first;for(intj=0;j<i-1;j++)q=q->link;

if(i==0)first=first->link;//删除头结点

else{p=q->link;q->link=p->link;}deletep;n--;returntrue;}

单链表运算的优缺点优点

单链表插入和删除只需修改一两个指针，无需移动元素。如已知前驱结点，插入删除运算的时间为O(1)

可以动态分配结点空间，线性表的长度只受内存大小限制。缺点

查找运算费时，只能顺序查找，不能随机查找2.3.2带表头结点的单链表请区分“表头结点”和“头结点”template<classT>HeaderList<T>::HeaderList(){Node<T>*first=newNode<T>; first->link=NULL;n=0;}

template<classT>boolHeaderList<T>::Insert(inti,Tx){if(i<−1||i>n−1){cout<<"OutOfBounds"<<endl;returnfalse;}Node<T>*p=first; for(intj=0;j<=i;j++)p=p->link;Node<T>*q=newNode<T>;q->element=x;q->link=p->link; p->link=q;n++;returntrue;}

template<classT>boolHeaderList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n−1){cout<<"OutOfBounds"<<endl;returnfalse;}Node<T>*q=first,*p; for(intj=0;j<i;j++)q=q->link;p=q->link; q->link=p->link; deletep; n--;returntrue;}2.3.3单循环链表2.3.4双向链表

结点类template<classT>classDoubleList; //超前声明template<classT> classDNode{private:Telement;DNode<T>*lLink,*rLink;friendDoubleList<T>;};

插入操作的核心步骤如下：（1）DNode<T>*q=newDNode<T>;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;

删除操作的核心步骤如下：（1）p->lLink->rLink=p->rLink;p->rLink->lLink=p->lLink;（2）deletep;2.4多项式的算术运算

多项式相加

p(x)=3x14−8x8+6x2+2q(x)=2x10+4x8−6x2

q(x)p(x)+q(x)结果：q(x)=3x14+2x10−4x8+2

多项式的逻辑结构：视为线性表

p(x)=3x14-8x8+6x2+2

数据元素(coef,exp)

表示多项式项coef·xexp，coef是该项的系数，exp是变元x的指数。

多项式的存储表示

p(x)=3x14-8x8+6x2+2((3,14)，(-8,8)，(6,2)，(2,0))

顺序表示

线性表长度事先难以确定；算术运算需插入和删除元素。

多项式的链接表示多项式的项

2.4.1

项结点类项结点类

Term*InsertAfter（intc,inte）构造一个新项（c,e）结点，插在*this项之后，函数返回新项结点的地址。

classTerm{public:Term(intc,inte);//构造函数1Term(intc,inte,Term*nxt);//构造函数2Term*InsertAfter(intc,inte);private:intcoef;intexp;Term*link;friendostream&operator<<(ostream&,constTerm&);//重载“<<”，输出多项式的一项

friendclassPolynominal;};

构造函数Term::Term(intc,inte):coef(c),exp(e){link=0;}Term::Term(intc,inte,Term*nxt):coef(c),exp(e){link=nxt;}Term::Term(intc,inte){coef=c;exp=e;link=0;}

InsertAfter函数实现Term*Term::InsertAfter(intc,inte){link=newTerm(c,e,link); returnlink;}调用语句：q=q->InsertAfter(c,e);

重载输出运算符ostream&operator<<(ostream&out,constTerm&val){//用-4x^2表示-4x2。

if(val.coef=

=0)returnout;out<<val.coef;switch(val.exp){case0:break;case1:out<<"X";break;default:out<<"X^"<<val.exp;break;}returnout;}2.4.3

多项式的C++类classPolynominal{public:Polynominal();

～Polynominal();voidAddTerms(istream&in);//建立多项式链表

voidOutput(ostream&out)const;//输出多项式

voidPolyAdd(Polynominal&r); //多项式相加

…

private:

Term*theList; //单循环链表的表头指针

friendostream&operator<<(ostream&,constPolynominal&);friendistream&operator>>(istream&,Polynominal&);friendPolynominal&operator+(Polynominal&,Polynominal&);};2.4.4

多项式类的实现

构造函数Polynominal::Polynominal() {theList=newTerm(0,−1);theList->link=theList; }2.4.5多项式的输入和输出输入多项式voidPolynominal::AddTerms(istream&in){

Term*q=theList;intc,e;for(;;){ cout<<"Inputaterm(coef,exp):\n"<<endl;in>>c>>e; if(e<0)break;q=q->InsertAfter(c,e);}}

输出多项式voidPolynominal::Output(ostream&out)const{boolstart=true;Term*p=theList->link;out<<"Thepolynominalis:\n"<<endl;for(;p!=theList;p=p->link){if(!start&&p->coef>0)out<<'+';start=false;out<<*p;}out<<endl;}

多项式相加

若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指向新结点，指针q不动，而指针p指向下一项。若p->exp<q->exp，则将q指示的当前项保留在q(x)中，所以令指针q1和q后移一项，指针p不动。

voidPolynominal::PolyAdd(Polynominal&r)//将多项式r加到多项式this上{Term*q,*q1=theList,*p;p=r.theList->link;q=q1->link;while(p->exp>=0){while(p->exp<q->exp){q1=q;q=q->link;}

if(p->exp==q->exp){q->coef=q->coef+p->coef;if(q->coef==0){q1->link=q->li