北大信息院數(shù)據(jù)結(jié)構(gòu)ds 02list

第二章線性表、棧和隊(duì)列

任課教員：張銘

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)與信息系統(tǒng)研究所，轉(zhuǎn)載或翻印必究

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2大綱2.1線性表(linearlist)2.1.1線性表的抽象數(shù)據(jù)類型2.1.2線性表的存儲(chǔ)結(jié)構(gòu)2.1.3線性表運(yùn)算分類

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

2.5.1順序棧

2.5.2鏈?zhǔn)綏?/p>

2.5.3順序棧與鏈?zhǔn)綏５谋容^

2.5.4棧的應(yīng)用——后綴表達(dá)式求值

2.5.4遞歸的實(shí)現(xiàn)

2.6隊(duì)列

2.6.1順序隊(duì)列

2.6.2鏈?zhǔn)疥?duì)列

2.2.3順序隊(duì)列與鏈?zhǔn)疥?duì)列的比較

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

取值空間運(yùn)算集

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

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

//參數(shù)ELEM。

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

//用curr++或curr--

//控制線性表游標(biāo)curr的前后游走。

//用公共變

//量curr_len指示線性表的尾部，并導(dǎo)出表的當(dāng)

//前長度，…等。

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

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

intcurr; //公共變量，該線性表的當(dāng)前指針，游標(biāo)

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

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

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

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

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

//插入一個(gè)新結(jié)點(diǎn)，表的長度加1。第i號(hào)位置后

//的元素后移

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

//后元素前移

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

ELEMfetch(inti);}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page172.1.2線性表的存儲(chǔ)結(jié)構(gòu)

定長的一維數(shù)組結(jié)構(gòu)又稱向量型的順序存儲(chǔ)結(jié)構(gòu)

變長的線性表存儲(chǔ)結(jié)構(gòu)鏈接式存儲(chǔ)結(jié)構(gòu)串結(jié)構(gòu)、動(dòng)態(tài)數(shù)組、以及順序文件

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page182.1.3線性表運(yùn)算分類

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

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

獲取有關(guān)當(dāng)前線性表的信息

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

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

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

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

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

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

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

intmsize; //私有變量，順序表實(shí)例的當(dāng)前長度

intcurr_len; 北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22 //私有變量，存儲(chǔ)順序表實(shí)例的向量

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

//當(dāng)前下標(biāo)，順序表的公共變量

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

//其實(shí)參是表實(shí)例的最大長度。

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

~list();

//將順序表存儲(chǔ)的內(nèi)容清除，成為空表

voidclear();

//將當(dāng)前下標(biāo)curr賦值為第一個(gè)元素的位置

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

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

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

intlength();//返回此順序表的當(dāng)前實(shí)際長度

voidprev();//將當(dāng)前下標(biāo)curr上移一格，即curr-1}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page252.2.2向量的運(yùn)算

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

ELEMremove()

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page27插入算法

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

//curr不能小于0,也不能大于當(dāng)前長度北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page28

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

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

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

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

總時(shí)間開銷估計(jì)為O（k）

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page30刪除算法

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

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

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

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

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

存儲(chǔ)結(jié)點(diǎn)由兩部分組成：

data字段

link字段

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page35單鏈表的存儲(chǔ)結(jié)構(gòu)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36單鏈表的結(jié)點(diǎn)類型以及變量first說明

structListNode{ ELEMdata；

ListNode*link;};typedefListNode*ListPtr;ListPtrfirst;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page37查找單鏈表中第i個(gè)結(jié)點(diǎn)算法

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

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

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

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page41插入過程

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page42單鏈表刪除算法

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page43刪除過程

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page44求長度算法

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page452.3.2雙鏈表

(doublelinkedlist)

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page47雙鏈表及其結(jié)點(diǎn)類型的說明

structDblListNode{ ELEMdata;

DblListNode*rlink; DblListNode*llink;};

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page51插入過程

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

(circularlylinkedlist)

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

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

沒用使用指針，不用花費(fèi)附加開銷

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

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

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

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

能夠適應(yīng)經(jīng)常插入刪除內(nèi)部元素的情況

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page55應(yīng)用場合的選擇

不要使用順序表的場合經(jīng)常插入刪除時(shí)，不宜使用順序表

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

不要使用鏈表的場合

當(dāng)讀操作比插入刪除操作頻率大時(shí)，不應(yīng)選擇鏈表當(dāng)指針的存儲(chǔ)開銷，和整個(gè)結(jié)點(diǎn)內(nèi)容所占空間相比其比例較大時(shí)，應(yīng)該慎重選擇

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

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

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

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

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

//度為定長

//棧的運(yùn)算集為：

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

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

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

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

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

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

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

