北大信息院數(shù)據(jù)結構ds 02list

第二章線性表、棧和隊列

任課教員：張銘

北京大學信息科學與技術學院網絡與信息系統(tǒng)研究所，轉載或翻印必究

北京大學信息學院，轉載或翻印必究Page2大綱2.1線性表(linearlist)2.1.1線性表的抽象數(shù)據(jù)類型2.1.2線性表的存儲結構2.1.3線性表運算分類

2.2順序表—向量(sequentiallist—vector)2.2.1向量的類定義(typedefinition)2.2.2向量的運算北京大學信息學院，轉載或翻印必究Page32.5棧

2.5.1順序棧

2.5.2鏈式棧

2.5.3順序棧與鏈式棧的比較

2.5.4棧的應用——后綴表達式求值

2.5.4遞歸的實現(xiàn)

2.6隊列

2.6.1順序隊列

2.6.2鏈式隊列

2.2.3順序隊列與鏈式隊列的比較

北京大學信息學院，轉載或翻印必究Page4大綱（續(xù)）2.3鏈表(linkedlist)2.3.1單鏈表(singlylinkedlist)2.3.2雙鏈表(doublelinkedlist)2.3.3循環(huán)鏈表(circularlylinkedlist)2.4線性表實現(xiàn)方法的比較北京大學信息學院，轉載或翻印必究Page5線性結構分類直接訪問型(directaccess)順序訪問型(sequentialaccess)目錄索引型(directoryaccess)北京大學信息學院，轉載或翻印必究Page6線性結構分類北京大學信息學院，轉載或翻印必究Page72.1線性表(linearlist)2.1.1線性表的抽象數(shù)據(jù)類型2.1.2線性表的存儲結構2.1.3線性表運算分類北京大學信息學院，轉載或翻印必究Page8線性表的抽象數(shù)據(jù)類型線性表定義：由結點集N，以及定義在結點集N上的線性關系r所組成的線性結構。這些結點稱為線性表的元素。北京大學信息學院，轉載或翻印必究Page9線性表的性質線性表（N,r）：（a）結點集N中有一個唯一的開始結點，它沒有前驅，但有一個唯一的后繼；（b）對于有限集N,它存在一個唯一的終止結點，該結點有一個唯一的前驅而沒有后繼；（c）其它的結點皆稱為內部結點，每一個內部結點既有一個唯一的前驅，也有一個唯一的后繼；北京大學信息學院，轉載或翻印必究Page10線性表的性質（續(xù)）線性表（N,r）：（d）線性表所包含的結點個數(shù)稱為線性表的長度，它是線性表的一個重要參數(shù)；長度為0的線性表稱為空表；（e）線性表的關系r，簡稱前驅關系，應具有反對稱性和傳遞性。北京大學信息學院，轉載或翻印必究Page11線性表的抽象數(shù)據(jù)類型

取值空間運算集

北京大學信息學院，轉載或翻印必究Page12線性表類模板template<classELEM>classlist//線性表類模板list，模板參數(shù)ELEM{ //1.線性表的取值類型：

//元素的類型為ELEM，是本list類模板的模板

//參數(shù)ELEM。

//本線性表用的最大長度為Max_length；北京大學信息學院，轉載或翻印必究Page13 //2.名字空間，使用變量訪問線性表的方法：

//用curr++或curr--

//控制線性表游標curr的前后游走。

//用公共變

//量curr_len指示線性表的尾部，并導出表的當

//前長度，…等。

//3.運算集：請參看下面的成員函數(shù)北京大學信息學院，轉載或翻印必究Page14private: //私有變量，線性表的存儲空間

//Max_length用于規(guī)定所存儲線性表的最大長度public: intcurr_len; //公共變量，該線性表的當前長度

intcurr; //公共變量，該線性表的當前指針，游標

list(); //constructor算子，創(chuàng)建一個空的新線性表北京大學信息學院，轉載或翻印必究Page15 //destructor算子,//從計算機存儲空間刪去整個線性表

~list(); //將該線性表的全部元素清除，成為空表

voidclear(); //尾附算子，在表的尾部添加一個新元素，參

