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