數(shù)據(jù)結(jié)構(gòu)之棧對(duì)列串課件-免費(fèi)閱讀
【正文】 3. 試編寫一個(gè)遍歷及顯示隊(duì)列中元素的算法。 4. 采用單鏈表結(jié)構(gòu)存儲(chǔ)的串 r，編寫一個(gè)函數(shù)將其中所有的’ c?字符替換成’ s?字符。 q=r。amp。amp。 if cs[j] return(false)。 int j。 j=0。 ?例： s=?abafabcg? t=?abc? 子串 t在 s中的起始位置為 5。 return(s)。 for(j=0。 int I, j, t_len。 return(s)。 一個(gè)存儲(chǔ)結(jié)點(diǎn)可以存儲(chǔ) 1個(gè)或多個(gè)字符，通常一個(gè)結(jié)點(diǎn)為一塊。 i。 0 1 2 3 4 5 6 …… a b c d e .….. 數(shù)據(jù)結(jié)構(gòu)的定義： define max 允許串的最大長(zhǎng)度 typedef struct { char string[max]。 ?空格也是合法字符，它可以出現(xiàn)在較長(zhǎng)的字符串中，也可以單獨(dú)出現(xiàn) 。 headnext=pnext。 } Pdata=x。 else length=n(fr)。從隊(duì)頭開始，沿著隊(duì)列順序搜索，每搜索一個(gè)元素，計(jì)數(shù)器加 1，直到隊(duì)尾，計(jì)數(shù)器的最終值即為隊(duì)列的長(zhǎng)度。 } 循環(huán)隊(duì)列出隊(duì)函數(shù) { if (==) { printf (“是空隊(duì)列 ！ \n”)。 例：一循環(huán)隊(duì)列 max =6，隊(duì)列中已有 3個(gè)元素，研究其插入 3個(gè)元素后和刪除 3個(gè)元素后的狀態(tài)。 /*判斷是否為空隊(duì)列 */ else { ++: x=Q. elements[]。 /*刪除 */ return([]) 1. 入隊(duì)（ insert） ?當(dāng)給隊(duì)列插入元素時(shí)，隊(duì)尾指針 r后移而隊(duì)頭指針不動(dòng)，但有一個(gè)情況例外，即當(dāng)向空隊(duì)列插入第一個(gè)元素時(shí)，隊(duì)頭指針與隊(duì)尾指針同時(shí)由 0變?yōu)?1。 ?對(duì)列的順序存儲(chǔ)結(jié)構(gòu) 假定有 A～ F 6個(gè)元素先后進(jìn)入隊(duì)列，但 A、B,C三個(gè)元素已出隊(duì)了，故隊(duì)尾指針 r=6，而隊(duì)頭指針 f=3。 希爾波特（ ,1891)曲線的定義； 塞平斯基（ Sierpinski)曲線的定義； Hanoi塔穩(wěn)問題； 中斷處理問題； …… 隊(duì)列（ Queue） ?隊(duì)列是一種運(yùn)算受限制的線性表，元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行。 } Fact(n) { Top=1。 ?求 n!的遞歸算法： Int fact(n) { if(n==0) Return(1)。 ?例：求 –B*（ C+D）的值。 headnext=pnext。 進(jìn)棧 ? Int push(stacklnode *head,elementtype x) {stacklnode *p。 else { top2=top21。 } 2. 出棧（ Pop） ?出棧運(yùn)算時(shí)，先將棧頂?shù)脑刂蒂x給某個(gè)變量，以備后面的運(yùn)算應(yīng)用； ?然后棧頂指針減 1，將棧頂位置下移。 ?設(shè)用下標(biāo)從 1到 n的數(shù)組 ST表示堆棧，入棧的元素值為 G，則可得到入棧函數(shù)如下： 棧的順序存儲(chǔ)結(jié)構(gòu) ?用一個(gè)一維數(shù)組作棧，加一個(gè)指針。 ?進(jìn)行插入或刪除操作的一段稱為棧頂（ top），另一端稱為棧底（ bottom）。 ?設(shè)數(shù)組名為 STACK，其下標(biāo)的下界為 1，上界為 n。 /*棧滿 */ return(1) } s. top++。 } 例 ?一個(gè)雙向棧是將兩個(gè)棧用一個(gè)數(shù)組構(gòu)成，它們的棧底分別設(shè)在數(shù)組的兩端。 } } 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?用一頭結(jié)點(diǎn)單鏈表的第一個(gè)元素，頭結(jié)點(diǎn)的指針表示棧頂，若一進(jìn)棧序列 a,b,c, 其鏈?zhǔn)浇Y(jié)構(gòu)如下： head c b a ^ ?其結(jié)構(gòu)定義如下： typedef struct node { elementtype data。 } 出棧 Int pop(stacklnode *head,elementtype *x) {stacklnode *p。 top r t STACK 2. 堆棧在 表達(dá)式計(jì)算 中的應(yīng)用 ?后綴表示法（逆波蘭表示法） ? ab+， abc*+， ab+c*， …… ? 逆波蘭表達(dá)式的特點(diǎn)：無括號(hào)，形式簡(jiǎn)潔，運(yùn)算符的順序與運(yùn)算順序相同。 ?基本思想：若遇見左括號(hào)，則進(jìn)棧；若右括號(hào)，則退棧，并比較是否匹配。 。 While(top1) { Top=top1。 ?設(shè)數(shù)組名為 Queue，其下標(biāo)下界為 1，上界為 n。 ?插入操作 若 maxsize1。 /*插入元素 */ } } 2. 出隊(duì)（ Delete） ?當(dāng)從隊(duì)列刪除元素時(shí)，隊(duì)頭指針 f后移而隊(duì)尾指針 r不動(dòng)，但也有一個(gè)情況例外，即當(dāng)刪除了最后一個(gè)元素，隊(duì)列成為了空隊(duì)列時(shí)，隊(duì)頭指針與隊(duì)尾指針同時(shí)變?yōu)?0。 循環(huán)隊(duì)列 循環(huán)隊(duì)列就是把順序隊(duì)列的頭和尾相連，構(gòu)成一個(gè)閉環(huán)。 } =(+1)%maxsize。 ?例如，操作系統(tǒng)在管理和分配系統(tǒng)資源時(shí)，大量的應(yīng)用了隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。 k=(k+1)%n } return(length)。 插入結(jié)點(diǎn)： P head rear rear ^ x ^ 刪除結(jié)點(diǎn)： Head
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1