樹和二叉樹-《數(shù)據(jù)結(jié)構(gòu)》山東省級精品課程

1、3.1 棧 3.2 棧的應用舉例 3.3 隊列,第3章 棧和隊列,重點: (1)棧、隊列的定義、特點、性質(zhì)和應用；(2)ADT棧、ADT隊列的設計和實現(xiàn)以及基本操作及相關算法。 難點: (1)循環(huán)隊列中對邊界條件的處理；(2)分析棧和隊列在表達式求值、括號匹配、數(shù)制轉(zhuǎn)換、迷宮求解中的應用實例，提高利用棧和隊列解決實際問題的應用水平。,本章重點難點,3.1 棧 3.2 棧的應用舉例

2、 3.3 隊列,第3章 棧和隊列,3.1 棧,3.1.1 抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實現(xiàn),3.1.1 抽象數(shù)據(jù)類型棧的定義,棧的定義,棧(Stack)是一種特殊的線性表，其插入和刪除操作均在表的一端進行，是一種運算受限的線性表。,棧頂(top)是棧中允許插入和刪除的一端。棧底(bottom)是棧頂?shù)牧硪欢恕?棧的術語,棧的特點,棧的示意圖,后進先出(Last In First Out，簡稱LIFO

3、)。又稱棧為后進先出表(簡稱LIFO結(jié)構(gòu))。,,棧底,,棧頂,,入棧,,出棧,3.1.1 抽象數(shù)據(jù)類型棧的定義,ADT Stack { 數(shù)據(jù)對象： 數(shù)據(jù)關系：,抽象數(shù)據(jù)類型棧,基本操作：,} ADT Stack,R1＝{ | ai-1, ai∈D, i=2,...,n }約定an 端為棧頂，a1 端為棧底。,D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 },見下頁,3.1

4、.1 抽象數(shù)據(jù)類型棧的定義,InitStack(&S) //初始化棧,DestroyStack(&S) //銷毀棧,ClearStack(&S) //清空棧,StackEmpty(S) //判?？?StackLength(S) //求

5、棧長度,GetTop(S, &e) //取棧頂元素,Push(&S, e) //入棧,Pop(&S, &e) //出棧,StackTravers(S, visit()) //遍歷棧,棧的基本操作,3.1.1 抽象數(shù)據(jù)類型棧的定義,3.1 棧,3.1.1 抽象數(shù)據(jù)

6、類型棧的定義 3.1.2 棧的表示和實現(xiàn),3.1.2 棧的表示和實現(xiàn),//----- 棧的順序存儲表示 ----- #define STACK_INIT_SIZE 100; //存儲空間初始分配量 #define STACKINCREMENT 10; //存儲空間分配增量 typedef struct { SElemType *base; //棧底指針 SElemType *to

7、p; //棧頂指針 int stacksize; //當前可使用最大容量 } SqStack;,SqStack S;,順序棧的C語言實現(xiàn),3.1.2 棧的表示和實現(xiàn),棧初始化過程演示,(1) 給棧S申請?？臻g,(2) 設置基地址S.base和棧頂?shù)刂稴.top,S.top,S.base,,,(3) 設置棧容量S.stacksize=STACK_INIT_SIZE,Status In

8、itStack (SqStack &S){ // 構(gòu)造一個空棧S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType)); if (!S.base) ex

9、it (OVERFLOW); //存儲分配失敗 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;},3.1.2 棧的表示和實現(xiàn),棧初始化算法,3.1.2 棧的表示和實現(xiàn),入棧操作演示,(1) 如果棧滿，給棧增加容量,(2) 將數(shù)據(jù)存入棧頂位置，棧頂后移一位,S.top,S.base,,,e,S.top,,Status Push (SqStack

10、 &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (Ele

11、mType)); if (!S.base) exit (OVERFLOW); //存儲分配失敗 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK;},3.1.2 棧的表示和實現(xiàn),入棧操作演示,3.1.2 棧的表示和實現(xiàn),DestroyStack(&am

