程序：第02章：线性表

第2章线性表

程序2.1线性表类

#include<iostream.h>

template<classT>

classLinearList

(

public:

virtualboolIslunpty()const=0;

virtualintLength()const=0;

virtualboolFind(inti,T&x)const=O;

virtualintSearch(Tx)const=0;

virtualboolInsert(inti,Tx)=0;

virtualboolDelete(inti)=0;

virtualboolUpdate(inti,Tx)=0;

virtualvoidOutput(ostream&out)const=0;

protected:

intn：线性表的长度

)；

程序2.2顺序表类

Sincludeinearlist.hz

template<classT>

classSeqList:publicLinearList<T>

(

public:

SeqLisl(intmSize);

~SeqList(){Delete[]elements};

boolIsEmptyOconst;

intLength0const;

boolFind(inti,T&x)const;

intSearch(Tx)const;

boolInsert(inti,Tx);

boolDelete(inti);

boolUpdate(inti,Tx);

voidOutput(ostrearo&out)const;

private:

intmaxLcngth;顺序表的最大长度

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

)；

template〈classT>

SeqList<T>::SeqList(intmSize)

(

maxLength=mSizc;

elements=newT[maxLength];动态分配顺序表的存储空间

n=0;

)

template<classT>

boolSeqList<T>::IsEmpty()const

(

returnn==0;

)

template<classT>

intSeqList<T>::Length0const

(

returnn;

)

tempiate<classT>

boolSeqList<T>::Find(inti,T&x)const

(

if(i<0||i>n-l)!对i进行越界检查

cout«/，0utofBounds，，«endl;returnfalse;

)

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

returntrue;

)

template<classT>

intSeqList<T>::Search(Tx)const

(

for(intj=O;j<n;j++)

if(clcmcnts[j]==x)returnj;从头开始搜索值为x的元素

return-1;

)

template<classT>

boolSeqList<T>::Insert(inti,Tx)

(

if(i<-l||i>n-l){

cout«z，0utOfBounds，，«endl;returnfalse;

)

if(n==maxLength){上溢出检查

cout«/，OverFlow，，«endl;returnfalse;

)

for(intj=n-l;j>i;j-)elements[j+l]=clcmcnts[j];从后往前逐个后移元素

elements[i+l]=x;将x插入下标为i的元素后面

n++;returntrue;

)

template<classT>

boolSeqList<T>::Delete(inti)

(

if(!n){下溢出检查

cout«，，UnderFlow，，«endl;returnfalse;

)

if(i<0||i>n-l)-

cout«7,0utOfBounds/，«endl;returnfalse;

)

for(intj=i+l;j<n;j++)elements[j-l]=elcmonts[j];从前往后逐个前移元素

n-;returntrue;

}

template<classT>

boolSeqList<T>::Update(inti,Tx)

(

if(i<011i>n-l)•：

cout«，zOutOfBounds，/«endl;returnfalse;

)

elemenls[i]=x;将下标为i的元素值修改为x

returntrue;

)

template<classT>

voidSeqList<T>::Output(ostreaniftout)const

(

for(inti=0;i<n;i++)out«elements[i]«，';

out«endl;

)

程序2.3结点类和单链表类

Sinclude"1incarlist.h"

template<classT>classSingleList;超前声明SingleList

template<classT>

classNode

{

private:

Telement;

Node<T>*link;

friendclassSingleList<T>;

)；

template<classT>

classSingleList:publicLinearList<T>

(

public:

SingleList(){first=NULL;n=0;}

^SingleList0;

boolIsEmptyOconst;

intLength0const;

boolFind(inti,T&x)const;

intSearch(Tx)const;

boolInsert(inti,Tx);

boolDelete(inti);

boolUpdate(inti,Tx);

voidClear();

voidOutput(ostreamfeout)const;

private:

Node<T>*first;

)；

template<classT>

SingleList<T>::〜SingleList()

