數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭

第3章棧和隊(duì)列3.1棧3.2隊(duì)列3.3棧與隊(duì)列的應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第1頁!3.1?！狝DT棧棧（Stack）只允許在表的一端進(jìn)行插入和刪除的線性表允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）不含元素的棧稱為空棧插入：進(jìn)棧，入棧刪除：出棧，退棧特點(diǎn)后進(jìn)先出（LIFO）先進(jìn)后出（FILO）數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第2頁!3.1?！狝DT棧問題有三個(gè)元素按a1,a2,a3的次序依次進(jìn)棧，其出棧次序有幾種可能？出棧次序：a1，a2，a3

a1，a3，a2

a2，a1，a3

a2，a3，a1

a3，a2，a1注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第3頁!3.1棧——ADT棧LengthProcess：求棧中元素個(gè)數(shù)Output：返回棧中元素的個(gè)數(shù)PushInput：要添加的數(shù)據(jù)元素Process：向棧中添加元素x，即進(jìn)棧PopProcess：刪除棧頂元素，即出棧Output：返回棧頂元素ClearProcess：刪除棧中所有元素并置新的棧頂}//Stack數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第4頁!3.1?！獥５膶?shí)現(xiàn)順序棧的基本操作出棧：先出棧top再減1進(jìn)棧：top先加1再進(jìn)棧?？眨簍op==-1

012345678a1topa2topa3top棧滿：top==MaxStackSize-1toptop數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第5頁!3.1?！獥５膶?shí)現(xiàn)順序棧的操作的實(shí)現(xiàn)構(gòu)造函數(shù)，初始化一個(gè)空棧Stack(){StackList=newDataType[MaxStackSize];top=-1;}//Stack數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第6頁!3.1?！獥５膶?shí)現(xiàn)判斷棧是否已滿

boolIsFull(){if(top==MaxStackSize-1)returntrue;elsereturnfalse;}//IsFull數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第7頁!3.1棧——棧的實(shí)現(xiàn)向棧頂壓入元素

