第三章棧和隊(duì)列公共郵箱

1、第三章 棧 和 隊(duì)列,3.1 棧 3.2 棧的應(yīng)用舉例 **3.3 棧與遞歸的實(shí)現(xiàn) 3.4 隊(duì)列 **3.5 離散事件模擬,,從數(shù)據(jù)結(jié)構(gòu)的角度看: 棧、隊(duì)列和線性表相同從數(shù)據(jù)類型的角度看: 棧、隊(duì)列和線性表不同 ListInsert(L, i,

2、e) (1≤i≤n+1) ListInsert(S, n+1, e) ListDelete(L, i，e)(1≤i≤n) ListDelete(S, n),,,,,棧底,,棧頂,,只允許在一端插入和刪除操作的線性表.允許插入和刪除的一端 稱為棧頂 (top)，另一端 稱為棧底(base)特點(diǎn): 后進(jìn)先出 (LIFO),3.1 棧 ( Stack ),退棧,進(jìn)棧,,,a1,,an,,,an-1,,?,top

3、,base,,,,,ADT Stack {數(shù)據(jù)對象：D＝{ ai |ai∈ElemSet,i=1,2,...,n, n≥0 }數(shù)據(jù)關(guān)系：R1＝{|ai-1,ai∈D, i=2,...,n } 約定an 端為棧頂，a1 端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。ClearS

4、tack(&S)初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件:棧S已存在.操作結(jié)果:若棧S為空棧,返回TRUE,否則FALE.,,StackLength(S)初始條件:棧S已存在.操作結(jié)果:返回S的元素個(gè)數(shù),即棧的長度。GetTop(S, &e)初始條件:棧S已存在且非空。操作結(jié)果:用e返回S的棧頂元素。Push(&S, e)初始條件：棧S已存在. 操作結(jié)

5、果:插入元素e為新的棧頂元素。Pop(&S, &e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。StackTraverse( S, visit() )初始條件：棧S已存在且非空。操作結(jié)果：從棧底到棧頂依次對S的每個(gè)數(shù)據(jù)元素調(diào)用visit()， 一旦visit()失敗，即操作失敗。}ADT Stack,進(jìn)棧,出棧,,,,二、 棧的表示和實(shí)現(xiàn),順序棧:是利用一

6、組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。 //----- 棧的順序存儲表示 -----#define STACK_INIT_SIZE 100;//存儲空間初始分配量#define STACKINCREMENT 10;//存儲空間分配增量typedef struct {SElemType *base; //棧底指針SElemType *top; //棧頂指針int

7、stacksize; //當(dāng)前已分配的存儲空間,以元素為單位} SqStack;,空棧:S.base==S.top (初始化狀態(tài)),a,b,c,d,e,棧滿:S.top-S.base>=S.stacksize,若棧結(jié)構(gòu)不存在，base為NULL,,棧頂指針始終是指在棧頂元素的后面一個(gè)位置,順序棧的初始化操作Status InitStack(SqStack &S) { // 構(gòu)造一個(gè)空棧S S.base = (

8、SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if (!S. base) exit(OVERFLOW); // 存儲分配失敗 S.top = S.base ; S.stacksize = STACK_INIT_SIZE ; // 初始存儲容量 return OK;} // InitStack,獲取

9、棧頂元素操作,Status GetTop(SqStack S, SElemType &e) { //若棧不空,用e返回S的棧頂元素,并返回OK;否則返回ERROR if (S.top == S.base) return ERROR; e=*(S.top-1); return OK;} //GetTop,進(jìn)棧操作,Status Push(SqStack &S, SElemType e) { //插入e作為新的棧

10、頂元素 if(S.top-S.base>=S.stacksize){//棧滿,追加存儲空間 S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if (!S.base) exit(OVERFLOW); // 存儲分配失敗 S.top =S.base+S.stacksize; S.stack

11、size +=STACKINCREMENT; } *S.top = e; S.top++ ; return OK;} //Push,出棧操作,Status Pop(SqStack &S, SElemType &e) { //若棧不空,則刪除S的棧頂元素,用e返回其值,并返回OK;否則 //返回ERROR if (S.top == S.base) return ERROR; e=*- -S.

12、top; return OK;} //Pop,- - S.top;,e=*(S.top-1);,,棧的鏈接存儲表示 — 鏈棧,插入與刪除僅在棧頂處執(zhí)行,非常簡單,不作討論。,鏈棧: 利用鏈表實(shí)現(xiàn)棧注意鏈表中指針的方向是從棧頂?shù)綏５住?3.2 棧的應(yīng)用舉例,問題有后進(jìn)先出的特點(diǎn)例一 數(shù)制轉(zhuǎn)換例二 括號匹配的檢驗(yàn)例三 行編輯程序問題例四 迷宮求解例五 表達(dá)式求值例六 實(shí)現(xiàn)遞歸（3.3）,例一 數(shù)制轉(zhuǎn)換十進(jìn)制

