數(shù)據(jù)結(jié)構(gòu)之棧對列串課件-資料下載頁
2025-08-22 09:01本頁面
【導讀】堆棧也簡稱為棧，是限定在表的一端進行插。入或刪除操作的線性表。另一端稱為棧底。插入元素又稱為入棧，刪除元素操。不含元素的棧稱為空棧。先出線性表或LIFO表。堆棧的最簡單的表示方法是采用一維數(shù)組，為。形象起見，一般在圖中將堆棧畫成豎直的。設數(shù)組名為STACK，其下標的下界為1，上界。一般需用一個變量top記錄當前棧頂?shù)南聵酥担瑃op也叫做棧指針。然后將入棧元素放到棧頂指針所指示下。用一個一維數(shù)組作棧，加一個指針。個變量，以備后面的運算應用；假設已指定的變量為*p，則出棧的函數(shù)。一個雙向棧是將兩個棧用一個數(shù)組構(gòu)成，它們。這個棧的棧頂指針top2是按相反的方向移。用一頭結(jié)點單鏈表的第一個元素，頭結(jié)。點的指針表示棧頂，若一進棧序列a,b,c,由于逆波蘭表示法以上特點，其處理很方。例：把進制的數(shù)355轉(zhuǎn)換成八進制的數(shù)。則退棧，并比較是否匹配。假設下列形式都是合法的：
【正文】 ，則運算結(jié)束，返回子串的起始位置為 2； ?依此類推，如出現(xiàn)不匹配，再返回來將 t的第一個字符與 s的第三個字符比較。 ?如此逐輪做下去，直至匹配成功，給出子串的起始位置或失敗返回起始位置為 0。 ?例： s=?abafabcg? t=?abc? 子串 t在 s中的起始位置為 5。 匹配算法 int indexstring ( stringtype s, t) { int i=0。 j=0。 /*Bruteforce算法 */ while(i)amp。amp。(j) { if ([i]==[j]) { i++。 j++。 } else { i=ij+1。 j=0。 } } if(j==) return(+1)。 /*成功返回在主串中 */ return(1)。 /*的位置 */ } ?以上算法稱為布魯 福斯（ BruteForce)算法，是由兩人完成的，但其效率不高，knuth, Pratt, Morris三人同時發(fā)現(xiàn)了其中的不足，并對其進行了改進，改進后的算法稱為 KMP算法。 串的應用舉例 ? 1. 中心對稱問題 滿足下列條件的串稱為中心對稱串： 字符的個數(shù)為偶數(shù)； 第 1個字符和最后一個字符相等，第 2個字符和 倒數(shù)第二 2個字符相等， …… 。 如串 ‘ texttxet? ?怎樣判斷一個串是中心對稱呢？ 基本思想 ： 把串的前半部分入棧，掃描后半部分的每一符號，并與棧頂元素比較，若均相等，則為中心對稱，否則，不是中心對稱。 ?算法如下： int symstring(char s[ ], int n) { stacktype stack。 char c。 int j。 setstacknull(stack)。 /*將棧置空 */ for(j=0。jn/2。j++) /*S的前半部分進棧 */ push(stack,s[j]） 。 for (j=n/2。 jn。 j++) { c=pop(stack)。 if cs[j] return(false)。 } return(true)。 } 2. 從鏈接存儲的串 r1中的第 i個字符開始，把連續(xù) j個字符組成的子串賦給 r。 linkstring *substring (linkstring *r1， int i， j) { int k。 linkstring *p， *q， *s， *r。 p=r1。 k=1。 while(ki amp。amp。 p!=NULL) { p=plink。 /*尋找第 i個結(jié)點 */ k++。 } if(p==NULL) printf(“出錯 \n”)。 else { r=(linkstring *) malloc(sizeof(linkstring))。 q=r。 k=1。 while(k=jamp。amp。p!=NULL) /* 復制 j個結(jié)點 */ { s=(linkstring *) malloc(sizeof(linkstring))。 sch=pch。 qlink=s。 /* q總是指向 r的最后一個結(jié)點 */ q=s。 p=plink。 k++。 } qlink=NULL。 q=r。 r=rlink。 free(q)。 } return (r)。 } 返回 小 結(jié) ?串 ?串的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 鏈接存儲結(jié)構(gòu) ?串的匹配運算 返回 習題與練習 ?一、基本知識題 1. 空串與空格串有何區(qū)別？ 2. 已知兩個串為 A＝ ’ ac cab cabcbbca? B＝ ’ abc? 判斷 B串是否是 A串的子串，如果是其子串，說明起始點是 A串的第幾個字符。 3. 串是一種特殊的線性表，其特殊性體現(xiàn)在什么地方？ 4. 串的兩種最基本的存儲方式是什么？ 5. 兩個串相等的充分必要條件是什么？ ?二、算法設計題 1. 對于采用順序結(jié)構(gòu)存儲的串 r，編寫一個函數(shù)刪除其值等于 ch的所有字符。 2. 對于采用順序結(jié)構(gòu)存儲的串 r，編寫一個函數(shù)刪除 r中第 i個字符開始的 j個字符。 3. 對于采用順序結(jié)構(gòu)存儲的串 r，設計一算法將串逆置。 4. 采用單鏈表結(jié)構(gòu)存儲的串 r，編寫一個函數(shù)將其中所有的’ c?字符替換成’ s?字符。 5. 已知兩個采用單鏈表結(jié)構(gòu)存儲的串 A和 B。試編寫一個函數(shù)將串 B插入到串 A中第 k個字符之后。 返回 習題與練習 ?一、基本知識題 1. 什么是數(shù)組？數(shù)組的主要特點是什么？ 2. 什么是線性表？線性表的主要運算有哪些？ 3. 什么是棧？什么是隊列？它們各自的特點是什么？ 4. 線性表、棧、隊列有什么異同？ 5. 簡述棧的入棧、出棧操作的過程。 6. 在循環(huán)隊列中簡述入隊、出隊操作的過程。 7. 在什么情況下，才能使用棧、隊列等數(shù)據(jù)結(jié)構(gòu)？ 8. 有 A、 B、 C三個數(shù)組： A[8]， B[4][7]，C[5][8][6]，試計算它們的元素個數(shù)是多少？ ?二、算法設計題 1. 設有一 n個元素的線性表，用一維數(shù)組 A[n]表示。試設計一個算法，使此線性表元素的排隊次序顛倒過來但仍存儲于原數(shù)組中。 2. 設用一維數(shù)組 stack[n]表示一個堆棧，若堆棧中一個元素需占用 length個數(shù)組單元（ length 1），試寫出其入棧、出棧操作的算法。 3. 試編寫一個遍歷及顯示隊列中元素的算法。 4. 設一循環(huán)隊列 Queue，只有頭指針 front，不設尾指針，另設一個內(nèi)含元素個數(shù)的計數(shù)器，試寫出相應的入隊、出隊算法。 5. 設計一算法能判斷一個算術(shù)表達式中的圓括號配對是否正確。（提示：對表達式進行掃描，凡遇到“（”就進棧，遇到“）”就退出棧頂?shù)摹埃ā保磉_式掃描完畢時棧若為空則圓括號配對正確。） 返回
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1