數(shù)據(jù)結(jié)構(gòu)之棧對列串課件-文庫吧在線文庫
【正文】 acktype。 ?堆棧元素的插入和刪除只在棧頂進(jìn)行，總是后進(jìn)去的元素先出來，所以堆棧又稱為后進(jìn)先出線性表或 LIFO（ LastInFirstOut）表。 ?不含元素的棧稱為空棧。 Int top。 /*棧為空 */ p=[]。 /*插入新元素 */ } } 出棧算法 void pop (S, int n, top1, top2, x) { if (top2==n+1) printf(“下溢出 !\n”)。 Pnext=headnext。 free(p) Return(0)。 1. n除以 r, 商為 S, 輸出余數(shù)。 } 遞歸的執(zhí)行 調(diào)用時(shí)做以下工作： 等； ； 。 While(m1) { S[top]=m。 ?向隊(duì)列添加元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。 Int front。 入隊(duì)函數(shù) void insert (Q, int n, front, rear, x) { if ( == n1) printf(“溢出 !\n”)。 其中的判斷條件是不科學(xué)的。那么，如何判斷是“空”還是“滿”呢？ ?解決方法： 1. 另設(shè)一標(biāo)記，以區(qū)分隊(duì)列是“空”還是“滿”； 2. 不設(shè)標(biāo)記，把 尾指針加 1后等于頭指針 作為隊(duì) 滿的條件。 } =(+1)%maxsize。 length=0。 } 返回 ?隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 增設(shè)兩個(gè)指針，分別指向隊(duì)列的頭和尾， Head …… rear 隊(duì)列空時(shí) : head rear ^ ^ 結(jié)點(diǎn)的定義 Typedef struct node { elementtype data。 rearnext=p。 If (p==rear) rear=head。 ?子串 ?主串 ?子串在主串中的位置 ?兩個(gè)串相等 串的基本運(yùn)算 ? assignstring(t,chars) ? lenstring(s)； ? equalstring(s,t)； ? 4. 兩個(gè)串的連接 concatstring(s， t)； ? indexstring(s,t)。 }stringtype。 =+。 struct lnode *next； }stringnode ?例：設(shè)每個(gè)結(jié)點(diǎn)只含一個(gè)字符，串的連接算法如下： Blstring concatstring(stringnode *s,*t) { stringnode *p。在 C語言中，用 malloc和 free來管理。 if(p=malloc(sizeof(char*t_len))==null) { printf(“空間不足 ” )。j++) /*復(fù)制 t到 P中 */ p[i++]=tstring[j]。 3 模式匹配 ?模式匹配就是判斷某串是否是另一個(gè)已知串的子串。 j=0。 /*成功返回在主串中 */ return(1)。 /*將棧置空 */ for(j=0。 } 2. 從鏈接存儲(chǔ)的串 r1中的第 i個(gè)字符開始，把連續(xù) j個(gè)字符組成的子串賦給 r。 /*尋找第 i個(gè)結(jié)點(diǎn) */ k++。 sch=pch。 free(q)。試編寫一個(gè)函數(shù)將串 B插入到串 A中第 k個(gè)字符之后。 5. 設(shè)計(jì)一算法能判斷一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對是否正確。試設(shè)計(jì)一個(gè)算法，使此線性表元素的排隊(duì)次序顛倒過來但仍存儲(chǔ)于原數(shù)組中。 2. 對于采用順序結(jié)構(gòu)存儲(chǔ)的串 r，編寫一個(gè)函數(shù)刪除 r中第 i個(gè)字符開始的 j個(gè)字符。 k++。 k=1。 k=1。 jn。 ?算法如下： int symstring(char s[ ], int n) { stacktype stack。 j++。 基本思想 ?首先將 t的第 1個(gè)字符與 s的第 1個(gè)字符比較，如二者匹配，則將 t的第二個(gè)字符與 r1的第二個(gè)字符比較，這樣比較下去，若直至 t的末尾一個(gè)字符都與 s的相應(yīng)字符匹配，則整個(gè)運(yùn)算結(jié)束，返回子串的起始位置為 1； ?當(dāng)進(jìn)行中遇到兩串的相應(yīng)字符不匹配時(shí)，則返回來將 t的第一個(gè)字符與 s的第二個(gè)比較，將t的第二個(gè)字符與 s的第三個(gè)字符進(jìn)行比較 …… ，若整個(gè) t的各個(gè)字符都與 s的相應(yīng)字符匹配，則運(yùn)算結(jié)束，返回子串的起始位置為 2； ?依此類推，如出現(xiàn)不匹配，再返回來將 t的第一個(gè)字符與 s的第三個(gè)字符比較。 sstring=p。jsstrlen。 }Hstring。} while (pnext null) p=pnext。 2。 return(1)。 ? copystring(t,s)。 ai(1=i=n)可以是字母、數(shù)字或其他字符； n為串中字符的個(gè)數(shù)，稱為串的長度。 Return(1)。 If (p=null) { printf(“隊(duì)列溢出” )。 } 例 2 int Que_lenrth(Queue,f,r,n) { int length=0。 1) 隊(duì)列在輸入 /輸出管理中的應(yīng)用 2) 對 CPU的分配管理 返回 例 ?對于循環(huán)隊(duì)列，試寫出求隊(duì)列長度的算法 。 []=x 。 （見圖） 當(dāng)尾指針 =max1 時(shí)，若要插入 (刪除）一個(gè)元素， 則要插入到第 0個(gè)位置， 即 [(max1)+1] % max=0 （取余數(shù)）。 ?假設(shè)要求將出隊(duì)的元素值賦給變量 x 。 /*對列不滿 */ 則插入： ++: /*插入 */ []=x。 ?一般使用一個(gè)變量 r指示隊(duì)尾的下標(biāo)
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1