數(shù)據(jù)結(jié)構(gòu)之棧對列串課件(存儲版)
【正文】 rear ^ 插入算法 Int insertque(head,rear,x) { p=malloc(sizeof(Qlnode))。 } 刪除算法 Deleteque (head,rear) { if (headnext=null) { printf(“隊列空” )。 /*刪除后隊列為空 */ } 第 4章 串 ?知 識 點(diǎn) 串的有關(guān)概念和術(shù)語 串的基本運(yùn)算功能 串的順序存儲方法（包括緊縮格式和非緊縮格式）和鏈接存儲方法 串的匹配運(yùn)算 串的定義及基本運(yùn)算 ?串 (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. 兩個串相等的充分必要條件是什么？ ?二、算法設(shè)計題 1. 對于采用順序結(jié)構(gòu)存儲的串 r，編寫一個函數(shù)刪除其值等于 ch的所有字符。 7. 在什么情況下，才能使用棧、隊列等數(shù)據(jù)結(jié)構(gòu)？ 8. 有 A、 B、 C三個數(shù)組： A[8]， B[4][7]，C[5][8][6]，試計算它們的元素個數(shù)是多少？ ?二、算法設(shè)計題 1. 設(shè)有一 n個元素的線性表，用一維數(shù)組 A[n]表示。（提示：對表達(dá)式進(jìn)行掃描，凡遇到“（”就進(jìn)棧，遇到“）”就退出棧頂?shù)摹埃ā?，表達(dá)式掃描完畢時棧若為空則圓括號配對正確。 返回 習(xí)題與練習(xí) ?一、基本知識題 1. 什么是數(shù)組？數(shù)組的主要特點(diǎn)是什么？ 2. 什么是線性表？線性表的主要運(yùn)算有哪些？ 3. 什么是棧？什么是隊列？它們各自的特點(diǎn)是什么？ 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)了其中的不足，并對其進(jìn)行了改進(jìn)，改進(jìn)后的算法稱為 KMP算法。 /*Bruteforce算法 */ while(i)amp。如是其子串，則給出該子串的起始點(diǎn)（即從已知串的哪個字符開始），故此運(yùn)算又稱為子串的定位。 p[i]=?\0?。 return(null)。 當(dāng)建立一個新串時，用 malloc來申請一塊空， 成功，則返回其首地址；當(dāng)不再使用時，用 free來釋放。 /*把串 t鏈到 s的尾部 */ p=s。 []=?\0?。 或去掉變量 len，在串的尾部放入一個特殊符號。 ? 6. 求子串 substring(s， pos， len)； 返回 ? 7. 置換 replace(s， t， v)。 /*若只有一個結(jié)點(diǎn)， Free(p)。 rear=p。 Struct node *next。 k=f。 Return([]。 這樣 , 隊滿的條件： (+1)%max= 隊空的條件： = 循環(huán)隊列入隊函數(shù) Int insert(Quetype Q, elementtype x) { if (( +1)%maxsize==) { printf(“隊列溢出 ” )。實(shí)際上，當(dāng) =maxsize1,時，對列未必滿，出現(xiàn)了 “假溢出”現(xiàn)象。 /*判斷是否已到數(shù)組末端 */ else { ++。 Int rear。 ?新入隊的元素只能添加在隊尾，出隊的元素只能是刪除隊頭的元素，隊列的特點(diǎn)是先進(jìn)入隊列的元素先出隊，所以隊列也稱作先進(jìn)先出表或 FIFO（ FirstInFirstOut）表。 m=m1 top=top+1。 返回時做以下工作： 。 2. 若 s=0，則結(jié)束，輸出序列的逆就是轉(zhuǎn) 換后的結(jié)果。 } 堆棧的應(yīng)用 ? 1. 堆棧在函數(shù)調(diào)用中的應(yīng)用 : 設(shè)有三個函數(shù) A1，A2， A3，這三個函數(shù)有如下的調(diào)用關(guān)系：函數(shù) A1在其函數(shù)體的某處 r調(diào)用函數(shù) A2，函數(shù) A2又在其函數(shù)體某處 t調(diào)用函數(shù) A3，函數(shù) A3不調(diào)用其他函數(shù)。 Headnext=p。 else { x=S[top2]。 。 } st
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1