//數(shù)value作為元素內容（數(shù)據(jù)類型為

//ELEM），表的長度加1 voidappend(ELEMvalue);北京大學信息學院，轉載或翻印必究Page16 //插入算子，整數(shù)i指出第i號位置，參數(shù)value //作為元素內容（數(shù)據(jù)類型為T），該位置上

//插入一個新結點，表的長度加1。第i號位置后

//的元素后移

voidinsert(inti,ELEMvalue); //刪除算子，刪去第i號元素，表的長度減1，其

//后元素前移

voidremove(inti); //讀取，返回第i個元素的值

ELEMfetch(inti);}北京大學信息學院，轉載或翻印必究Page172.1.2線性表的存儲結構

定長的一維數(shù)組結構又稱向量型的順序存儲結構

變長的線性表存儲結構鏈接式存儲結構串結構、動態(tài)數(shù)組、以及順序文件

北京大學信息學院，轉載或翻印必究Page182.1.3線性表運算分類

創(chuàng)建線性表的一個實例list(-)

線性表消亡（即析構函數(shù)）~list()

獲取有關當前線性表的信息

訪問線性表并改變線性表的內容或結構線性表的輔助性管理操作北京大學信息學院，轉載或翻印必究Page192.2順序表—向量(sequentiallist—vector)

采用定長的一維數(shù)組存儲結構主要特性:元素的類型相同

元素順序地存儲在連續(xù)存儲空間中，每一個元素唯一的索引值

使用常數(shù)作為向量長度

北京大學信息學院，轉載或翻印必究Page202.2.1向量的類定義(typedefinition)

數(shù)組存儲讀寫其元素很方便，通過下標即可指定位置

北京大學信息學院，轉載或翻印必究Page21順序表類定義enumBoolean{False,True};//假定最大長度為100//并假定順序表的元素類型T為ELEMconstintMax_length=100;classlist{//順序表，向量private: //私有變量，順序表實例的最大長度

intmsize; //私有變量，順序表實例的當前長度

intcurr_len; 北京大學信息學院，轉載或翻印必究Page22 //私有變量，存儲順序表實例的向量

ELEM*nodelist; public: //以下列出成員函數(shù)（順序表的算子集)

//當前下標，順序表的公共變量

intcurr; //constructor算子,創(chuàng)建一個新的順序表，

//其實參是表實例的最大長度。

list(constintsize);北京大學信息學院，轉載或翻印必究Page23 //destructor算子，用于將該表實例刪去

~list();

//將順序表存儲的內容清除，成為空表

voidclear();

//將當前下標curr賦值為第一個元素的位置

voidsetFirst(); //將當前下標curr下移一格，即curr+1 voidnext(); //若當前下標curr位置有值時，返回True BooleanisInList();北京大學信息學院，轉載或翻印必究Page24 //在表尾增添一個新元素，順序表的實際長度加1 voidappend(constELEM&); //在當前下標curr位置插入元素新值。

voidinsert(constELEM&); //當前下標curr位置的元素值作為返回值，并刪去該元素

ELEMremove(); BooleanisEmpty();//當線性表為空時，返回True ELEMcurrValue();//返回當前curr位置的元素值。

intlength();//返回此順序表的當前實際長度

voidprev();//將當前下標curr上移一格，即curr-1}北京大學信息學院，轉載或翻印必究Page252.2.2向量的運算

插入元素運算voidinsert(item)刪除元素運算

ELEMremove()

北京大學信息學院，轉載或翻印必究Page26北京大學信息學院，轉載或翻印必究Page27插入算法

