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

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

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

3、)。又稱棧為后進(jìn)先出表(簡稱LIFO結(jié)構(gòu))。,,棧底,,棧頂,,入棧,,出棧,3.1.1 抽象數(shù)據(jù)類型棧的定義,ADT Stack { 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系：,抽象數(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 棧的表示和實(shí)現(xiàn),3.1.2 棧的表示和實(shí)現(xiàn),//----- 棧的順序存儲表示 ----- #define STACK_INIT_SIZE 100; //存儲空間初始分配量 #define STACKINCREMENT 10; //存儲空間分配增量 typedef struct { SElemType *base; //棧底指針 SElemType *to

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

8、itStack (SqStack &S){ // 構(gòu)造一個(gè)空棧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 棧的表示和實(shí)現(xiàn),棧初始化算法,3.1.2 棧的表示和實(shí)現(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 棧的表示和實(shí)現(xiàn),入棧操作演示,3.1.2 棧的表示和實(shí)現(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 棧的表示和實(shí)現(xiàn),鏈棧的C語言類型定義,鏈棧的實(shí)現(xiàn)與鏈

14、表的實(shí)現(xiàn)基本相同，頭結(jié)點(diǎn)作為棧頂位置。,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()) //遍歷棧,討論鏈棧基本操作的實(shí)現(xiàn),3.

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

17、：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2,輸出順序,,,計(jì)算順序,3.2.1 數(shù)制轉(zhuǎn)換,例,將10進(jìn)制1346轉(zhuǎn)換成8進(jìn)制,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進(jìn)制數(shù)N轉(zhuǎn)換成8進(jìn)制的算法,一個(gè)表達(dá)式中，包含三種括號“(”和“)”，“[”和“]”和“{”和“}”，這三種括號可以按任意的合法次序使用。 設(shè)計(jì)算法檢驗(yàn)表達(dá)式中所使用括號的合法性。,3.2.2 括號匹配的檢驗(yàn),問題描述,討論：如果第一次遇到的右括號是“]”，那么前面出現(xiàn)的左括號有什么特點(diǎn)。,問題討論,結(jié)論：如果第一次遇到的右括號是“]”，那么前面出現(xiàn)的左括號最后一個(gè)必然是“[”，否則不合法。,算法過

20、程,3.2.2 括號匹配的檢驗(yàn),當(dāng)遇到左括號時(shí)，進(jìn)棧，遇到右括號時(shí)出棧；(2) 當(dāng)遇到某一個(gè)右括號時(shí)，棧已空，說明到目前為止，右括號多于左括號；(3) 從棧中彈出的左括號與當(dāng)前檢驗(yàn)的右括號類型不同，說明出現(xiàn)了括號交叉情況；(4) 算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。,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;,括號匹配檢驗(yàn)算法,3.2.2 括號匹配的檢驗(yàn),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;},括號匹配檢驗(yàn)算法,3.2.2 括號匹配的檢驗(yàn)

24、,3.2.3 行編輯程序問題,設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符，“@”為退行符。,在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。,解決辦法,問題描述,假設(shè)從終端接受了這樣兩行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++);,則實(shí)際有效的是下列兩行： 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(); // 從終端接收下一個(gè)字符,ClearStack(S); // 重置S為空棧if (ch != EOF) ch = getchar();,棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；,3.2.3 行編輯程序問題,行編輯問題算法,入口,出口,3.2.4 迷宮求解,如圖表示一個(gè)迷宮，有一個(gè)入口，一個(gè)出口，從一個(gè)位置可以向4個(gè)方向(東、南、西、北)走，白

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

29、當(dāng)前路徑。,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,當(dāng)前位置：在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置。當(dāng)前位置可通：未承走到過的通道塊，該方塊既不在當(dāng)前路徑上，也不是曾經(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,,下一位置：當(dāng)前位置四周4個(gè)方向(東、南、西、北)上相鄰的方塊。,當(dāng)前位置,當(dāng)前路徑,3.2.4 迷宮求解,算法思想,(1)若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；(2)若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除了“來向”之外的其他方向繼續(xù)探索；(3)若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除

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

32、 則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；,若棧不空但棧頂位置的四周均不可通，則 { 刪去棧頂位置； 若棧不空，則重新測試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？?；},若?？?，則表明迷宮沒有通路。,迷宮路徑求解算法,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 表達(dá)式求值,一個(gè)表達(dá)式由操作數(shù)(operand)、運(yùn)算符(operator)、界限符(delimiter)組成。寫出“算符優(yōu)先法”求值的算法。,問題描述,例,求3*(2+3*5)+6的值,設(shè)置兩個(gè)棧，一個(gè)存操作數(shù)，棧名為OPND，一個(gè)存操作符，棧名為OPTR棧。 (1) 首先置操作數(shù)棧為空，表達(dá)式起始符#為運(yùn)算符棧的棧底元素； (2)依次讀入表達(dá)式中每個(gè)字符，若是操

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

35、個(gè)操作數(shù)與彈出運(yùn)算符計(jì)算后再存入OPND棧，繼續(xù)。,3.2.5 表達(dá)式求值,算法求解過程,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 表達(dá)式求值,表達(dá)式求值算法,case ‘<‘: Push(OPTR,c);c=getchar();break;case ‘=’: Pop(OPTR,x);c=getchar;break;,3.2.5 表達(dá)式求值,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é)束,表達(dá)式求值算法,3.1 棧 3

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

39、irst In First Out ，簡稱FIFO)。 又稱隊(duì)列為先進(jìn)先出表。,ADT Queue { 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系：,抽象數(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 端為隊(duì)列頭， an 端為隊(duì)列

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

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

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

43、Q.rear,帶頭結(jié)點(diǎn)的鏈隊(duì)列示意圖,3.4.2 鏈隊(duì)列,頭結(jié)點(diǎn),,,空隊(duì)列,,,……,,,Q.frontQ.rear,,,,Status InitQueue (LinkQueue &Q) { // 構(gòu)造一個(gè)空隊(duì)列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 鏈隊(duì)列,帶頭結(jié)點(diǎn)的鏈隊(duì)列初始化,Status EnQueue (LinkQueue &Q, QE

45、lemType e) { // 插入元素e為Q的新的隊(duì)尾元素 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 鏈隊(duì)列,帶頭結(jié)點(diǎn)的鏈隊(duì)列入隊(duì)算法,Status DeQueue (LinkQueue &Q, QElemType &e) { // 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， //用 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 鏈隊(duì)列,帶頭結(jié)點(diǎn)的鏈隊(duì)列出隊(duì)算法,DestroyQueue(&Q) //銷毀隊(duì)列QueueEmpty(Q) //判隊(duì)列是否空QueueLength(Q)

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

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

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

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

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

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

54、/ 構(gòu)造一個(gè)空隊(duì)列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)隊(duì)列,隊(duì)列初始化算法,Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素e為Q的新的隊(duì)尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //隊(duì)列滿 Q.base[Q.rear] = e; Q.re

56、ar = (Q.rear+1) % MAXQSIZE; return OK;},3.4.3 循環(huán)隊(duì)列,入隊(duì)列算法,Status DeQueue (SqQueue &Q, ElemType &e) { // 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， // 用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)隊(duì)列,出隊(duì)列算法,分析以下兩種狀態(tài)如何求隊(duì)列長度,3.4.3 循環(huán)隊(duì)列,,Sq.front,,,,Sq.rear,,,Sq.front,,,,Sq.rear,int QueueLength(SqQueue Q){ return (Q.rear-Q.front+MaxSize