(

Node<T>*p;

while(first){

p=first->link;

deletefirst;

first=p;

)

template<classT>

intSingleList<T>::Length()const

(

returnn;

)

template<classT>

boolSingleList<T>::IsEmpty0const

(

returnn==0;

}

template<classT>

boolSingleList<T>::Find(inti,T&x)const

(在⑸,&中找下标为i的元素&

if(i<0||i>n-l)(对i进行越界检查

cout«”OutOfBounds”;returnfalse;

)

Node<T>*p=first;

for(intj=0;j<i;j++)p=p->link;

x=p->element;returntrue;

}

tcmplate<classT>

intSingleList<T>::Search(Tx)const

(

Node<T>*p=first;

for(intj=0;p&&p->element!=x;j++)p=p->link：

if(p)returnj;

return-1;

)

tempiate<classT>

boolSingleList<T>::Insert(inti,Tx)

{

if(i<-l||i>n-l){

cout«”OutOfBounds”;returnfalse;

}

Node<T>*q=newNode<T>;q->element=x;生成新结点q

Node<T>*p=first;从头结点开始找元素所在的结点p

for(intj=0;j<i;j++)p-p->link;

if(i>-l){

q->link=p->link;新结点q插在P之后

p->link=q;

else{

q->1ink=first;新结点q插在头结点之前，成为新的头结点

first=q：

n++;returntrue;

)

tempiate<classT>

boolSingleList<T>::Delete(inti)

if(!n)若n=0,则再删除就会下溢出

cout«，/UndorFlov，，«endl;returnfalse;

if(i<0||i>n-l){

cout«”OutOfBounds*«endl;returnfalse;

}

Node<T>*p=first,*q=first;

for(intj=0;j<i-l;j++)q=q->link;q指向要删除的结点的前一结点

if(i==0)first=first->link;若i=0,则删除的是头结点

else{否则删除的是非头结点

p=q->link;P指向要删除的结点，q是P的前驱

q->link=p->link;从单链表中删除P结点

deletep;释放p占据的存储单元

n-;returntrue;

tempiate<classT>

boolSingleList<T>::Update(inti,Tx)

if(i<0||i>n-l){

cout«”OutOfBounds/，«endl;returnfalse;

Node<T>*p=first;

for(intj=0;j<i;j++)p=p->link;

p->element=x;returntrue;

)

template<classT>

voidSinglcList<T>::Output(ostreamftout)const

Node<T>*p=first;

while(p){

out«p->element«/，

p=p->link;

)

out«cndl;

)

程序2.4带表头结点单链表的构造、插入和删除函数

template<classT>

HeaderList<T>::HeaderListO

(

Node<T>*first=newNode<T>;空的带表头结点的单链表仍然有一个表头结点

first->1ink=NULL;

n=0;

)

template<classT>

boolHeaderList<T>::Insert(inti,Tx)

(

if(i<-l||i>n-l)(

cout«”OutOfBounds，/«endl;returnfalse;

}

Node<T>*p=first;从表头结点开始沿链查找i结点p

for(intj=0;j<=i;j++)p=p->link;

Node<T>*q=new5lode(T>;q->element=x;生成新结点q

q->link=p->link;p插入q之后，无需区分头结点和一般结点

p->link=q;

n++;returntrue;

)

template<classT>

boolHeaderList<T>::Delete(inti)

(

if(!n){

cout«，/UnderFlov，，«endl;returnfalse;

)

if(i<0||i>n-i){

cout«”OutOfBounds/，«endl;returnfalse;

Nodc<T>*q=first,*p;从表头结点开始沿链查找i结点的前驱结点q

for(intj=0;j<i;j++)q=q->link;

p=q->link;P指向要删除的结点

q->link=p->link;从链表中删除P，无需区分头结点和一般结点

deletep;释放P占据的存储单元

n-;returntrue;

}

程序2.5双向链表的结点类

template<classT>classDoubleList;超前声明DoubleList类

template<classT>声明DNode类

classDNode

(

private:

Telement;

DNode<T>*1Link,*rLink;

friendDoubleList<T>;

)；

程序2.6多项式项结点的C++类

classTerm

{

public:

Term(intc,inte);

Term(intc,inte,Term*nxt);

Term*InsertAfter(intc,inte);在this指针指示的结点后插入新结点

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(c)

(

link=nxt;

)

Term*Term::InsertAfter(intc,inte)

{为新项申请结点的存储单元，并用Term函数将

link=newTerm(c,e,link);c,e和this->link的值填入新结点的相应域

returnlink;

)

ostream&operator«^ostream&out,constTern&val)

{重载"<<"，输出多项式的一项,用coefX"exp表示coefXw

if(val.coef==0^returnout;

out«val.coef;

switch(val.exp；(

case0:break;

case1:out«，，X，/;break;

defaultexp;break;

)

returnout;

)

程序2.7多项式的C++类

classPolynominal

(

public:

Polynominal();

〜Polynominal();

voidAddTerms(istream&in);输入多项式的各项，构造多项式链表

voidOutput(ostroamftout)const;将多项式送输出流

voidPo1yAdd(Po1yn()mina1&r);多项式相加

♦••

private:

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

friendostream&operator«(ostream&,constPolynominal&);

friendistrcam&operator»(istrcam&,Polynominal&);

friendPolynoniinal&operator+(Polynominal&,Polynominal&);

｝；

程序2.8多项式类的构造和析构函数

Polynominal::Polynominal()创建多项式的空的单循环链表

(

theList=nowTerm(0,-1);分配表头结点的存储单元

thcList->link=theList;构成循环链表

)

Polynominal:「Polynominal()撤消多项式的单循环链表

{

Term*p=theList->link;

while(p!=theList)(

theList->link=p->link;删除P结点

deletep;释放p之存储空间

p=theList->link;P指向下1个待删除结点

)

deletetheList;释放表头结点的存储单元

)

程序2.9多项式类的输入和输出函数

voidPolynominal::AddTerms(istream&in)按降哥输入各项，构造单循环链表

{

Term*q=theList;

intc,e;

for(;;)(

cout«，zInputaterm(coef,exp):\n，z«endl;

cin»c»e;

if(e<0)break;当输入的指数小于0时，构造过程结束

q=q->InsertAfter(c,e);将c,e插入表尾结点q之后

)

)

voidPolynominal::Output(ostroan)&out)const

{

intfirst=l;Tern*p=theList->link;

cout«，，Thepolynoninalis:\n，z«endl;

for(;p!=theList;p=p->link){

if(!first&&'p->coef>0))out<<"+";在非第一项的正系数前输出号

first=0;

out«*p;调用Term类上重载的〃<<〃操作

}

cout«，，\n/，«endl;

)

程序2.10多项式相加函数

voidPo1ynomina1::Po1yAdd(Po1ynomina1&r)

{将多项式r加到多项式this上

Tenn*q,*ql=theList,*p;ql指向表头结点

p=r.theList->link;