/*（設元素的類型為ELEM，nodelist是存儲順序表的向量，msize是此向量的最大長度，curr_len是此向量的當前長度，curr為此向量當前下標）*/＃include<assert.h>viodinsert(ELEMitem){ //需要檢查當前長度不能等于msize，當前游標指針

//curr不能小于0,也不能大于當前長度北京大學信息學院，轉載或翻印必究Page28

assert((curr_len<msize)&&(curr>=0)&&(curr<=curr_len)); //此條件不滿足時，程序異常，退出運行

//從表尾curr_len-1起往右移動直到curr for(inti=curr_len;i>curr;i--) nodelist[i]=nodelist[i-1]; //當前指針處插入新元素

nodelist[curr]=item; //表的實際長度curr_len加1 curr_len++;}北京大學信息學院，轉載或翻印必究Page29算法執(zhí)行時間

元素總個數(shù)為k，各個位置插入的概率相等為p＝1/k平均移動元素次數(shù)為

總時間開銷估計為O（k）

北京大學信息學院，轉載或翻印必究Page30刪除算法

/*（設元素的類型為ELEM，nodelist是存儲順序表的向量，msize是此向量的最大長度，curr_len是此向量的當前長度，curr為此向量當前下標）*///返回curr所指的元素值，并從表中刪去此元素ELEMremove(){//首先需要檢驗當前長度不能等于0,當前指針//curr不能小于0,不能等于curr_len北京大學信息學院，轉載或翻印必究Page31assert((curr_len!=0)&&(curr>=0)&&(curr<curr_len));//若上述條件為假，則程序異常，退出運行ELEMtemp＝

nodelist[curr];//從指針curr到curr_len每個元素往前移一格for(inti=curr;i<curr_len-1;i++)nodelist[i]=nodelist[i+1];curr_len--;//表的實際長度cur_len減1returntemp;//返回值是進入時的舊值}北京大學信息學院，轉載或翻印必究Page32算法時間代價

與插入操作相似，O(k)

順序表存取元素方便，時間代價為O(1)但插入、刪除操作則付出時間代價O(k)

北京大學信息學院，轉載或翻印必究Page332.3鏈表(linkedlist)單鏈表雙鏈表循環(huán)鏈表北京大學信息學院，轉載或翻印必究Page342.3.1單鏈表通過指針把它的一串存儲結點鏈接成一個鏈

存儲結點由兩部分組成：

data字段

link字段

北京大學信息學院，轉載或翻印必究Page35單鏈表的存儲結構

北京大學信息學院，轉載或翻印必究Page36單鏈表的結點類型以及變量first說明

structListNode{ ELEMdata；

ListNode*link;};typedefListNode*ListPtr;ListPtrfirst;北京大學信息學院，轉載或翻印必究Page37查找單鏈表中第i個結點算法

//函數(shù)返回值是找到的結點指針ListNode*FindIndex(constinti){ //first表首變量，可能指向空表

if(i==-1)returnfirst; *p=first->link;//p沒有定義! intj=0;北京大學信息學院，轉載或翻印必究Page38 while(p!=NULL&&j<i) { p=p->link; j++; } //指向第i結點，i＝0,1,…，當鏈表

//中結點數(shù)小于i時返回NULL returnp;}北京大學信息學院，轉載或翻印必究Page39單鏈表插入算法//插入數(shù)據(jù)內容為value的新結點，為第i個結點。

ListNode*Insert(ELEMvalue,inti){ ListNode*p，*q; q=newListNode; p=FindIndex(i-1); if(p==NULL)returnNULL;北京大學信息學院，轉載或翻印必究Page40 q->link=p->link; q->data=value;

p->link=q; if(q->link==NULL) last=q; returnq;}

北京大學信息學院，轉載或翻印必究Page41插入過程

北京大學信息學院，轉載或翻印必究Page42單鏈表刪除算法

//刪除由參數(shù)link所指定的結點voidRemoveAfter(ListNode*link){ ListNode*newlink=link; if(link!=NULL) link=link->link; deletenewlink;}

北京大學信息學院，轉載或翻印必究Page43刪除過程

北京大學信息學院，轉載或翻印必究Page44求長度算法

intLength(){ ListNode*p=first->link; intcount=0; while(p!=NULL) { p=p->link; count++; } returncount;}

北京大學信息學院，轉載或翻印必究Page452.3.2雙鏈表

(doublelinkedlist)

單鏈表的主要不足之處是：link字段僅僅指向后繼結點，不能有效地找到前驅雙鏈表彌補了上述不足之處增加一個指向前驅的指針北京大學信息學院，轉載或翻印必究Page46雙鏈表示意圖

北京大學信息學院，轉載或翻印必究Page47雙鏈表及其結點類型的說明

structDblListNode{ ELEMdata;

DblListNode*rlink; DblListNode*llink;};

structDoubleList{ DblListNode*first，*last;};北京大學信息學院，轉載或翻印必究Page48雙鏈表刪除結點如果要刪除指針變量p所指的結點，只需修改該結點前驅的rlink字段和該結點后繼的llink字段，即p->llink->rlink=p->rlink;p->rlink->llink=p->llink;然后把變量p變空，再把p所指空間釋放即可。p->rlink=NULL;p->llink=NULL;deletep;北京大學信息學院，轉載或翻印必究Page49刪除過程

北京大學信息學院，轉載或翻印必究Page50雙鏈表的插入如果要在p所指結點后插入一個新結點，首先執(zhí)行newq開辟結點空間。然后，讓該新結點的rlink填入p所指的后繼地址，新結點的llink填入p所指結點的后繼的llink字段，即newq;q->rlink=p->rlink;q->llink=p->rlink->llink;此外，要把新結點的地址填入原p所指結點的rlink字段，而且新結點后繼的llink字段也應該回指新結點。p->rlink=q;q->rlink->llink=q;

北京大學信息學院，轉載或翻印必究Page51插入過程

北京大學信息學院，轉載或翻印必究Page522.3.3循環(huán)鏈表

(circularlylinkedlist)

將單鏈表或者雙鏈表的頭尾結點鏈接起來，就是一個循環(huán)鏈表。不增加額外存儲花銷，卻給不少操作帶來了方便從循環(huán)表中任一結點出發(fā)，都能訪問到表中其他結點。北京大學信息學院，轉載或翻印必究Page53幾種主要鏈表比較

北京大學信息學院，轉載或翻印必究Page542.4線性表實現(xiàn)方法的比較順序表的主要優(yōu)點

沒用使用指針，不用花費附加開銷

線性表元素的讀訪問非常簡潔便利

鏈表的主要優(yōu)點

無需事先了解線性表的長度

允許線性表的長度有很大變化

能夠適應經常插入刪除內部元素的情況

北京大學信息學院，轉載或翻印必究Page55應用場合的選擇

不要使用順序表的場合經常插入刪除時，不宜使用順序表

線性表的最大長度也是一個重要因素

不要使用鏈表的場合

當讀操作比插入刪除操作頻率大時，不應選擇鏈表當指針的存儲開銷，和整個結點內容所占空間相比其比例較大時，應該慎重選擇

北京大學信息學院，轉載或翻印必究Page562.5棧(stack)

一種限制訪問端口的線性表，后進先出表(LIFO表，Least-InFirst-Out)。也稱為“下推表”。元素插入稱為棧的‘壓入’，push，刪除稱為棧的‘彈出’，pop表首被稱為‘棧頂’，而棧的另一端則叫做‘棧底’

每次取出（并被刪除）的總是剛壓進的元素，而最先壓入的元素則被放在棧的底部

北京大學信息學院，轉載或翻印必究Page57棧的抽象數(shù)據(jù)類型

enumBoolean{True,False}template<classELEM>classStack{ //棧的元素類型為ELEM //棧的存儲：可以用順序表或單鏈表存儲，長

//度為定長

//棧的運算集為：

stack(ints);//創(chuàng)建棧的實例

~stack();//該實例消亡北京大學信息學院，轉載或翻印必究Page58voidPush(ELEMitem); //item壓入棧頂

ELEMPop();//返回棧頂內容，并從棧頂彈出

ELEMGetTop();//返回棧頂內容，但不彈出

voidMakeEmpty(); //變?yōu)榭諚?/p>

BooleanIsEmpty(); //返回真，若棧已空

BooleanIsFull();//返回真，若棧已滿};北京大學信息學院，轉載或翻印必究Page59棧的實現(xiàn)

順序棧使用向量實現(xiàn)鏈式棧用單鏈表方式存儲，其中指針的方向是從棧頂向下鏈接

北京大學信息學院，轉載或翻印必究Page602.5.1順序棧

//設棧的類定義為stack，棧元素類型為浮點float類型

enumBoolean{True,False}#include<assert.h>//引入邏輯斷言語句classStack{public: float*ElmList;//存放數(shù)據(jù)元素的指針變量北京大學信息學院，轉載或翻印必究Page61inttop;//該變量指示棧頂在該向量的位置，下標值//當新元素壓入或棧內容彈出，top值隨之增減intmaxsize; //棧的最大長度//構建函數(shù)，創(chuàng)建棧的實例，向量空間長度為sizeStack(intsize); …};北京大學信息學院，轉載或翻印必究Page62順序棧

按壓入先后次序，最先壓入的元素編號為1，然后依次為2,3,4

北京大學信息學院，轉載或翻印必究Page63

順序棧的創(chuàng)建

//棧實例的創(chuàng)建，指定最大長度10Stack::Stack(intsize=10){ maxsize=size; //開辟向量存儲空間

ElmList=newfloat[maxsize]; //判斷new命令成功否，否則斷言程序異常

assert(ElmList!=NULL); top=-1;//表示?？諁北京大學信息學院，轉載或翻印必究Page64壓入棧頂

voidStack::Push(floatitem){ //判非棧滿，否則棧溢出，退出運行

assert(!IsFull()); top++;//棧頂

ElmList[top]=item;}北京大學信息學院，轉載或翻印必究Page65從棧頂彈出

floatStack::Pop(){ //判棧非空，否則斷言?？债惓?，退//出運行

assert(!IsEmpty()); returnElmList[top--];}北京大學信息學院，轉載或翻印必究Page66從棧頂讀取，但不彈出

floatStack::GetTop(){ //判棧非空，否則斷言?？债惓＃?/出運行

assert(!IsEmpty()); returnElmList[top];}北京大學信息學院，轉載或翻印必究Page67其他算法

變空棧voidStack::MakeEmpty(){top=-1;}棧消亡

~Stack(){delete[]ElmList;}棧滿時，返回非零值（真true）

BooleanIsFull(){returntop==maxsize-1;}北京大學信息學院，轉載或翻印必究Page682.5.2鏈式棧

用單鏈表方式存儲指針的方向從棧頂向下鏈接

北京大學信息學院，轉載或翻印必究Page69單鏈表的結點類型

structListNode{

ELEMdata;

ListNode*link; };北京大學信息學院，轉載或翻印必究Page70鏈式棧的創(chuàng)建

#include<assert.h>ClassStack{//linkedstack，假定其元素類型為ListNodeprivate:ListNode*top;public：

Stack() { //創(chuàng)建一個空棧，不用指定最大長度

top=NULL;

};…};北京大學信息學院，轉載或翻印必究Page71壓入棧頂

voidStack::Push(floatitem){ ListNode*temp; temp=newListNode; //若無存儲空間則異常，程序退出運行

assert(!temp==NULL); temp->data=item; temp->link=top;//老棧頂指針

top＝temp;//新棧頂指針}北京大學信息學院，轉載或翻印必究Page72自單鏈棧彈出

ELEMStack::Pop(){ //判棧非空，否則斷言?？债惓?，程序退出

assert(!IsEmpty()); ELEMresult=top->data;//暫存棧頂內容

ListNode*temptr; temptr=top;//老棧頂指針

top=top->link;//新棧頂指針

deletetemptr;//釋放空間

returnresult;//返回的是彈出內容}北京大學信息學院，轉載或翻印必究Page73

小結實際應用中，順序棧比鏈式棧用得更廣泛些

順序棧容易根據(jù)棧頂位置，進行相對位移，快速定位并讀取棧的內部元素

順序棧讀取內部元素的時間為O(1)，而鏈式棧則需要沿著指針鏈游走，顯然慢些，讀取第k個元素需要時間為O(k)

一般來說，棧不允許“讀取內部元素”，只能在棧頂操作北京大學信息學院，轉載或翻印必究Page742.5.3棧的應用--計算表達式的值

?？梢詰糜谶f歸函數(shù)(recursivefunction)的實現(xiàn)

使用下推表（棧）自動進行復雜的算術表達式的遞歸求值

北京大學信息學院，轉載或翻印必究Page75計算表達式的值表達式的遞歸定義基本符號集：{0，1，…，9，+，-，*，/，（，）}

語法成分集：{<表達式>,<項>,<因子>,<常數(shù)>,<數(shù)字>}

語法公式集

后綴表達式

后綴表達式求值

北京大學信息學院，轉載或翻印必究Page76語法公式(中綴表達法)

<表達式>∷=<項>+<項>|<項>－<項>|<項><項>：：=<因子>*<因子>|<因子>/<因子>|<因子><因子>::=<常數(shù)>|（<表達式>）<常數(shù)>∷=<數(shù)字>|<數(shù)字><常數(shù)><數(shù)字>∷=0|1|2|3|4|5|6|7|8|9

北京大學信息學院，轉載或翻印必究Page77中綴表達的算術表達式的計算次序

(1)先執(zhí)行括號內的計算，后執(zhí)行括號外的計算。在具有多層括號時，按層次反復地脫括號，左右括號必須配對。(2)在無括號或同層括號時，先乘(*)、除(／)，后作加(+)、減(-)。(3)在同一個層次，若有多個乘除（*、／）或加減(+，-)的運算，那就按自左至右順序執(zhí)行。

北京大學信息學院，轉載或翻印必究Page78后綴表達式

<表達式>∷=<項><項>+|<項><項>－|<項><項>：：=<因子><因子>*|<因子><因子>/|<因子><因子>::=<常數(shù)><常數(shù)>∷=<數(shù)字>|<數(shù)字><常數(shù)>|<數(shù)字>.<常數(shù)>|<數(shù)字>∷=0|1|2|3|4|5|6|7|8|9

北京大學信息學院，轉載或翻印必究Page79中綴表達式轉換成等價的后綴表達式（1）當輸入的是操作數(shù)時，直接輸出到后綴表達式PostfixExp序列。（2）當輸入的是開括號時，也把它壓棧。（3）當輸入的是閉括號時，先判斷棧是否為空，若為空（括號不匹配），應該當錯誤異常處理，清棧退出。若非空，則把棧中的元素依次彈出，直到遇到第一個開括號為止，將彈出的元素輸出到后綴表達式PostfixExp的序列中（彈出的開括號不放到序列中），若沒有遇到開括號，說明括號也不匹配，做異常處理，清棧退出。北京大學信息學院，轉載或翻印必究Page80（4）當輸入的是運算符時（a)循環(huán)，當（棧非空

and棧頂不是開括號

and棧頂運算符的優(yōu)先級不低于輸入的運算符的優(yōu)先級）時，反復操作將棧頂元素彈出，放到后綴表達式序列中；

（b）把輸入的運算符壓棧。（5）最后，當中綴表達式InfixExp的符號序列全部讀入時，若棧內仍有元素，把它們全部依次彈出，都放到后綴表達式PostfixExp序列尾部。若彈出的元素遇到開括號時，則說明括號不匹配，做錯誤異常處理，清棧退出。北京大學信息學院，轉載或翻印必究Page81后綴表達式求值

循環(huán)：依次順序讀用戶鍵入的符號序列，組成并判別語法成分的類別1.當遇到的是一個操作數(shù)，則壓入棧頂；2.當遇到的是一個運算符,就從棧中兩次取出棧頂，按照運算符對這兩個操作數(shù)進行計算。然后將計算結果壓入棧頂。如此繼續(xù)，直到遇到符號＝,這時棧頂?shù)闹稻褪禽斎氡磉_式的值。

北京大學信息學院，轉載或翻印必究Page82棧的應用

——后綴表達式求值中綴表達式：運算符在中間需要括號改變優(yōu)先級

4*x*(2*x+a)–c后綴表達式運算符在后面完全不需要括號4x*2x*a+*c–北京大學信息學院，轉載或翻印必究Page83后綴計算器的類定義//ClassDeclaration類的說明enumBoolean{False,True};typedefdoubleELEM;//文件astack.h中有棧，類stack的定義#include"astack.h"classCalculator{private: StackS;//這個棧是用于壓入保存操作數(shù)

//把一個浮點數(shù)num壓入棧

voidEnter(doublenum);北京大學信息學院，轉載或翻印必究Page84 //從棧頂彈出兩個操作數(shù)，賦值給變參opnd1和opnd2 BooleanGetTwoOperands(double&opnd1,double&opnd2); //調用GetTwoOperands，并按op運算，對兩個操作數(shù)

//進行計算

voidCompute(charop);public: //創(chuàng)建計算器實例，開辟一個空棧

Calculator(void){};

北京大學信息學院，轉載或翻印必究Page85 //后綴表達式的讀入，在遇到＝符號，

//啟動求值計算

voidRun（void); //計算器的清除，為隨后的下一次計算作準備