13、數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題,其解決方法很多,其中一個(gè)簡單算法基于下列原理： N = (N div d)×d + N mod d (其中:div為整除運(yùn)算，mod為求余運(yùn)算）例如：（1348)10 = (2504)8 ，其運(yùn)算過程如下： N N div 8 N mod 8 1348 168

14、 4 168 21 0 21 2 5 2 0 2,輸出順序,,void conversion( ){//對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù),打印輸出與其等值的八進(jìn)制數(shù) InitStack(S); // 構(gòu)造空棧 scanf(&

15、quot;%d",N); while(N) { Push(S, N % 8); N = N/8; } while(!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); }} //conversion,例二 括號匹配的檢驗(yàn),假設(shè)表達(dá)式中允許包含兩種括號:即（［］（））或［（［ ］［ ］）］等為正確的格式［（ ］）或 (( )]

16、)或（［（ ））均為不正確的格式。檢驗(yàn)括號是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。例如考慮下列括號序列：[ ( [ ] [ ] ) ]1 2 3 4 5 6 7 8分析可能出現(xiàn)的不匹配的情況: 到來的右括弧非是所“期待”的; 到來的是“不速之客”; 直到結(jié)束，也沒有到來所“期待”的。,算法設(shè)計(jì)思想：1)凡出現(xiàn)左括號，則進(jìn)棧；2)凡出現(xiàn)右括號，首先檢查棧是否空 若?？眨瑒t表明右括號多了； 否則和

17、棧頂元素比較,若匹配,則左括號出棧； 否則不匹配；3)表達(dá)式檢驗(yàn)結(jié)束時(shí) 若?？眨瑒t匹配正確； 否則表明左括號多了，不匹配；,status matching(SqList exp) {//順序表exp中存有數(shù)據(jù)元素為字符的表達(dá)式,檢驗(yàn)表達(dá)式中所含括弧是否正確嵌套,若是,則返回OK,否則返回ERRORstate= 1; i =0; InitStack(S);whil

18、e (i< exp.length && state) { switch （exp.elem[i]）{ case ‘(’ : { Push(S,exp.elem[i]); i++; break; } case ‘[’ : { Push(S,exp.elem[i]); i++; break; } case ‘)’:{ if(!StackEmpty(S)&&GetTop(S)=‘(’

19、) { Pop(S,e); i++; } else state=0; break;} case ‘]’:{ if(!StackEmpty(S)&&GetTop(S)=‘[’) {Pop(S,e); i++; } else state=0; break;} } }if(state&&am

20、p;StackEmpty(S)) return OK；else return ERROR;}//matching,作業(yè),1、從鍵盤輸入一個(gè)整數(shù)序列：a1,a2,a3…，an,編寫算法PushPops實(shí)現(xiàn);用棧存儲輸入的整數(shù)序列,當(dāng)ai≠-1時(shí),將ai進(jìn)棧;當(dāng)ai=-1時(shí),輸出棧頂元素并出棧.算法應(yīng)對異常情況(棧滿,?？?等給出相應(yīng)信息。,void PushPops (SqStack &S){//根據(jù)輸入序列的值,進(jìn)行入棧和出

21、棧操作 for(i=1; i=S.stacksize ) { printf(“棧滿”); exit(0);} else Push(S,a); else if(S.top= =S.base) { printf(“?？铡?; exit(0);} else { Pop(S,e); printf(“%d”,e);} }},1、從鍵盤輸入一個(gè)整

22、數(shù)序列：a1,a2,a3…，an,編寫算法PushPops實(shí)現(xiàn);用棧存儲輸入的整數(shù)序列,當(dāng)ai≠-1時(shí),將ai進(jìn)棧;當(dāng)ai=-1時(shí),輸出棧頂元素并出棧.算法應(yīng)對異常情況(棧滿,?？?等給出相應(yīng)信息。,例三 行編輯程序問題,一個(gè)簡單的行編輯程序的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)?！懊拷邮找粋€(gè)字符即存入用戶數(shù)據(jù)區(qū)”{不恰當(dāng)。}較好的做法是：設(shè)立一個(gè)輸入緩沖區(qū)，用以接收用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)