12、p;S) //銷毀棧,ClearStack(&S) //清空棧,StackEmpty(S) //判?？?StackLength(S) //求棧長度,GetTop(S, &e) //取棧頂元素,Pop(&S, &e)

13、 //出棧,StackTravers(S, visit()) //遍歷棧,其它棧操作討論,Typedef struct SNode { ElemType data; //數(shù)據(jù)域 struct Snode *next; //鏈域 }SNode, *LinkStack;,3.1.2 棧的表示和實現(xiàn),鏈棧的C語言類型定義,鏈棧的實現(xiàn)與鏈

14、表的實現(xiàn)基本相同，頭結(jié)點作為棧頂位置。,LinkStack *top; //棧頂指針,InitStack(&S) //初始化棧,DestroyStack(&S) //銷毀棧,ClearStack(&S) //清空棧,StackEmpty(S) //判?？?StackLe

15、ngth(S) //求棧長度,GetTop(S, &e) //取棧頂元素,Push(&S, e) //入棧,Pop(&S, &e) //出棧,StackTravers(S, visit()) //遍歷棧,討論鏈?；静僮鞯膶崿F(xiàn),3.

16、1.2 棧的表示和實現(xiàn),3.2 棧的應用舉例,3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗3.2.3 行編輯程序問題3.2.4 迷宮求解3.2.5 表達式求值,3.2.1 數(shù)制轉(zhuǎn)換,任何X進制數(shù)N轉(zhuǎn)換成Y進制數(shù)其結(jié)果都是要化成如下形式。,進制轉(zhuǎn)換原理：,轉(zhuǎn)換的過程就是通過取余運算求出a0,a1,…,an，而先求出的是個位，十位…，與我們寫數(shù)的習慣先從高位寫正好相反，通過棧先進后出的特點，很容易實現(xiàn)倒過來的過程。,過程如下

17、：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2,輸出順序,,,計算順序,3.2.1 數(shù)制轉(zhuǎn)換,例,將10進制1346轉(zhuǎn)換成8進制,void conversion () { Init

18、Stack(S); scanf ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); }} // conversion,3.2

