工程級使用數(shù)據(jù)結(jié)構(gòu)章

返回主目錄

本章說明3.1棧3.2棧的應(yīng)用舉例3.3棧與遞歸的實現(xiàn)3.4隊列

本章小結(jié)學(xué)習(xí)目標(biāo)

掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用問題中正確選用它們熟練掌握棧類型的兩種實現(xiàn)方法熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。重點和難點

掌握棧和隊列這兩種結(jié)構(gòu)的特點，以便能在應(yīng)用問題中正確使用知識點順序棧、鏈棧、循環(huán)隊列、鏈隊列本章說明

棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點在于基本操作的特殊性，棧必須按“后進先出”的規(guī)則進行操作，而隊列必須按“先進先出”的規(guī)則進行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。線性表和棧及隊列的插入和刪除操作的主要區(qū)別：線性表允許在表內(nèi)任一位置進行插入和刪除棧只允許在表尾一端進行插入和刪除隊列只允許在表尾一端進行插入，在表頭一端進行刪除3.1

棧1.棧的定義和特點定義：限定僅在表尾進行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點：先進后出（FILO）或后進先出（LIFO）基本操作：插入刪除初始化取棧頂元素判空等ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)2.棧的抽象數(shù)據(jù)類型定義ADTStack{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,…,n,n>=0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：

InitStack(&S)//建空棧

DestroyStack(&S)//撤消棧

ClearStack(&S)//清空棧3.1

棧StackEmpty(&S)//判空棧

StackLength(S)//返回棧元素個數(shù)

GetTop(S,&e)//用e返回棧頂元素

Push(&S,e)//在棧頂插入元素ePop(&S,&e)//在棧頂刪除元素，e返

StackTraverse(S,visit())}ADTStack3.1

棧

（1）棧的存儲結(jié)構(gòu)順序棧實現(xiàn)：一維數(shù)組s[M]top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，棧底basetop123450進棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=base,?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？?.棧的表示和實現(xiàn)3.1

棧入棧算法0M-1棧1底棧1頂棧2底棧2頂出棧算法在一個程序中同時使用兩個棧3.1

棧

棧的存儲結(jié)構(gòu):表示取棧頂元素表示*避免棧“上溢”的辦法是事先分配一個足夠大的空間。但事先無法估計。實際上，各個棧的大小都是動態(tài)變化的，往往有這樣的情況:即其中某個棧發(fā)生上溢，而其余的棧尚有很多空間。此時，我們可以設(shè)法調(diào)整空間，減少“上溢”的發(fā)生。如果只有兩個棧，則可以這樣做(該做法經(jīng)常被采用):（2）鏈棧棧頂^…...topdatanext棧底結(jié)點定義入棧算法出棧算法typedefstructLNode{intdata;structLNode*next;}LNode;^…...棧底toptopxptop^…...棧底topq3.1

棧1.回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop（1）讀入字符串（2）去掉空格（原串）（3）壓入棧（4）原串字符與出棧字符依次比較若不等，非回文若直到?？斩枷嗟龋匚?.數(shù)制轉(zhuǎn)換字符串：“madamimadam”例把十進制數(shù)159轉(zhuǎn)換成八進制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top7323.2棧的應(yīng)用算法:3.13.行編輯程序功能：接受用戶從終端輸入的程序和數(shù)據(jù)，并存入數(shù)據(jù)區(qū)。允許用戶輸入出錯，如發(fā)現(xiàn)剛輸入的一個字符錯時，可補進一個退格符“#”，表示前一個字符無效；如果發(fā)現(xiàn)當(dāng)前輸入的行內(nèi)差錯較多或難以補救，則可以鍵入一個退行符“@”，表示當(dāng)前行中字符均無效。如：whli##ilr#e(s#*s)outcha@putchar(*s=#++);是：while(*s)putchar(*s++);3.2棧的應(yīng)用算法思想設(shè)行輸入緩沖區(qū)為一個棧結(jié)構(gòu)，每接受一個字符后便進行判斷：（1）如果它既不是退格符#也不是退行符@，則將其壓入棧頂；（2）如果是一個#，則從棧頂刪除一個字符；（3）如果是一個@，則將棧清為空棧。3.2棧的應(yīng)用