23、。允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。,退格符： #退行符：@例如，假設(shè)從終端接受了這樣兩行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行： while (*s) putchar(*s++);,保留已經(jīng)輸入的字符的緩沖區(qū)結(jié)構(gòu)應(yīng)該是一個(gè)棧,void LineEdit( ) {// 利用字符棧S,從終端接收一行并傳送至調(diào)用過

24、程的數(shù)據(jù)區(qū)。InitStack(S); ch = getchar(); //從終端接收第一個(gè)字符while (ch != EOF) { //EOF為全文結(jié)束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' :Pop(S, c); break; // 僅當(dāng)棧非空時(shí)退棧 case

25、 '@':ClearStack(S); break; // 重置S為空棧 default :Push(S, ch);break;//有效字符進(jìn)棧 } ch = getchar(); // 從終端接收下一個(gè)字符 } 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)； ClearStack(S); // 重置S為空棧 if (ch != EOF) ch = getchar(); }

26、DestroyStack(S);}// LineEdit,例五 表達(dá)式求值,限于二元運(yùn)算符的表達(dá)式定義:表達(dá)式 : (操作數(shù))+(運(yùn)算符)+(操作數(shù))操作數(shù) : 簡單變量 | 表達(dá)式簡單變量 : 標(biāo)識符 | 無符號整數(shù),設(shè) Exp = S1 + OP + S2在計(jì)算機(jī)中,表達(dá)式可以有三種不同的表示方法 稱 OP + S1 + S2 為表達(dá)式的前綴表示法 稱 S1 + OP + S2 為表達(dá)式的中綴表示法 稱

27、 S1 + S2 + OP 為表達(dá)式的后綴表示法 可見，它以運(yùn)算符所在不同位置命名的。,例如： Exp= a × b +(c-d/e) ×f前綴式： + a× b (c-d/e) ×f + ×a b ×(c-d/e) f + ×a b ×- c d/e f

28、 + ×a b ×-c /d e f中綴式： a × b + c-d/e ×f后綴式： a × b (c-d/e) ×f+ a b ×(c-d/e) f×+ a b × cd/e- f×+

29、a b × cde/- f×+,,,,,,,,,,,,寫出23 +((12*3-2)/4 +34*5/7)+108/9的后綴表達(dá)式：23 12 3*2-4/34 5*7/++108 9/+,結(jié)論 1)操作數(shù)之間的相對次序不變; 2)運(yùn)算符的相對次序不同; 3)中綴式丟失了括弧信息，致使運(yùn)算的次序不確定; 4)前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們 之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)

30、式; 5)后綴式的運(yùn)算規(guī)則為: 運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序; 每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式; 如何從后綴式求值？先找運(yùn)算符，后找操作數(shù),后綴式計(jì)算機(jī)處理起來比較方便，所以很多編譯程序，每碰到一個(gè)表達(dá)式先求出后綴形式，然后再求值。,,如何從原表達(dá)式求得后綴式？ 分析 “原表達(dá)式” 和 “后綴式”中的運(yùn)算符每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定,在后綴式中優(yōu)先級高的運(yùn)算符

