鏈式存儲的表堆棧和隊列

一、鏈表—表的鏈式存儲順序表的特點：

邏輯上關(guān)系上相鄰的兩個元素在物理位置上也相鄰。

優(yōu)點：

可以隨即存取元素缺點：在插入刪除操作時，需要移動大量元素。

鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)是計算機中另外一種最基本的數(shù)據(jù)存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)初始時為空鏈，當有新的數(shù)據(jù)元素需要存儲時用戶向系統(tǒng)動態(tài)申請所需要的存儲空間，然后插入鏈中。也樣，存儲空間不一定連續(xù)，為了表示每個元素ai和其后繼元素ai＋1的邏輯關(guān)系，對ai來說，不但要存儲ai本身的數(shù)據(jù)信息，還必須存儲一個直接指示其后繼的信息（后繼的存儲地址），這兩部分組成ai的存儲映象，叫做結(jié)點。其中存儲數(shù)據(jù)元素信息的域叫做數(shù)據(jù)域，存儲直接后繼存儲位置的域叫做指針域。線性表如下：(ZHAO，QIAN，SUN,LI,ZHOU,WU,ZHENG,WANG)

存儲地址數(shù)據(jù)域指針域1 LI 437 QIAN 1313SUN1頭指針19WANG NULL3125WU 3731ZHAO 737 ZHENG 1943ZHOU 25頭指針指示鏈表中第一個結(jié)點的存儲位置。一般把鏈表畫成箭頭相鏈的結(jié)點的序列，如：WUZHOUZHENGWANGLISUNQIANZHAOHead數(shù)據(jù)域，存儲數(shù)據(jù)信息指針域，存儲下一個元素的地址template<classT>單鏈表的刪除（帶頭結(jié)點的情況）default:cin.有n個人圍成一個圓圈，任意給出一總結(jié)：帶頭結(jié)點的鏈表可以方便（統(tǒng)一）結(jié)點的插入操作使用的數(shù)據(jù)結(jié)構(gòu)有哪些？elsepower=power*d;node<T>*next;遞歸定義a)逆位序輸入n個元素的值，建立帶頭節(jié)點的單鏈表L；s->next=p->next;閱讀下面算法，用適當?shù)恼Z句完成各下劃線的處理，使其能實現(xiàn)刪除鏈表中voiddelete(L,x)的邏輯關(guān)系，對ai來說，不但要存儲ai本身的數(shù)據(jù)信息，還必1）單鏈表

A)定義以及相關(guān)概念

鏈表中每個結(jié)點中只包含一個指針域，這樣的鏈表叫做單鏈表。鏈表為空的標志：head==NULL（1）單鏈表headhead（2）帶頭節(jié)點的單鏈表有時，為了操作方便，我們在單鏈表的第一個節(jié)點之前附設(shè)一個節(jié)點，稱為頭節(jié)點。頭節(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存放如線性表的長度等附加信息。a1a2...LL鏈表為空：L->next=NULL分析問題：數(shù)據(jù)成員：數(shù)據(jù)信息，指針信息函數(shù)成員：構(gòu)造函數(shù)，析構(gòu)函數(shù)數(shù)據(jù)元素不確定，所以應(yīng)該使用類模板datanextA)鏈表（表的鏈式存儲）的實現(xiàn)1）節(jié)點類的定義和實現(xiàn)實現(xiàn)template<calssT>classnode;{private:node<T>*next;遞歸定義Public:Tdata;node(Ta，node<T>*next=Null);~node(){};voidprint();};datanext

template<classT>node<T>::node(Ta，node<T>*ptrnext){next=ptrnext;data＝a;}2）節(jié)點類的具體實現(xiàn)voidmain(){node<int>*p; p=newnode<int>(20,NULL); p->print();}template<classT>voidnode<T>::print(){cout<<data<<endl; cout<<next<<endl;}3）單鏈表類的定義分析數(shù)據(jù)成員：頭指針，單鏈表元素個數(shù)，當前指針函數(shù)成員：…見P68a)逆位序輸入n個元素的值，建立帶頭節(jié)點的單鏈表L；

3）建立鏈表template<classT>list<T>::list(intx){inti;head=newnode<T>(x,NULL);for(i=x;i>0;--i){p=newnode<T>;p->next=head->next;head->next=p;}}