voidClear（void); ////}//計算器類classCalculator的程序實現(xiàn)voidCalculator::Enter(doublenum) { S.Push(num); }北京大學信息學院，轉載或翻印必究Page86BooleanCalculator::GetTwoOperands(double&opnd1,double&opnd2){ if(S.StackEmpty()) { cerr<<"Missingoperand!"<<endl; returnFalse; } opnd1=S.Pop();//右操作數(shù)北京大學信息學院，轉載或翻印必究Page87 if(S.StackEmpty()) { cerr<<"Missingoperand!"<<endl; returnFalse; } opnd2=S.Pop();//左操作數(shù)

returnTrue;}北京大學信息學院，轉載或翻印必究Page88voidCalculator::Compute（charop）{ Booleanresult; doubleoperand1,operand1; result=GetTwoOperands(operand1,operand2); if(result==True) switch(op) {北京大學信息學院，轉載或翻印必究Page89 case'+':S.Push(operand2+operand1); break; case'-':S.Push(operand2-operand1); break;

case'*':S.Push(operand2*operand1);

break;

case'/':if(operand1==0.0)

{

cerr<<"Dividedby0!"<<endl;北京大學信息學院，轉載或翻印必究Page90

S.ClearStack(); } else

S.Push(operand2/operand1);

break;

}

else

S.ClearStack();}北京大學信息學院，轉載或翻印必究Page91voidCalculator::Run(void){ charc; doublenewoperand; while(cin>>c,c!='=') { case'+': case'-': case'*':北京大學信息學院，轉載或翻印必究Page92 case'/': Compute(c); break; default: cin.putback(c); cin>>newoperand; Enter(newoperand); break; }北京大學信息學院，轉載或翻印必究Page93 if(!S.StackEmpty()) //印出求值的最后結果

cout<<S.top()<<endl;}voidCalculator::Clear(void){

S.ClearStack();}[后綴計算器的類定義，結束]北京大學信息學院，轉載或翻印必究Page942.5.4棧與遞歸