算法3.24.表達式求值概念前綴表達式:+ab中綴表達式:a+b后綴表達式:ab+中綴表達式后綴表達式（逆波蘭表達式)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+算符：運算符和界符。算符的優(yōu)先關(guān)系：<、=、>（見表3.1)

這里重點介紹中綴表達式、后綴表達式求值。3.2棧的應(yīng)用表3.1算符間的優(yōu)先關(guān)系剛讀入的棧頂?shù)?.2棧的應(yīng)用（1）中綴表達式求值：操作數(shù)棧和運算符棧3.2棧的應(yīng)用

算法思想①設(shè)置兩個工作棧,運算符棧OPTR和操作數(shù)棧OPND。操作數(shù)棧也放表達式的運算結(jié)果；②置操作數(shù)棧為空棧，置運算符棧的棧底為表達式的起始符#；③自左向右掃描表達式(即每次讀一個字符)；④若遇操作數(shù)，則進棧OPND，轉(zhuǎn)③3.2棧的應(yīng)用⑤遇運算符，則運算符與OPTR棧頂進行優(yōu)先數(shù)比較(同級的棧項為大，剛讀入的為小)：若讀的運算符大于OPTR棧頂項，則進棧，轉(zhuǎn)③；若棧頂項大，則棧頂運算符退棧，操作數(shù)棧頂兩個元素退棧，并作一個運算，結(jié)果入棧OPND，轉(zhuǎn)③；若相等且為括號，則脫括號，轉(zhuǎn)③；若讀的運算符為#，則轉(zhuǎn)⑥；⑥若運算符棧頂項為#，則操作數(shù)棧頂為計算結(jié)果，結(jié)束；否則出錯3.2棧的應(yīng)用例：掃描A+B*C-D/(E+F)#’*’>’+’遇"-"<"*"

做B*C并進棧操作數(shù)#運算符AB*C+"-"<"+"做A+B*C并進棧操作數(shù)#運算符A+B*C進?！?’>‘(‘‘(‘>’/’’/’>’-‘‘-’>#操作數(shù)#運算符A+B*CD-/EF(+#操作數(shù)運算符AB+C*進棧‘+’>’#’3.2棧的應(yīng)用遇’)’<’+’操作數(shù)#運算符A+B*CD-/EF(+做E+F操作數(shù)#運算符A+B*CD-/(’)’=’(‘脫括號操作數(shù)#運算符A+B*CD-/E+F‘做D/(E+F)操作數(shù)#運算符A+B*CD/(E+F)-E+F‘#’<‘/’3.2棧的應(yīng)用‘#’<’/’做D/(E+F)操作數(shù)#運算符A+B*CD/(E+F)-‘#’<’/’做A+B*C-D/(E+F)操作數(shù)#運算符A+B*C-D/(E+F)‘#’=‘#’操作數(shù)出棧即計算結(jié)果3.4算法（2）中綴表達式轉(zhuǎn)為后綴表達式設(shè)中綴表達式和后綴表達式分別在向量IFX和PFX中，用棧S實現(xiàn)中綴式轉(zhuǎn)為后綴式，對IFX中表達式從左到右掃描，設(shè)TOKEN是掃描讀到的符號，轉(zhuǎn)換算法可描述如下:

棧初始化。從左到右掃描向量IFX，重復(fù)下述兩步操作，直到表達式尾。①從IFX中取出下個TOKEN(數(shù)字、運算符、左括號、右括號)；3.2棧的應(yīng)用②CASETOKENOF'('：將TOKEN壓入棧S;

操作數(shù)：將操作數(shù)直接送入PFX;

操作符：如棧空或TOKEN比棧頂元素優(yōu)先級高，將TOKEN進棧；否則，退棧并將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之;‘)'：退棧并將退棧元素送PFX，直到碰到左括號，左括號退棧不送PFX。當(dāng)遇到中綴表達式結(jié)束符號，連續(xù)退棧并送退棧元素到PFX，直至?？?。3.2棧的應(yīng)用（3）后綴表達式求值步驟：

a.讀入表達式一個字符

b.若是操作數(shù)，壓入棧，轉(zhuǎn)dc.若是運算符，從棧中彈出2個數(shù)，將運算結(jié)果再壓入棧