1）單鏈表的插入，刪除a在第一個位置上的操作abaxppsbheadheads->next=p;head=s;B)鏈表的幾個重要操作分析s->next=p;p->next=s;b）在普通位置上的插入操作ababpscheadheadcxs->next=p->next;p->next=s;abheadcpc）在鏈表尾端的插入操作xsp->next=s;s->next=p;p->next=s;鏈表如果帶頭結(jié)點呢？sxapbheads->next=p->next;p->next=s;總結(jié)：帶頭結(jié)點的鏈表可以方便（統(tǒng)一）結(jié)點的插入操作bacp（A）刪除操作（一般情況）s->next=p->nextdelete(p);2）單鏈表刪除（不帶頭結(jié)點的單鏈表）heads（B）特殊情況head=p->nextp->next=NULLdelete(p)bacphead單鏈表的刪除（帶頭結(jié)點的情況）abheadpss->next=p->nextdeletepps3）單鏈表類的定義分析數(shù)據(jù)成員：頭指針，單鏈表元素個數(shù)，當前指針函數(shù)成員：…見P68template<classT>classlist{private:node<T>*head; intsize; node<T>*p,*q; public:list(void); list(intx); ~list(){} intlistsize(void)const; intisempty(void)const;

node<T>*index(intpos); voidinsert(constT&item,Tx); Tdelet(intpos); voidclear(void); voidprint();};單鏈表的操作都是從頭指針開始的。單鏈表的刪除（帶頭結(jié)點的情況）a在第一個位置上的操作（A）刪除操作（一般情況）l1->next=s;用基數(shù)排序的思想對穿孔卡片進行排序的。p->next=head->next;inti,j,k,power=1;雙向鏈表的節(jié)點有兩個指針域，一個指向直接后繼，一個指insert(a[j]);~node(){};p=newnode<int>(20,NULL);1)將兩個鏈表合并成一個鏈表。result=Getdata(operand1,operand2);{private:node<T>*head;head=newnode();voidClear(void);p=newnode<int>(20,NULL);template<classT>list<T>::list(intx){inti; head=newnode<T>(x,NULL);for(i=x;i>0;--i) {p=newnode<T>;p->next=head->next;head->next=p;}}

template<classT>voidlist<T>::print()//輸出鏈表中節(jié)點的數(shù)據(jù)域{cout<<"鏈表中得數(shù)據(jù)如下："<<endl; p=head->next; while(p!=NULL) {cout<<p->data<<""<<endl; p=p->next;}}template<classT>voidlist<T>::insert(constT&item,Tx)//在單鏈表中數(shù)據(jù)域為x的節(jié)點之后插入一個新節(jié)點{ p=head->next; while(p->data!=x&&p->next!=NULL) p=p->next; node<T>*q; q=newnode<T>(item,NULL); q->next=p->next; p->next=q;}template<classT>Tlist<T>::delet(intpos)//刪除指定的節(jié)點{ inti(1); p=head->next; q=head; while(p!=NULL&&i!=pos) {p=p->next;q=q->next;i++;}q->next=p->next; returnp->data; deletep;}作業(yè)：1）編寫一個在線性鏈表中數(shù)據(jù)域為a的節(jié)點之后，插入一個新節(jié)點的算法。若原鏈表中無數(shù)據(jù)域為a的節(jié)點，則把新節(jié)點插入表尾。新節(jié)點的數(shù)據(jù)域為x。2）編寫一個將線性鏈表逆置的算法。以上算法均以鏈表類的成員函數(shù)的形式給出。（2）循環(huán)鏈表特點：將表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)條件：p是否為頭指針.headhead->next==headp->next==head單循環(huán)鏈表舉例1)將兩個鏈表合并成一個鏈表。p=L1->next;while(p->next!=L1)p=p->next;p->next=L2->next;while(p->next!=L2)p=p->next;p->next=L1;時間復雜度：L1L2ABBA僅設(shè)尾指針的循環(huán)鏈表，合并情況如下：p=A;p->next=B->next->next;B->next=A->next;A=b;2）Josephus(約瑟夫）問題。有n個人圍成一個圓圈，任意給出一個整整數(shù)m，從第一個人開始計數(shù)，數(shù)到第m個人時第m個人被從圓圈中除去。問最后剩下是哪個人。分析問題，寫出算法。三、雙向鏈表（雙向循環(huán)鏈表）cbheadhead->prior==head;head->next==head;為了克服單鏈表的不足——找后繼容易，找前驅(qū)難。雙向鏈表的節(jié)點有兩個指針域，一個指向直接后繼，一個指向直接前驅(qū)。空表循環(huán)條件：p->next是否為head1)雙向鏈表上的插入與刪除操作acbpA）刪除

e=p->data;p->prior-->next=p-->next;p->next-->prior=p-->prior;delete(p);axbss-->prior=p-->prior;p-->prior-->next=s;s-->next=p;p-->prior=s;

B）插入p2）雙向鏈表舉例（2002年電子科大專業(yè)試題）

設(shè)雙向鏈表結(jié)構(gòu)如下：頭節(jié)點有兩個域，其中，firstlink指向第一個數(shù)據(jù)節(jié)點，lastlink指向最后一個數(shù)據(jù)節(jié)點，鏈表空時，firstlink＝lastlink＝NULL。閱讀下面算法，用適當?shù)恼Z句完成各下劃線的處理，使其能實現(xiàn)刪除鏈表中data域為x的所有節(jié)點…datalinkfirstlinklastlinkvoiddelete(L,x){p=L->firstlink;q=L;{置初值：p，q為同步指針，q為p的直接前驅(qū)}while(p!=NULL){if(p->data==x)case{分三種情況}L=q;{第一個節(jié)點為x和只有一個節(jié)點為x的處理}

LL->lastlink=p:{最后一個節(jié)點為x的處理}

others:{其他節(jié)點為x的處理}else{不為x的處理}}}1）鏈表的基本操作的實現(xiàn)舉例。2）課后作業(yè)（1）上機實現(xiàn)循環(huán)單鏈表的基本操作；（2）實現(xiàn)雙向鏈表的基本操作。單鏈表的應(yīng)用舉例一元多項式的表示和相加pn(x)=p0+p1(x)+p2(x2)+…+pn(xn)p=(p0,p1,p2,…pn)qm(x)=q0+q1(x)+q2(x2)+…+qm(xm)q=(q0,q1,q2,…qm)r=((p0+q0),(p1+q1),(p2+q2),…(pm+qm),pm+1,…pn)(m<n)S(x)=1+3x1000+2x2000一般情況下，一元n次多項式可寫成如下形式：Pn(x)=p1xe1+p2xe2+p3xe3+...+pmxem則可以用一個長度為m,每個元素有兩個數(shù)據(jù)項的線性表（（p1,e1),(p2,e2),(p3,e3),...,(pm,em))來唯一確定多項式Pn(x).-1071893175A-118722B8-9-1071

