數(shù)據(jù)結構第3章課件 中國石油大學(華東)

《數(shù)據(jù)結構第3章課件 中國石油大學(華東)》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構第3章課件 中國石油大學(華東)（91頁珍藏版）》請在裝配圖網上搜索。

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

2、/棧 元 素 存 放 數(shù) 組 int top; /棧 頂 指 針 int maxSize; /棧 最 大 容 量 棧 的 數(shù) 組 存 儲 表 示 順 序 棧0 1 2 3 4 5 6 7 8 9 maxSize-1top ( )elements 4 void overflowProcess(); /棧 的 溢 出 處 理public: SeqStack(int sz =50); /構 造 函 數(shù) SeqStack() delete elements; /析 構 函 數(shù) void Push(int /進 棧 int Pop(int /出 棧 int getTop(int /取 棧 頂 內 容 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 順 序 棧 的 構 造 函 數(shù)#include #include SeqStack: SeqStack（ int sz） elements=new intsz;assert(elements!=NULL); top=-1;maxSize=sz; 斷 言 （ assert） 機 制 是 C+提 供

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

5、; delete elements; elements = newArray; /改 變 elements指 針; 思 路 ： 創(chuàng) 建 更 大 的 存 儲 數(shù) 組 把 原 來 的 元 素 復 制 到 新 數(shù) 組 中 改 變 棧 大 小 ， 刪 除 原 來 的 數(shù) 組 ， 棧 指 針 指 向 新 數(shù) 組 7 入 棧 操 作void SeqStack:Push(int /棧 滿 elementstop+ = x; /棧 頂 指 針 先 加 1, 再 進 棧; 出 棧 操 作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 雙 棧 共 享 一 個 棧 空 間b0 t0 t1 b10 maxSize-1V兩 個 棧 共 享 一 個 數(shù) 組 空 間 VmaxSize設 立 棧 頂 指 針 數(shù) 組 t0 和 t1分 別 指 示 兩 個 棧 的 棧 頂初 始

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

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

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

10、 入 棧 操 作void LinkedStack:Push(int /創(chuàng) 建 新 結 點 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; /釋 放 結 點 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 棧 的 應 用 -數(shù) 制 轉 換 例 如 ： （ 1348)10 = (2504)8 ， 其運 算 過 程 如 下 ： N N div 8 N mod 81348 168 4

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

13、應 用 -括 號 匹 配 的 檢 驗 左 括 號 入 棧 右 括 號 ， 檢 驗 棧 空 ？ 表 達 式 檢 驗 結 束 時 ， 若 空 ， 則 匹 配 ， 若 非空 ， 則 表 明 左 括 號 多 了 。若 空 ， 表 明 右 括 號 多 了非 空 ， 與 棧 頂 元 素 比 較 匹 配 ， 棧 頂 的 左 括 號 出 棧不 匹 配 ， 出 錯 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. 表 達 式 的 三 種 表 示 方 法 ：設 Exp = S1 OP S2則 稱 OP S1 S2 為 前 綴 表 示 法 S1 OP S2 為 中 綴 表 示 法 S1 S2 OP 為 后 綴 表 示 法 3.1.6 棧 的 應 用 舉 例 -表 達 式 求 值 例 如 : 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 + 結 論 :1） 操 作 數(shù) 之 間 的 相 對 次 序 不 變 ;2） 運 算 符 的 相 對 次 序 不 同 ;3） 中 綴 式 有 操 作 符 的 優(yōu) 先 級 問 題 ， 還 有 可 加 括 號 改變 運 算 順 序 的 問 題 ， 所 以 編 譯 程 序 一 般 不 使 用 中 綴 表示 處 理 表 達 式 。 例 如 : 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 + 結 論 :4)前 綴 式 的 運 算 規(guī) 則 為 : 連 續(xù) 出 現(xiàn) 的 兩 個 操 作 數(shù) 和 在 它 們 之 前 且 緊 靠 它 們的 一 個 運 算 符 構 成 一 個 最 小 表 達 式 ;5)后 綴 式 的 運 算 規(guī) 則 為 : 連 續(xù) 出 現(xiàn) 的 兩 個 操 作 數(shù) 和 在 它 們 之 后 且 緊 靠 它 們 的一 個 運 算 符 構 成 一 個 最 小 表 達 式 ; 2.如 何 從 后 綴 式 求 值 ？遇 到 運 算 數(shù) 則 入 棧 ，遇 到 操 作 數(shù) 則 2個 數(shù) 出 棧 ， 計 算 ， 結 果 入 棧例 如 ： 2

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

18、erands(double /從 操 作 數(shù) 棧 中 取 出 兩 個 操 作 數(shù) void DoOperator(char op); /pop出 兩 個 操 作 數(shù) (Get2Operands)， 進 行 op 計 算 ， 將 計 算 結 果 入 棧 (AddOperand); 將 操 作 數(shù) 的 值 value入 操 作 數(shù) 棧void Calculator: AddOperand(double value)S.Push(value); 清 棧void Calculator: Clear() S.MakeEmpty(); 從 操 作 數(shù) 棧 中 取 出 兩 個 操 作 數(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; /輸 出 計 算 結 果 ; 取 兩 個 操 作 數(shù) ， 根 據(jù) 操 作 符 op計 算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進 棧 ， 讀 入 下 一 個 字 符 ch。u 若 icp(ch) isp(op)， 出 棧 、 輸 出 、 不 讀 ,ch繼

21、續(xù) 比 較 。u 若 icp(ch) = isp(op)， 出 棧 但 不 輸 出 ， 若 退 出 的 是“ (”號 ， 則 讀 入 下 一 個 字 符 ch。 算 法 結 束 ， 輸 出 序 列 即 為 所 需 的 后 綴 表 達 式 。 例 ： 中 綴 表 達 式 為 A+B*(C-D)-E/F,求 其 后 綴 表 達 式 。ABCD-*+EF/- 37 中 綴 表 達 式 轉 換 為 后 綴 表 達 式 的 算 法 ：void postfix(expression e) /把 中 綴 表 達 式 e轉 換 成 后 綴 表 示 并 輸 出 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進 OPTR棧 ， 讀 下 一 字 符 到 ch；u若 icp(ch) isp(OPTR)， 則 從 OPND棧 退 出 a2和 a1， 從 OPTR棧 退 出 , 形 成 運 算 指 令 (a1)(a2)， 結 果 進 OPND棧 ,不 讀 入 讀下 一 字 符 而 是 繼 續(xù) 比 較 棧 頂 元 素 ；u若 icp(ch) = isp(OPT

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

24、lse /是 操 作 符 , 比 較 優(yōu) 先 級 OPTR.GetTop(op); /讀 一 個 操 作 符 42 if(icp(ch) isp(op) /棧 頂 優(yōu) 先 級 低 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. 問 題 的 解 法 是 遞 歸 的 47 在 鏈 表 中 尋 找 等 于 給 定 值 的 結 點 并 打 印 其 數(shù) 值void Print(ListNode*f, int value) if (

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

26、用 自 己 。 層 層 向 下 遞 歸 ， 退 出 時 的 次 序 正 好 相 反 ： 遞 歸 調 用 n! (n-1)! (n-2)! 1! 0!=1 返 回 次 序 主 程 序 第 一 次 調 用 遞 歸 過 程 為 外 部 調 用 ； 遞 歸 過 程 每 次 遞 歸 調 用 自 己 為 內 部 調 用 。3.2.2遞 歸 過 程 與 遞 歸 工 作 棧 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; 外 部 調 用內 部 調 用 51 1. 遞 歸 工 作 棧 每 一 次 遞 歸 調 用 時 ， 需 要 為 過 程 中 使 用 的參 數(shù) 、 局 部 變 量 等 另 外 分 配 存 儲 空 間 。 每 層 遞 歸 調 用 需 分 配 的 空 間 形 成 遞 歸 工 作記 錄 ， 按 后 進 先 出 的 棧 組 織 。 棧 頂 的 工 作 記 錄 是 當 前 正 在 執(zhí) 行 的 這 一 層的 工 作 記 錄 。 稱 之 為 活 動 記 錄 。 遞 歸工 作 記 錄 52 2. 遞 歸 過 程 改 為

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

29、句 ， 但 各 遞 歸 調 用 語句 的 參 數(shù) 之 間 沒 有 關 系 ， 并 且 這 些 遞 歸 調 用 語 句 都 處 在遞 歸 算 法 的 最 后 。 顯 然 ， 尾 遞 歸 是 單 向 遞 歸 的 特 例 。 例如 求 斐 波 那 契 數(shù) 列 的 遞 歸 算 法 。 2.其 他 的 遞 歸 ： 用 棧 實 現(xiàn) 。 53調 用 次 數(shù) NumCall(k) =斐 波 那 契 數(shù) 列 的 遞 歸 調 用 樹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)時 間 復 雜 度 ： 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 尾 遞 歸 用 迭 代 法 實 現(xiàn) 對 于 尾 遞 歸 形 式 的 遞 歸 算 法 ， 可 以 利 用 循 環(huán) 結 構 來 替 代 。 例如 求 階 乘 的 遞 歸 算 法 可 以 寫 成 如 下 循 環(huán) 結 構 的 非 遞 歸 算 法 ：long fact(int n) int s=0; for (int i=1; i=n;i+) s=s*i; /用 s保 存 中 間 結 果 return s; 56 單 向 遞 歸 用 迭 代 法 實 現(xiàn) 對 于 單 向 遞 歸 ， 可 以 設 置 一 些 變 量 保 存 中 間 結 構 ， 將 遞歸 結 構 用 循 環(huán) 結 構 來 替 代 。 例

32、如 求 斐 波 那 契 數(shù) 列 的 算 法 中 用s1和 s2保 存 中 間 的 計 算 結 果 ， 非 遞 歸 函 數(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. 間 接 轉 換 法該 方 法 使 用 棧 保 存 中 間 結 果 ， 一 般 需 根 據(jù) 遞 歸 函 數(shù) 在 執(zhí)行 過 程 中 棧 的 變 化 得 到 。 其 一 般 過 程 如 下 ：將 初 始 狀 態(tài) s0進 棧wh

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

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

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

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

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

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

39、/構 造 函 數(shù) 循 環(huán) 隊 列 的 類 定 義 65 SeqQueue() delete elements; /析 構 函 數(shù) int EnQueue(int x); /新 元 素 進 隊 列 int DeQueue(int /退 出 隊 頭 元 素 int getFront(int /取 隊 頭 元 素 值 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/輸 出 隊 列 中 元 素 的 重 載 操 作 ; 66 循 環(huán) 隊 列 操 作 的 定 義 構 造 函 數(shù)SeqQueue:SeqQueue(int sz) /構 造 函 數(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; /先 取 隊 頭 front = (front+1) % maxSize; /再 隊 頭 指 針 加 一 return 1; 68 3.3.3 隊 列 的 鏈 接 存 儲 表 示 鏈 式 隊 列 隊 頭 在 鏈 頭 ， 隊 尾 在 鏈 尾 。 鏈 式 隊 列 在 進 隊 時 無 隊 滿 問 題 ， 但 有 隊 空 問題 。 隊 空 條 件 為 front = NULLfront rear 69 #include struct QueueN

42、ode /隊 列 結 點 類 定 義private: int data; /隊 列 結 點 數(shù) 據(jù) QueueNode *link; /結 點 鏈 指 針public: QueueNode(int d = 0, QueueNode *next = NULL) : data(d), link(next) ; 鏈 式 隊 列 類 的 定 義 70 class LinkedQueue private: QueueNode *front, *rear; /隊 頭 、 隊 尾 指 針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插 入 到 隊 列 的 隊 尾int LinkedQueue:EnQueue(int if (front = NULL) return 0; /分 配 失 敗 else /隊 列 不 空 , 插 入

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

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

46、alink; ; front rear p 75 3.3.4 隊 列 的 應 用 ： 打 印 楊 輝 三 角 形 逐 行 打 印 二 項 展 開 式 (a + b)i 的 系 數(shù) ： 楊 輝三 角 形 (Pascals triangle) 分 析 第 i 行 元 素 與 第 i+1行 元 素 的 關 系從 前 一 行 的 數(shù) 據(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ù) 計 算 并 存 放 第 i+1 行 數(shù) 據(jù) 1 1 0 1 2 1 0 1 3 3 1

47、 0 int s=0,t; 利 用 隊 列 打 印 二 項 展 開 式 系 數(shù) 的 算 法#include #include #include queue.hvoid YANGHUI(int n) SeqQueue q(n+2); /隊 列 初 始 化 p121 q.EnQueue(1); q.EnQueue(1); int s = 0, t; for (int i = 1; i = n; i+) /逐 行 計 算 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 ; 改 進 :楊 輝 三 角 格 式 輸 出 80 3.4 優(yōu) 先 級 隊 列 (Priority Queue) 優(yōu) 先 級 隊 列 :每 次 從 隊 列 中 取 出 的 是 具 有最 高 優(yōu) 先 權 的 元 素 如 下 表 ： 任 務 優(yōu) 先 權 及 執(zhí) 行 順 序 的 關 系 81 #include #include #include class PQueue private: int *pqelements; /存 放 數(shù) 組 int count; /隊 列 元 素 計 數(shù) int maxPQSize; /最 大 元 素 個

49、數(shù) void adjust(); /調 整最 小 優(yōu) 先 級 隊 列 的 類 定 義 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 構 造 函 數(shù)PQueue:PQueue(int sz) maxPQSize = sz; count = 0; pqelements = new intmaxPQSize; assert (pqelements != NULL); 插 入 元 素int PQueue:Insert(int x) if (IsFull( ) return 0; /判 隊 滿 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) 先 權 調 整 元 素 位 置 操 作 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) 先 級 的 元 素 出 隊int PQueue:RemoveMin(int x = pqelements0; /取 出 0號 元 素 for (int i = 1; i count; i+) pqelementsi-1 = pqelementsi; /從 后 向 前 逐 個 移 動 元 素 填 補 空 位 count-; return 1; 10 20 40 50 60 70 90 87 取 隊 頭 元 素int PQueue:GetFront (int x = pqelements0; return 1; 10 20 40 50 60 70 90 1. 掌 握 棧 和 隊 列 類

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