數(shù)據(jù)結(jié)構(gòu)-3棧和隊列

1、 選做題目：假設(shè)某機(jī)場共有m次航班，第i次航班有ni個座位，且每次航班達(dá)到一個目的機(jī)場。設(shè)計一個滿足該機(jī)場需要的用戶定票、退票程序。 姓名 身份證號目的地0 126 861 282 168票數(shù)航班號M-1 鏈?zhǔn)酱鎯γ總€訂票者信息,構(gòu)成一個結(jié)點（如圖示）。所有訂同一航班的旅客結(jié)點形成一個雙鏈表。當(dāng)訂票成功時，航班總票數(shù)減去訂票數(shù)。退票時，要檢驗退票數(shù)與訂票數(shù)是否相符。順序存儲 從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊列也是線性表，從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊列也是線性表，不過是兩種特殊的線性表：不過是兩種特殊的線性表：n棧只允許在表的一端進(jìn)行插入或刪除操作;n隊列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作。

2、因而，棧和隊列也可以被稱作為操作受限的線性表。 通過本章的學(xué)習(xí)，讀者應(yīng)能掌握棧和隊列的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及棧和隊列的基本運算以及實現(xiàn)算法。本章學(xué)習(xí)導(dǎo)讀第三章第三章 棧和隊列棧和隊列棧的定義和特點：定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾棧頂（top），表頭棧底（bottom），不含元素的空表稱空棧；特點：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2.棧底棧頂棧頂.出棧出棧進(jìn)棧進(jìn)棧棧s=(a1,a2,an)3.1 棧（Stack)關(guān)于“?！币莆盏牟僮?棧的構(gòu)造：順序或鏈?zhǔn)剑?空棧的判斷：TOP=BOTTOM； 入?；蜻M(jìn)棧(push)：棧的插入操作； 出?；蛲藯?pop)

3、：棧的刪除操作。練習(xí)假設(shè)有線性表（a b c d ），按順序輸入一個棧進(jìn)行處理。問能否得到下列幾種輸出序列注意：每個元素只能進(jìn)一次棧，也只能退一次棧。bcad; cadb;dcba;abcd;cdba;bdac;cbda;bacd;dbca;cdab;adcb;acbd;1、棧的存儲結(jié)構(gòu) 順序棧一維數(shù)組sMtop=0123450空棧棧頂棧頂top,指向?qū)嶋H棧指向?qū)嶋H棧頂頂后的空位置，初值后的空位置，初值為為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組長度為設(shè)數(shù)組長度為Mtop=0,?？眨藭r出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)to

