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