11175C722

#include"iostream.h"classnode{ friendclasslist;private: floatcoef; intexpn; node*next;public: node(){next=NULL;} ~node(){}};classlist{ friendclassnode;private: node*head,*p;public: list(){} node*creat(intn); node*add(node*p1,node*p2); voidprint(node*s);};node*list::creat(intn){ head=newnode(); node*q;

q=head; for(inti=0;i<n;i++) { p=newnode(); cin>>p->coef; cin>>p->expn; q->next=p; q=p; } returnhead;}node*list::add(node*p1,node*p2){ node*l1,*s,*q; p=p1->next;

l1=p1; q=p2->next;while(p!=NULL&&q!=NULL) { if(p->expn<q->expn) { p=p->next; l1=l1->next; cout<<"A表的指針后移即可！"<<endl; } if(p->expn>q->expn) { s=q; q=q->next; s->next=p;

l1->next=s; l1=s; cout<<"將B的節(jié)點插入到A！"<<endl; } if(p->expn==q->expn) { p->coef=p->coef+q->coef; if(p->coef==0) { node*m; m=p; l1->next=p->next; p=l1->next; m->next=NULL; deletem;

q=q->next; cout<<"兩個節(jié)點相加，和為0"<<endl; } else { p=p->next; l1=l1->next; q=q->next; cout<<"兩個節(jié)點相加，和不為0"<<endl; } } } if(p==NULL)l1->next=q;returnp1;}voidlist::print(node*s){ p=s->next; while(p->next!=NULL) { cout<<p->coef<<"X"<<p->expn<<"+"; p=p->next; } cout<<p->coef<<"X"<<p->expn; cout<<endl;}voidmain(){ listA,B,C; node*p1,*p2;p1=A.creat(4); p2=B.creat(3); node*mylist; mylist=C.add(p1,p2); C.print(mylist);}二、鏈?！獥５逆準酱鎯?..topdatanext棧底棧頂節(jié)點類的定義數(shù)據(jù)信息：頭指針數(shù)據(jù)域，指針域函數(shù)：1）入棧操作的實現(xiàn)...topdatanext棧底棧頂ss->next=top->nexttop->next=s