31、領(lǐng)先于優(yōu)先級低的運(yùn)算符，若當(dāng)前運(yùn)算符的優(yōu)先數(shù)小,則暫不進(jìn)行;否則立即進(jìn)行。,從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立運(yùn)算符棧; 2)設(shè)表達(dá)式的結(jié)束符為“#”,設(shè)運(yùn)算符棧的棧底為“#” 3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式; 4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧; 5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式; 6)“(”對它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。,void transf

32、orm(char suffix[], char exp[] ) {// 從合法的表達(dá)式字符串exp求得其相應(yīng)的后綴式InitStack(S); Push(S, ‘#’); p = exp; ch = *p;while (!StackEmpty(S)) {if (!IN(ch, OP)) Pass( Suffix, ch); // 直接發(fā)送給后綴式else{switch (ch) { case ‘(‘ : Push

33、(S, ch); break; case ‘)’ :{ Pop(S,c); while(c!=‘(’){ Pass(Suffix,c);Pop(S,c)} break;} defult:{ while(!Gettop(S,c)&&(precede(c,ch))) { Pass( Suffix, c);Pop(S, c); }

34、 if(ch!=‘#’) Push(S,ch); break;} } // switch } // else if ( ch!= ‘#’ ) { p++; ch = *p; }} // while} // CrtExptree,OperandType EvaluateExpression() {//算術(shù)表達(dá)式求值的算符優(yōu)先算法.設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧,OP為運(yùn)算符集合Ini

35、tStack(OPTR); Push (OPTR,'#');IinitStack(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) {

36、 case '’# //退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b));break; } // switch} // whilereturn GetTop(OPND);} // EvaluateExpression,3.3 實(shí)現(xiàn)遞

37、歸,遞歸( recursion)做為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用.是指函數(shù)在運(yùn)行過程序中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)像.用遞歸思想寫出的程序往往十分簡潔易懂。 設(shè)a是含n個(gè)分量的整數(shù)數(shù)組,寫出求n個(gè)整數(shù)之和 f(n)的遞歸定義：,void hanoi (int n, char x, char y, char z) {//漢諾塔問題：將塔座x上按直徑由小到大且至上而下編號//為1至n的n個(gè)圓盤按規(guī)則搬到塔座z上,

38、y可用作輔助塔座 if(n==1) move(x,1,z);//將編號為１的圓盤從x移到z else{ hanoi(n-1,x,z,y);//將x上編號為１至n-1的圓盤 移到y(tǒng),z作輔助塔 move(x,n,z); hanoi(n-1,y,x,z); } },3,2,1,hanoi (3,a,b,c),1,2,1,3,1,2,1,3.4 隊(duì)列 ( Queu

39、e ),定義隊(duì)列是只允許在一端插入,在另一端刪除的順序表。允許插入的一端叫做隊(duì)尾(rear) ,允許刪除的一端叫做隊(duì)頭(front)。特性先進(jìn)先出(FIFO, First In First Out),抽象數(shù)據(jù)類型隊(duì)列的定義ADT Queue {數(shù)據(jù)對象：D＝{ai | ai∈ElemSet,i=1,2,...,n, n≥0}數(shù)據(jù)關(guān)系:R1＝{ |ai-1, ai∈D, i=2,...,n} 約定其中a

40、1 端為隊(duì)列頭，an 端為隊(duì)列尾。基本操作：InitQueue(&Q)操作結(jié)果:構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q)初始條件:隊(duì)列Q已存在.操作結(jié)果:隊(duì)列Q被銷毀,不再存在,ClearQueue(&Q)初始條件:隊(duì)列Q已存在.操作結(jié)果:將Q清為空隊(duì)列。QueueEmpty(Q)初始條件:隊(duì)列Q已存在。操作結(jié)果:若Q為空隊(duì)列,則返回TRUE,否則返回FALSE。QueueLeng

41、th(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。QueueTraverse( Q, visit() )初始條件：棧S已存在且非空。操作結(jié)果：從棧底到棧頂依次對S的每個(gè)數(shù)據(jù)元素調(diào)用visit()，一旦visit()失敗，即操作失敗。,GetHead(Q, &e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。EnQueue(&Q, e)初始條件:隊(duì)列Q已存在.操作結(jié)果

42、:插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q, &e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。} ADT Queue,取隊(duì)頭元素,GetTop (S,&e),出隊(duì)列操作,入隊(duì)列操作,Push (&S, e),Pop (&S, &e),隊(duì)列的表示和實(shí)現(xiàn) 鏈隊(duì)列 順序隊(duì)列,3.4.2 鏈

43、隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)ADT鏈隊(duì)列——鏈?zhǔn)接诚?typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; // 隊(duì)頭指針 QueuePtr rear; // 隊(duì)尾指針 } LinkQueue;,,,,,,,…,^

44、,,,Q.rear,Q.front,^,,Q.front,Q.front,,//----- 基本操作的函數(shù)原型說明 -----Status InitQueue (LinkQueue &Q) // 構(gòu)造一個(gè)空隊(duì)列QStatus DestroyQueue (LinkQueue &Q) // 銷毀隊(duì)列Q，Q不再存在Status ClearQueue (LinkQueue &Q) // 將Q清為空隊(duì)列

45、Status QueueEmpty (LinkQueue Q) // 若隊(duì)列Q為空隊(duì)列，則返回TRUE，否則返回FALSE,int QueueLength (LinkQueue Q) // 返回Q的元素個(gè)數(shù)，即為隊(duì)列的長度Status GetHead (LinkQueue Q, QElemType &e) // 若隊(duì)列不空，則用e返回Q的隊(duì)頭元素，并返回OK；// 否則返回ERRORStatus EnQueue

46、 (LinkQueue &Q, QElemType e) // 插入元素e為Q的新的隊(duì)尾元素Status DeQueue (LinkQueue &Q, QElemType &e) // 若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，// 并返回OK；否則返回ERROR,Status InitQueue(LinkQueue &Q) { // 構(gòu)造一個(gè)空隊(duì)列Q

47、 (QueuePtr)malloc(sizeof(Qnode)); if (!Q.front) exit(OVERFLOW); // 存儲分配失敗 Q.front->next =NULL; return OK;},^,Q.front=Q.rear=,Status EnQueue (LinkQueue &Q, QElemType e)

48、 // 插入元素e為Q的新的隊(duì)尾元素 p=(QueuePtr)malloc(sizeof(Qnode));//生成新的結(jié)點(diǎn) if (!p ) exit(OVERFLOW); // 存儲分配失敗 p->data = e; p->next= NULL; Q.rear->next = p; // 插入隊(duì)尾 Q.rear = p; // 修改隊(duì)尾指針 return OK;},,

49、,,,…,^,,,Q.rear,Q.front,^,e,,Status DeQueue(LinkQueue &Q, QElemType& e) { // 若隊(duì)列不空，則刪除Q的隊(duì)頭元素,以 e 帶回其值， //并返回OK，否則返回 ERROR if (Q.front == Q.rear) return ERROR ; // 空隊(duì)列 p = Q.front->next; e = p

50、->data; Q.front->next = p->next; // 刪除隊(duì)頭元素 if (Q.rear== p) Q.rear = Q.front; free(p); return OK; // 釋放被刪結(jié)點(diǎn)},,,,,,,…,^,,,Q.rear,Q.front,,^,,,Q.rear,Q.front,^,作業(yè),1、試編寫一個(gè)算法OpinionStr

51、ing:識別依次讀入的一個(gè)以@為結(jié)束符的字符序列str是否為形如‘序列1&序列2’模式的對稱字符序列.其中序列1和序列2中都不含字符’&‘,且序列2是序列1的逆序列.(比如:‘a(chǎn)+b+c&c+b+a’是對稱字符序列,而‘1+3&3-1’不是)算法思想：使用棧存放序列1。2、判別讀入的以’@’為結(jié)束符的字符序列是否為”回文”，正讀和反讀都相同的字符序列稱為”回文”。例如:abcdcba 或 aba

52、 是回文,abcde不是回文。算法思想：將依次讀入的字符分別插入棧和隊(duì)列，然后依次比較“棧頂”和“隊(duì)頭”的字符。,試編寫一個(gè)算法OpinionString:識別依次讀入的一個(gè)以@為結(jié)束符的字符序列str是否為形如‘序列1&序列2 ’模式的對稱字符序列.其中序列1和序列2中都不含字符’&‘,且序列2是序列1的逆序列.,比如:‘a(chǎn)+b+c&c+b+a’是對稱字符序列,‘1+3&3-1’則不是,分析：判斷題目

53、中給出的字符序列是否為對稱的，只要將字符序列的前半部分放入棧中，然后當(dāng)棧非空時(shí)，依次取棧頂元素與后半部的字符進(jìn)行比較，若棧不空而且棧頂元素與比較的不同，則該字符序列不是對稱序列，若?？眨瑒t是對稱序列，算法描述如下：,作業(yè)1,Status OpinionString(SqStack &S, char *str){//判斷給定的字符序列是否是對稱序列，字符序列由str給出 InitStack(S); p=str; wh

54、ile( *p!=’&’ && *p!=’@’) { Push(S,*p); p++;} if(*p==’@’) return ERROR; if(*p==’&’) p++; while( !StackEmpty(S) ) { Pop(S,c); if(c!=*p) return ERROR; p++; }if (StackEmpty(S) &

55、& *p==’@’ ) return OK;else return ERROR;},判別讀入的以’@’為結(jié)束符的字符序列是否為“回文”，正讀和反讀都相同的字符序列稱為“回文”。,例如:abcdcba 或 aba 是回文,abcde不是回文。,由于回文的字符序列中的分界線不明確，因此無法判定字符序列的“中間位置”, 即只能按照回文的定義從字符的兩頭出發(fā)進(jìn)行判別。,作業(yè)2,算法的基本思想是:,將依次讀入的字符分別插入棧和隊(duì)列，然

56、后依次比較“棧頂”和“隊(duì)頭”的字符。,然而，按照題目的要求，這個(gè)字符序列是從外部環(huán)境輸入的。為了在輸入結(jié)束的時(shí)候，同時(shí)能得到序列的“頭”和“尾”，因此算法中，除了需要用一個(gè)棧之外，還需要一個(gè)隊(duì)列。,Status Opinion_palindrome ( ) {// 從終端輸入的字符序列是”回文”,返回TRUE,否則返回FALSE InitStack(S); InitQueue(Q); ch=getchar( ); w

57、hile(ch!=?@?) { Push(S, ch); EnQueue(Q, ch); ch=getchar( ); } state=TRUE; while(!StackEmpty(S) && state) { if (GetTop(S)= =GetHead(Q) ) { Pop(S,c); DeQueue(Q,e); } else state=FA

58、LSE; } return state;},判斷abcba是否是回文,a,b,c,b,a,a,b,a,b,c,鏈隊(duì)列——鏈?zhǔn)接诚?typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; // 隊(duì)頭指針 Q

59、ueuePtr rear; // 隊(duì)尾指針 } LinkQueue;,,,,,,,…,^,,,Q.rear,Q.front,3.4.3 循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)#define MAXQSIZE 10 //最大隊(duì)列長度typedef struct {QElemType *base; // 初始化的動態(tài)分配存儲空間int front; // 頭指針，若隊(duì)列不空，指向隊(duì)列頭元素int rear;//尾指針,若隊(duì)列不空,指

60、向隊(duì)列尾元素的下一個(gè)位置} SqQueue;,普通的順序存儲隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)； 解決辦法之一：將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)(環(huán)形)隊(duì)列。,,,,,,,0,1,2,3,4,5,6,7,,Q.front:0,Q.rear:0,,空隊(duì)列,,Q.base,隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則,進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)一 rear = rear + 1， 再將新元素按 rear 指示位置加入。 出隊(duì)時(shí)隊(duì)頭指針先進(jìn)一 front = fr