4、ptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？沼糜肅語言實現(xiàn)棧的順序存儲表示如下：語言實現(xiàn)棧的順序存儲表示如下：typedef struct SElemType *base； SElemType *top; int stacksize; SqStack ; 3 2 1 0 a b c d進(jìn)棧99棧頂端basetop退棧生成一個空棧生成一個空棧 功能：在內(nèi)存構(gòu)成一個名字為功能：在內(nèi)存構(gòu)成一個名字為S的空棧。的空棧。Void InitStack(SqStack *s) S-base = (SElemType * ) malloc(STACK_INIT_S

5、IZE*sizeof(SElemType)；if (!S-base) exit(0); / 分配空間失敗S-top = S-base; / 棧頂指示器初值S-stacksize = STACK_ INIT_ SIZE; 注意：此時棧頂指示器與棧底指示器的值相等。即指示棧中同一位置。也就是M個連續(xù)空間的第一個空間的地址。進(jìn)棧運算進(jìn)棧運算 ( PUSH ) 對于一個非空棧，棧頂指示器對于一個非空棧，棧頂指示器top始終是在當(dāng)前棧頂數(shù)始終是在當(dāng)前棧頂數(shù)據(jù)元素位置加據(jù)元素位置加1的位置上。的位置上。 用用C語言編寫的算法如下：語言編寫的算法如下：Status Push (SqStack *S, SEl

6、emType e) if (S-top S-base = S-stacksize) /判預(yù)分空間是否用完 S-base =( SElemType*)realloc(S-base, (S-stacksize +STACKINCREMENT)*sizeof(SElemType); if (!S-base) exit ( ); / 空間分配失敗 S-top =S-base +S-stacksize; / 修改棧頂指示器 S-stacksize + =STACKINCREMENT; *(s-top +) = e; / 把數(shù)據(jù)進(jìn)棧后TOP再加1出棧運算(pop)把棧頂上的元素刪除（即最后進(jìn)棧的數(shù)據(jù)）。用

7、C語言編寫的算法如下： void popvoid pop(SqStack *S, SElemType *e) if if (S-top = S-base) return return; / 棧空*e = *(-S-top);/當(dāng)前棧頂指示器減1位置上的數(shù)據(jù)刪除 returnreturn; 0M-1棧1底棧1頂棧2底棧2頂補充：在一個程序中同時使用兩個棧鏈棧棧頂 .topdata link棧底 結(jié)點定義 入棧算法 出棧算法typedef struct node int data; struct node *next;NODE; .棧底toptopxptop .棧底topq思考題1、完成兩個棧的設(shè)

8、計以及進(jìn)、退棧的算法。2、編寫鏈?zhǔn)綏５倪M(jìn)、退棧算法。 3、設(shè)有abcd，按順序進(jìn)入一個棧，試寫出所有可能的輸出序列。4、設(shè)有abcde,經(jīng)過一個棧的處理得到輸出序列為cdbea 假設(shè)，用P代表一次進(jìn)棧操作，Q代表一次退棧操作。要求，寫出用PQ序列表示得到上述輸出結(jié)果的過程。 棧的應(yīng)用 過程的嵌套調(diào)用r主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3例例 遞歸的執(zhí)行情況分析遞歸的執(zhí)行情況分析 遞歸過程及其實現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身叫實現(xiàn)：建立遞歸工作棧void print(int w) int i; if ( w!=0) print(w-1); for(i=1

9、;i1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題執(zhí)行情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號表示n x y z 返回地址返回地址 Hanoi塔算法分析 An=2*An-1+1 An=2n-1 64塊金盤時答案： 設(shè)有一熟練工種的僧侶，每秒種移動一次金盤，則需要264-1秒鐘才可完成。18446744073709551615秒 5849億年 main() int m; printf(Input numbe

10、r of disks”); scanf(%d,&m); printf(”Steps : %3d disks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(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) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A

11、 C B 6 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(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) ABC3 A B C 02 A C B 61 C A B 8ABC3

12、A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(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

13、) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 0 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) mo

14、ve(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0棧空3 A B C 02 B A C 8 回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較 若不等，非回文 若直到棧空都相等，回文 多進(jìn)制輸出：字符串：“madam im adam”例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73to

15、p732 表達(dá)式求值 中綴表達(dá)式 后綴表達(dá)式（RPN) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+中綴表達(dá)式：操作數(shù)棧和運算符棧例 計算 2+4-3*6操作數(shù)運算符24+操作數(shù)運算符6-操作數(shù)運算符6-36*操作數(shù)運算符6-18操作數(shù)運算符12后綴表達(dá)式求值步驟：1、讀入表達(dá)式一個字符2、若是操作數(shù)，壓入棧，轉(zhuǎn)43、若是運算符，從棧中彈出2個數(shù)，將運算結(jié)果再壓入棧4、若表達(dá)式輸入完畢，棧頂即表達(dá)式值； 若表達(dá)式未輸入完，轉(zhuǎn)1top4top43top735top例 計算 4+3*5后綴表達(dá)式：435*+top415top19 3.2 隊列（Queu

16、e)隊列的定義及特點 定義：隊列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊尾(rear)允許插入的一端隊頭(front)允許刪除的一端 隊列特點：先進(jìn)先出(FIFO)a1 a2 a3.an 入隊出隊frontrear隊列Q=(a1,a2,an)鏈隊列 結(jié)點定義typedef struct node int data; struct node *next;JD;頭結(jié)點 .front隊頭隊尾rear設(shè)隊首、隊尾指針front和rear,front指向頭結(jié)點，rear指向隊尾frontrearx入隊xfrontreary入隊xyfrontrearx出隊xyfront rear空隊f

17、ront reary出隊入隊算法入隊算法JD *EnQueue(JD *rear,int x) JD *p; p=(JD *)malloc(sizeof(JD); p-data=x; p-next=NULL; rear-next=p; return(p); frontData Data 0 Data 0 prear出隊算法出隊算法int DeQueue(JD *front, JD *rear) JD *s; int x; if(front=rear) return(-1); s=front-next; front-next=s-next; if(s-next=NULL) rear=front;

18、 x=s-data; free(s); return(x);隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu) 實現(xiàn)：用一維數(shù)組實現(xiàn)sqMfront=0rear=0123450隊空隊空123450frontJ1,J2,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設(shè)兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素前一位置初值front=rear=0空隊列條件：front=rear入隊列：sq+rear=x;出隊列：x=sq+front;rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront 存在問題設(shè)數(shù)組維數(shù)為M，則： 當(dāng)front=0,rear=M-1時，再有元素入隊發(fā)生溢出真溢出 當(dāng)front0,rear=M-1時，再有元素入隊發(fā)生溢出假溢出 解決方案 隊首固定，每次出隊剩余元素向下移動浪費時間 循環(huán)隊列 基本思想：把隊列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0