voidPush(DataTypex){if(IsFull()){cout<<”棧滿！”<<endl;elseStackList[++top]=x;}//Push數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第8頁!3.1?！獥５膶?shí)現(xiàn)清空棧

voidClear(){top=-1;}//Cleartop=-1012341001234壓入10top=0102501234壓入25top=110255001234壓入50top=2102501234彈出50top=11001234彈出25top=0圖3.2出棧和入棧操作以及棧頂?shù)淖兓瘮?shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第9頁!3.1棧——棧的實(shí)現(xiàn)鏈?zhǔn)綏ｎ惖亩xclassStackNode{DataTypedata; //結(jié)點(diǎn)數(shù)據(jù) StackNode*next; //結(jié)點(diǎn)鏈指針 public:friendclassLinkStack；StackNode(DataTyped=nulldata){data=d;next=NULL;}};//StackNodeclassLinkStack{StackNode*top;//棧頂指針public:LinkStack(){top=newStackNode();top->next=NULL;}//創(chuàng)建頭結(jié)點(diǎn)voidPush(DataTypedata);數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第10頁!3.1?！獥５膶?shí)現(xiàn)類中操作算法的描述入棧操作

voidPush(DataTypeitem){p=newStackNode(item);p->next=top->next;top->next=p;}//Push數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第11頁!3.1?！獥５膶?shí)現(xiàn)取棧頂元素操作

DataTypeGetTop(){if(top->next!=NULL)returntop->next->data;else{//?？盏那闆rcout<<”thestackisempty!”<<endl;returnnulldata;}}//GetTop數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第12頁!3.1?！獥Ｅc遞歸遞歸是在計(jì)算機(jī)科學(xué)和數(shù)學(xué)中一種解決問題的極其重要的方法。在數(shù)據(jù)結(jié)構(gòu)中，可以用它來設(shè)計(jì)簡(jiǎn)單、易于理解的算法，特別是在一些具有遞歸定義的結(jié)構(gòu)上設(shè)計(jì)算法。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第13頁!3.1棧——棧與遞歸描述問題例如，求階乘計(jì)算階乘的遞歸算法

intfact(intw){

if(w==0)return(1);

elset=fact(w-1);returnw*t;}數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第14頁!3.1?！獥Ｅc遞歸解決問題漢諾塔問題迷宮問題皇后問題背包問題數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第15頁!3.1棧——棧與遞歸漢諾塔（TowerofHanoi）問題漢諾塔問題來自一個(gè)古老的傳說：在世界剛被創(chuàng)建的時(shí)候有一座鉆石寶塔（塔A），其上有64個(gè)金盤。所有盤子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩座鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的盤子移動(dòng)到塔C上去，其間借助于塔B的幫助。由于盤子非常重，因此，每次只能移動(dòng)一個(gè)盤子。另外，任何時(shí)候都不能把一個(gè)盤子放在比它小的盤子上面。按照這個(gè)傳說，當(dāng)牧師們完成他們的任務(wù)之后，世界末日也就到了。需要移動(dòng)的次數(shù)為264-1數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第16頁!3.1?！獥Ｅc遞歸數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第17頁!3.1?！獥Ｅc遞歸遞歸過程和運(yùn)行時(shí)棧遞歸函數(shù)的運(yùn)行軌跡描述方法1）寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用箭頭表示語句的執(zhí)行次序；2）對(duì)函數(shù)的每個(gè)遞歸調(diào)用，寫出相應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫一條箭頭指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫一條箭頭指向調(diào)用語句的下面，表示返回路線；3）在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第18頁!3.1棧——棧與遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需要將實(shí)參和返回值地址等數(shù)據(jù)傳遞給被調(diào)函數(shù)，當(dāng)函數(shù)調(diào)用時(shí)，這些數(shù)據(jù)與局部變量一起構(gòu)成一條“工作記錄”，被壓入系統(tǒng)提供的棧（運(yùn)行時(shí)棧）。當(dāng)被調(diào)函數(shù)返回時(shí)，按照返回地址執(zhí)行調(diào)用函數(shù)中下一條指令，同時(shí)釋放棧中相應(yīng)的工作記錄。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第19頁!3.1棧——棧與遞歸遞歸調(diào)用的內(nèi)部執(zhí)行過程運(yùn)行開始時(shí)，首先為遞歸調(diào)用建立一個(gè)系統(tǒng)運(yùn)行時(shí)棧；每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址等組成的工作記錄壓入棧中；每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第20頁!3.1棧——棧與遞歸遞歸總結(jié)遞歸是重要的設(shè)計(jì)和編程工具，使許多算法變得簡(jiǎn)單，易于設(shè)計(jì)和實(shí)現(xiàn)。

－－－－優(yōu)點(diǎn)遞歸使算法的時(shí)間復(fù)雜度和空間復(fù)雜度同時(shí)增大，有時(shí)會(huì)導(dǎo)致效率急劇惡化，或者溢出系統(tǒng)棧。

－－－－缺點(diǎn)使用遞歸時(shí)應(yīng)該權(quán)衡效率和設(shè)計(jì)的關(guān)系。在有足夠的空間并且時(shí)間要求不高的情況下可以使用遞歸。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第21頁!3.2隊(duì)列——ADT定義ADT隊(duì)列的定義ADTQueue{Data數(shù)據(jù)項(xiàng)列表front：隊(duì)列中個(gè)元素的位置rear：隊(duì)列中最后一個(gè)元素的位置OperationsConstructorProcess：初始化隊(duì)首和隊(duì)尾IsEmptyProcess：判斷是否為空隊(duì)列Output：若隊(duì)列空，返回true，否則返回false數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第22頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)順序隊(duì)列順序隊(duì)列的定義constintMaxQSize=50;classSeqQueue{intfront,rear;DataTypeQueueList[MaxQSize];public:SeqQueue();//構(gòu)造函數(shù),初始化數(shù)據(jù)成員voidEnter(DataTypeitem);DataTypeLeave();voidClear();DataTypeFront();intLength();boolIsEmpty();boolIsFull();};//SeqQueue數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第23頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)存在問題rear==MaxQSize時(shí)，再有元素進(jìn)隊(duì)發(fā)生溢出當(dāng)front==0——真溢出當(dāng)front0——假溢出解決假溢出的方案固定隊(duì)頭，出隊(duì)時(shí)，剩余元素均向前移動(dòng)固定隊(duì)尾，入隊(duì)時(shí)，剩余元素均向前移動(dòng)循環(huán)隊(duì)列：把隊(duì)列設(shè)想成環(huán)形，讓0接在MaxQSize-1后——更好數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第24頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)仍然存在問題如何判斷隊(duì)列是“空”還是“滿”？隊(duì)空：front==rear隊(duì)滿：front==rear數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第25頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列類的操作算法描述構(gòu)造函數(shù)，初始化一個(gè)空隊(duì)列

SeqQueue(){front=rear=0;}//SeqQueue入隊(duì)操作voidEnter(DataTypeitem){if((rear+1)%MaxQSize==front)//判斷是否隊(duì)滿cout<<”隊(duì)列已滿，不能入隊(duì)！”<<endl;elseQueueList[rear]=item;rear=(rear+1)%MaxQSize;}//Enter數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第26頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)判斷隊(duì)列是否為空boolIsEmpty(){if(rear==front)returntrue;elsereturnfalse;}//IsEmpty判斷隊(duì)列是否已滿boolIsFull(){if((rear+1)%MaxQSize==front)returntrue;elsereturnfalse;}//IsFull數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第27頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列描述classQNode{//鏈隊(duì)結(jié)點(diǎn)的類DataTypedata;QNode*next;public:QNode(DataTypeitem=nulldata){data=item;next=NULL;}friendclassLinkQueue;};//QNode數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第28頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列基本操作的算法描述入隊(duì)操作voidEnter(DataTypeitem){rear->next=newQNode(item);rear=rear->next;}//Enter數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第29頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)取隊(duì)頭元素DataTypeFront(){if(!IsEmpty()) returnfront->next->data; else{cout<<”隊(duì)列空，無隊(duì)頭元素！”<<endl;returnnulldata;}}//Front數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第30頁!3.3棧與隊(duì)列的應(yīng)用棧的應(yīng)用應(yīng)用1：數(shù)制轉(zhuǎn)換問題將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)轉(zhuǎn)換方法：輾轉(zhuǎn)相除法例，N=3467，r=8（1348）10=（2504）8

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第31頁!3.3棧與隊(duì)列的應(yīng)用算法描述voidconversion(intN，intr){SeqStacks;intx;while(N){s.Push(N%r);N=N/r;}while(!s.IsEmpty()){x=s.Pop();cout<<x;}//while}//conversion數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第32頁!3.3棧與隊(duì)列的應(yīng)用后綴表達(dá)式（逆波蘭式）求值后綴表達(dá)式不含括號(hào)運(yùn)算符放在兩個(gè)操作數(shù)后面例中綴表達(dá)式2+(3*8–4)/5后綴表達(dá)式238*4-5/+所有的求值計(jì)算皆按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行比中綴表達(dá)式的計(jì)算簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第33頁!3.3棧與隊(duì)列的應(yīng)用棧輸入操作序列

ABCD+EF/PushABCDCDPushPushPop,Pop,PushPushPop,Pop,PushB(CD)Pop,Pop,PushA+B(CD)EFE/FPushPushPop,Pop,PushPop,Pop,PushA+B(C-D)E/F數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第34頁!3.3棧與隊(duì)列的應(yīng)用計(jì)算方法1根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的運(yùn)算符1和2，都要比較優(yōu)先關(guān)系運(yùn)算符間的優(yōu)先關(guān)系見下表

21

*/+－()#*/+－（）#>>>><>>>>>><>><<>><>><<>><>><<<<<=>>>>>><<<<<=數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第35頁!3.3棧與隊(duì)列的應(yīng)用OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,-3,72)#Push(opnd,’2’)#,*,(,-3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第36頁!3.3棧與隊(duì)列的應(yīng)用elseswitch(pare(s2.GetTop(),c)){case‘<’:s2.Push(c);c=getchar();break;case‘=’:s2.Pop();c=getchar();break;case‘>’:{temat=s2.Pop();b=s1.Pop();a=s1.Pop();result=Operate(a,temat,b);s1.Push(result);

c=getchar();break;}}//switch}//whileresult=s1.GetTop();}//EvaluateExpression數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第37頁!3.3棧與隊(duì)列的應(yīng)用應(yīng)用3：迷宮求解問題

入口出口數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第38頁!3.3棧與隊(duì)列的應(yīng)用迷宮求解問題的遞歸算法算法中用到的數(shù)據(jù)結(jié)構(gòu)intMaze[m+2][p+2]：表示迷宮m表示行數(shù)，p表示列數(shù)第0、m+1行，第0、p+1列是迷宮的圍墻Maze[i][j]=1時(shí)，表示該位置是墻壁，不能通行Maze[i][j]=0時(shí)，表示該位置是通路intmark[m+2][p+2]：標(biāo)志矩陣初始為0，當(dāng)某一位置[i][j]走過時(shí)，置mark[i][j]=1數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第39頁!3.3棧與隊(duì)列的應(yīng)用遞歸函數(shù)intSeekPath(intx,inty){inti,g,h;char*d;if(x==m&&y==p)return1;for(i=0;i<4;i++){g=x+move[i].a;h=y+move[i].b;d=move[i].dir;if(!Maze[g][h]&&!mark[g][h]){mark[g][h]=1;if(SeekPath(g,h)){

cout<<“(“<<g<<“,”<<h<<“),”<<“Direction”<<dir<<“,”;return1;}}}if(x==1&&y==1)cout<<“nopathvinMaze”<<endl;return0;}數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第40頁!3.3棧與隊(duì)列的應(yīng)用迷宮求解的非遞歸算法structBlock{intord;//通道塊的序號(hào)PosTypeseat;//通道塊在迷宮中的坐標(biāo)位置intdirection;//從此通道塊走向下一通道塊的方向};classMaze{structBlocke;public:boolMazePath((PosTypestart,PosTypeend);……};數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第41頁!3.3棧與隊(duì)列的應(yīng)用else{//當(dāng)前位置不通if(!s.IsEmpty()){e=s.Pop();while(e.direction==4&&!s.IsEmpty()){MarkPrint(e.seat);e=s.Pop();//留下不能通過的標(biāo)記并后退}//endwhileif(e.direction<4){e.direction++;s.Push(e);//換下一個(gè)方向探索curpos=NextPos(e.seat,e.direction);//新位置是舊的相鄰塊}//endif}//endif}//endelse}while(!s.IsEmpty());return(false);};//Mazth數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第42頁!3.3棧與隊(duì)列的應(yīng)用分析第i行元素與第i+1行元素的關(guān)系目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第43頁!書面作業(yè)p883-1，3-2，3-5，3-8實(shí)驗(yàn)題實(shí)驗(yàn)2，實(shí)驗(yàn)3，實(shí)驗(yàn)4數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第44頁!3.1?！狝DT棧棧的抽象數(shù)據(jù)類型ADTStack{

Data數(shù)據(jù)項(xiàng)列表top：棧頂位置

OperationsConstructorProcess：創(chuàng)建一個(gè)空棧IsEmptyProcess：判斷棧是否為空Output：如果棧為空，則返回true，否則返回falseGetTopProcess：取棧頂元素Output：返回棧頂元素?cái)?shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第45頁!3.1?！獥５膶?shí)現(xiàn)順序棧順序棧的定義如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？

0123456②附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top①確定用數(shù)組的哪一端表示棧底。a1a2a3數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第46頁!3.1?！獥５膶?shí)現(xiàn)constintMaxStackSize=50;//棧中能容納最大元素個(gè)數(shù)classSeqStack{DataTypeStackList[MaxStackSize];inttop;public:Stack();//構(gòu)造函數(shù)，初始化topboolIsEmpty();//判斷棧的狀態(tài)是否為空boolIsFull();DataTypeGetTop();//取棧頂元素voidPush(constDataTypex);//入棧DataTypePop();//出棧voidClear();//棧清空};//SeqStack數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第47頁!3.1?！獥５膶?shí)現(xiàn)判斷棧是否為空boolIsEmpty(){if(top==-1)returntrue;elsereturnfalse;}//IsEmpty數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第48頁!3.1棧——棧的實(shí)現(xiàn)取棧頂元素

DataTypeGetTop(){if(IsEmpty()){cout<<”?？?！”<<endl;returnnulldata;}returnStackList[top];}數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第49頁!3.1?！獥５膶?shí)現(xiàn)刪除棧頂元素

