【數(shù)據(jù)結構與算法】堆棧與隊列2

1、3.2 棧的應用舉例3.2.5 表達式求值,算符優(yōu)先法: 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作數(shù)(operand): 進OPND棧 操作符(operator): 進OPTR棧 界限符(delimiter):,算符間的優(yōu)先關系:,1 2+-*/()# + - * / ( # =,Precede: 判定運算符棧的棧頂運算符1與讀入的運算符2之間 的優(yōu)先關系的函數(shù). Operate: 進行二元運算ab的函數(shù).,算術表達式求值過程(算法3.4)OperandType EvaluateExpression(),InitStack(OPTR); Push

2、(OPTR, #); InitStack(OPND); c = getchar(); While(c!=# | GetTop(OPTR)!=#) If(!In(c,OP) Push(OPND,c); c = getchar(); / 不是運算符則進棧 else switch(Precede(GetTop(OPTR),c) case : / 退棧并將運算結果入棧 Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; default: printf(“Expression error!”); r

3、eturn(ERROR); / switch / while return GetTop(OPND); / EvaluateExpression,對算術表達式3*(7-2)求值.,步驟 OPTR棧 OPND棧 輸入字符 主要操作 1 # 3 * ( 7 - 2 ) # Push(OPND,3) 2 # 3 * ( 7 - 2 ) # Push(OPTR,*) 3 # * 3 ( 7 - 2 ) # Push(OPTR,() 4 # * ( 3 7 - 2 ) # Push(OPND,7) 5 # * ( 3 7 - 2 ) # Push(OPTR,-) 6 # * ( - 3 7 2 ) #

4、Push(OPND,2) 7 # * ( - 3 7 2 ) # Operate(7,-,2) 8 # * ( 3 5 ) # POP(OPTR) 9 # * 3 5 # Operate(3,*,5) 10 # 15 # Return(GetTop(OPND),例：漢諾塔問題： 將a柱子上的盤移到 c柱，用 b柱放臨時盤 要求：一次只能移動一個盤，大盤不可放于小盤上。,a,b,c,hanoi塔問題,定義函數(shù)：movetower(n,a,c,b) n個盤ac，b放臨時盤 分三步： movetower(n-1,a,b,c) 將n-1個盤從a-b， c放臨時盤 movedisk(a,n,c) 將第n

5、個盤從a-c movetower(n-1,b,c,a) 將n-1個盤從b-c,a放臨時盤 void hanoi(int n, char a, char b, char c) if (n=1) move(a,1,c); else hanoi(n-1,a,c,b); move(a,n,c); hanoi(n-1,b,a,c); ,hanoi塔的遞歸算法,3.4 隊列3.4.1抽象數(shù)據(jù)類型隊列的定義,隊列（Queue）: 先進先出(First In First Out) (縮寫為FIFO）的線性表。 僅在隊尾進行插入和隊頭進行刪除操作的線性表。 隊頭（front）: 線性表的表頭端，即可刪除端。 隊

6、尾（rear）: 線性表的表尾端，即可插入端。,隊頭,對尾,.,a1,a2,a3,an-1,an,隊列的抽象數(shù)據(jù)類型,ADT Queue 數(shù)據(jù)對象：D = ai | ai屬于Elemset, (i=1,2,n, n0) 數(shù)據(jù)關系：R1 = ai-1,ai|ai-1,ai屬于D,(i=2,3,n) 約定an為隊尾, a1為隊頭。 基本操作： InitQueue( QueueTraverse(Q ,visit () ADT Queue,隊列的基本操作(之一),InitQueue (否則返回FALSE。 QueueLength(Q) 初始條件: 隊列Q已經(jīng)存在。 操作結果: 返回隊列Q中的數(shù)據(jù)元素個

7、數(shù), 即隊列Q的長度。 GetHead(Q, struct QNode *next; Qnode, *QueuePtr; typedef struct QueuePtr front; / 隊頭指針 QueuePtr rear; / 隊尾指針 LinkQueue; #define OK 1 #define OVERFLOW -1 #define ERROR 0,data,*next,front,rear,鏈隊列示意圖,(a)空隊列,(b)元素“趙”入隊列,(c)元素“錢”入隊列,(d)元素“趙”出隊列,鏈隊列的操作實現(xiàn)舉例/* InitQueue 構造一個空的隊列Q*/,Status InitQ

8、ueue(LinkQueue / InitQueue,鏈隊列的操作實現(xiàn)(DestroyQueue) / 銷毀隊列Q,Status DestroyQueue(LinkQueue / DestroyQueue,鏈隊列的操作實現(xiàn)(EnQueue) / 插入元素e為新的隊尾元素,Status EnQueue(LinkQueue / EnQueue,鏈隊列的操作實現(xiàn)(DeQueue)/ 若隊列不空, 刪除隊列Q 的隊頭元素并用e返回其值, 同時返回OK; 否則返回ERROR 。,Status DeQueue(LinkQueue / DeQueue,3.4.3 循環(huán)隊列 - 隊列的順序表示與實現(xiàn),采用順序

9、存儲結構 約定:1)初始空隊列：front = rear=0 ; 2)插入新的元素時, rear+; 3)刪除隊頭元素時,front+;,循環(huán)列表-解決數(shù)組越界但未占滿空間的辦法,當Q.rear Q.front時: Q.rear Q.front = 隊列中元素個數(shù) 當Q.rear Q.front時: Q.rear Q.front +maxsize = 隊列中元素個數(shù) 當Q.rear = Q.front時: 隊列是空或滿,循環(huán)隊列的頭尾指針,循環(huán)隊列-隊列的順序存儲結構實現(xiàn)(1),typedef struct QElemType *base; / 存儲空間基地址 int front; / 隊頭指針 int rear; / 隊尾指針 SqQueue; #define MAXSIZE 100 Status InitQueue(SqQueue / InitQueue,循環(huán)隊列-隊列的順序存儲結構實現(xiàn)(2),Status EnQ