武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用(已修改)
2025-07-11 14:48 本頁面
【正文】 第三章 棧和隊列第九講 棧的應(yīng)用 1．鞏固棧的定義及表示。2．掌握棧的應(yīng)用方法,理解棧的重要作用。216。 教學(xué)重點： 利用棧實現(xiàn)表達(dá)式求值216。 教學(xué)難點：利用棧實現(xiàn)表達(dá)式求值216。 授課內(nèi)容3． 棧的應(yīng)用舉例由于棧的“先進先出”特點，在很多實際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進行求解，下面通過幾個例子進行說明?！纠?】簡單應(yīng)用：數(shù)制轉(zhuǎn)換問題將十進制數(shù)N轉(zhuǎn)換為r進制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3456，r=8為例轉(zhuǎn)換方法如下： N N / 8 （整除） N % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高所以：（3456）10 =（6563）8我們看到所轉(zhuǎn)換的8進制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進制數(shù)則進棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想如下：當(dāng)N0時重復(fù)1，21． 若 N≠0，則將N % r 壓入棧s中 ，執(zhí)行2。若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。2． 用N / r 代替 N算法如下： typedef int datatype。 define L 10void conversion(int N，int r) void conversion(int N，int r){ SeqStack s。 { int s[L],top。 /*定義一個順序棧*/datetype x。 int x。Init_SeqStack(amp。s)。 top =1。 /*初始化棧*/while ( N ) while ( N ) { Push_SeqStack ( amp。s ，N % r )。 { s[++top]=N%r。 /*余數(shù)入棧 */ N=N / r 。 N=N / r 。 /* 商作為被除數(shù)繼續(xù) */ } }while ( Empty_SeqStack(amp。 s ) ) while (top!=1) { Pop_SeqStack (amp。s ，amp。x ) 。 { x=s[top]。 printf ( “ %d ”，x ) 。 printf(“%d”,x)。 } }} }(a) (b)(a)是將對棧的操作抽象為模塊調(diào)用，使問題的層次更加清楚。(b)中的直接用int向量S和int 變量top作為一個棧來使用，往往初學(xué)者將棧視為一個很復(fù)雜的東西，不知道如何使用，通過這個例子可以消除棧的“神秘”，當(dāng)應(yīng)用程序中需要一個與數(shù)據(jù)保存時相反順序使用數(shù)據(jù)時，就要想到棧。通常用順序棧較多，因為很便利。在后面的例子中，為了在算法中表現(xiàn)出問題的層次，有關(guān)棧的操作調(diào)用了的相關(guān)函數(shù)，(a)那樣，對余數(shù)的入棧操作：Push_SeqStack ( amp。s ，N % r )。 因為是用c語言描述，第一個參數(shù)是棧的地址才能對棧進行加工。在后面的例子中，為了算法的清楚易讀，在不至于混淆的情況下，不再加地址運算符，請讀者注意?！纠?】 利用棧實現(xiàn)迷宮的求解。問題： 這是實驗心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解思想：回溯法是一種不斷試探且及時糾正錯誤的搜索方法。下面的求解過程采用回溯法。從入口出發(fā)，按某一方向向前探索
公司管理相關(guān)推薦
鄂ICP備17016276號-1