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