61、ont + 1， 再將下標(biāo)為 front 的元素取出。,隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從MAXQSIZE -1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1: Q.front = (Q.front+1) % MAXQSIZE;隊(duì)尾指針進(jìn)1: Q.rear = (Q.rear+1) % MAXQSIZE;隊(duì)列初始化：Q.front = Q.rear = 0;隊(duì)空條件：Q.front

62、== Q.rear;隊(duì)滿條件：(Q.rear+1) % MAXQSIZE == Q.front,循環(huán)隊(duì)列 (Circular Queue),P64,,,,,0,1,2,3,4,5,6,7,,front,,,,,0,1,2,3,6,7,,front,,,,,A,A,B,C,rear,,rear,,A進(jìn)隊(duì),B, C進(jìn)隊(duì),,,,,,,0,1,2,3,4,5,6,7,,,,,0,1,2,3,4,5,6,7,,,A退隊(duì),B退隊(duì),,,,,,,0,

63、1,2,3,4,5,6,7,D,E,F,G,H,I進(jìn)隊(duì),,front,B,C,rear,,A,front,B,C,rear,,,front,C,rear,,,D,E,F,G,H,I,,,,,,,0,1,2,3,4,5,6,7,,front,rear,,空隊(duì)列,練習(xí)：假設(shè)循環(huán)隊(duì)列定義為：以域變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的下一個(gè)位置和內(nèi)含元素的個(gè)數(shù)。給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法。隊(duì)滿條