DataTypePop(){if(IsEmpty()){cout<<”?？?！”<<endl;returnnulldata;}returnStackList[top--];}//Pop數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第50頁!3.1?！獥５膶?shí)現(xiàn)鏈?zhǔn)綏＃↙inkedStack）鏈?zhǔn)綏＃ㄦ湕＃╂準(zhǔn)酱鎯?chǔ)的棧用單鏈表來實(shí)現(xiàn)鏈棧，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充鏈?zhǔn)綏５臈ｍ斣阪滎^top圖3.3鏈棧a1a2a3a4

數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第51頁!3.1?！獥５膶?shí)現(xiàn)DataTypePop();DataTypeGetTop();voidClear(){top->next=NULL;}boolIsEmpty(){returntop->next==NULL;}};//LinkStack數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第52頁!3.1棧——棧的實(shí)現(xiàn)出棧操作DataTypepop(){if(top->next!=NULL){p=top->next;retvalue=p->data; //暫存棧頂數(shù)據(jù)top->next=p->next;//修改棧頂指針deletep;//釋放，返回?cái)?shù)據(jù)returnretvalue;} else{//?？盏那闆rcout<<”thestackisempty!”<<endl;returnnulldata;}}//Pop數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第53頁!3.1棧——棧的實(shí)現(xiàn)順序棧和鏈棧的比較時(shí)間復(fù)雜度：相同，都是常數(shù)時(shí)間O(1)空間性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問題。鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。定義順序棧時(shí)，應(yīng)該知道所需的最大棧長度。如果事先無法預(yù)知棧的最大長度，可以采用鏈?zhǔn)綏！?shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第54頁!3.1棧——棧與遞歸遞歸的概念遞歸子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己遞歸是一種描述問題和解決問題的基本方法遞歸的基本思想問題分解：把一個(gè)不能或不好解決的大問題轉(zhuǎn)化為一個(gè)或幾個(gè)同類型的小問題，再把這些小問題進(jìn)一步分解成更小的小問題，直至每個(gè)小問題都可以直接解決。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第55頁!3.1?！獥Ｅc遞歸例如，計(jì)算斐波那契數(shù)列計(jì)算斐波那契數(shù)列的遞歸算法

