【正文】 的表示方法是采用一維數(shù)組，為形象起見，一般在圖中將堆棧畫成豎直的 。 ?設用下標從 1到 n的數(shù)組 ST表示堆棧，入棧的元素值為 G，則可得到入棧函數(shù)如下： 棧的順序存儲結構 ?用一個一維數(shù)組作棧，加一個指針。 入棧函數(shù) int push (stacktype s, elementtype x) { if (==maxsize1) { printf(“棧溢出 !\n”)。 } 2. 出棧（ Pop） ?出棧運算時，先將棧頂?shù)脑刂蒂x給某個變量，以備后面的運算應用； ?然后棧頂指針減 1，將棧頂位置下移。 return(0)。 else { top2=top21。 top2=top2+1。 進棧 ? Int push(stacklnode *head,elementtype x) {stacklnode *p。 Return(0)。 headnext=pnext。 r t A1 A2 A3 ?函數(shù)嵌套調用A1調用 A2， A2調用 A3時的返回地址在堆棧中的情況如右圖所示。 ?例：求 –B*（ C+D）的值。 3. n:=s, 轉 1. 例：把進制的數(shù) 355轉換成八進制的數(shù)。 ?求 n!的遞歸算法： Int fact(n) { if(n==0) Return(1)。 。 } Fact(n) { Top=1。 } R=1。 希爾波特（ ,1891)曲線的定義； 塞平斯基（ Sierpinski)曲線的定義； Hanoi塔穩(wěn)問題； 中斷處理問題； …… 隊列（ Queue） ?隊列是一種運算受限制的線性表，元素的添加在表的一端進行，而元素的刪除在表的另一端進行。 隊列的表示 ?與堆棧類似，隊列也可以簡單的用一維數(shù)組表示。 ?對列的順序存儲結構 假定有 A～ F 6個元素先后進入隊列，但 A、B,C三個元素已出隊了，故隊尾指針 r=6，而隊頭指針 f=3。 }quetype。 /*刪除 */ return([]) 1. 入隊（ insert） ?當給隊列插入元素時，隊尾指針 r后移而隊頭指針不動，但有一個情況例外，即當向空隊列插入第一個元素時，隊頭指針與隊尾指針同時由 0變?yōu)?1。 []=x。 /*判斷是否為空隊列 */ else { ++: x=Q. elements[]。 采用循環(huán)對列可以解決這一問題。 例：一循環(huán)隊列 max =6，隊列中已有 3個元素，研究其插入 3個元素后和刪除 3個元素后的狀態(tài)。 return(1)。 } 循環(huán)隊列出隊函數(shù) { if (==) { printf (“是空隊列 ！ \n”)。 } 隊列的應用 ?對于各種具有“先進先出”需排隊處理的問題，都可以應用隊列來解決。從隊頭開始，沿著隊列順序搜索，每搜索一個元素，計數(shù)器加 1，直到隊尾，計數(shù)器的最終值即為隊列的長度。 while (k!=r) { length++。 else length=n(fr)。 }Qlnode。 } Pdata=x。 Return(0)。 headnext=pnext。 return(0)。 ?空格也是合法字符，它可以出現(xiàn)在較長的字符串中，也可以單獨出現(xiàn) 。 ? insertstring(s,pos,t)。 0 1 2 3 4 5 6 …… a b c d e .….. 數(shù)據(jù)結構的定義： define max 允許串的最大長度 typedef struct { char string[max]。 例 : 求串 s和 t連接 stringtype concatstring(stringtype s, t) { int i。 i。 return(0)。 一個存儲結點可以存儲 1個或多個字符，通常一個結點為一塊。 If(p==null) { p=t。 return(s)。 typedef struct { char string。 int I, j, t_len。 } i=0。 for(j=0。 /*加結束標記 */ free(sstring)。 return(s)。 ?設已知串 s和 t，要求判斷 t是否是 s的子串，如果是其子串則給出起始點。 ?例： s=?abafabcg? t=?abc? 子串 t在 s中的起始位置為 5。amp。 j=0。 串的應用舉例 ? 1. 中心對稱問題 滿足下列條件的串稱為中心對稱串： 字符的個數(shù)為偶數(shù)； 第 1個字符和最后一個字符相等，第 2個字符和 倒數(shù)第二 2個字符相等， …… 。 int j。j++) /*S的前半部分進棧 */ push(stack,s[j]） 。 if cs[j] return(false)。 linkstring *p， *q， *s， *r。amp。 else { r=(linkstring *) malloc(sizeof(linkstring))。amp。 /* q總是指向 r的最后一個結點 */ q=s。 q=r。 } 返回 小 結 ?串 ?串的存儲結構 順序存儲結構 鏈接存儲結構 ?串的匹配運算 返回 習題與練習 ?一、基本知識題 1. 空串與空格串有何區(qū)別？ 2. 已知兩個串為 A＝ ’ ac cab cabcbbca? B＝ ’ abc? 判斷 B串是否是 A串的子串，如果是其子串，說明起始點是 A串的第幾個字符。 4. 采用單鏈表結構存儲的串 r，編寫一個函數(shù)將其中所有的’ c?字符替換成’ s?字符。 6. 在循環(huán)隊列中簡述入隊、出隊操作的過程。 3. 試編寫一個遍歷及顯示隊列中元素的算法。） 返回