...topdatanext棧底棧頂stops->next=top;top=s;voidLinStack<T>::push(constT&item){StackNode<T>*newNode=newStackNode<T>(item,top); top=newNode; size++;}個整整數(shù)m，從第一個人開始計數(shù)，數(shù)到第m個人時第m個人head=newnode();特點：將表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。鏈式存儲結(jié)構(gòu)是計算機中另外一種最基本的數(shù)據(jù)存儲結(jié)構(gòu)。{p=L->firstlink;if(p->expn>q->expn)while(p!=NULL)Pn(x)=p1xe1+p2xe2+p3xe3+.for(j=0,k=0;j<d;j++)//順序回收各隊列中的對象（A）刪除操作（一般情況）p->print();head=p->nexts-->prior=p-->prior;returndata;cin>>p->coef;node*next;2）出棧的操作實現(xiàn)...topdatanext棧底棧頂棧不空時：p=top->next;data=p->data;top->next=p->next;deletep;returndata;p...topdatanext棧底棧頂p=top;top=top->next;deletep;template<classT>TLinStack<T>::pop(void){ if(size==0) { cerr<<"堆?？?！"<<endl; exit(1); } StackNode<T>*p=top->next; Tdata=top->data; deletetop; size--; top=p; returndata;}表達式計算輸入后綴表達式，計算表達式的值。#include<ctype.h>#include"LinStack.h"template<classT>classPost{ private: LinStack<T>s;//定義一個棧 voidEnter(Tnum);//將數(shù)據(jù)元素T入棧 intGetdata(T&op1,T&op2);//出棧頂元素分別到op1和op2中 voidcomputer(charop);//做相應(yīng)的運算，將結(jié)果入棧 public: Post(void){}; voidrun(void); voidClear(void);};template<classT>voidPost<T>::Enter(Tnum){ s.Push(num);}template<classT>intGetdata(T&op1,T&op2){ if(s.StackEmpty()) { cerr<<"?？?"<<endl; return0; }

op1=s.Pop();if(s.StackEmpty()) { cerr<<"缺少操作數(shù)!"<<endl; return0; }op2=s.Pop();return1;}template<classT>voidPost<T>::computer(charop){ intresult; Toperand1,operand2; result=Getdata(operand1,operand2); if(result==1) switch(op) { case'+':s.Push(operand2+operand1);break; case'-':s.Push(operand2-operand1);break; case'*':s.Push(operand2*operand1);break; case'/':s.Push(operand2/operand1);break; }else s.ClearStack();

}template<classT>voidPost<T>::run(void){ charc; Tnewoperand; cout<<"輸入后綴表達式，以＃結(jié)束！"<<endl; while(cin>>c,c!='#') { switch(c) { case'+': case'-': case'*': case'/':Compute(c); break;

default:cin.putback(c);//是操作數(shù)，入棧 cin>>newoperand; Enter(newoperand); break; } } if(!s.StackEmpty()) cout<<"計算結(jié)果為："<<s.Peek()<<endl;}template<classT>voidPost<T>::Clear(void){ s.ClearStack();}#include"Post.h"voidmain(void){ Post<float>exp; exp.run();}三、鏈式隊列鏈式隊列式隊列的鏈式存儲結(jié)構(gòu)。frontrearfrontrear空隊列1）出隊列frontrearpintlinqueue::del(void){ if(size==0) { cerr<<“隊列為空"<<endl; exit(1); }node*p=front->next; intx=front->data; deletefront; front=p; if(front==NULL)rear=NULL; size--; returnx;}2）入隊列frontrearsrearrear->next=s;rear=s;一般情況：特殊情況：voidlinqueue::insert(int&item){ node*p=newnode(item); if(size>0) { rear->next=p; rear=p; } else { front=p; rear=p; } size++;}3)鏈隊列的應(yīng)用舉例——鏈式基數(shù)排序基數(shù)排序是一種依據(jù)組成關(guān)鍵字的各位值進行排序的方法。該方法是最早的排序方法之一，早在計算機出現(xiàn)之前的卡片排序機就是利用基數(shù)排序的思想對穿孔卡片進行排序的。278109063930083008269505184589voidradixsort(inta[],intn,intm,intd){ inti,j,k,power=1; linqueue*tub=newlinqueue[d]; for(i=0;i<m;i++)//進行m次排序 { if(i==0)power=1; elsepower=power*d;for(j=0;j<n;j++)//將對象按關(guān)鍵碼第k為的大小放到相應(yīng)的隊列中 {

k=a[j]/power-(a[j]/(power*d))*d; tub[k].inser