【正文】 rear ^ 插入算法 Int insertque(head,rear,x) { p=malloc(sizeof(Qlnode))。 } 刪除算法 Deleteque (head,rear) { if (headnext=null) { printf(“隊列空” )。 /*刪除后隊列為空 */ } 第 4章 串 ?知 識 點 串的有關概念和術語 串的基本運算功能 串的順序存儲方法（包括緊縮格式和非緊縮格式）和鏈接存儲方法 串的匹配運算 串的定義及基本運算 ?串 (string)是由有限個字符組成的序列，又稱為字符串 (character string)，一般記為 : s=ˊa1 a2 a3…a nˊ 其中 s是串名，用單引號括起來的字符序列是串的值。 ? deletestring(,len)。 If ( + t. len maxlen) { printf(“連接后太長” )。 } ?求子串： substring(s, pos, len,t)：求從串 S的 pos位置開始，長度為 len的子串，并存放在 t中。 return(s)。 /*按串的長度分配 */ Int strlen。 for(j=0。 free(tstring)。顯然 t是 s的子串的一個必要條件是， t的長度一定要小于或等于 s的長度。(j) { if ([i]==[j]) { i++。 如串 ‘ texttxet? ?怎樣判斷一個串是中心對稱呢？ 基本思想 ： 把串的前半部分入棧，掃描后半部分的每一符號，并與棧頂元素比較，若均相等，則為中心對稱，否則，不是中心對稱。 for (j=n/2。 p=r1。 q=r。 p=plink。 3. 串是一種特殊的線性表，其特殊性體現(xiàn)在什么地方？ 4. 串的兩種最基本的存儲方式是什么？ 5. 兩個串相等的充分必要條件是什么？ ?二、算法設計題 1. 對于采用順序結構存儲的串 r，編寫一個函數刪除其值等于 ch的所有字符。 7. 在什么情況下，才能使用棧、隊列等數據結構？ 8. 有 A、 B、 C三個數組： A[8]， B[4][7]，C[5][8][6]，試計算它們的元素個數是多少？ ?二、算法設計題 1. 設有一 n個元素的線性表，用一維數組 A[n]表示。（提示：對表達式進行掃描，凡遇到“（”就進棧，遇到“）”就退出棧頂的“（”，表達式掃描完畢時棧若為空則圓括號配對正確。 返回 習題與練習 ?一、基本知識題 1. 什么是數組？數組的主要特點是什么？ 2. 什么是線性表？線性表的主要運算有哪些？ 3. 什么是棧？什么是隊列？它們各自的特點是什么？ 4. 線性表、棧、隊列有什么異同？ 5. 簡述棧的入棧、出棧操作的過程。 } return (r)。 qlink=s。 } if(p==NULL) printf(“出錯 \n”)。 linkstring *substring (linkstring *r1， int i， j) { int k。jn/2。 /*的位置 */ } ?以上算法稱為布魯 福斯（ BruteForce)算法，是由兩人完成的，但其效率不高，knuth, Pratt, Morris三人同時發(fā)現(xiàn)了其中的不足，并對其進行了改進，改進后的算法稱為 KMP算法。 /*Bruteforce算法 */ while(i)amp。如是其子串，則給出該子串的起始點（即從已知串的哪個字符開始），故此運算又稱為子串的定位。 p[i]=?\0?。 return(null)。 當建立一個新串時，用 malloc來申請一塊空， 成功，則返回其首地址；當不再使用時，用 free來釋放。 /*把串 t鏈到 s的尾部 */ p=s。 []=?\0?。 或去掉變量 len，在串的尾部放入一個特殊符號。 ? 6. 求子串 substring(s， pos， len)； 返回 ? 7. 置換 replace(s， t， v)。 /*若只有一個結點， Free(p)。 rear=p。 Struct node *next。 k=f。 Return([]。 這樣 , 隊滿的條件： (+1)%max= 隊空的條件： = 循環(huán)隊列入隊函數 Int insert(Quetype Q, elementtype x) { if (( +1)%maxsize==) { printf(“隊列溢出 ” )。實際上，當 =maxsize1,時，對列未必滿，出現(xiàn)了 “假溢出”現(xiàn)象。 /*判斷是否已到數組末端 */ else { ++。 Int rear。 ?新入隊的元素只能添加在隊尾，出隊的元素只能是刪除隊頭的元素，隊列的特點是先進入隊列的元素先出隊，所以隊列也稱作先進先出表或 FIFO（ FirstInFirstOut）表。 m=m1 top=top+1。 返回時做以下工作： 。 2. 若 s=0，則結束，輸出序列的逆就是轉 換后的結果。 } 堆棧的應用 ? 1. 堆棧在函數調用中的應用 : 設有三個函數 A1，A2， A3，這三個函數有如下的調用關系：函數 A1在其函數體的某處 r調用函數 A2，函數 A2又在其函數體某處 t調用函數 A3，函數 A3不調用其他函數。 Headnext=p。 else { x=S[top2]。 。 } st