武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用-展示頁
2025-07-08 14:48本頁面
【正文】 N % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高所以：（3456）10 =（6563）8我們看到所轉(zhuǎn)換的8進(jìn)制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。 教學(xué)難點(diǎn)：利用棧實(shí)現(xiàn)表達(dá)式求值216。216。第三章 棧和隊列第九講 棧的應(yīng)用 1．鞏固棧的定義及表示。2．掌握棧的應(yīng)用方法,理解棧的重要作用。 教學(xué)重點(diǎn)： 利用棧實(shí)現(xiàn)表達(dá)式求值216。 授課內(nèi)容3． 棧的應(yīng)用舉例由于棧的“先進(jìn)先出”特點(diǎn)，在很多實(shí)際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行求解，下面通過幾個例子進(jìn)行說明。算法思想如下：當(dāng)N0時重復(fù)1，21． 若 N≠0，則將N % r 壓入棧s中 ，執(zhí)行2。2． 用N / r 代替 N算法如下： typedef int datatype。 { int s[L],top。 int x。s)。 /*初始化棧*/while ( N ) while ( N ) { Push_SeqStack ( amp。 { s[++top]=N%r。 N=N / r 。 s ) ) while (top!=1) { Pop_SeqStack (amp。x ) 。 printf ( “ %d ”，x ) 。 } }} }(a) (b)(a)是將對棧的操作抽象為模塊調(diào)用，使問題的層次更加清楚。通常用順序棧較多，因?yàn)楹鼙憷?。s ，N % r )。在后面的例子中，為了算法的清楚易讀，在不至于混淆的情況下，不再加地址運(yùn)算符，請讀者注意。問題： 這是實(shí)驗(yàn)心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處趕進(jìn)迷宮。求解思想：回溯法是一種不斷試探且及時糾正錯誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向 。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無路）時，能正確返回前一點(diǎn)以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。 其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時，中間點(diǎn)有8個方向可以試探，（）而四個角點(diǎn)有3個方向，其它邊緣點(diǎn)有5個方向，為使問題簡單化我們用maze[m+2][n+2]來表示迷宮，而迷宮的四周的值全部為1。 8的迷宮。 入口(1,1) 01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111 出口 (6,8) 圖 用maze[m+2][n+2]表示的迷宮迷宮的定義如下：define m 6 /* 迷宮的實(shí)際行 */define n 8 /* 迷宮的實(shí)際列 */int maze [m+2][n+2] 。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時針方向進(jìn)行。Move數(shù)組定義如下：typedef struct
公司管理相關(guān)推薦
鄂ICP備17016276號-1