順序棧使用向量實(shí)現(xiàn)鏈?zhǔn)綏Ｓ脝捂湵矸绞酱鎯?chǔ)，其中指針的方向是從棧頂向下鏈接

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page602.5.1順序棧

//設(shè)棧的類定義為stack，棧元素類型為浮點(diǎn)float類型

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page63

順序棧的創(chuàng)建

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

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

assert(ElmList!=NULL); top=-1;//表示棧空}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page64壓入棧頂

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

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

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

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

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

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

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

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

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

BooleanIsFull(){returntop==maxsize-1;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page682.5.2鏈?zhǔn)綏?/p>

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page69單鏈表的結(jié)點(diǎn)類型

structListNode{

ELEMdata;

ListNode*link; };北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page70鏈?zhǔn)綏５膭?chuàng)建

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

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

top=NULL;

};…};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page71壓入棧頂

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

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

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

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

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

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

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

deletetemptr;//釋放空間

returnresult;//返回的是彈出內(nèi)容}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page73

小結(jié)實(shí)際應(yīng)用中，順序棧比鏈?zhǔn)綏Ｓ玫酶鼜V泛些

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

順序棧讀取內(nèi)部元素的時(shí)間為O(1)，而鏈?zhǔn)綏t需要沿著指針鏈游走，顯然慢些，讀取第k個(gè)元素需要時(shí)間為O(k)

一般來說，棧不允許“讀取內(nèi)部元素”，只能在棧頂操作北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page742.5.3棧的應(yīng)用--計(jì)算表達(dá)式的值

棧可以應(yīng)用于遞歸函數(shù)(recursivefunction)的實(shí)現(xiàn)

使用下推表（棧）自動(dòng)進(jìn)行復(fù)雜的算術(shù)表達(dá)式的遞歸求值

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page75計(jì)算表達(dá)式的值表達(dá)式的遞歸定義基本符號(hào)集：{0，1，…，9，+，-，*，/，（，）}

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

語法公式集

后綴表達(dá)式

后綴表達(dá)式求值

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page76語法公式(中綴表達(dá)法)

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page77中綴表達(dá)的算術(shù)表達(dá)式的計(jì)算次序

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page78后綴表達(dá)式

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

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

and棧頂不是開括號(hào)

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

（b）把輸入的運(yùn)算符壓棧。（5）最后，當(dāng)中綴表達(dá)式InfixExp的符號(hào)序列全部讀入時(shí)，若棧內(nèi)仍有元素，把它們?nèi)恳来螐棾?，都放到后綴表達(dá)式PostfixExp序列尾部。若彈出的元素遇到開括號(hào)時(shí)，則說明括號(hào)不匹配，做錯(cuò)誤異常處理，清棧退出。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page81后綴表達(dá)式求值

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page82棧的應(yīng)用

——后綴表達(dá)式求值中綴表達(dá)式：運(yùn)算符在中間需要括號(hào)改變優(yōu)先級(jí)

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

//把一個(gè)浮點(diǎn)數(shù)num壓入棧

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

//進(jìn)行計(jì)算

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

Calculator(void){};

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page85 //后綴表達(dá)式的讀入，在遇到＝符號(hào)，

//啟動(dòng)求值計(jì)算

voidRun（void); //計(jì)算器的清除，為隨后的下一次計(jì)算作準(zhǔn)備

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

returnTrue;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page88voidCalculator::Compute（charop）{ Booleanresult; doubleoperand1,operand1; result=GetTwoOperands(operand1,operand2); if(result==True) switch(op) {北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究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;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page90

S.ClearStack(); } else

S.Push(operand2/operand1);

break;

}

else

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

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

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

(recursionwithstack)

函數(shù)的遞歸定義

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

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

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page96計(jì)算階乘n！的兩個(gè)程序

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page101北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page102hanoi塔問題的遞歸求解

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

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

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

列(queue)

限制訪問點(diǎn)的線性表

‘加入’新元素時(shí)，限于表的一端進(jìn)行（隊(duì)列的前端）

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page112隊(duì)列的應(yīng)用

消息緩沖器

郵件緩沖器

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

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

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

//線性表結(jié)構(gòu)

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

//用curr_len存儲(chǔ)當(dāng)時(shí)的隊(duì)列長度

//棧的運(yùn)算集為：

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

//返回隊(duì)列的前端元素內(nèi)容，并從隊(duì)列刪去

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

TGetFirst(); voidMakeEmpty();//變?yōu)榭贞?duì)列

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

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

};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page1152.6.1順序隊(duì)列

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page116隊(duì)列的類定義

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

//隊(duì)列前端和尾端向量的下標(biāo)值

intfront，rear; //當(dāng)新元素進(jìn)入或隊(duì)列尾端的元素取出，這兩

//個(gè)變量值隨之增減北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page117 intmaxsize;//隊(duì)列最大長度

intcurr_len;//隊(duì)列當(dāng)前長度public：

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究