19、.1 數(shù)制轉(zhuǎn)換,10進制數(shù)N轉(zhuǎn)換成8進制的算法,一個表達式中，包含三種括號“(”和“)”，“[”和“]”和“{”和“}”，這三種括號可以按任意的合法次序使用。 設計算法檢驗表達式中所使用括號的合法性。,3.2.2 括號匹配的檢驗,問題描述,討論：如果第一次遇到的右括號是“]”，那么前面出現(xiàn)的左括號有什么特點。,問題討論,結(jié)論：如果第一次遇到的右括號是“]”，那么前面出現(xiàn)的左括號最后一個必然是“[”，否則不合法。,算法過

20、程,3.2.2 括號匹配的檢驗,當遇到左括號時，進棧，遇到右括號時出棧；(2) 當遇到某一個右括號時，棧已空，說明到目前為止，右括號多于左括號；(3) 從棧中彈出的左括號與當前檢驗的右括號類型不同，說明出現(xiàn)了括號交叉情況；(4) 算術表達式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。,Status check( ) { char ch; InitStack(S); while ((c

21、h=getchar())!=‘#') { switch (ch) { case (ch=='('||ch=='['||ch=='{'):Push(S,ch);break; case (ch== ')'): if (StackEmpty(S)) retrun FALSE;

22、 else { Pop(S,e); if(e!= '(') return FALSE; } break;,括號匹配檢驗算法,3.2.2 括號匹配的檢驗,case (ch== ‘]'): if (StackEmpty(S)) retr

23、un FALSE; else { Pop(S,e); if(e!= ‘[') return FALSE; } break;………… default:break; }}if (StackEmpty(S)) return TRUE;else return FALSE;},括號匹配檢驗算法,3.2.2 括號匹配的檢驗

24、,3.2.3 行編輯程序問題,設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設“#”為退格符，“@”為退行符。,在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。,解決辦法,問題描述,假設從終端接受了這樣兩行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++);,則實際有效的是下列兩行： whil

25、e (*s) putchar(*s++);,例,3.2.3 行編輯程序問題,DestroyStack(S);},void LineEdit(){ //利用字符棧S，從終端接收一行并傳送至調(diào) //用過程的數(shù)據(jù)區(qū) InitStack(S); ch=getchar(); ………….,3.2.3 行編輯程序問題,行編輯問題算法,while (ch != EOF

26、) { //EOF為全文結(jié)束符,while (ch != EOF && ch != ‘\n’) {……},switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break;// 重置S為空棧 default : Push(S, ch); break;

27、 } ch = getchar(); // 從終端接收下一個字符,ClearStack(S); // 重置S為空棧if (ch != EOF) ch = getchar();,棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；,3.2.3 行編輯程序問題,行編輯問題算法,入口,出口,3.2.4 迷宮求解,如圖表示一個迷宮，有一個入口，一個出口，從一個位置可以向4個方向(東、南、西、北)走，白

28、方塊表示通道，藍方塊表示墻，求從入口到出口的路徑。,問題描述,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,,,3.2.4 迷宮求解,求解方法,“窮舉求解”方法：從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。,為了保證在任何位置上都能沿原路退回，需要一個后進先出的結(jié)構(gòu)來保存從入口到當前位置的路徑。因此，求解迷宮通路算法需要應用“?！眮肀４?/p>

29、當前路徑。,3.2.4 迷宮求解,四周墻壁解決辦法如圖,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,當前位置：在搜索過程中某一時刻所在圖中某個方塊位置。當前位置可通：未承走到過的通道塊，該方塊既不在當前路徑上，也不是曾經(jīng)納入過路徑的通道塊。,3.2.4 迷宮求解,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7

30、,8,9,,下一位置：當前位置四周4個方向(東、南、西、北)上相鄰的方塊。,當前位置,當前路徑,3.2.4 迷宮求解,算法思想,(1)若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當前位置”，如此重復直至到達出口；(2)若當前位置“不可通”，則應順著“來向”退回到“前一通道塊”，然后朝著除了“來向”之外的其他方向繼續(xù)探索；(3)若該通道塊的四周4個方塊均“不可通”，則應從“當前路徑”上刪除

31、該通道塊。,設定當前位置的初值為入口位置； do｛ 若當前位置可通， 則｛將當前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束； 否則切換當前位置的東鄰方塊為 新的當前位置；} 否則 {…………….}｝while (棧不空）；,迷宮路徑求解算法,3.2.4 迷宮求解,若棧不空且棧頂位置尚有其他方向未被探索，

32、 則設定新的當前位置為: 沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；,若棧不空但棧頂位置的四周均不可通，則 { 刪去棧頂位置； 若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？?；},若棧空，則表明迷宮沒有通路。,迷宮路徑求解算法,3.2.4 迷宮求解,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,,3.2.4

33、 迷宮求解,求解過程示例,,3.2.5 表達式求值,一個表達式由操作數(shù)(operand)、運算符(operator)、界限符(delimiter)組成。寫出“算符優(yōu)先法”求值的算法。,問題描述,例,求3*(2+3*5)+6的值,設置兩個棧，一個存操作數(shù)，棧名為OPND，一個存操作符，棧名為OPTR棧。 (1) 首先置操作數(shù)棧為空，表達式起始符#為運算符棧的棧底元素； (2)依次讀入表達式中每個字符，若是操

34、作數(shù)則進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應操作，直到整個表達式操作完畢。,3.2.5 表達式求值,算法求解過程,(1)若棧頂運算符小于輸入運算符，輸入運算符進棧OPTR； (2)若棧頂運算符等于輸入運算符（只有棧頂是“（”，輸入是“）”，或者棧頂是“#”，輸入是“#）”兩種情況，分別去除一對括號，或結(jié)束。 (3)若棧頂運算符大于輸入運算符，彈出棧頂運算符，從OPND中彈出兩

35、個操作數(shù)與彈出運算符計算后再存入OPND棧，繼續(xù)。,3.2.5 表達式求值,算法求解過程,OperandType EvaluateExpression(){ initStack(OPTR);Push(OPTR,’#’); initStack(OPND);c=getchar(); while(c!=‘#’)||GetTop(OPTR)!=‘#’){ if(!In(c,OP))

36、 {Push((OPND,c);c=getchar();} else switch(Precede(GetTop(OPTR),c)){,3.2.5 表達式求值,表達式求值算法,case ‘<‘: Push(OPTR,c);c=getchar();break;case ‘=’: Pop(OPTR,x);c=getchar;break;,3.2.5 表達式求值,case ‘

37、>’: Pop(OPTR,theta); Pop(OPND,a); Pop(OPND,b); Push(OPND,Operate(a,theta,b));break; } //switch語句結(jié)束} //while 語句結(jié)束 return(GetTop(OPND));} //算法結(jié)束,表達式求值算法,3.1 棧 3

38、.2 棧的應用舉例 3.3 隊列,第3章 棧和隊列,隊列的定義,3.4.1 抽象數(shù)據(jù)類型隊列的定義,隊列(Queue)——是一種運算受限的特殊的線性表，它只允許在表的一端進行插入，而在表的另一端進行刪除。,隊尾(rear)是隊列中允許插入的一端。 隊頭(front)是隊列中允許刪除的一端。,隊列的術語,隊列的特點,隊列示意圖,3.4.1 抽象數(shù)據(jù)類型隊列的定義,,隊頭,,隊尾,,出隊,,出隊,先進先出(F

39、irst In First Out ，簡稱FIFO)。 又稱隊列為先進先出表。,ADT Queue { 數(shù)據(jù)對象： 數(shù)據(jù)關系：,抽象數(shù)據(jù)類型棧,基本操作：,} ADT Queue,見下頁,3.1.1 抽象數(shù)據(jù)類型棧的定義,D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0},R1＝{ | ai-1, ai ∈D, i=2,...,n}約定其中a1 端為隊列頭， an 端為隊列

40、尾,InitQueue(&Q) //初始化隊列DestroyQueue(&Q) //銷毀隊列QueueEmpty(Q) //判隊列是否空QueueLength(Q) //求隊列長度GetHead(Q, &e) //取隊頭元素Cl

41、earQueue(&Q) //清空隊列EnQueue(&Q, e) //入隊列DeQueue(&Q, &e) //出隊列QueueTravers(Q, visit()) //遍歷隊列,隊列的基本操作,3.1.1 抽象數(shù)據(jù)類型棧的定義,3.4.2 鏈隊列,typedef struct QN

42、ode { // 結(jié)點類型 QElemType data; struct QNode *next; } QNode, *QueuePtr;,鏈隊列結(jié)點實現(xiàn),typedef struct { // 鏈隊列類型 QueuePtr front; // 隊頭指針 QueuePtr rear; // 隊尾指針} LinkQueue;,鏈隊列數(shù)據(jù)類型實現(xiàn),Q.front

43、Q.rear,帶頭結(jié)點的鏈隊列示意圖,3.4.2 鏈隊列,頭結(jié)點,,,空隊列,,,……,,,Q.frontQ.rear,,,,Status InitQueue (LinkQueue &Q) { // 構(gòu)造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeo

44、f(QNode)); if (!Q.front) exit (OVERFLOW); //存儲分配失敗 Q.front->next = NULL; return OK;},3.4.2 鏈隊列,帶頭結(jié)點的鏈隊列初始化,Status EnQueue (LinkQueue &Q, QE

45、lemType e) { // 插入元素e為Q的新的隊尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存儲分配失敗 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK;},3.4

46、.2 鏈隊列,帶頭結(jié)點的鏈隊列入隊算法,Status DeQueue (LinkQueue &Q, QElemType &e) { // 若隊列不空，則刪除Q的隊頭元素， //用 e 返回其值，并返回OK；否則返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.fro

47、nt->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK;},3.4.2 鏈隊列,帶頭結(jié)點的鏈隊列出隊算法,DestroyQueue(&Q) //銷毀隊列QueueEmpty(Q) //判隊列是否空QueueLength(Q)

48、 //求隊列長度GetHead(Q, &e) //取隊頭元素ClearQueue(&Q) //清空隊列QueueTravers(Q, visit()) //遍歷隊列,3.4.2 鏈隊列,帶頭結(jié)點的鏈隊列其它操作討論,3.4.3 循環(huán)隊列,循環(huán)隊列屬于順序隊列的一種，討論在采用一般順序隊列時出現(xiàn)的問題。,順

49、序隊列討論,空隊列,A入隊,B入隊,C,D,E相繼入隊,Sq.rear,Sq.front,Sq.rear,Sq.front,Sq.rear,Sq.front,Sq.rear,Sq.front,隊列滿,A被刪除(出隊),B被刪除,討論結(jié)論：在采用一般順序隊列時出現(xiàn)假上溢現(xiàn)象？,C,D,E相繼被刪除,順序隊列討論,3.4.3 循環(huán)隊列,Sq.rear,Sq.front,Sq.front,Sq.rear,Sq.rear,Sq.front,Sq

50、.front,Sq.rear,循環(huán)隊列示意圖,3.4.3 循環(huán)隊列,,Sq.front,,,,Sq.rear,3.4.3 循環(huán)隊列,#define MAXQSIZE 100 //最大隊列長度 typedef struct { QElemType *base; // 動態(tài)分配存儲空間 int front; // 頭指針，若隊列不空， // 指向隊列頭

51、元素 int rear; // 尾指針，若隊列不空，指向 隊列尾元素 的下一個位置 } SqQueue;,SqQueue Sq;,鏈隊列數(shù)據(jù)類型實現(xiàn),循環(huán)隊列是順序隊列的一種特例，它是把順序隊列構(gòu)造成一個首尾相連的循環(huán)表。指針和隊列元素之間關系不變。,3.4.3 循環(huán)隊列,循環(huán)隊列的定義,,,0,1,maxsize-1,,Sq.front,,,,Sq.r

52、ear,…,…,3.4.3 循環(huán)隊列,循環(huán)隊列空狀態(tài)和滿狀態(tài)的討論,討論結(jié)論：循環(huán)隊列空狀態(tài)和滿狀態(tài)都滿足Q.front=Q.rear,(1) 另設一個標志區(qū)別隊列是空還是滿；,3.4.3 循環(huán)隊列,循環(huán)隊列空狀態(tài)和滿狀態(tài)的判別,例如：設一個變量count用來記錄隊列中元素個數(shù)，當count==0時隊列為空，當count= MAXQSIZE時隊列為滿。,(2)隊滿條件：以隊頭指針在隊列尾指針的下一位置作為隊列呈滿狀態(tài)的標志，犧牲一個存

53、儲空間；,3.4.3 循環(huán)隊列,循環(huán)隊列空狀態(tài)和滿狀態(tài)的判別,隊滿條件為： (sq.rear+1) mod maxsize==sq.front 隊空條件為：sq.rear==sq.front,3.4.3 循環(huán)隊列,循環(huán)隊列空狀態(tài)和滿狀態(tài)的判別,隊列滿,Status InitQueue (SqQueue &Q) { /

54、/ 構(gòu)造一個空隊列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存儲分配失敗 Q.front = Q.rear = 0; return OK; }

55、,3.4.3 循環(huán)隊列,隊列初始化算法,Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素e為Q的新的隊尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //隊列滿 Q.base[Q.rear] = e; Q.re

56、ar = (Q.rear+1) % MAXQSIZE; return OK;},3.4.3 循環(huán)隊列,入隊列算法,Status DeQueue (SqQueue &Q, ElemType &e) { // 若隊列不空，則刪除Q的隊頭元素， // 用e返回其值，并返回OK; 否則返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.

57、base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK;},3.4.3 循環(huán)隊列,出隊列算法,分析以下兩種狀態(tài)如何求隊列長度,3.4.3 循環(huán)隊列,,Sq.front,,,,Sq.rear,,,Sq.front,,,,Sq.rear,int QueueLength(SqQueue Q){ return (Q.rear-Q.front+MaxSize