longFib(intn){

if(n==0||n==1)returnn;

elsereturnFib(n-1)+Fib(n-2);}數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第56頁!3.1棧——棧與遞歸遞歸算法的設(shè)計(jì)遞歸三要素定義出口，即定義一個(gè)最小規(guī)模的問題，并給出其解；把一個(gè)大的問題劃分成同類型的規(guī)模較小的子問題；把子問題的解合成為原問題的解。遞歸的實(shí)現(xiàn)建立遞歸工作棧數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第57頁!3.1?！獥Ｅc遞歸漢諾塔解決方法n=1時(shí)，直接把圓盤從塔A移到塔C；n>1時(shí)，先把塔A上的n-1個(gè)圓盤移到塔B，然后將n號(hào)盤從塔A移到塔C，再將n-1個(gè)圓盤從塔B移到塔C。即把求解n個(gè)圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問題。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第58頁!3.1?！獥Ｅc遞歸解決漢諾塔問題的算法

main(){intn;cout<<"Inputnumberofdisks”;cin>>n;hanoi(n,'A','B','C');}voidhanoi(intn,charx,chary,charz){if(n==1)move(1,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第59頁!3.1棧——棧與遞歸n=3時(shí)漢諾塔遞歸算法的運(yùn)行軌跡Hanoi(3,A,B,C）Move(A,3,C)Hanoi(2,A,C,B）Hanoi(2,A,C,B）Hanoi(3,A,B,C）Hanoi(1,A,B,C）遞歸第三層遞歸第二層遞歸層Move(A,1,C)Hanoi(1,C,A,B）Move(C,1,B)Hanoi(1,B,C,A）Move(B,1,A)Hanoi(1,A,B,C）Move(A,1,C)Hanoi(1,A,B,C）Move(A,2,B)Hanoi(1,C,A,B）Hanoi(2,B,A,C）Hanoi(1,B,C,A）Move(B,2,C)Hanoi(1,A,B,C）Hanoi(2,B,A,C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第60頁!3.1?！獥Ｅc遞歸主程序Callproc1rproc1proc2proc3sCallproc2tCallproc3rst系統(tǒng)運(yùn)行時(shí)棧局部變量返回地址實(shí)際參數(shù)工作記錄數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第61頁!3.1?！獥Ｅc遞歸n=3時(shí)漢諾塔遞歸算法的部分執(zhí)行過程

main(){hanoi(3,'A','B','C');}voidhanoi(intn,charx,chary,charz){if(n==1)move(1,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}0123456789ABC321返回地址zyxn3ABC01CAB82ACB61ABC612數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第62頁!3.2隊(duì)列——ADT定義定義隊(duì)列（Queue）是只允許在表的一端進(jìn)行刪除，而在另一端進(jìn)行插入的線性表。允許刪除的一端叫做隊(duì)頭（front）允許插入的一端叫做隊(duì)尾（rear）特點(diǎn)先進(jìn)先出（FIFO，F(xiàn)irstInFirstOut）a1a2a3……………….an

入隊(duì)出隊(duì)frontrear數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第63頁!3.2隊(duì)列——ADT定義LengthProcess：求隊(duì)列中元素個(gè)數(shù)Output：返回隊(duì)列的元素個(gè)數(shù)FrontProcess：取出隊(duì)頭元素Output：返回隊(duì)頭元素EnterInput：要進(jìn)入隊(duì)列的元素Process：在隊(duì)尾插入新的元素LeaveProcess：刪除隊(duì)頭元素Output：返回隊(duì)頭元素ClearQueueProcess：刪除隊(duì)列中所有元素并設(shè)置初始狀態(tài)}//Queue數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第64頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)設(shè)兩個(gè)指針front和rear（初始front＝rear＝0）front指向隊(duì)頭元素，出隊(duì)時(shí)先取出，再front+1rear指向隊(duì)尾元素的下一個(gè)位置，進(jìn)隊(duì)時(shí)先將新元素加入，再rear+1隊(duì)空條件：front==rear，此時(shí)不能出隊(duì)隊(duì)滿條件：rear==MaxQSize，此時(shí)不能進(jìn)隊(duì)數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第65頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列也是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)利用“?！边\(yùn)算入隊(duì)QueueList[rear]=item;rear=(rear+1)%MaxQSize;出隊(duì)item=QueueList[front];front=(front+1)%MaxQSize;01frontrear…...…...MaxQSize-1數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第66頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)三種處理方法給隊(duì)列設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿給隊(duì)列增加一個(gè)統(tǒng)計(jì)元素個(gè)數(shù)的變量count，當(dāng)count=MaxQSize時(shí)隊(duì)滿；count=0時(shí)隊(duì)空少用一個(gè)變量，約定rear+1等于front（從后面趕上隊(duì)頭指針）為隊(duì)滿的情況隊(duì)滿條件：(rear+1)%MaxQSize==front隊(duì)空條件：

front

==rear數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第67頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)出隊(duì)操作DataTypeLeave(){if(front==rear){//判斷是否隊(duì)空cout<<”隊(duì)列已空，不能出隊(duì)”<<endl;returnnulldata;}e=QueueList[front]);front=(front+1)%MaxQSize;returne;}//Leave清空隊(duì)列voidClearQueue(){rear=front;}//ClearQueue數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第68頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用單鏈表來實(shí)現(xiàn)鏈隊(duì)列設(shè)置一個(gè)隊(duì)頭指針front：在鏈頭設(shè)置一個(gè)隊(duì)尾指針rear：在鏈尾鏈隊(duì)列無隊(duì)滿問題隊(duì)空條件：front->next==NULLfront圖3.13鏈隊(duì)列a1a2a3a4

rear數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第69頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)classLinkQueue{QNnode*front,*rear;public:LinkQueue(){rear=front=newQNode();}voidEnter(DataTypeitem);DataTypeLeave(); DataTypeFront(); voidClear(){front->next=rear->next=NULL;}boolIsEmpty(){returnfront–>next==NULL;} };//LinkQueue數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第70頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)出隊(duì)操作DataTypeLeave(){if(!IsEmpty()){//判隊(duì)不空p=front->next; DataTyperetvalue=p->data; //保存隊(duì)頭的值front->next=p->next;deletep;if(front->next==NULL)//刪除隊(duì)列中唯一結(jié)點(diǎn)后，重新設(shè)置rearrear=front;returnretvalue; }else{cout<<”隊(duì)列空!”<<endl;returnnulldata;}}//Leave數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第71頁!3.2隊(duì)列——隊(duì)列的實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列主要有插入和刪除操作插入操作：與普通隊(duì)列相同刪除操作：優(yōu)先級(jí)高的元素先被刪除，同一優(yōu)先級(jí)的元素按其到達(dá)先后進(jìn)行處理實(shí)際應(yīng)用中經(jīng)常用到，例如操作系統(tǒng)中的進(jìn)程優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列的ADT與普通隊(duì)列的ADT相似，只是刪除操作與普通隊(duì)列不同數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第72頁!3.3棧與隊(duì)列的應(yīng)用所轉(zhuǎn)換的8進(jìn)制數(shù)按低位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計(jì)算過程相反，因此轉(zhuǎn)換過程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想當(dāng)N>0時(shí)重復(fù)（1），（2）（1）若N≠0，則將N%r壓入棧s中，執(zhí)行（2）；若N＝0，將棧s的內(nèi)容依次出棧，算法結(jié)束。（2）用N/r代替N數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第73頁!3.3棧與隊(duì)列的應(yīng)用應(yīng)用2：表達(dá)式求值表達(dá)式表達(dá)式由操作數(shù)（operand）、運(yùn)算符（operator）和分界符（delimiter）組成操作數(shù)：變量或常數(shù)運(yùn)算符：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符分界符：括號(hào)表達(dá)式的表示方法前綴表達(dá)式中綴表達(dá)式后綴表達(dá)式數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第74頁!3.3棧與隊(duì)列的應(yīng)用算法思想設(shè)一個(gè)棧；順序掃描后綴表達(dá)式的每一項(xiàng)，根據(jù)其類型做如下處理：如果該項(xiàng)是操作數(shù)，則將其壓入棧頂；如果該項(xiàng)是運(yùn)算符<op>，則連續(xù)從棧頂退出兩個(gè)操作數(shù)x和y，形成運(yùn)算指令x<op>y，并將結(jié)果重新壓入棧頂。表達(dá)式所有項(xiàng)掃描并處理完后（以符號(hào)“=”為結(jié)束），棧頂存放的就是計(jì)算結(jié)果。數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第75頁!3.3棧與隊(duì)列的應(yīng)用中綴表達(dá)式的計(jì)算中綴表達(dá)式的計(jì)算次序根據(jù)運(yùn)算符優(yōu)先級(jí)由高到低的順序進(jìn)行運(yùn)算有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行乘方連續(xù)出現(xiàn)時(shí)先算最右面的計(jì)算方法1按中綴表達(dá)式的順序計(jì)算（本書）計(jì)算方法2先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式再進(jìn)行后綴表達(dá)式求值數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在瀏覽的是第76頁!3.3棧與隊(duì)列的應(yīng)用算法思想設(shè)定兩棧：操作數(shù)棧OPND，運(yùn)算符棧OPTR棧初始化：設(shè)操作數(shù)棧OPND為空；運(yùn)算符棧OPTR的棧底元素為表達(dá)式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是運(yùn)算符則要判斷（設(shè)OPTR的棧頂元素為1，當(dāng)前讀入的運(yùn)算符為2）：

1）if1<2，將2壓入OPTR棧；

2）if1==2且不為‘#’，退括號(hào)（彈出左括號(hào)）；

3）if1>2，則退棧、計(jì)算，結(jié)果壓入OPND棧；重復(fù)，直至讀入字符和OPTR的棧頂元素均為‘#’，此時(shí)OPND的棧頂即為計(jì)算結(jié)果數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭共86頁，您現(xiàn)在