(recursionwithstack)

函數(shù)的遞歸定義

主程序和子程序的參數(shù)傳遞

棧在實現(xiàn)函數(shù)遞歸調用中所發(fā)揮的作用

北京大學信息學院，轉載或翻印必究Page95遞歸定義階乘n！函數(shù)

階乘n！的遞歸定義如下：

北京大學信息學院，轉載或翻印必究Page96計算階乘n！的兩個程序

//使用循環(huán)迭代方法，計算階乘n!的程序longfactorial(longn){ intm=1; inti; if(n>0) for(i=1;i<=n;i++) m=m*i; returnm;}北京大學信息學院，轉載或翻印必究Page97//遞歸定義的計算階乘n!的函數(shù)longfactorial(longn){ if(n==0) return1; else returnn*factorial(n-1);//遞歸調用}北京大學信息學院，轉載或翻印必究Page98用5個F機器來模擬4!的計算左邊是一個F機器，它能夠計算乘積并能夠與其他機器交換信息。通過內部棧交換信息.右邊是它們所使用的棧北京大學信息學院，轉載或翻印必究Page99北京大學信息學院，轉載或翻印必究Page100遞歸計算時內部棧情況

北京大學信息學院，轉載或翻印必究Page101北京大學信息學院，轉載或翻印必究Page102hanoi塔問題的遞歸求解

