[理學(xué)]第四章棧和隊(duì)列-wenkub.com
2024-10-13 21:31 本頁面
【正文】 底 end1 end2 end1 end2 3. 超隊(duì)列 超隊(duì)列是一種輸出受限的雙端隊(duì)列，即刪除限制在一端 (例如 end1) 4. 超棧是一種輸入受限的雙端隊(duì)列，即插入限制在一端（例如 end2）進(jìn)行，而刪除仍允許在兩端進(jìn)行。如無，繼續(xù)退棧，直到棧空或到達(dá)最終狀態(tài)為止。amp。 //通過 location狀態(tài)由農(nóng)夫過河引起的所有可能的安全且尚未走過的狀態(tài)提取 for (movers = 1。 因此： route數(shù)組記錄前驅(qū)狀態(tài)， 即：此狀態(tài)來自哪個(gè)狀態(tài)？ 實(shí)現(xiàn) ： p109~112 結(jié)果： p113 15, 6, 14, 2, 11, 1, 9, 0 0000 1001 0001 1011 0010 1110 0110 1111 1101 0100 while (!IsEmptyQueue_seq(moveTo) amp。（序列中不能出現(xiàn)重復(fù)狀態(tài)） 如何由某種狀態(tài)提取所有可能的、安全的、未走過的狀態(tài)？ 算法 ： moveTo整數(shù)隊(duì)列 ，元素為可以安全到達(dá)的中間狀態(tài)。 (goat(location) != farmer(location))) return(0)。amp。 0x02) != 0)。 0x08) != 0)。 廣度優(yōu)先： (m種狀態(tài)） A1 A2 A3 … Am A11 A12 … A1n A21 A22 … … 深度優(yōu)先： (m種狀態(tài)） … A12 … A111 A11 A1 … A22 … A211 A21 A2 … Am2 … Am11 Am1 Am …… 假定采用廣度優(yōu)先搜索解決農(nóng)夫過河問題 ： 采用隊(duì)列做輔助結(jié)構(gòu) ，把本步的所有狀態(tài)都放在隊(duì)列中，然后順序取出對(duì)其分別處理，處理過程中再把下一步的狀態(tài)放在隊(duì)列中， …… 。（棧應(yīng)用） 關(guān)于狀態(tài)空間搜索問題 兩種基本方式：深度優(yōu)先搜索和廣度優(yōu)先搜索 深度優(yōu)先 ：在途徑的每個(gè)分支點(diǎn)選一個(gè)分支前進(jìn)，保留其它可能分支的信息，遇到死路時(shí)回溯。 （ 2）少用一個(gè)空間，當(dāng)尾 +1 等于頭時(shí)為滿；當(dāng)頭等 于尾時(shí)為空。 int f, r。 刪除 ： p=f。 }； typedef struct LinkQueue, *PLinkQueue。 }。 } : 是一種 先進(jìn)先出 的線性表（ First In First Out, FIFO)，只允許在表的一端 (隊(duì)尾）進(jìn)行插入，另一端（隊(duì)頭）進(jìn)行刪除。 //輸出 while (!EmptyStack(s)) { v = pop(s)。v)。 scanf(%d, amp。 printf(\n)。 printf(輸出結(jié)果 :)。 i = 0。m)。如： 5*(27+3*7)+22 輸出： 5 27 3 7 *+* 22+ 棧變化： （ * + （ * * + （ * * + （ * + 掃描： *優(yōu)先級(jí) 碰到 ) 高于 + 輸出 *+(， +優(yōu)先級(jí)低于 * 當(dāng)掃描到左括號(hào)時(shí)立即推入棧，繼續(xù)掃描直到出現(xiàn)右括號(hào)時(shí)才將留在棧中的這對(duì)左右括號(hào)之間的運(yùn)算符逐一彈出輸出 。 ?掃描結(jié)束時(shí)，棧頂元素就是最后的結(jié)果。 B. 為記錄當(dāng)前位置及在該位置上所選的方向，設(shè)置一個(gè)棧，棧中每個(gè)元素包括三項(xiàng)，分別記錄當(dāng)前位置的行、列坐標(biāo)及在該位置上所選的方向。 直到?？栈蛘业匠隹跒橹?。 } 背包問題的非遞歸算法實(shí)現(xiàn)如下 ： 4. 迷宮問題 (a) 迷宮的圖形表示 (b) 迷宮的二維數(shù)組表示 求解 ： （ 1）數(shù)學(xué)模型 : 看成一個(gè)二維數(shù)組，如圖 (b)所示。 (n1))) return FALSE。 = 3 , 繼續(xù)處理 2。 轉(zhuǎn)換的做法按以下規(guī)律進(jìn)行 ： 凡調(diào)用語句 knap( s1 , n1 ) (1) = s1 ； = n1 ； = 返回地址編號(hào)； (2) Push( st, x )。 /* 返回地址，值為 1,2,3 */ int k。 } return ( res )。 n = n – 1。 } 3. 遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換 （ 1） 階乘的非遞歸計(jì)算 int nfact( int n ) { int res。(n1))) return 0。問能否從這 n件物品中選擇若干件放入此背包，使得放入的重量之和正好為 s。 3: … } 2: … } 1: … } first main second 用自身的簡(jiǎn)單情況來定義自己的方式，稱為“遞歸定義” (函數(shù)自己調(diào)用自己）。 2: … } int second(int d) { int x,y。 2）釋放被調(diào)用函數(shù)的局部變量數(shù)據(jù)區(qū) 3）按被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù) 1. 函數(shù)調(diào)用的過程 多個(gè)函數(shù)嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則進(jìn)行，如下所示： int main() { int m,n。 top= plink。 /* 棧頂指針，指向棧頂結(jié)點(diǎn) */ }。 /* 信息 */ struct Node *link。 int t。 ? 棧底 ：表頭端。這種操作限制主要體現(xiàn)在插入、刪除操作的限制，普通的線性表的插入、刪除可以在任何位置，而棧、隊(duì)列的插入、刪除數(shù)據(jù)元素的位置受到限制。 棧、隊(duì)列在系統(tǒng)軟件和應(yīng)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1