第二章+線性表

第二章線性表線性表順序表鏈表順序表與鏈表的比較線性表定義：

n（0）個數(shù)據(jù)元素的有限序列，記作（a1,…ai-1,ai,ai+1,…,an）

其中,ai

是表中數(shù)據(jù)元素，n是表長度。特點:同一線性表中元素具有相同特性。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。除第一個元素外，其他每一個元素有一個且僅有一個直接前驅(qū)。除最后一個元素外，其他每一個元素有一個且僅有一個直接后繼。 順序表定義：將線性表中的元素相繼存放在一個連續(xù)的存儲空間中。

存儲結(jié)構(gòu)：數(shù)組。特點：線性表的順序存儲方式。存取方式：順序存取,隨機存取順序存儲結(jié)構(gòu)示意圖458990674078

012345順序表的存儲方式：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l

a1

a2

…ai………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle順序表（SeqList）的類型定義

#defineListSize100//最大允許長度

typedefintListData;

typedefstruct

{

ListData*data;//存儲空間基址

intlength; //當前元素個數(shù)

}

SeqList;SeqLista;a.data[1]順序表基本運算初始化

voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存儲分配失敗!\n”);exit(1);}L.length=0;}順序搜索圖示x=48x=50按值查找：找x在表中的位置，若查找成功，返回表項的位置，否則返回-1

intFind(SeqList&L,ListDatax){inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}搜索成功

若搜索概率相等，則

搜索不成功數(shù)據(jù)比較n

次按值查找：判斷x是否在表中

intIsIn(SeqList&L,ListDatax){ inti=0, found=0; while(i<L.length&&!found) if(L.data[i]!=x)i++; elsefound=1;returnfound;}求表的長度

intLength(SeqList&L){returnL.length;}提取函數(shù)：在表中提取第i個元素的值

ListDataGetData(SeqList&L,inti){if(i>=0&&i<L.length)returnL.data[i];elseprintf(“參數(shù)

i不合理！\n”); }

按值查找：尋找x的后繼

intNext(SeqList&L,ListDatax){inti=Find(L,x);if(i>0&&i<L.length)returni+1; elsereturn-1;}尋找x的前驅(qū)

intPrevious(SeqList&L,ListDatax){inti=Find(L,x);if(i>0&&i<L.length)returni-1; elsereturn-1;}插入25345716480963

0123456750插入x2534575016480963

0123456750i順序表插入時，平均數(shù)據(jù)移動次數(shù)AMN在各表項插入概率相等時順序表的插入

intInsert(SeqList&L,ListDatax,inti){

//在表中第i個位置插入新元素x

if(i<0||i>L.length||L.length==ListSize)return0;//插入不成功

else{ for(intj=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i]=x;L.length++; return1;//插入成功

}}刪除253457501648096316刪除

x2534575048096301234567順序表刪除平均數(shù)據(jù)移動次數(shù)AMN在各表項刪除概率相等時順序表的刪除

intDelete(SeqList&L,ListDatax){

//在表中刪除已有元素x

inti=Find(L,x); //在表中查找xif(i>=0){ L.length--; for(intj=i;j<L.length;j++) L.data[j]=L.data[j+1];return1; //成功刪除

} return0;//表中沒有x}順序表的應(yīng)用:集合的“并”運算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i<m;i++){ intx=GetData(B,i);//在B中取一元素

intk=Find(A,x);//在A中查找它

if(k==-1)//若未找到插入它

{Insert(A,x,n);n++;}}}集合的“交”運算

voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i<n){intx=GetData(A,i);//在A中取一元素

intk=Find(B,x);//在B中查找它

if(k==-1){Delete(A,i);n--;} elsei++;//未找到在A中刪除它

}}多項式(Polynomial)n階多項式Pn(x)有n+1項。系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列classPolynomial