北京大學信息學院，轉載或翻印必究Page103hanoi塔的執(zhí)行過程

北京大學信息學院，轉載或翻印必究Page104河內塔問題的遞歸求解程序hanoi(n,X,Y,Z)的含義是： 移動n個槃環(huán)，由X柱子（出發(fā)柱）將槃環(huán)移動到Z柱（終點柱）。其移動過程中，Y柱和X柱皆可用于暫時存放環(huán)槃，不過注意每一步移動都必須嚴格遵循大盤不能壓小盤的原則。例如，hanoi(2,‘B’,‘C’,‘A’),其含義是初始位于B柱上部的2個環(huán)槃移動到A柱，執(zhí)行過程中可以使用C，B柱暫存環(huán)槃。北京大學信息學院，轉載或翻印必究Page105//move(charX,charY)子程序，表示移動一步，//輸出打印，把柱X的頂部環(huán)槃移到柱Yvoidmove(charX,charY){ cout<<"move"<<X<<"to"<<Y<<endl;}北京大學信息學院，轉載或翻印必究Page106voidhanoi(intn,charX,charY,charZ){ if(n<=1) move(X,Z); else { //最大的環(huán)槃在X上不動，把X上的n－1個環(huán)槃移到Y hanoi(n-1,X,Z,Y); move(X,Z); //移動最大環(huán)槃到Z，放好

