鏈式存儲的表堆棧和隊列

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

邏輯上關系上相鄰的兩個元素在物理位置上也相鄰。

優(yōu)點：

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

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

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

A)定義以及相關概念

鏈表中每個結點中只包含一個指針域，這樣的鏈表叫做單鏈表。鏈表為空的標志：head==NULL（1）單鏈表headhead（2）帶頭節(jié)點的單鏈表有時，為了操作方便，我們在單鏈表的第一個節(jié)點之前附設一個節(jié)點，稱為頭節(jié)點。頭節(jié)點的數據域可以不存儲任何信息，也可以存放如線性表的長度等附加信息。a1a2...LL鏈表為空：L->next=NULL分析問題：數據成員：數據信息，指針信息函數成員：構造函數，析構函數數據元素不確定，所以應該使用類模板datanextA)鏈表（表的鏈式存儲）的實現1）節(jié)點類的定義和實現實現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é)點類的具體實現voidmain(){node<int>*p; p=newnode<int>(20,NULL); p->print();}template<classT>voidnode<T>::print(){cout<<data<<endl; cout<<next<<endl;}3）單鏈表類的定義分析數據成員：頭指針，單鏈表元素個數，當前指針函數成員：…見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;鏈表如果帶頭結點呢？sxapbheads->next=p->next;p->next=s;總結：帶頭結點的鏈表可以方便（統(tǒng)一）結點的插入操作bacp（A）刪除操作（一般情況）s->next=p->nextdelete(p);2）單鏈表刪除（不帶頭結點的單鏈表）heads（B）特殊情況head=p->nextp->next=NULLdelete(p)bacphead單鏈表的刪除（帶頭結點的情況）abheadpss->next=p->nextdeletepps3）單鏈表類的定義分析數據成員：頭指針，單鏈表元素個數，當前指針函數成員：…見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();};單鏈表的操作都是從頭指針開始的。單鏈表的刪除（帶頭結點的情況）a在第一個位置上的操作（A）刪除操作（一般情況）l1->next=s;用基數排序的思想對穿孔卡片進行排序的。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é)點的數據域{cout<<"鏈表中得數據如下："<<endl; p=head->next; while(p!=NULL) {cout<<p->data<<""<<endl; p=p->next;}}template<classT>voidlist<T>::insert(constT&item,Tx)//在單鏈表中數據域為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）編寫一個在線性鏈表中數據域為a的節(jié)點之后，插入一個新節(jié)點的算法。若原鏈表中無數據域為a的節(jié)點，則把新節(jié)點插入表尾。新節(jié)點的數據域為x。2）編寫一個將線性鏈表逆置的算法。以上算法均以鏈表類的成員函數的形式給出。（2）循環(huán)鏈表特點：將表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(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僅設尾指針的循環(huán)鏈表，合并情況如下：p=A;p->next=B->next->next;B->next=A->next;A=b;2）Josephus(約瑟夫）問題。有n個人圍成一個圓圈，任意給出一個整整數m，從第一個人開始計數，數到第m個人時第m個人被從圓圈中除去。問最后剩下是哪個人。分析問題，寫出算法。三、雙向鏈表（雙向循環(huán)鏈表）cbheadhead->prior==head;head->next==head;為了克服單鏈表的不足——找后繼容易，找前驅難。雙向鏈表的節(jié)點有兩個指針域，一個指向直接后繼，一個指向直接前驅。空表循環(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è)試題）

設雙向鏈表結構如下：頭節(jié)點有兩個域，其中，firstlink指向第一個數據節(jié)點，lastlink指向最后一個數據節(jié)點，鏈表空時，firstlink＝lastlink＝NULL。閱讀下面算法，用適當的語句完成各下劃線的處理，使其能實現刪除鏈表中data域為x的所有節(jié)點…datalinkfirstlinklastlinkvoiddelete(L,x){p=L->firstlink;q=L;{置初值：p，q為同步指針，q為p的直接前驅}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）鏈表的基本操作的實現舉例。2）課后作業(yè)（1）上機實現循環(huán)單鏈表的基本操作；（2）實現雙向鏈表的基本操作。單鏈表的應用舉例一元多項式的表示和相加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,每個元素有兩個數據項的線性表（（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é)點類的定義數據信息：頭指針數據域，指針域函數：1）入棧操作的實現...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++;}個整整數m，從第一個人開始計數，數到第m個人時第m個人head=newnode();特點：將表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)。鏈式存儲結構是計算機中另外一種最基本的數據存儲結構。{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）出棧的操作實現...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);//將數據元素T入棧 intGetdata(T&op1,T&op2);//出棧頂元素分別到op1和op2中 voidcomputer(charop);//做相應的運算，將結果入棧 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<<"缺少操作數!"<<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<<"輸入后綴表達式，以＃結束！"<<endl; while(cin>>c,c!='#') { switch(c) { case'+': case'-': case'*': case'/':Compute(c); break;

default:cin.putback(c);//是操作數，入棧 cin>>newoperand; Enter(newoperand); break; } } if(!s.StackEmpty()) cout<<"計算結果為："<<s.Peek()<<endl;}template<classT>voidPost<T>::Clear(void){ s.ClearStack();}#include"Post.h"voidmain(void){ Post<float>exp; exp.run();}三、鏈式隊列鏈式隊列式隊列的鏈式存儲結構。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)鏈隊列的應用舉例——鏈式基數排序基數排序是一種依據組成關鍵字的各位值進行排序的方法。該方法是最早的排序方法之一，早在計算機出現之前的卡片排序機就是利用基數排序的思想對穿孔卡片進行排序的。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++)//將對象按關鍵碼第k為的大小放到相應的隊列中 {

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