【正文】 值，叫做隊尾指針；用另一個變量 f 指示隊頭的下標值，稱為隊頭指針。 R= R * s[top]。 例：階乘 Int fact(int n) { if (n==0) return(1)。 ?假設(shè)下列形式都是合法的： （）， [ ]，（ [ ]），（ [ ] [ ]），（ [（） ]）； 而下列是不合法的： （ ]， [），（ [ ] ]， …… 棧與遞歸 ?遞歸：自己調(diào)用自己，分直接遞歸和間接遞歸 ?例：階乘 n!=1 當 n=0時 n!=n*(n1)! 當 n0時 定義遞歸時要做到： 1. 調(diào)用必須越來越簡單，并且能在有限步內(nèi)結(jié)束。 ? 由于逆波蘭表示法以上特點，其處理很方便。 p=headnext。 Struct node *next。寫出以數(shù)組高端為底的棧的入棧和出棧的算法。 []=x。 ?一般需用一個變量 top記錄當前棧頂?shù)南聵酥?，top也叫做棧指針。數(shù)據(jù)結(jié)構(gòu) 第 三 章 棧 對列 串 ?要 求 熟練掌握以下內(nèi)容： 堆棧的特征 、 基本運算并能設(shè)計簡單算法 隊列 、 循環(huán)隊列的特征 、 基本運算并能設(shè)計簡單算法 串的定義和應(yīng)用 了解以下內(nèi)容： 線性表運算時間復(fù)雜性分析 堆棧 、 隊列實際應(yīng)用 堆棧 (Stack) ?堆棧也簡稱為棧，是限定在表的一端進行插入或刪除操作的線性表。 ?本例中 top=4 top A D C B 4 7 5 3 2 1 6 STACK 棧的基本運算 ?進棧 push(s,x) ?出棧 pop(s) ?取棧頂元素 gettop(s) ?判斷?？? emptystack(s) ?置空棧 setstacknull ?求棧的長度 stacklen(s) ?棧的遍歷 stacktraverse(s) 1. 入棧（ push） ?入棧的主要操作是先將棧頂指針加 1； ?然后將入棧元素放到棧頂指針所指示下標值的位置上。 return(0)。 ………… A B C D b a S c 1 2 3 4 5 6 n 2 n 1 n t op1 t op2 ………… 例 ?這個棧的棧頂指針 top2是按相反的方向移動的 ， 因此 ,在操作時要判斷： 入棧時： top21=top1 ？ 出棧時： top2=n+1 ? 入棧算法 void push (S, int n, top1, top2, G) { if (top21==top1) printf(“溢出 !\n”)。 }stacklnode。 if (p==null) printf (“棧已空 ” )。建立一個棧，對逆波蘭表達式從左到右掃描，遇到運算分量則進棧，遇到運算符號則取其棧頂元素（二目或一目）運算，并把結(jié)果進棧。 2. 調(diào)用到最后一步時，必須有非遞歸的確切的定 義。 Else return(n*fact(n1))。 } } 斐波那契（ Fibonacci)數(shù)的定義 。 ?隊列中元素的數(shù)目等于零稱為空隊列。 ?刪除操作 若 /*對列非空 */ 則刪除： ++。 出隊函數(shù) void Delete (Q, int front, rear, n, x) { if (Qfront==) printf(“下溢出 !\n”)。 若 max=8 時，要插入一個元素，應(yīng)插入到第 0個位置，即 (+1) % max=(7+1) % 8=0 ?如何判斷循環(huán)隊列的“空”和“滿”呢？ 先看一個例子。 return(0)。 ?解 1：設(shè)隊列的最大元素個數(shù)為 n，設(shè)一個計數(shù)器，將其初始值設(shè)為 0。 if (r=f) length=rf。 Return(1)。 } P=headnext。 ?一個長度為零的串稱為空串，表示為 s =ˊˊ。 串的存儲結(jié)構(gòu) : 用一個一維數(shù)組存放串。 } for (i=0。串的動態(tài)存儲結(jié)構(gòu) 又分為 鏈式存儲結(jié)構(gòu) 和 堆式存儲結(jié)構(gòu) 串的鏈式存儲 形式與一般的鏈表類似，是將存儲區(qū)分成許多結(jié)點，每個結(jié)點有一個存放字符的域和一個存放指向下一個結(jié)點的指針域。 pnext=t。 兩個串 S和 T連接算法 Hstring *concat(s,t) { char *p。j++) /*復(fù)制 S到 P中 */ p[i++]=sstring[j]。 sstring=t_len。 ?如此逐輪做下去，直至匹配成功，給出子串的起始位置或失敗返回起始位置為 0。 } else { i=ij+1。 char c。 j++) { c=pop(stack)。 while(ki amp。 while(k=jamp。 } qlink=NULL。 3. 對于采用順序結(jié)構(gòu)存儲的串 r，設(shè)計一算法將串逆置。 2. 設(shè)用一維數(shù)組 stack[n]表示一個堆棧，若堆棧中一個元素需占用 length個數(shù)組單元（ length 1），試寫出其入棧、出棧操作的算法。 4. 設(shè)一循環(huán)隊列 Queue，只有頭指針 front，不設(shè)尾指針，另設(shè)一個內(nèi)含元素個數(shù)的計數(shù)器，試寫出相應(yīng)的入隊、出隊算法。 5. 已知兩個采用單鏈表結(jié)構(gòu)存儲的串 A和 B。 r=rlink。p!=NULL) /* 復(fù)制 j個結(jié)點 */ { s=(linkstring *) malloc(sizeof(linkstring))。 p!=NULL) { p=plink。 } return(true)。 setstacknull(stack)。 } } if(j==) return(+1)。 匹配算法 int indexstring ( stringtype s, t) { int i=0。 } 4。jtstrlen。 t_len=s