hanoi(n-1,Y,X,Z); //把Y上的n－1個環(huán)槃移到Z }}北京大學信息學院，轉載或翻印必究Page107hanoi遞歸子程序的運行示意圖北京大學信息學院，轉載或翻印必究Page108北京大學信息學院，轉載或翻印必究Page109遞歸運行時,堆棧的進退以及通過堆棧傳遞參數(shù)北京大學信息學院，轉載或翻印必究Page110123北京大學信息學院，轉載或翻印必究Page1112.6隊

列(queue)

限制訪問點的線性表

‘加入’新元素時，限于表的一端進行（隊列的前端）

元素的‘取出’則被限制于表的另一端（隊列的尾端）

“先進先出表”(FIFO，F(xiàn)irstInFirstOut)

北京大學信息學院，轉載或翻印必究Page112隊列的應用

消息緩沖器

郵件緩沖器

計算機的硬設備之間的通信也需要隊列作為數(shù)據(jù)緩沖

操作系統(tǒng)中也使用隊列

北京大學信息學院，轉載或翻印必究Page113隊列的抽象數(shù)據(jù)類型template<classT>classQueue{ //隊列的元素類型為T，它們是按先后次序的

//線性表結構

//一般使用front和rear指示隊列的前端和尾端

//用curr_len存儲當時的隊列長度

//棧的運算集為：

Queue(ints);//創(chuàng)建隊列實例，最大長度為s ~Queue();//該實例消亡,釋放全部空間北京大學信息學院，轉載或翻印必究Page114 voidEnQueue(Titem);//item進入隊列前端

//返回隊列的前端元素內容，并從隊列刪去

TDeQueue(); //返回隊列的前端元素內容，但不從尾部刪去

TGetFirst(); voidMakeEmpty();//變?yōu)榭贞犃?/p>

intIsEmpty();//返回真，若隊列已空

intIsFull();//返回真，若隊列已滿

};北京大學信息學院，轉載或翻印必究Page1152.6.1順序隊列

使用順序表來實現(xiàn)隊列。用向量存儲隊列元素，并用兩個變量分別指向隊列的前端和尾端

北京大學信息學院，轉載或翻印必究Page116隊列的類定義

#include<assert.h>//包括邏輯斷言函數(shù)庫classQueue{private: float*Qlist;//存放數(shù)據(jù)元素的向量

//隊列前端和尾端向量的下標值

intfront，rear; //當新元素進入或隊列尾端的元素取出，這兩

//個變量值隨之增減北京大學信息學院，轉載或翻印必究Page117 intmaxsize;//隊列最大長度

intcurr_len;//隊列當前長度public：

//創(chuàng)建隊列實例，指定該實例的向量空間長度

Queue(intsize); …};北京大學信息學院，轉載或翻印必究Page118新元素壓入隊列的尾端

北京大學信息學院，轉載或翻印必究