數(shù)據(jù)結(jié)構(gòu)之棧對列串課件-wenkub
2022-09-11 09:01:56 本頁面
【正文】 束。 1. n除以 r, 商為 S, 輸出余數(shù)。 ? 由于逆波蘭表示法以上特點(diǎn)，其處理很方便。 free(p) Return(0)。 p=headnext。 Pnext=headnext。 Struct node *next。 /*插入新元素 */ } } 出棧算法 void pop (S, int n, top1, top2, x) { if (top2==n+1) printf(“下溢出 !\n”)。寫出以數(shù)組高端為底的棧的入棧和出棧的算法。 /*棧為空 */ p=[]。 []=x。 Int top。 ?一般需用一個(gè)變量 top記錄當(dāng)前棧頂?shù)南聵?biāo)值，top也叫做棧指針。 ?不含元素的棧稱為空棧。數(shù)據(jù)結(jié)構(gòu) 第 三 章 棧 對列 串 ?要 求 熟練掌握以下內(nèi)容： 堆棧的特征 、 基本運(yùn)算并能設(shè)計(jì)簡單算法 隊(duì)列 、 循環(huán)隊(duì)列的特征 、 基本運(yùn)算并能設(shè)計(jì)簡單算法 串的定義和應(yīng)用 了解以下內(nèi)容： 線性表運(yùn)算時(shí)間復(fù)雜性分析 堆棧 、 隊(duì)列實(shí)際應(yīng)用 堆棧 (Stack) ?堆棧也簡稱為棧，是限定在表的一端進(jìn)行插入或刪除操作的線性表。 ?堆棧元素的插入和刪除只在棧頂進(jìn)行，總是后進(jìn)去的元素先出來，所以堆棧又稱為后進(jìn)先出線性表或 LIFO（ LastInFirstOut）表。 ?本例中 top=4 top A D C B 4 7 5 3 2 1 6 STACK 棧的基本運(yùn)算 ?進(jìn)棧 push(s,x) ?出棧 pop(s) ?取棧頂元素 gettop(s) ?判斷?？? emptystack(s) ?置空棧 setstacknull ?求棧的長度 stacklen(s) ?棧的遍歷 stacktraverse(s) 1. 入棧（ push） ?入棧的主要操作是先將棧頂指針加 1； ?然后將入棧元素放到棧頂指針?biāo)甘鞠聵?biāo)值的位置上。 } stacktype。 return(0)。 。 ………… A B C D b a S c 1 2 3 4 5 6 n 2 n 1 n t op1 t op2 ………… 例 ?這個(gè)棧的棧頂指針 top2是按相反的方向移動(dòng)的 ， 因此 ,在操作時(shí)要判斷： 入棧時(shí)： top21=top1 ？ 出棧時(shí)： top2=n+1 ? 入棧算法 void push (S, int n, top1, top2, G) { if (top21==top1) printf(“溢出 !\n”)。 else { x=S[top2]。 }stacklnode。 Headnext=p。 if (p==null) printf (“棧已空 ” )。 } 堆棧的應(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ù)。建立一個(gè)棧，對逆波蘭表達(dá)式從左到右掃描，遇到運(yùn)算分量則進(jìn)棧，遇到運(yùn)算符號則取其棧頂元素（二目或一目）運(yùn)算，并把結(jié)果進(jìn)棧。 2. 若 s=0，則結(jié)束，輸出序列的逆就是轉(zhuǎn) 換后的結(jié)果。 2. 調(diào)用到最后一步時(shí)，必須有非遞歸的確切的定 義。 返回時(shí)做以下工作： 。 Else return(n*fact(n1))。 m=m1 top=top+1。 } } 斐波那契（ Fibonacci)數(shù)的定義 。 ?新入隊(duì)的元素只能添加在隊(duì)尾，出隊(duì)的元素只能是刪除隊(duì)頭的元素，隊(duì)列的特點(diǎn)是先進(jìn)入隊(duì)列的元素先出隊(duì)，所以隊(duì)列也稱作先進(jìn)先出表或 FIFO（ FirstInFirstOut）表。 ?隊(duì)列中元素的數(shù)目等于零稱為空隊(duì)列。 Int rear。 ?刪除操作 若 /*對列非空 */ 則刪除： ++。 /*判斷是否已到數(shù)組末端 */ else { ++。 出隊(duì)函數(shù) void Delete (Q, int front, rear, n, x) { if (Qfront==) printf(“下溢出 !\n”)。實(shí)際上，當(dāng) =maxsize1,時(shí)，對列未必滿，出現(xiàn)了 “假溢出”現(xiàn)象。 若 max=8 時(shí)，要插入一個(gè)元素，應(yīng)插入到第 0個(gè)位置，即 (+1) % max=(7+1) % 8=0 ?如何判斷循環(huán)隊(duì)列的“空”和“滿”呢？ 先看一個(gè)例子。 這樣 , 隊(duì)滿的條件： (+1)%max= 隊(duì)空的條件： = 循環(huán)隊(duì)列入隊(duì)函數(shù) Int insert(Quetype Q, elementtype x) { if (( +1)%maxsize==) { printf(“隊(duì)列溢出 ” )。 return(0)。 Return([]。 ?解 1：設(shè)隊(duì)列的最大元素個(gè)數(shù)為 n，設(shè)一個(gè)計(jì)數(shù)器，將其初始值設(shè)為 0。 k=f。 if (r=f) length=rf。 Struct node *next。 Return(1)。 rear=p。 } P=headnext。 /*若只有一個(gè)結(jié)點(diǎn)， Free(p)。 ?一個(gè)長度為零的串稱為空串，表示為 s =ˊˊ。 ? 6. 求子串 substring(s， pos， len)； 返回 ? 7. 置換 replace(s， t， v)。 串的存儲結(jié)構(gòu) : 用一個(gè)一維數(shù)組存放串。 或去掉變量 len，在串的尾部放入一個(gè)特殊符號。 } for (i=0。 []=?\0?。串的動(dòng)態(tài)存儲結(jié)構(gòu)
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1