[理學(xué)]第四章棧和隊列-展示頁
2024-10-25 21:31本頁面
【正文】 mp。 A. 分析問題，得到數(shù)學(xué)模型 1 當(dāng) s = 0 0 當(dāng) s 0 knap( s , n ) = 0 當(dāng) s 0 且 n 1 knap( s , n 1 ) 或 knap( s wn , n 1 ) 當(dāng) s 0 且 n ≥ 1 選擇的一組物品中不包含 wn 選擇的一組物品中包含 wn 不選擇任何物品 無法實現(xiàn) 無物品可選 B. 設(shè)計算法：遞歸算法 C. 程序設(shè)計： int knap(int s,int n) { if ( s == 0 ) return 1。 } 2. 遞歸的概念及遞歸調(diào)用過程 （ 2）簡化的背包問題 * 設(shè)有一個背包可以放入的物品重量為 s，現(xiàn)有 n件物品，重量分別為 w1, w2, … ， wn。 （ 1）階乘： if n=0, then n!= 1 else n! = n(n1)! 遞歸實現(xiàn) ： int factorial(int n) { if(n == 1) return 1。 … { int x,y。 3: … } 如果改成用一個函數(shù)，則如下所示： int main() { int m,n。 … second(i)。 ... first(m,n)。 返回 ： 1）保存被調(diào)用函數(shù)的計算結(jié)果。 free(p)。 鏈接實現(xiàn) 2. 鏈接表示 棧空條件 ： plstacktop = NULL 下溢條件 ： if (plstacktop == NULL) 還要繼續(xù)刪除 棧頂元素 ： plstacktop 壓入元素 ：在 top與棧頂之間插入 s （ slink = top, top = s) 彈出元素 ：刪除棧頂元素 ( p = top。 typedef struct LinkStack *PLinkStack。 鏈接棧類型定義 struct LinkStack { PStackNode top。 /* 下一個結(jié)點 */ }。 順序?qū)崿F(xiàn) pastackt: 棧頂指示變量 pastacks: 存放棧元素的數(shù)組 pastacks[pastackt]：棧頂元素 A A B C D A B t = 1 t = 0 t = 3 t = 1 t = 1 空棧 壓入 A 壓入 B C D 刪除 D C 刪除 B A(空 ) t 棧的插入、刪除 棧滿條件 ： t = MAXNUM1 棧上溢條件 ： t = MAXNUM ?？諚l件 ： t = 1 棧下溢條件 ： t 1 單鏈表結(jié)點結(jié)構(gòu) struct Node { ElemType info。 /* 指示棧頂位置，空棧 =1 */ } typedef struct SeqStack, *PSeqStack。 an ... a2 a1 棧底 棧頂 出棧 進(jìn)棧 棧的表示和實現(xiàn) 1. 順序表示 順序棧類型定義 : define MAXNUM 1000 /* 最大容量 */ struct SeqStack { ElemType s[MAXNUM]。 棧及其基本運算 an ... a2 a1 棧底 棧頂 出棧 進(jìn)棧 ?棧的修改原則 ：按 后進(jìn)先出（ Last In First Out， LIFO）的原則進(jìn)行插入、刪除運算。 ? 棧頂 ：表尾端，元素從這端進(jìn)行插入和刪除。 棧、隊列在系統(tǒng)軟件和應(yīng)用軟件設(shè)計中應(yīng)用廣泛?；緝?nèi)容 ： ? 棧 ? 棧的實現(xiàn) ? 棧的應(yīng)用 ?遞歸調(diào)用 ?迷宮問題 ? 隊列 ? 隊列的實現(xiàn) ? 隊列的應(yīng)用 第四章 棧和隊列 棧和隊列是 操作受限 的線性表。這種操作限制主要體現(xiàn)在插入、刪除操作的限制，普通的線性表的插入、刪除可以在任何位置，而棧、隊列的插入、刪除數(shù)據(jù)元素的位置受到限制。 1. 基本概念 ? 棧 ：是限定在 表尾 進(jìn)行插入和刪除操作的線性表；插入、刪除在表的同一端進(jìn)行。 ? 棧底 ：表頭端。 ?棧的插入 ：進(jìn)棧 ?棧的刪除 ：退棧 2. 棧的基本運算 ? 創(chuàng)建一個空棧； ? 判斷棧是否為空棧； ? 往棧中插入一個元素； ? 從棧中刪除一個元素； ? 取棧頂元素的值。 int t。 PSeqStack pastack。 /* 信息 */ struct Node *link。 typedef struct Node *PStackNode。 /* 棧頂指針，指向棧頂結(jié)點 */ }。 PLinkStack plstack。 top= plink。 ) …… info link ^ plstacktop D C B …… info link ^ plstacktop C B …… inf
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1