【正文】 +。 ?子串 ?主串 ?子串在主串中的位置 ?兩個(gè)串相等 串的基本運(yùn)算 ? assignstring(t,chars) ? lenstring(s)； ? equalstring(s,t)； ? 4. 兩個(gè)串的連接 concatstring(s， t)； ? indexstring(s,t)。 rearnext=p。 length=0。那么，如何判斷是“空”還是“滿”呢？ ?解決方法： 1. 另設(shè)一標(biāo)記，以區(qū)分隊(duì)列是“空”還是“滿”； 2. 不設(shè)標(biāo)記，把 尾指針加 1后等于頭指針 作為隊(duì) 滿的條件。 入隊(duì)函數(shù) void insert (Q, int n, front, rear, x) { if ( == n1) printf(“溢出 !\n”)。 ?向隊(duì)列添加元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。 } 遞歸的執(zhí)行 調(diào)用時(shí)做以下工作： 等； ； 。 free(p) Return(0)。 /*插入新元素 */ } } 出棧算法 void pop (S, int n, top1, top2, x) { if (top2==n+1) printf(“下溢出 !\n”)。 Int top。 ?堆棧元素的插入和刪除只在棧頂進(jìn)行，總是后進(jìn)去的元素先出來，所以堆棧又稱為后進(jìn)先出線性表或 LIFO（ LastInFirstOut）表。 。 Headnext=p。 2. 若 s=0，則結(jié)束，輸出序列的逆就是轉(zhuǎn) 換后的結(jié)果。 m=m1 top=top+1。 Int rear。實(shí)際上，當(dāng) =maxsize1,時(shí)，對(duì)列未必滿，出現(xiàn)了 “假溢出”現(xiàn)象。 Return([]。 Struct node *next。 /*若只有一個(gè)結(jié)點(diǎn)， Free(p)。 或去掉變量 len，在串的尾部放入一個(gè)特殊符號(hào)。 /*把串 t鏈到 s的尾部 */ p=s。 return(null)。如是其子串，則給出該子串的起始點(diǎn)（即從已知串的哪個(gè)字符開始），故此運(yùn)算又稱為子串的定位。 /*的位置 */ } ?以上算法稱為布魯 福斯（ BruteForce)算法，是由兩人完成的，但其效率不高，knuth, Pratt, Morris三人同時(shí)發(fā)現(xiàn)了其中的不足，并對(duì)其進(jìn)行了改進(jìn)，改進(jìn)后的算法稱為 KMP算法。 linkstring *substring (linkstring *r1， int i， j) { int k。 qlink=s。 返回 習(xí)題與練習(xí) ?一、基本知識(shí)題 1. 什么是數(shù)組？數(shù)組的主要特點(diǎn)是什么？ 2. 什么是線性表？線性表的主要運(yùn)算有哪些？ 3. 什么是棧？什么是隊(duì)列？它們各自的特點(diǎn)是什么？ 4. 線性表、棧、隊(duì)列有什么異同？ 5. 簡(jiǎn)述棧的入棧、出棧操作的過程。 7. 在什么情況下，才能使用棧、隊(duì)列等數(shù)據(jù)結(jié)構(gòu)？ 8. 有 A、 B、 C三個(gè)數(shù)組： A[8]， B[4][7]，C[5][8][6]，試計(jì)算它們的元素個(gè)數(shù)是多少？ ?二、算法設(shè)計(jì)題 1. 設(shè)有一 n個(gè)元素的線性表，用一維數(shù)組 A[n]表示。 p=plink。 p=r1。 如串 ‘ texttxet? ?怎樣判斷一個(gè)串是中心對(duì)稱呢？ 基本思想 ： 把串的前半部分入棧，掃描后半部分的每一符號(hào)，并與棧頂元素比較，若均相等，則為中心對(duì)稱，否則，不是中心對(duì)稱。顯然 t是 s的子串的一個(gè)必要條件是， t的長(zhǎng)度一定要小于或等于 s的長(zhǎng)度。 for(j=0。 return(s)。 If ( + t. len maxlen) { printf(“連接后太長(zhǎng)” )。 /*刪除后隊(duì)列為空 */ } 第 4章 串 ?知 識(shí) 點(diǎn) 串的有關(guān)概念和術(shù)語(yǔ) 串的基本運(yùn)算功能 串的順序存儲(chǔ)方法（包括緊縮格式和非緊縮格式）和鏈接存儲(chǔ)方法 串的匹配運(yùn)算 串的定義及基本運(yùn)算 ?串 (string)是由有限個(gè)字符組成的序列，又稱為字符串 (character string)，一般記為 : s=ˊa1 a2 a3…a nˊ 其中 s是串名，用單引號(hào)括起來的字符序列是串的值。 插入結(jié)點(diǎn)： P head rear rear ^ x ^ 刪除結(jié)點(diǎn)： Head rear ^ 插入算法 Int insertque(head,rear,x) { p=malloc(sizeof(Qlnode))。 ?例如，操作系統(tǒng)在管理和分配系統(tǒng)資源時(shí)，大量的應(yīng)用了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。 循環(huán)隊(duì)列 循環(huán)隊(duì)列就是把順序隊(duì)列的頭和尾相連，構(gòu)成一個(gè)閉環(huán)。 ?插入操作 若 maxsize1。 While(top1) { Top=top1。 ?基本思想：若遇見左括