d.若表達式輸入完畢，棧頂即表達式值；若表達式未輸入完，轉(zhuǎn)atop4top43top735top例計算4+3*5后綴表達式：435*+top415top193.2棧的應(yīng)用3.3棧與遞歸的實現(xiàn)當(dāng)一個函數(shù)在運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三件事：將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存為被調(diào)用函數(shù)的局部變量分配存儲區(qū)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成：保存被調(diào)函數(shù)的計算結(jié)果釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)由于函數(shù)的運行規(guī)則是：后調(diào)用先返回，因此各函數(shù)占有的存儲管理應(yīng)實行"棧式管理"1.過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程33.3棧與遞歸的實現(xiàn)例遞歸的執(zhí)行情況分析2.遞歸過程及其實現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身叫遞歸實現(xiàn)：建立遞歸工作棧voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}運行結(jié)果：1，2，2，3，3，3，3.3棧與遞歸的實現(xiàn)3.遞歸調(diào)用執(zhí)行情況如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2,2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0結(jié)束(1)3.3棧與遞歸的實現(xiàn)

5.TowerofHanoi問題問題描述：有X,Y,Z三個塔座，X上套有n個直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號1,2,3……n。要求將n個圓盤從X移到Z，疊放順序不變，移動過程中遵循下列原則：每次只能移一個圓盤圓盤可在三個塔座上任意移動任何時刻，每個塔座上不能將大盤壓到小盤上解決方法：n=1時，直接把圓盤從X移到Zn>1時，先把上面n-1個圓盤從X移到Y(jié),然后將n號盤從X移到Z,再將n-1個盤從Y移到Z。即把求解n個圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ3.3棧與遞歸的實現(xiàn)XYZ執(zhí)行情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號表示nxyz

返回地址

3.3棧與遞歸的實現(xiàn)3.3棧與遞歸的實現(xiàn)main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB63.3棧與遞歸的實現(xiàn)main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC03.3棧與遞歸的實現(xiàn)3.3棧與遞歸的實現(xiàn)main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0?？?ABC02BAC8(1)(2)(4)(5)(6)(7)(3)6.地圖四染色問題R[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#

紫色

2#黃色3#

紅色4#

綠色3.3棧與遞歸的實現(xiàn)1.隊列的定義及特點定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表隊尾(rear)——允許插入的一端隊頭(front)——允許刪除的一端隊列特點：先進先出(FIFO)a1a2a3…….an入隊出隊frontrear隊列Q=(a1,a2,……,an)雙端隊列a1a2a3…….an端1端2入隊出隊入隊出隊3.4隊列2.鏈隊列結(jié)點定義typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;Typedefstruct{QueuePtrfront;QueuePtrrear;}頭結(jié)點^…...front隊頭隊尾rear設(shè)隊首、隊尾指針front和rear,front指向頭結(jié)點，rear指向隊尾3.4隊列frontrearx入隊^xfrontreary入隊x^yfrontrearx出隊x^yfrontrear空隊^frontreary出隊^3.4隊列入隊算法出隊算法3.4隊列3.循環(huán)隊列——隊列的順序存儲結(jié)構(gòu)實現(xiàn)：用一維數(shù)組實現(xiàn)sq[M]Q.front=0Q.rear=0123450隊空123450frontJ1,J1,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設(shè)兩個指針front,rear,約定：Q.rear指示隊尾元素的下一個位置；Q.front指示隊頭元素初值Q.front=Q.rear=0空隊列條件：front==rear入隊列：sq[rear++]=x;出隊列：x=sq[front++];rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront3.4隊列存在問題設(shè)數(shù)組大小為M，則：當(dāng)front=0,rear=M時，再有元素入隊發(fā)生溢出——真溢出當(dāng)front0,rear=M時，再有元素入隊發(fā)生溢出——假溢出解決方案隊首固定，每次出隊剩余元素向下移動——浪費時間循環(huán)隊列基本思想：把隊列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear==M,則令rear=0;M-1rear01front…...…...實現(xiàn)：利用“?！边\算入隊：sq[rear]=x;

rear=(rear+1)%M;出隊：x=sq[fron