{public:

Polynomial();//構(gòu)造函數(shù)

intoperator!

();//判斷是否零多項式

CoefficientCoef(Exponente);

Exponent

LeadExp();//返回最大指數(shù)

Polynomial

Add(Polynomial

poly);

Polynomial

Mult(Polynomialpoly);

floatEval(float

x); //求值}多項式(Polynomial)的抽象數(shù)據(jù)類型#include<iostream.h>class

power{

double

x;

int

e;

double

mul;

public:

power(double

val,intexp);

double

get_power(){returnmul;}

};創(chuàng)建power類，計算x的冪

power::power(double

val,int

exp){

//按val值計算乘冪

x=val;

e=exp;mul=1.0;

if(exp==0)return;

for(;

exp>0;

exp--)mul=mul*x;

}main(){

powerpwr(1.5,2);

cout<<pwr.get_power()<<“\n”;

}

多項式的存儲表示第一種：

private:(靜態(tài)數(shù)

intdegree; 組表示)floatcoef[maxDegree+1];

Pn(x)可以表示為：

pl.degree=n

pl.coef[i]=ai,0

i

n第二種：private:

(動態(tài)數(shù)

int

degree;組表示)

float*coef;

Polynomial::Polynomial(int

sz){

degree=sz;

coef=newfloat[degree+1];

}以上兩種存儲表示適用于指數(shù)連續(xù)排列的多項式。但對于指數(shù)不全的多項式如P101(x)=3+5x50-14x101,不經(jīng)濟。第三種：

class

Polynomial;

classterm{

//多項式的項定義

friendPolynomial;

private:

floatcoef;//系數(shù)

intexp; //指數(shù)

};classPolynomial{//多項式定義public:……private:

statictermtermArray[MaxTerms];//項數(shù)組

staticintfree;//當前空閑位置指針

//term

Polynomial::termArray[MaxTerms];//intPolynomial::free=0;

intstart,finish; //多項式始末位置

}A(x)=2.0x1000+1.8B(x)=1.2+51.3x50+3.7x101

兩個多項式存放在termArray中兩個多項式的相加結(jié)果多項式另存掃描兩個相加多項式，若都未檢測完：

若當前被檢測項指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項式。若當前被檢測項指數(shù)不等，將指數(shù)小者加到結(jié)果多項式。若有一個多項式已檢測完，將另一個多項式剩余部分復(fù)制到結(jié)果多項式。PolynomialPolynomial::Add(PolynomialB){

PolynomialC;

int

a=start;

int

b=B.start;

C.start=free;

floatc;

while(a<=finish&&b<=B.finish)

Switch

(compare(termArray[a].exp,termArray[b].exp)){

//比較對應(yīng)項指數(shù)

case‘=’://指數(shù)相等

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;

return

C;}在多項式中加入新的項

void

Polynomial::NewTerm(floatc,

inte){

//把一個新的項加到多項式C(x)中

if(free>=maxTerms){cout<<"Toomanytermsinpolynomials”<<

endl;return;

}

termArray[free].coef=c;

termArray[free].exp=e;

free++;}

鏈表（LinkedList）鏈表是線性表的鏈接存儲表示單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表單鏈表(SinglyLinkedList)定義：用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。例如：線性表ZHOU,ZHAO,SUN,WU,WANG,ZHANG,LI數(shù)據(jù)域指針域ZHANG13WANG1LInullZHAO37WU7ZHOU19SUN25存儲地址17131925313731頭指針表中節(jié)點位置6572413單鏈表的存儲映像每個元素由結(jié)點(Node)構(gòu)成, 它包括兩個域:數(shù)據(jù)域Data和指針域Linkdatalink存儲結(jié)構(gòu)：鏈式存儲結(jié)構(gòu)特點：存儲單元可以不連續(xù)。存取方式：順序存取。Node單鏈表結(jié)構(gòu)單鏈表的類型定義typedefcharListData;typedefstructnode{//鏈表結(jié)點

ListDatadata; //結(jié)點數(shù)據(jù)域

structnode*link;//結(jié)點鏈域}ListNode;typedefListNode*LinkList;//鏈表頭指針LinkListfirst;//鏈表頭指針單鏈表的基本運算插入（三種情況）

第一種情況：在第一個結(jié)點前插入

newnode->link=first;first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst第二種情況：在鏈表中間插入

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodepnewnodep第三種情況：在鏈表末尾插入

newnode->link=p->link; p->link=newnode；p(插入前)(插入后)newnodenewnodep算法描述intInsert(LinkList&first,ListDatax,inti){//在鏈表第i個結(jié)點處插入新元素xListNode*p=first;intk=0;while(p!=NULL&&k<i-1){p=p->link;k++;}//找第i-1個結(jié)點

if(p==NULL&&first!=NULL){ printf(“無效的插入位置!\n”);//終止插入

return0;}ListNode*newnode=//創(chuàng)建新結(jié)點

(ListNode*)malloc(sizeof(ListNode));

newnode->data=x;if(first==NULL||i==1){//插入空表或非空表第一個結(jié)點之前

newnode->link=first;//新結(jié)點成為第一個結(jié)點

if(first==NULL)last=newnode;//若是空表，表尾指針指向新結(jié)點

first=newnode;}else{//插在表中間或末尾

newnode->link=p->link; if(p->link==NULL)last=newnode; p->link=newnode;}return1;}刪除 在單鏈表中刪除ai結(jié)點

q=p->link; p->link=q->link;刪除前刪除后ai-1aiai+1pqpai-1ai+1aiintDelete(LinkList&first,inti){//在鏈表中刪除第i個結(jié)點

ListNode*p,*q;if(i==0)//刪除表中第1個結(jié)點

{q=first;first=first->link;}else{p=first;intk=0;while(p!=NULL&&k<i-1){p=p->link;k++;}//找第i-1個結(jié)點if(p==NULL||p->link==NULL)

{//找不到第i-1個結(jié)點

printf(“無效的刪除位置!\n”);return0;

}else{//刪除中間結(jié)點或尾結(jié)點元素

q=p->link;

p->link=q->link;} if(q==last)last=p;//刪除表尾結(jié)點

k=q->data;free(q);returnk;//取出被刪結(jié)點數(shù)據(jù)并釋放q } }帶表頭結(jié)點的單鏈表表頭結(jié)點位于表的最前端，本身不帶數(shù)據(jù)，僅標志表頭。設(shè)置表頭結(jié)點的目的:簡化鏈表操作的實現(xiàn)。非空表空表^ana1firstfirst^插入

q->link=p->link; p->link=q;firstqfirstqfirstq^firstq^pppp插入前插入后表頭表尾qq插入pp表中intInsert(LinkListfirst,ListDatax,inti){//將新元素x插入在鏈表中第i號結(jié)點位置

ListNode*p=Locate(first,i-1);if(p==NULL)return0; //參數(shù)i值不合理返回0ListNode*newnode=//創(chuàng)建新結(jié)點

(ListNode*)malloc(sizeof(ListNode));newnode->data=x;newnode->link=p->link;//鏈入

p->link=newnode;return1; }刪除

q=p->link;p->link=q->link;deleteq;刪除前first(非空表）(空表）first^firstpq^pqfirst刪除后intdelete(LinkListfirst,inti){ //將鏈表第i號元素刪去

ListNode*p,*q p=Locate(first,i-1);//尋找第i-1個結(jié)點

if(p==NULL||p->link==NULL) return0;//i值不合理或空表

q=p->link; p->link=q->link;//刪除結(jié)點

free(q); //釋放

return1;}前插法建立單鏈表從一個空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中將該新結(jié)點插入到鏈表的前端直到讀入結(jié)束符為止。firstqfirstq^^LinkListcreateListF(void){charch;ListNode*q;LinkListhead=//建立表頭結(jié)點(LinkList)malloc(sizeof(ListNode));head->link=NULL;while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新結(jié)點

q->link=head->link;//插入到表前端

head->link=q;}returnhead;}后插法建立單鏈表每次將新結(jié)點加在鏈表的表尾；尾指針r,總是指向表中最后一個結(jié)點，新結(jié)點插在它的后面；^qfirst^r^first^rLinkListcreateListR(void){charch;LinkListhead=//建立表頭結(jié)點(LinkList)malloc(sizeof(ListNode));ListNode*q,*r=head; while((ch=getchar())!=‘\n’){q=(ListNode*)malloc(sizeof(ListNode));q->data=ch;//建立新結(jié)點

r->link=q;r=q;

//插入到表末端}

r->link=NULL;

returnhead;}單鏈表清空voidmakeEmpty(LinkListfirst){//刪去鏈表中除表頭結(jié)點外的所有其它結(jié)點

ListNode*q;while(first->link!=NULL){//當鏈不空時，循環(huán)逐個刪去所有結(jié)點

q=first->link;first->link=q->link; free(q);//釋放

} last=first;}計算單鏈表長度intLength(LinkListfirst){ListNode*p=first->link;//指針p指示第一個結(jié)點

intcount=0;while(p!=NULL){//逐個結(jié)點檢測

p=p->link;count++;} returncount;}

按值查找ListNode*Find(LinkListfirst,ListDatavalue){ //在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點

ListNode*p=first->link;

//指針p指示第一個結(jié)點

while(p!=NULL&&p->data!=value)p=p->link;returnp;}按序號查找（定位）

ListNode*Locate(LinkListfirst,inti){//返回表中第i個元素的地址

if(i<0)returnNULL;ListNode*p=first;intk=0;while(p!=NULL&&k<i){p=p->link;k++;} //找第i個結(jié)點

if(k==i)returnp;//返回第i個結(jié)點地址

elsereturnNULL;}1ZHANG2WANG6LI5ZHAO5WU-1CHEN31ZHANG2WANG3LI4ZHAO5WU-101234560123456修改前（插入chen,刪除zhao)修改后用一維數(shù)組描述線性鏈表靜態(tài)鏈表定義constintMaxSize=100;//靜態(tài)鏈表大小typedefintListData;typedefstructnode{//靜態(tài)鏈表結(jié)點

ListDatadata;

intlink;}SNode;typedefstruct{//靜態(tài)鏈表

SNodeNodes[MaxSize];intnewptr; //當前可分配空間首地址}SLinkList;鏈表空間初始化voidInitList(SLinkList*SL){SL->Nodes[0].link=-1;SL->newptr=1;//當前可分配空間從1開始

//建立帶表頭結(jié)點的空鏈表

for(inti=1;i<MaxSize-1;i++)SL->Nodes[i].link=i+1;//構(gòu)成空閑鏈表

SL->Nodes[MaxSize-1].link=-1;

//鏈表收尾}在靜態(tài)鏈表中查找具有給定值的結(jié)點intFind(SLinkListSL,ListDatax){intp=SL.Nodes[0].link;//指針p指向鏈表第一個結(jié)點

while(p!=-1)//逐個查找有給定值的結(jié)點

if(SL.Nodes[p].data!=x)p=SL.Nodes[p].link;elsebreak; returnp;}在靜態(tài)鏈表中查找第i個結(jié)點intLocate(SLinkListSL,inti){if(i<0)return-1;//參數(shù)不合理

intj=0,p=SL.Nodes[0].link;while(p!=-1&&j<i){//循環(huán)查找第i號結(jié)點

p=SL.Nodes[p].link;j++;}if(i==0)return0;returnp;}在靜態(tài)鏈表第i個結(jié)點處插入一個新結(jié)點intInsert(SLinkList*SL,inti,ListDatax){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點

intq=SL->newptr;//分配結(jié)點

SL->newptr=SL->Nodes[SL->newptr].link;SL->Nodes[q].data=x;

SL->Nodes[q].link=SL.Nodes[p].link;SL->Nodes[p].link=q;

//插入

return1;}在靜態(tài)鏈表中釋放第i個結(jié)點intRemove(SLinkList*SL,inti){intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點

intq=SL->Nodes[p].link;//第i號結(jié)點

SL->Nodes[p].link=SL->Nodes[q].link;SL->Nodes[q].link=SL->newptr;//釋放

SL->newptr=q;return1;}循環(huán)鏈表(CircularList)特點:最后一個結(jié)點的link指針不為NULL，而是指向頭結(jié)點。只要已知表中某一結(jié)點的地址，就可搜尋所有結(jié)點的地址。存儲結(jié)構(gòu):鏈式存儲結(jié)構(gòu)

帶表頭結(jié)點的循環(huán)鏈表an-1firsta1a0first(空表)(非空表)循環(huán)鏈表的插入約瑟夫問題用循環(huán)鏈表求解約瑟夫問題n個人圍成一個圓圈，首先第1個人從1開始一個人一個人順時針報數(shù),報到第m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。例如n=8m=3約瑟夫問題的解法#include<iostream.h>#include“CircList.h”voidJosephus(intn,intm){for(inti=0;i<n-1;i++){//執(zhí)行n-1次

for(intj=0;j<m-1;j++)Next();

//數(shù)m-1個人

cout<<“Deleteperson”<<getData()<<endl;Remove();//刪去

}}voidmain(){CircList<int>clist; intn,m; cout<<“EntertheNumberofContestants?”;cin>>n>>m;for(inti=1;i<=n;i++)clist.insert(i);//形成約瑟夫環(huán)

clist.Josephus(n,m);//解決約瑟夫問題}多項式及其相加在多項式的鏈表表示中每個結(jié)點增加了一個數(shù)據(jù)成員link，作為鏈接指針。優(yōu)點是：多項式的項數(shù)可以動態(tài)地增長，不存在存儲溢出問題。插入、刪除方便，不移動元素。多項式鏈表的相加AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x18

Polynomialoperator+(constPolynomial &ah,constPolynomial&bh){Term*pa,*pb,*p;ListIterator<Element>Aiter(ah.poly);ListIterator<Element>Biter(bh.poly);//建立兩個多項式對象Aiter、Biterpa=pc=Aiter.First();//pa檢測指針

p=pb=Biter.First(); //pb檢測指針

pa=Aiter.Next();pb=Biter.Next();//pa,pb越過表頭結(jié)點

deletep;while(Aiter.NotNull()&&Biter.NotNull())switch(compare(pa→exp,pb→exp)){case'=': pa→coef=pa→coef+pb→coef; p=pb;pb=Biter.Next();deletep; if(!pa→coef){p=pa;pa=Aiter.Next(); deletep;}else{pc→link=pa;pc=pa;pa=Aiter.Next();} break;

case‘>': pc→link=pb;pc=pb; pb=Biter.Next();break;case‘<': pc→link=pa;pc=pa; pa=Aiter.Next();}if(Aiter.NotNull())pc→link=pa; elsepc→link=pb;returnah;}

雙向鏈表(DoublyLinkedList)雙向鏈表結(jié)點結(jié)構(gòu)：priordatanext指向直接前驅(qū)指向直接后繼非空表空表firstfirst雙向循環(huán)鏈表的定義typedefintListData;typedefstructdnode{ListNodedata;