數(shù)據(jù)結(jié)構(gòu)第3章課件 中國(guó)石油大學(xué)(華東)

《數(shù)據(jù)結(jié)構(gòu)第3章課件 中國(guó)石油大學(xué)(華東)》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)第3章課件 中國(guó)石油大學(xué)(華東)（91頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 第 三 章 棧 與 隊(duì) 列 2 3.1.1 棧 的 定 義 只 允 許 在 一 端 插 入 和 刪 除 的 線 性 表 。允 許 插 入 和 刪 除 的 一 端 稱 為 棧 頂(top)， 另 一 端 稱 為 棧 底 (bottom) 特 點(diǎn)后 進(jìn) 先 出 (LIFO) 3.1 棧 ( Stack ) 退 棧 進(jìn) 棧a0an-1an-2top基 于 數(shù) 組 的 存 儲(chǔ) 表 示 實(shí) 現(xiàn) 的 棧 稱為 順 序 棧 ， 基 于 鏈 表 的 存 儲(chǔ) 表 示實(shí) 現(xiàn) 的 棧 稱 為 鏈 式 棧 。 3class SeqStack /順 序 棧 類 定 義private: int *elements;

2、/棧 元 素 存 放 數(shù) 組 int top; /棧 頂 指 針 int maxSize; /棧 最 大 容 量 棧 的 數(shù) 組 存 儲(chǔ) 表 示 順 序 棧0 1 2 3 4 5 6 7 8 9 maxSize-1top ( )elements 4 void overflowProcess(); /棧 的 溢 出 處 理public: SeqStack(int sz =50); /構(gòu) 造 函 數(shù) SeqStack() delete elements; /析 構(gòu) 函 數(shù) void Push(int /進(jìn) 棧 int Pop(int /出 棧 int getTop(int /取 棧 頂 內(nèi) 容 i

3、nt IsEmpty() const return top = -1; int IsFull() const return top = maxSize-1; int getSize() const return top+1; void MakeEmpty()top=-1; friend ostream 順 序 棧 的 構(gòu) 造 函 數(shù)#include #include SeqStack: SeqStack（ int sz） elements=new intsz;assert(elements!=NULL); top=-1;maxSize=sz; 斷 言 （ assert） 機(jī) 制 是 C+提 供

4、 的 一 種 功能 ， 若 參 數(shù) 表 中 給 定 的 條 件 滿 足 ， 則 繼 續(xù) 執(zhí) 行后 續(xù) 的 語(yǔ) 句 ； 否 則 出 錯(cuò) 處 理 終 止 程 序 的 執(zhí) 行 。 6 順 序 棧 的 溢 出 處 理void SeqStack:overflowProcess() /私 有 函 數(shù) ： 當(dāng) 棧 滿 則 執(zhí) 行 擴(kuò) 充 棧 存 儲(chǔ) 空 間 處 理 int *newArray = new int 2*maxSize;/創(chuàng) 建 更 大 的 存 儲(chǔ) 數(shù) 組 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize

5、; delete elements; elements = newArray; /改 變 elements指 針; 思 路 ： 創(chuàng) 建 更 大 的 存 儲(chǔ) 數(shù) 組 把 原 來(lái) 的 元 素 復(fù) 制 到 新 數(shù) 組 中 改 變 棧 大 小 ， 刪 除 原 來(lái) 的 數(shù) 組 ， 棧 指 針 指 向 新 數(shù) 組 7 入 棧 操 作void SeqStack:Push(int /棧 滿 elementstop+ = x; /棧 頂 指 針 先 加 1, 再 進(jìn) 棧; 出 棧 操 作int SeqStack:Pop(int x = elements-top ; /先 取 元 素 ， 棧 頂 指 針 退 1

6、return 1; /退 棧 成 功; +top top- 8 取 棧 頂 元 素int SeqStack:getTop(int x = elementstop; return 1; 輸 出 棧 中 元 素 的 重 載 操 作 ostreamfor (int i=0;i=S.top;i+)osi+1“:”S. elementsi endl; return os; 9 雙 棧 共 享 一 個(gè) 棧 空 間b0 t0 t1 b10 maxSize-1V兩 個(gè) 棧 共 享 一 個(gè) 數(shù) 組 空 間 VmaxSize設(shè) 立 棧 頂 指 針 數(shù) 組 t0 和 t1分 別 指 示 兩 個(gè) 棧 的 棧 頂初 始

7、 t0 = -1, t1 = maxSize 棧 滿 條 件 ： t0+1 = t1 /棧 頂 指 針 相 遇棧 空 條 件 ： t0 = -1或 t1 = maxSize /退 到 棧 底 10 3.1.3 棧 的 鏈 接 存 儲(chǔ) 表 示 鏈 式 棧 鏈 式 棧 無(wú) 棧 滿 問(wèn) 題 ， 空 間 可 擴(kuò) 充 插 入 與 刪 除 僅 在 棧 頂 處 執(zhí) 行 鏈 式 棧 的 棧 頂 在 鏈 頭top 11 class LinkedStack /鏈 式 棧 類 定 義 private: StackNode *top; /棧 頂 指 針 public:LinkedStack() : top(NULL)

8、 /構(gòu) 造 函 數(shù)LinkedStack() makeEmpty(); /析 構(gòu) 函 數(shù)void Push(int /進(jìn) 棧int Pop(int /退 棧int getTop(int /取 棧 頂 元 素 int IsEmpty() const return (top = NULL)? 1:0; int getSize()const;void makeEmpty(); /清 空 棧 的 內(nèi) 容friend ostream;struct StackNode /棧 結(jié) 點(diǎn) 類 型 的 定 義public: int data; /棧 結(jié) 點(diǎn) 數(shù) 據(jù) struct StackNode *link;

9、/結(jié) 點(diǎn) 鏈 指 針 StackNode(int d = 0, StackNode *next = NULL) : data(d), link(next) StackNode(); 12 鏈 式 棧 類 操 作 的 實(shí) 現(xiàn)#include 清 空 棧 操 作void LinkedStack:makeEmpty( ) /逐 次 刪 去 鏈 式 棧 中 的 元 素 直 至 棧 頂 指 針 為 空 。 StackNode *p = top-link ;while (top != NULL) /逐 個(gè) 結(jié) 點(diǎn) 釋 放 p = top; top = top-link; delete p; ;top 13

10、 入 棧 操 作void LinkedStack:Push(int /創(chuàng) 建 新 結(jié) 點(diǎn) assert (top != NULL); /創(chuàng) 建 失 敗 退 出; StackNode(int d = 0, StackNode *next = NULL) : data(d), link(next) x,top 14 出 棧 操 作int LinkedStack:Pop(int /棧 空 返 回 StackNode *p = top; /暫 存 棧 頂 元 素 top = top-link; /退 棧 頂 指 針 x = p-data; delete p; /釋 放 結(jié) 點(diǎn) return 1; 15

11、 取 棧 頂 元 素int LinkedStack:getTop(int /棧 空 返 回 x = top-data; /返 回 棧 頂 元 素 的 值 return 1;ostream StackNode *p=S.top;int i=0;while(p!=NULL)os+i“:”datalink;return os; top 算 法 基 于 原 理 ： N = (N div d) d + N mod d 3.1.4 棧 的 應(yīng) 用 -數(shù) 制 轉(zhuǎn) 換 例 如 ： （ 1348)10 = (2504)8 ， 其運(yùn) 算 過(guò) 程 如 下 ： N N div 8 N mod 81348 168 4

12、168 21 0 21 2 5 2 0 2計(jì)算順序 輸出順序 思 路 ： 初 始 化 棧 輸 入 要 轉(zhuǎn) 換 的 數(shù) 據(jù) N 當(dāng) N不 為 0,把 N%8取 余 入 棧 當(dāng) 棧 不 為 空 ， 棧 頂 元 素 出 棧 ， 輸 出 。 void conversion () LinkedStack S; int N ; cin N; while (N) S.Push( N % 8); N = N/8; cout s; 假 設(shè) 在 表 達(dá) 式 中（ （ ） ） 或 （ ） 等 為 正 確 的 格 式 ， （ ） 或 （ （ ） ） 或 （ （ ） )為 不 正 確 的 格 式 。3.1.5 棧 的

13、應(yīng) 用 -括 號(hào) 匹 配 的 檢 驗(yàn) 左 括 號(hào) 入 棧 右 括 號(hào) ， 檢 驗(yàn) 棧 空 ？ 表 達(dá) 式 檢 驗(yàn) 結(jié) 束 時(shí) ， 若 空 ， 則 匹 配 ， 若 非空 ， 則 表 明 左 括 號(hào) 多 了 。若 空 ， 表 明 右 括 號(hào) 多 了非 空 ， 與 棧 頂 元 素 比 較 匹 配 ， 棧 頂 的 左 括 號(hào) 出 棧不 匹 配 ， 出 錯(cuò) int matching(char *exp) int state = 1; i = 0;L = Length(exp);char x; while (iL) switch (expi ) case (,: S.Push(expi); break;

14、case ) : if(S.Pop(x) else return 0; case : if(S.Pop(x) else return 0; i+; if (S.StackEmpty() return 1 else return 0 if(S.Pop(x) 1. 表 達(dá) 式 的 三 種 表 示 方 法 ：設(shè) Exp = S1 OP S2則 稱 OP S1 S2 為 前 綴 表 示 法 S1 OP S2 為 中 綴 表 示 法 S1 S2 OP 為 后 綴 表 示 法 3.1.6 棧 的 應(yīng) 用 舉 例 -表 達(dá) 式 求 值 例 如 : Exp = a b + (c d / e) f前 綴 式 :

15、 + a b c / d e f中 綴 式 : a b + (c d / e) f后 綴 式 : a b c d e / f + 結(jié) 論 :1） 操 作 數(shù) 之 間 的 相 對(duì) 次 序 不 變 ;2） 運(yùn) 算 符 的 相 對(duì) 次 序 不 同 ;3） 中 綴 式 有 操 作 符 的 優(yōu) 先 級(jí) 問(wèn) 題 ， 還 有 可 加 括 號(hào) 改變 運(yùn) 算 順 序 的 問(wèn) 題 ， 所 以 編 譯 程 序 一 般 不 使 用 中 綴 表示 處 理 表 達(dá) 式 。 例 如 : Exp = 2 3 + (4 5 / 6) 7前 綴 式 : + 2 3 4 / 5 6 7中 綴 式 : 2 3 + (4 5 / 6)

16、 7后 綴 式 : 2 3 4 5 6 / 7 + 結(jié) 論 :4)前 綴 式 的 運(yùn) 算 規(guī) 則 為 : 連 續(xù) 出 現(xiàn) 的 兩 個(gè) 操 作 數(shù) 和 在 它 們 之 前 且 緊 靠 它 們的 一 個(gè) 運(yùn) 算 符 構(gòu) 成 一 個(gè) 最 小 表 達(dá) 式 ;5)后 綴 式 的 運(yùn) 算 規(guī) 則 為 : 連 續(xù) 出 現(xiàn) 的 兩 個(gè) 操 作 數(shù) 和 在 它 們 之 后 且 緊 靠 它 們 的一 個(gè) 運(yùn) 算 符 構(gòu) 成 一 個(gè) 最 小 表 達(dá) 式 ; 2.如 何 從 后 綴 式 求 值 ？遇 到 運(yùn) 算 數(shù) 則 入 棧 ，遇 到 操 作 數(shù) 則 2個(gè) 數(shù) 出 棧 ， 計(jì) 算 ， 結(jié) 果 入 棧例 如 ： 2

17、3 4 5 6 / 7 + 模 擬 一 個(gè) 簡(jiǎn) 單 的 后 綴 表 達(dá) 式 計(jì) 算 器Calculator類 的 定 義 ：class Calculatorpublic: Calculator(int sz)S=sz; void Run(); /執(zhí) 行 表 達(dá) 式 計(jì) 算 ； 類 似 于 主 程 序 :輸 入 數(shù) 字 和 操 作 符 ， 若 數(shù) 字 則 調(diào) 用AddOperand； 符 號(hào) 則 調(diào) 用 DoOperator；void Clear();private: SeqStack S; void AddOperand(double value); /操 作 數(shù) 進(jìn) 棧 int Get2Op

18、erands(double /從 操 作 數(shù) 棧 中 取 出 兩 個(gè) 操 作 數(shù) void DoOperator(char op); /pop出 兩 個(gè) 操 作 數(shù) (Get2Operands)， 進(jìn) 行 op 計(jì) 算 ， 將 計(jì) 算 結(jié) 果 入 棧 (AddOperand); 將 操 作 數(shù) 的 值 value入 操 作 數(shù) 棧void Calculator: AddOperand(double value)S.Push(value); 清 棧void Calculator: Clear() S.MakeEmpty(); 從 操 作 數(shù) 棧 中 取 出 兩 個(gè) 操 作 數(shù)int Calcul

19、ator:Get2Operands(doublereturn 0;S.Pop(right); if (S.IsEmpty()cerr“缺 少 左 操 作 數(shù) ！ ”newOperand; /讀 取 操 作 數(shù) AddOperand(newOperand); /加 入 到 操 作 數(shù) 棧 S.Pop(newoperand ); cout newoperand; /輸 出 計(jì) 算 結(jié) 果 ; 取 兩 個(gè) 操 作 數(shù) ， 根 據(jù) 操 作 符 op計(jì) 算void Calculator: DoOperator(char op) double left,right,value; if (get2Opera

20、nds(left, right) switch(op) case +: value=left+right;S.Push(value);break; case -: value=left-right;S.Push(value);break; case *: value=left*right;S.Push(value);break; case /: if (right=0.0) cerr“Divide by 0!”isp則 入 棧 ； icp isp(op)， 令 ch進(jìn) 棧 ， 讀 入 下 一 個(gè) 字 符 ch。u 若 icp(ch) isp(op)， 出 棧 、 輸 出 、 不 讀 ,ch繼

21、續(xù) 比 較 。u 若 icp(ch) = isp(op)， 出 棧 但 不 輸 出 ， 若 退 出 的 是“ (”號(hào) ， 則 讀 入 下 一 個(gè) 字 符 ch。 算 法 結(jié) 束 ， 輸 出 序 列 即 為 所 需 的 后 綴 表 達(dá) 式 。 例 ： 中 綴 表 達(dá) 式 為 A+B*(C-D)-E/F,求 其 后 綴 表 達(dá) 式 。ABCD-*+EF/- 37 中 綴 表 達(dá) 式 轉(zhuǎn) 換 為 后 綴 表 達(dá) 式 的 算 法 ：void postfix(expression e) /把 中 綴 表 達(dá) 式 e轉(zhuǎn) 換 成 后 綴 表 示 并 輸 出 Stack S; char ch=#,ch1,op

22、; S.Push(ch);cin.get(ch); While(!S.IsEmpty()cin.get(ch);else S.getTop(ch1); if (isp(ch1)icp(ch) S.Pop(op);cout isp(OPTR)， 則 ch進(jìn) OPTR棧 ， 讀 下 一 字 符 到 ch；u若 icp(ch) isp(OPTR)， 則 從 OPND棧 退 出 a2和 a1， 從 OPTR棧 退 出 , 形 成 運(yùn) 算 指 令 (a1)(a2)， 結(jié) 果 進(jìn) OPND棧 ,不 讀 入 讀下 一 字 符 而 是 繼 續(xù) 比 較 棧 頂 元 素 ；u若 icp(ch) = isp(OPT

23、R) 且 ch = )， 則 從 OPTR棧 退 出 (，對(duì) 消 括 號(hào) ， 然 后 從 中 綴 表 達(dá) 式 取 下 一 字 符 送 入 ch 41 void InFixRun() SeqStack OPTR, SeqStack OPND; char ch, op; double x; OPTR.Push(#); cin.get (ch); /讀 入 一 個(gè) 字 符 op = # ; while (ch != # | op != #) if (isdigit(ch) /是 操 作 數(shù) , 進(jìn) 棧 cin.putback(ch);cinx OPND.Push(x); cin.get(ch); e

24、lse /是 操 作 符 , 比 較 優(yōu) 先 級(jí) OPTR.GetTop(op); /讀 一 個(gè) 操 作 符 42 if(icp(ch) isp(op) /棧 頂 優(yōu) 先 級(jí) 低 OPTR.Push (ch); cin.get(ch); else if (icp(ch) link = NULL) cout data link); f f f f f a0 a1 a2 a3 a4遞 歸 找 鏈 尾3. 問(wèn) 題 的 解 法 是 遞 歸 的 47 在 鏈 表 中 尋 找 等 于 給 定 值 的 結(jié) 點(diǎn) 并 打 印 其 數(shù) 值void Print(ListNode*f, int value) if (

25、f != NULL) if (f - data = value) cout data link, value); f f f f 遞 歸 找 含 value值 的 結(jié) 點(diǎn)x 48 構(gòu) 成 遞 歸 的 條 件 不 能 無(wú) 限 制 地 調(diào) 用 本 身 ， 必 須 有 一 個(gè) 出 口 ，化 簡(jiǎn) 為 非 遞 歸 狀 況 直 接 處 理 。Procedure ( ) if ( ) /遞 歸 結(jié) 束 條 件 return ( initial value ); else /遞 歸 return ( ( parameter exchange ); 49 遞 歸 過(guò) 程 在 實(shí) 現(xiàn) 時(shí) ， 需 要 自 己 調(diào)

26、用 自 己 。 層 層 向 下 遞 歸 ， 退 出 時(shí) 的 次 序 正 好 相 反 ： 遞 歸 調(diào) 用 n! (n-1)! (n-2)! 1! 0!=1 返 回 次 序 主 程 序 第 一 次 調(diào) 用 遞 歸 過(guò) 程 為 外 部 調(diào) 用 ； 遞 歸 過(guò) 程 每 次 遞 歸 調(diào) 用 自 己 為 內(nèi) 部 調(diào) 用 。3.2.2遞 歸 過(guò) 程 與 遞 歸 工 作 棧 50 long Factorial(long n) int temp; if (n = 0) return 1; else temp = n * Factorial(n-1); return temp; void main() int r

27、esult; result = Factorial(4); cout result endl; 外 部 調(diào) 用內(nèi) 部 調(diào) 用 51 1. 遞 歸 工 作 棧 每 一 次 遞 歸 調(diào) 用 時(shí) ， 需 要 為 過(guò) 程 中 使 用 的參 數(shù) 、 局 部 變 量 等 另 外 分 配 存 儲(chǔ) 空 間 。 每 層 遞 歸 調(diào) 用 需 分 配 的 空 間 形 成 遞 歸 工 作記 錄 ， 按 后 進(jìn) 先 出 的 棧 組 織 。 棧 頂 的 工 作 記 錄 是 當(dāng) 前 正 在 執(zhí) 行 的 這 一 層的 工 作 記 錄 。 稱 之 為 活 動(dòng) 記 錄 。 遞 歸工 作 記 錄 52 2. 遞 歸 過(guò) 程 改 為

28、 非 遞 歸 過(guò) 程 遞 歸 過(guò) 程 簡(jiǎn) 潔 、 易 編 、 易 懂 ， 但 是 效 率 低 ， 重 復(fù) 計(jì) 算 多 。 單 向 遞 歸 和 尾 遞 歸 可 直 接 用 迭 代 實(shí) 現(xiàn) 其 非 遞 歸 過(guò) 程 ， 其 他 情形 必 須 借 助 棧 實(shí) 現(xiàn) 非 遞 歸 過(guò) 程 ； 改 為 非 遞 歸 過(guò) 程 的 目 的 是 提高 效 率 。 1.迭 代 法 ： 尾 遞 歸 ： 遞 歸 語(yǔ) 句 只 有 一 個(gè) ， 而 且 在 程 序 最 后 ， 因 為 是尾 部 , 所 以 根 本 沒(méi) 有 必 要 去 保 存 任 何 局 部 變 量 。 單 向 遞 歸 ： 雖 然 有 多 處 遞 歸 調(diào) 用 語(yǔ)

29、句 ， 但 各 遞 歸 調(diào) 用 語(yǔ)句 的 參 數(shù) 之 間 沒(méi) 有 關(guān) 系 ， 并 且 這 些 遞 歸 調(diào) 用 語(yǔ) 句 都 處 在遞 歸 算 法 的 最 后 。 顯 然 ， 尾 遞 歸 是 單 向 遞 歸 的 特 例 。 例如 求 斐 波 那 契 數(shù) 列 的 遞 歸 算 法 。 2.其 他 的 遞 歸 ： 用 棧 實(shí) 現(xiàn) 。 53調(diào) 用 次 數(shù) NumCall(k) =斐 波 那 契 數(shù) 列 的 遞 歸 調(diào) 用 樹Fi b(1) Fi b(0)Fi b(1)Fi b(2) Fi b(3) Fi b(4)Fi b(1) Fi b(0)Fi b(2) Fi b(1) Fi b(0)Fi b(1)Fi

30、 b(2)Fi b(3)Fi b(5)時(shí) 間 復(fù) 雜 度 ： 2n如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 52*Fib(k+1)-1 54 斐 波 那 契 數(shù) 列 的 函 數(shù) Fib(n)的 定 義求 解 斐 波 那 契 數(shù) 列 的 遞 歸 算 法 long Fib(long n) if (n = 1) return n; else return Fib(n-1)+Fib(n-2); 1n2),Fib(n1)Fib(n 0,1nn,)Fib(n如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5

31、55 尾 遞 歸 用 迭 代 法 實(shí) 現(xiàn) 對(duì) 于 尾 遞 歸 形 式 的 遞 歸 算 法 ， 可 以 利 用 循 環(huán) 結(jié) 構(gòu) 來(lái) 替 代 。 例如 求 階 乘 的 遞 歸 算 法 可 以 寫 成 如 下 循 環(huán) 結(jié) 構(gòu) 的 非 遞 歸 算 法 ：long fact(int n) int s=0; for (int i=1; i=n;i+) s=s*i; /用 s保 存 中 間 結(jié) 果 return s; 56 單 向 遞 歸 用 迭 代 法 實(shí) 現(xiàn) 對(duì) 于 單 向 遞 歸 ， 可 以 設(shè) 置 一 些 變 量 保 存 中 間 結(jié) 構(gòu) ， 將 遞歸 結(jié) 構(gòu) 用 循 環(huán) 結(jié) 構(gòu) 來(lái) 替 代 。 例

32、如 求 斐 波 那 契 數(shù) 列 的 算 法 中 用s1和 s2保 存 中 間 的 計(jì) 算 結(jié) 果 ， 非 遞 歸 函 數(shù) 如 下 ：int f(int n) int i, s; int s1=1, s2=1; for (i=3; i=n; +i) s=s1+s2; s2=s1; / 保 存 f(n-2)的 值 s1=s; /保 存 f(n-1)的 值 return s; 2. 間 接 轉(zhuǎn) 換 法該 方 法 使 用 棧 保 存 中 間 結(jié) 果 ， 一 般 需 根 據(jù) 遞 歸 函 數(shù) 在 執(zhí)行 過(guò) 程 中 棧 的 變 化 得 到 。 其 一 般 過(guò) 程 如 下 ：將 初 始 狀 態(tài) s0進(jìn) 棧wh

33、ile (棧 不 為 空 ) 退 棧 ， 將 棧 頂 元 素 賦 給 s; if (s是 要 找 的 結(jié) 果 ) 返 回 ; else 尋 找 到 s的 相 關(guān) 狀 態(tài) s1; 將 s1進(jìn) 棧 58 3.3 隊(duì) 列 ( Queue ) 定 義u 隊(duì) 列 是 只 允 許 在 一 端 刪 除 ， 在 另 一 端 插 入的 線 性 表u 允 許 刪 除 的 一 端 叫 做 隊(duì) 頭 (front)， 允 許 插入 的 一 端 叫 做 隊(duì) 尾 (rear)。 特 性 ： 先 進(jìn) 先 出 (FIFO, First In First Out)a0 a1 a2 an-1front rear 59 class

34、Queue public: Queue() ; /構(gòu) 造 函 數(shù) Queue() ; /析 構(gòu) 函 數(shù) virtual int EnQueue(int x) = 0; /進(jìn) 隊(duì) 列 virtual int DeQueue(int /出 隊(duì) 列 virtual int getFront(int /取 隊(duì) 頭 virtual int IsEmpty() const = 0; /判 隊(duì) 列 空 virtual int IsFull() const = 0; /判 隊(duì) 列 滿; 隊(duì) 列 的 抽 象 數(shù) 據(jù) 類 型 60 隊(duì) 列 的 進(jìn) 隊(duì) 和 出 隊(duì)front rear 空 隊(duì) 列 front rea

35、r A進(jìn) 隊(duì)Afront rear B進(jìn) 隊(duì)A B front rear C, D進(jìn) 隊(duì)A B C Dfront rear A退 隊(duì)B C D front rear B退 隊(duì)C Dfront rear E,F,G進(jìn) 隊(duì)C D E F G C D E F Gfront rear H進(jìn) 隊(duì) ,溢 出假 溢 出3.3.2 隊(duì) 列 的 數(shù) 組 存 儲(chǔ) 表 示 順 序 隊(duì) 列 61 隊(duì) 列 的 進(jìn) 隊(duì) 和 出 隊(duì) 原 則進(jìn) 隊(duì) 時(shí) 先 將 新 元 素 按 rear 指 示 位 置 加 入 ， 再將 隊(duì) 尾 指 針 加 一 rear = rear + 1。隊(duì) 尾 指 針 指 示 實(shí) 際 隊(duì) 尾 的 后 一

36、 位 置 。出 隊(duì) 時(shí) 先 按 隊(duì) 頭 指 針 指 示 位 置 取 出 元 素 ， 再將 隊(duì) 頭 指 針 進(jìn) 一 front = front + 1，隊(duì) 頭 指 針 指 示 實(shí) 際 隊(duì) 頭 位 置 。隊(duì) 滿 時(shí) 再 進(jìn) 隊(duì) 將 溢 出 出 錯(cuò) ；隊(duì) 空 時(shí) 再 出 隊(duì) 將 隊(duì) 空 處 理 。解 決 假 溢 出 的 辦 法 ?將 隊(duì) 列 元 素 存 放 數(shù) 組 首 尾 相 接 ， 形 成 循 環(huán)（ 環(huán) 形 ） 隊(duì) 列 。 62 012345 6 7 front 012345 6 7 front012345 6 7 frontrear A ABCrearrear空 隊(duì) 列 A進(jìn) 隊(duì) B, C進(jìn) 隊(duì)

37、012345 6 7 012345 6 7A退 隊(duì) B退 隊(duì) 012345 6 7D,E,F,G,H,I 進(jìn) 隊(duì) (隊(duì) 滿 )frontBCrear A frontBCrear frontC rearDEFG H I 63 隊(duì) 列 存 放 數(shù) 組 被 當(dāng) 作 首 尾 相 接 的 表 處 理 。隊(duì) 頭 、 隊(duì) 尾 指 針 加 1時(shí) 從 maxSize-1直 接 進(jìn) 到 0，可 用 取 模 (余 數(shù) )運(yùn) 算 實(shí) 現(xiàn) 。隊(duì) 頭 指 針 進(jìn) 1:隊(duì) 尾 指 針 進(jìn) 1:隊(duì) 列 初 始 化 ：隊(duì) 空 條 件 ：隊(duì) 滿 條 件 ： 循 環(huán) 隊(duì) 列 (Circular Queue)front = (fro

38、nt+1) % maxSize;rear = (rear+1) % maxSize;front = rear = 0;front = rear; (rear+1) % maxSize = = front012345 6 7 front空 隊(duì) 列 rear 64 #include #include class SeqQueue /隊(duì) 列 類 定 義protected: int rear, front; /隊(duì) 尾 與 隊(duì) 頭 指 針 int*elements; /隊(duì) 列 存 放 數(shù) 組 int maxSize; /隊(duì) 列 最 大 容 量public: SeqQueue(int sz = 10);

39、/構(gòu) 造 函 數(shù) 循 環(huán) 隊(duì) 列 的 類 定 義 65 SeqQueue() delete elements; /析 構(gòu) 函 數(shù) int EnQueue(int x); /新 元 素 進(jìn) 隊(duì) 列 int DeQueue(int /退 出 隊(duì) 頭 元 素 int getFront(int /取 隊(duì) 頭 元 素 值 void makeEmpty() front = rear = 0; int IsEmpty() const return front = rear; int IsFull() const return (rear+1)% maxSize = front); int getSize()

40、 const return (rear-front+maxSize) % maxSize; friend ostream/輸 出 隊(duì) 列 中 元 素 的 重 載 操 作 ; 66 循 環(huán) 隊(duì) 列 操 作 的 定 義 構(gòu) 造 函 數(shù)SeqQueue:SeqQueue(int sz) /構(gòu) 造 函 數(shù) front=0; rear=0; maxSize=sz; elements = new intmaxSize; assert ( elements != NULL ); 67 int SeqQueue:EnQueue(int elementsrear = x; /先 存 入 rear = (rear

41、+1) % maxSize; /尾 指 針 加 一 return 1;int SeqQueue:DeQueue(int x = elementsfront; /先 取 隊(duì) 頭 front = (front+1) % maxSize; /再 隊(duì) 頭 指 針 加 一 return 1; 68 3.3.3 隊(duì) 列 的 鏈 接 存 儲(chǔ) 表 示 鏈 式 隊(duì) 列 隊(duì) 頭 在 鏈 頭 ， 隊(duì) 尾 在 鏈 尾 。 鏈 式 隊(duì) 列 在 進(jìn) 隊(duì) 時(shí) 無(wú) 隊(duì) 滿 問(wèn) 題 ， 但 有 隊(duì) 空 問(wèn)題 。 隊(duì) 空 條 件 為 front = NULLfront rear 69 #include struct QueueN

42、ode /隊(duì) 列 結(jié) 點(diǎn) 類 定 義private: int data; /隊(duì) 列 結(jié) 點(diǎn) 數(shù) 據(jù) QueueNode *link; /結(jié) 點(diǎn) 鏈 指 針public: QueueNode(int d = 0, QueueNode *next = NULL) : data(d), link(next) ; 鏈 式 隊(duì) 列 類 的 定 義 70 class LinkedQueue private: QueueNode *front, *rear; /隊(duì) 頭 、 隊(duì) 尾 指 針public: LinkedQueue() : rear(NULL), front(NULL) LinkedQueue(M

43、akeEmpty(); int EnQueue(int int DeQueue(int int GetFront(int void MakeEmpty(); int IsEmpty() const return (front = NULL)?1:0 ; int getSize( )const; friend ostream delete p; ; front rear p 72 將 新 元 素 x插 入 到 隊(duì) 列 的 隊(duì) 尾int LinkedQueue:EnQueue(int if (front = NULL) return 0; /分 配 失 敗 else /隊(duì) 列 不 空 , 插 入

44、rear-link = new QueueNode(x); if (rear-link = NULL) return 0; /分 配 失 敗 rear = rear-link; return 1;front rearfrontrear frontrear 73 如 果 隊(duì) 列 不 空 ， 將 隊(duì) 頭 結(jié) 點(diǎn) 從 鏈 式 隊(duì) 列 中 刪 去 int LinkedQueue:DeQueue(int /判 隊(duì) 空 QueueNode *p = front; x = front-data; front = front-link; delete p; return 1; 若 隊(duì) 列 不 空 ， 則 函

45、數(shù) 以 引 用 返 回 隊(duì) 頭 元 素 的 值 int LinkedQueue:GetFront(int x = front-data; return 1; front rear p 74 求 隊(duì) 列 元 素 個(gè) 數(shù) int LinkedQueue:getSize( )const QueueNode *p = front; int k=0; while(p!=NULL) k+; p= p-link; return k; 輸 出 隊(duì) 列 中 元 素 的 重 載 操 作 ostream QueueNode *p = front; int i=0; while(p!=NULL) os+i“:”dat

46、alink; ; front rear p 75 3.3.4 隊(duì) 列 的 應(yīng) 用 ： 打 印 楊 輝 三 角 形 逐 行 打 印 二 項(xiàng) 展 開 式 (a + b)i 的 系 數(shù) ： 楊 輝三 角 形 (Pascals triangle) 分 析 第 i 行 元 素 與 第 i+1行 元 素 的 關(guān) 系從 前 一 行 的 數(shù) 據(jù) 可 以 計(jì) 算 下 一 行 的 數(shù) 據(jù)i = 2i = 3i = 4 0 1 3 3 1 01 4 6 4 10 1 2 1 00 1 1 0s t s+t 從 第 i 行 數(shù) 據(jù) 計(jì) 算 并 存 放 第 i+1 行 數(shù) 據(jù) 1 1 0 1 2 1 0 1 3 3 1

47、 0 int s=0,t; 利 用 隊(duì) 列 打 印 二 項(xiàng) 展 開 式 系 數(shù) 的 算 法#include #include #include queue.hvoid YANGHUI(int n) SeqQueue q(n+2); /隊(duì) 列 初 始 化 p121 q.EnQueue(1); q.EnQueue(1); int s = 0, t; for (int i = 1; i = n; i+) /逐 行 計(jì) 算 cout endl; q.EnQueue(0); for (int j = 1; j = i+2; j+) /下 一 行 q.DeQueue(t); q.EnQueue(s + t

48、); s = t; if (j != i+2) cout s ; 改 進(jìn) :楊 輝 三 角 格 式 輸 出 80 3.4 優(yōu) 先 級(jí) 隊(duì) 列 (Priority Queue) 優(yōu) 先 級(jí) 隊(duì) 列 :每 次 從 隊(duì) 列 中 取 出 的 是 具 有最 高 優(yōu) 先 權(quán) 的 元 素 如 下 表 ： 任 務(wù) 優(yōu) 先 權(quán) 及 執(zhí) 行 順 序 的 關(guān) 系 81 #include #include #include class PQueue private: int *pqelements; /存 放 數(shù) 組 int count; /隊(duì) 列 元 素 計(jì) 數(shù) int maxPQSize; /最 大 元 素 個(gè)

49、數(shù) void adjust(); /調(diào) 整最 小 優(yōu) 先 級(jí) 隊(duì) 列 的 類 定 義 82 public: PQueue(int sz = 50); PQueue() delete pqelements; int Insert(int int RemoveMin(int int GetFront(int void MakeEmpty() count = 0; int IsEmpty() const return count = 0; int IsFull() const return count = maxPQSize; int Length() const return count; ; 8

50、3 構(gòu) 造 函 數(shù)PQueue:PQueue(int sz) maxPQSize = sz; count = 0; pqelements = new intmaxPQSize; assert (pqelements != NULL); 插 入 元 素int PQueue:Insert(int x) if (IsFull( ) return 0; /判 隊(duì) 滿 pqelementscount+ = x; /插 入 adjust(); return 1; /p125 84 10 20 40 50 70 90 插 入 6010 20 40 50 70 90 606010 20 40 50 70 90

51、 606097610 20 40 50 60 70 90jjj j 85 按 優(yōu) 先 權(quán) 調(diào) 整 元 素 位 置 操 作 void PQueue:adjust() int temp = pqelementscount-1; /將 最 后 元 素 暫 存 再 從 后 向 前 找 插 入 位 置 for (int j = count-2; j = 0; j-) if (pqelementsj = temp) break; else pqelementsj+1 = pqelementsj; pqelementsj+1 = temp; 10 20 40 50 70 90 60jtemp 86 具 有

52、最 小 優(yōu) 先 級(jí) 的 元 素 出 隊(duì)int PQueue:RemoveMin(int x = pqelements0; /取 出 0號(hào) 元 素 for (int i = 1; i count; i+) pqelementsi-1 = pqelementsi; /從 后 向 前 逐 個(gè) 移 動(dòng) 元 素 填 補(bǔ) 空 位 count-; return 1; 10 20 40 50 60 70 90 87 取 隊(duì) 頭 元 素int PQueue:GetFront (int x = pqelements0; return 1; 10 20 40 50 60 70 90 1. 掌 握 棧 和 隊(duì) 列 類

53、 型 的 特 點(diǎn) ， 并 能 在 相 應(yīng)的 應(yīng) 用 問(wèn) 題 中 正 確 選 用 它 們 。 2. 熟 練 掌 握 棧 類 型 的 兩 種 實(shí) 現(xiàn) 方 法 ， 特 別 應(yīng)注 意 棧 滿 和 棧 空 的 條 件 以 及 它 們 的 描 述 方 法 。 3. 熟 練 掌 握 循 環(huán) 隊(duì) 列 和 鏈 隊(duì) 列 的 基 本 操 作 實(shí)現(xiàn) 算 法 ， 特 別 注 意 循 環(huán) 隊(duì) 列 隊(duì) 滿 和 隊(duì) 空 的 描 述方 法 。 4. 理 解 遞 歸 算 法 執(zhí) 行 過(guò) 程 中 棧 的 狀 態(tài) 變 化 過(guò)程 。 本 章 學(xué) 習(xí) 要 點(diǎn) 思 考 ： 給 定 (已 生 成 )一 個(gè) 帶 表 頭 結(jié) 點(diǎn)的 單 鏈 表 ， 設(shè) head為 頭 指 針 ， 結(jié) 點(diǎn)的 結(jié) 構(gòu) 為 (data,next),data為 整 型 元素 ， next為 指 針 ， 試 寫 出 算 法 :通過(guò) 遍 歷 一 趟 鏈 表 ， 將 鏈 表 中 所 有 結(jié)點(diǎn) 按 逆 序 鏈 接 。