64、件 Q.length== MAXQSIZE;1）入隊(duì)列操作Status EnQueue(SqQueue &Q,ElemType e){ //若隊(duì)列Q不滿，則將元素e插入到該隊(duì)列 if(Q.length==MAXQSIZE) exit(0); //隊(duì)滿 Q.base[Q.rear] = e; Q.rear=( Q.rear+1)% MAXQSIZE; Q.length++;} // EnQueue,2）出

65、隊(duì)列操作Status DeQueue(SqQueue &Q,ElemType &e){ //若隊(duì)列Q不空，則讓隊(duì)頭元素出隊(duì)列，其值由e輸出 if(Q.length==0) exit(0);//空隊(duì)列 e=Q.base[(Q.rear-Q.length+MAXQSIZE)%MAXQSIZE]; Q.length--; return e;} // DeQueue,將隊(duì)列Q中元素逆置。（使用順序棧進(jìn)行過

66、渡，要求使用基本操作實(shí)現(xiàn)）Status ReverseQueue(SqQueue &Q ){ //將非空隊(duì)列Q中的元素逆置，元素的過度使用一個(gè)順序棧S InitStack(S); //初始化棧Swhile(!QueueEmpty(Q)) //隊(duì)列Q非空，將隊(duì)列中的元素入棧{ DeQueue(Q,c); Push(S,c);}while(!StackEmpty(S)) //棧S非空，將棧中的元素入隊(duì)列{ Pop (

67、S,c); EnQueue(Q,c); }} // ReverseQueue,練習(xí),1、設(shè)棧的輸入序列是1，2，3，4，5，則（ ）不可能是其出棧序列。 A. 54321 B. 45321 C. 43512 D. 123452、若已知一個(gè)棧的入棧序列是1，2，3，…,n,其輸出序列為p1,p2,p3,…,pn，若p1=n,則pi為（ ）。 A. i

68、 B.n=i C.n-i+1 D.不確定,C,C,4、一個(gè)遞歸算法必須包括（ ）A.遞歸部分 B.終止條件和遞歸部分 C.迭代部分 D.終止條件和迭代部分5、用鏈表方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ ）A.僅修改頭指針 B. 僅修改尾指針 C.頭、尾指針都要修改

69、 D. 尾指針可能都要修改,B,D,6、假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針分別front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ） A. (rear-front+m)%m B. rear-front+1 C. (front-rear+m)%m D. (rear-front)%m 7、棧和隊(duì)列的共同點(diǎn)是( ) A.都是先進(jìn)先出

70、 B. 都是先進(jìn)后出 C.允許在端點(diǎn)處插入和刪除元素 D.無共同點(diǎn),A,C,8、表達(dá)式3*2^(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時(shí),操作數(shù)棧和運(yùn)算符棧分別為（ ） 【這種題目一定要會做！】 A. 3,2,4,1,1; #*^(+*- B. 3,2,8; #*^- C. 3,2,4,2,2; #