【正文】 6. 在循環(huán)隊列中簡述入隊、出隊操作的過程。 /* q總是指向 r的最后一個結(jié)點 */ q=s。 linkstring *p， *q， *s， *r。 串的應(yīng)用舉例 ? 1. 中心對稱問題 滿足下列條件的串稱為中心對稱串： 字符的個數(shù)為偶數(shù)； 第 1個字符和最后一個字符相等，第 2個字符和 倒數(shù)第二 2個字符相等， …… 。 ?設(shè)已知串 s和 t，要求判斷 t是否是 s的子串，如果是其子串則給出起始點。 } i=0。 If(p==null) { p=t。 例 : 求串 s和 t連接 stringtype concatstring(stringtype s, t) { int i。 return(0)。 }Qlnode。 } 隊列的應(yīng)用 ?對于各種具有“先進先出”需排隊處理的問題，都可以應(yīng)用隊列來解決。 采用循環(huán)對列可以解決這一問題。 }quetype。 } R=1。 3. n:=s, 轉(zhuǎn) 1. 例：把進制的數(shù) 355轉(zhuǎn)換成八進制的數(shù)。 Return(0)。 return(0)。 堆棧的表示 ?堆棧的最簡單的表示方法是采用一維數(shù)組，為形象起見，一般在圖中將堆棧畫成豎直的 。 其定義如下： define maxsize 允許的最大元素個數(shù) Typedef struct { elementtype elenents[maxsize]。 S[top2]=G。 /*刪除 P*/ *x=pdata。 Else return(n*fact(n1))。 ?允許添加元素的一端稱為隊尾（ Rear）；允許刪除元素的一端稱為隊頭（ Front）。 ?設(shè)用下標從 1到 n的數(shù)組 Q表示隊列，且已知待添加的元素在變量 x中。 ?可以看出，不管隊列是“滿”還是“空”，都有front=rear。 ?解 2：利用隊頭指針與隊尾指針也可求出隊列的長度： 當 r≥f 時， length=rf 當 rf 時， length=n(fr) 例3.2算法1 int Que_Length (Queue,int f,r,n) { int length,k。 pnext=null。例如 A=ˊabc def ˊ就是長度為 7的字符串，因為 abc和 def中間有一個空格字符。 i++) [+i]=[i]。 } 串的堆式存儲結(jié)構(gòu) 基本思想： 首先系統(tǒng)開辟一個足夠大，連續(xù)的空間共串使用，串的堆式存儲結(jié)構(gòu)仍以一維數(shù)組的形式存放，但它們是在程序執(zhí)行過程中動態(tài)分配的。jtstrlen。 匹配算法 int indexstring ( stringtype s, t) { int i=0。 setstacknull(stack)。 p!=NULL) { p=plink。 r=rlink。 4. 設(shè)一循環(huán)隊列 Queue，只有頭指針 front，不設(shè)尾指針，另設(shè)一個內(nèi)含元素個數(shù)的計數(shù)器，試寫出相應(yīng)的入隊、出隊算法。 3. 對于采用順序結(jié)構(gòu)存儲的串 r，設(shè)計一算法將串逆置。 while(k=jamp。 j++) { c=pop(stack)。 } else { i=ij+1。 sstring=t_len。 兩個串 S和 T連接算法 Hstring *concat(s,t) { char *p。串的動態(tài)存儲結(jié)構(gòu) 又分為 鏈式存儲結(jié)構(gòu) 和 堆式存儲結(jié)構(gòu) 串的鏈式存儲 形式與一般的鏈表類似，是將存儲區(qū)分成許多結(jié)點，每個結(jié)點有一個存放字符的域和一個存放指向下一個結(jié)點的指針域。 串的存儲結(jié)構(gòu) : 用一個一維數(shù)組存放串。 } P=headnext。 if (r=f) length=rf。 return(0)。 出隊函數(shù) void Delete (Q, int front, rear, n, x) { if (Qfront==) printf(“下溢出 !\n”)。 ?隊列中元素的數(shù)目等于零稱為空隊列。 Else return(n*fact(n1))。建立一個棧，對逆波蘭表達式從左到右掃描，遇到運算分量則進棧，遇到運算符號則取其棧頂元素（二目或一目）運算，并把結(jié)果進棧。 }stacklnode。 return(0)。數(shù)據(jù)結(jié)構(gòu) 第 三 章 棧 對列 串 ?要 求 熟練掌握以下內(nèi)容： 堆棧的特征 、 基本運算并能設(shè)計簡單算法 隊列 、 循環(huán)隊列的特征 、 基本運算并能設(shè)計簡單算法 串的定義和應(yīng)用 了解以下內(nèi)容： 線性表運算時間復雜性分析 堆棧 、 隊列實際應(yīng)用 堆棧 (Stack) ?堆棧也簡稱為棧，是限定在表的一端進行插入或刪除操作的線性表。 []=x。 Struct node *next。 ? 由于逆波蘭表示法以上特點，其處理很方便。 例：階乘 Int fact(int n) { if (n==0) return(1)。 ?一般使用一個變量 r指示隊尾的下標值，叫做隊尾指針；用另一個變量 f 指示隊頭的下標值，稱為隊頭指針。 ?假設(shè)要求將出隊的元素值賦給變量 x 。 []=x 。 } 例 2 int Que_lenrth(Queue,f,r,n) { int length=0。 Return(1)。 ? copystring(t,s)。 2。 }Hstring。 sstring=p。 j++。 jn。 k=1。 2. 對于采用順序結(jié)構(gòu)存儲的串 r，編寫一個函數(shù)刪除 r中第 i個字符開始的 j個字符。 5. 設(shè)計一算法能判斷一個算術(shù)表達式中的圓括號配對是否正確。 free(q)。 /*尋找第 i個結(jié)點 */ k++。 /*將棧置空 */ for(j=0。 j=0。j++) /*復制 t到 P中 */ p[i++]=tstring[j]。在 C語言中，用 malloc和 free來管理。 =