【數(shù)據(jù)結(jié)構(gòu)與算法】堆棧與隊(duì)列2

1、3.2 棧的應(yīng)用舉例3.2.5 表達(dá)式求值,算符優(yōu)先法: 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作數(shù)(operand): 進(jìn)OPND棧 操作符(operator): 進(jìn)OPTR棧 界限符(delimiter):,算符間的優(yōu)先關(guān)系:,1 2+-*/()# + - * / ( # =,Precede: 判定運(yùn)算符棧的棧頂運(yùn)算符1與讀入的運(yùn)算符2之間 的優(yōu)先關(guān)系的函數(shù). Operate: 進(jìn)行二元運(yùn)算ab的函數(shù).,算術(shù)表達(dá)式求值過程(算法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(); / 不是運(yùn)算符則進(jìn)棧 else switch(Precede(GetTop(OPTR),c) case : / 退棧并將運(yùn)算結(jié)果入棧 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,對(duì)算術(shù)表達(dá)式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柱放臨時(shí)盤 要求：一次只能移動(dòng)一個(gè)盤，大盤不可放于小盤上。,a,b,c,hanoi塔問題,定義函數(shù)：movetower(n,a,c,b) n個(gè)盤ac，b放臨時(shí)盤 分三步： movetower(n-1,a,b,c) 將n-1個(gè)盤從a-b， c放臨時(shí)盤 movedisk(a,n,c) 將第n

5、個(gè)盤從a-c movetower(n-1,b,c,a) 將n-1個(gè)盤從b-c,a放臨時(shí)盤 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 隊(duì)列3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義,隊(duì)列（Queue）: 先進(jìn)先出(First In First Out) (縮寫為FIFO）的線性表。 僅在隊(duì)尾進(jìn)行插入和隊(duì)頭進(jìn)行刪除操作的線性表。 隊(duì)頭（front）: 線性表的表頭端，即可刪除端。 隊(duì)

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

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

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

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