【正文】 strlen+tstrlen。 } 串的堆式存儲結(jié)構(gòu) 基本思想： 首先系統(tǒng)開辟一個足夠大，連續(xù)的空間共串使用，串的堆式存儲結(jié)構(gòu)仍以一維數(shù)組的形式存放，但它們是在程序執(zhí)行過程中動態(tài)分配的。 ?單字符結(jié)點(diǎn)的串的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?多字符結(jié)點(diǎn)的串的鏈?zhǔn)酱鎯Y(jié)構(gòu) h w v u x y z ∧ w v u x y z ∧ ?結(jié)點(diǎn)類型定義如下： typedef struct Lnode { char data。 i++) [+i]=[i]。 int len。例如 A=ˊabc def ˊ就是長度為 7的字符串，因?yàn)?abc和 def中間有一個空格字符。 x=pdata。 pnext=null。 return(length)。 ?解 2：利用隊(duì)頭指針與隊(duì)尾指針也可求出隊(duì)列的長度： 當(dāng) r≥f 時， length=rf 當(dāng) rf 時， length=n(fr) 例3.2算法1 int Que_Length (Queue,int f,r,n) { int length,k。 return(1)。 ?可以看出，不管隊(duì)列是“滿”還是“空”，都有front=rear。 /*取隊(duì)頭元素給 x賦值 */ if (==) {==0 /*置成空對列 } } } “假溢出”問題 ?在插入時，由條件 =maxsize1, 判斷對列是否滿， 在刪除時，由條件 =, 判斷對列是否空。 ?設(shè)用下標(biāo)從 1到 n的數(shù)組 Q表示隊(duì)列，且已知待添加的元素在變量 x中。 A B C D E F 1 2 3 4 5 6 …………………… n QU EUE f r 對列的形式定義 define maxsize 允許數(shù)組元素的最大個數(shù) Typedef struct { elementtype elements[maxsize]。 ?允許添加元素的一端稱為隊(duì)尾（ Rear）；允許刪除元素的一端稱為隊(duì)頭（ Front）。 m=n。 Else return(n*fact(n1))。 ( 其逆波蘭表示： BCD+* ) ? 把進(jìn)制的數(shù) n轉(zhuǎn)換成八進(jìn)制的數(shù) r。 /*刪除 P*/ *x=pdata。 If ((p==malloc(sizeof(struct node)))==null Printf(“沒有空間” ) ； Pdata=x。 S[top2]=G。 ?假設(shè)已指定的變量為 *p，則出棧的函數(shù)如下： 出棧 函數(shù) Int pop (stacktype s, elementtype *p) { if (== 1) printf(“空棧 !\n”)。 其定義如下： define maxsize 允許的最大元素個數(shù) Typedef struct { elementtype elenents[maxsize]。 ?插入元素又稱為入棧（ push），刪除元素操作稱為出棧（ pop）。 堆棧的表示 ?堆棧的最簡單的表示方法是采用一維數(shù)組，為形象起見，一般在圖中將堆棧畫成豎直的 。 入棧函數(shù) int push (stacktype s, elementtype x) { if (==maxsize1) { printf(“棧溢出 !\n”)。 return(0)。 top2=top2+1。 Return(0)。 r t A1 A2 A3 ?函數(shù)嵌套調(diào)用A1調(diào)用 A2， A2調(diào)用 A3時的返回地址在堆棧中的情況如右圖所示。 3. n:=s, 轉(zhuǎn) 1. 例：把進(jìn)制的數(shù) 355轉(zhuǎn)換成八進(jìn)制的數(shù)。 。 } R=1。 隊(duì)列的表示 ?與堆棧類似，隊(duì)列也可以簡單的用一維數(shù)組表示。 }quetype。 []=x。 采用循環(huán)對列可以解決這一問題。 return(1)。 } 隊(duì)列的應(yīng)用 ?對于各種具有“先進(jìn)先出”需排隊(duì)處理的問題，都可以應(yīng)用隊(duì)列來解決。 while (k!=r) { length++。 }Qlnode。 Return(0)。 return(0)。 ? insertstring(s,pos,t)。 例 : 求串 s和 t連接 stringtype concatstring(stringtype s, t) { int i。 return(0)。 If(p==null) { p=t。 typedef struct { char string。 } i=0。 /*加結(jié)束標(biāo)記 */ free(sstring)。 ?設(shè)已知串 s和 t，要求判斷 t是否是 s的子串，如果是其子串則給出起始點(diǎn)。amp。 串的應(yīng)用舉例 ? 1. 中心對稱問題 滿足下列條件的串稱為中心對稱串： 字符的個數(shù)為偶數(shù)； 第 1個字符和最后一個字符相等，第 2個字符和 倒數(shù)第二 2個字符相等， …… 。j++) /*S的前半部分進(jìn)棧 */ push(stack,s[j]） 。 linkstring *p， *q， *s， *r。 else { r=(linkstring *) malloc(sizeof(linkstring))。 /* q總是指向 r的最后一個結(jié)點(diǎn) */ q=s。 } 返回 小 結(jié) ?串 ?串的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 鏈接存儲結(jié)構(gòu) ?串的匹配運(yùn)算 返回 習(xí)題與練習(xí) ?一、基本知識題 1. 空串與空格串有何區(qū)別？ 2. 已知兩個串為 A＝ ’ ac cab cabcbbca? B＝ ’ abc? 判斷 B串是否是 A串的子串，如果是其子串，說明起始點(diǎn)是 A串的第幾個字符。 6. 在循環(huán)隊(duì)列中簡述入隊(duì)、出隊(duì)操作的過程。） 返回