《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》PPT課件

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) -成 果 展 示 網(wǎng)絡(luò)122 -張艷升 目錄一 . 雙 向 循 環(huán) 鏈 表二 . 二 叉 樹三 .有 向 圖 雙 向 循 環(huán) 鏈 表 功 能 :1. 實(shí) 現(xiàn) 雙 向 循 環(huán) 鏈 表 空 表 創(chuàng) 建2. 實(shí) 現(xiàn) 雙 向 循 環(huán) 鏈 表 添 加 節(jié) 點(diǎn)3. 實(shí) 現(xiàn) 雙 向 循 環(huán) 鏈 表 刪 除 節(jié) 點(diǎn)4 實(shí) 現(xiàn) 雙 向 循 環(huán) 鏈 表 就 地 逆 置5 打 印 出 雙 向 循 環(huán) 鏈 表 雙 向 循 環(huán) 鏈 表方 法 ：1.構(gòu) 造 方 法 建 立 空 表 :DoubleCircularLinked()2.插 入 節(jié) 點(diǎn) 的 方 法 ： insert（ AnyType x）3.在 某 個(gè) 位 置 插 入 節(jié) 點(diǎn) 的 方 法 ： insert（ int idx，AnyType x）4.刪 除 某 個(gè) 位 置 的 節(jié) 點(diǎn) 方 法 ： remove（ int idx）5.就 地 逆 置 的 方 法 ： transfer（ ）6打 印 鏈 表 的 方 法 ： print（ ） 雙 向 循 環(huán) 鏈 表 思路：1.建 立 頭 節(jié) 點(diǎn) headNode和 尾 節(jié) 點(diǎn) endNode的雙 向 循 環(huán) 鏈 表2.從 鍵 盤 上 直 接 輸 入 節(jié) 點(diǎn) 數(shù) 和 節(jié) 點(diǎn) 值 添 加 到鏈 表3.執(zhí) 行 插 入 方 法 可 以 實(shí) 現(xiàn) 某 個(gè) 位 上 的 插 入4.通 過 刪 除 方 法 刪 除 某 個(gè) 位 置 上 的 節(jié) 點(diǎn)5.就 地 逆 置 通 過 改 變 指 針 指 向 逆 向 輸 出 二 叉 樹 功 能 ：1.實(shí) 現(xiàn) 二 叉 樹 的 創(chuàng) 建2.實(shí) 現(xiàn) 二 叉 樹 的 層 次 遍 歷3.計(jì) 算 出 二 叉 樹 的 葉 子 節(jié) 點(diǎn) 數(shù)4.通 過 建 立 一 個(gè) 哈 夫 曼 樹 ， 實(shí) 現(xiàn) 哈夫 曼 算 法 二 叉 樹 方 法 ：1.創(chuàng) 建 二 叉 樹 的 方 法 ： createTree（ ）2.層 次 遍 歷 的 方 法 ： leavelOrder（ ）3.計(jì) 算 葉 子 節(jié) 點(diǎn) 的 方 法 ：countLeafNode（ ）4.創(chuàng) 建 哈 夫 曼 樹 的 方 法 ： compareNum（ ）5.計(jì) 算 碼 長 的 方 法 ： print（ ） 二 叉 樹 思 路 ：1.通 過 從 鍵 盤 上 讀 取 利 用 先 序 遍 歷 結(jié) 果 創(chuàng) 建 一 顆 二叉 樹2.層 次 遍 歷 ： 通 過 利 用 隊(duì) 列 思 想 看 訪 問 的 節(jié) 點(diǎn) 不 是空 時(shí) 進(jìn) 隊(duì) 列 ， 然 后 訪 問 下 一 個(gè) 節(jié) 點(diǎn) ， 頭 一 個(gè) 節(jié) 點(diǎn) 出隊(duì) 列 。3.通 過 判 斷 訪 問 節(jié) 點(diǎn) 左 右 孩 子 為 空 來 計(jì) 算 葉 子 節(jié) 點(diǎn)4.通 過 輸 入 一 數(shù) 組 找 出 該 數(shù) 組 中 最 小 的 兩 個(gè) ， 然 后相 加 得 到 的 數(shù) 為 這 兩 個(gè) 最 小 數(shù) 的 根 節(jié) 點(diǎn) 依 次 類 推 ，哈 弗 曼 編 碼 是 向 右 拐 加 1向 左 拐 加 0 有 向 圖 功 能 ：1.創(chuàng) 建 一 個(gè) 有 向 圖2.實(shí) 現(xiàn) 有 向 圖 的 深 度 優(yōu) 先 遍 歷3.實(shí) 現(xiàn) 有 向 圖 的 廣 度 優(yōu) 先 遍 歷4.實(shí) 現(xiàn) 實(shí) 現(xiàn) 有 向 圖 的 增 加 邊 的 功 能5.實(shí) 現(xiàn) 有 向 圖 的 刪 除 邊 的 功 能6.實(shí) 現(xiàn) 有 向 圖 的 連 通 性 判 斷 及 求 連 通分 量 有 向 圖 方 法 ： 1.有 向 圖 的 構(gòu) 造 方 法 實(shí) 現(xiàn) 圖 的 創(chuàng) 建 ：adjDWGraph（ ） 2.深 度 優(yōu) 先 遍 歷 的 方 法 ： DFSTransfer（ ） 3.廣 度 優(yōu) 先 遍 歷 的 方 法 ： BFSTransfer（ ） 4.增 加 變 得 方 法 ： addArc（ ） 5.刪 除 邊 的 方 法 ： deleteArc（ ） 6.判 斷 圖 的 連 通 性 及 求 連 通 分 量 ： isConnect() 有 向 圖 思 路 ： 1.通 過 從 鍵 盤 上 輸 入 來 創(chuàng) 建 有 向 圖 2.通 過 節(jié) 點(diǎn) 是 否 被 訪 問 過 來 進(jìn) 行 深 度 優(yōu) 先 遍 歷和 廣 度 優(yōu) 先 遍 歷 ， 廣 度 優(yōu) 先 遍 歷 通 過 隊(duì) 列 的 思想 訪 問 過 的 進(jìn) 隊(duì) 列 ， 訪 問 下 一 個(gè) 是 頭 一 個(gè) 出 來來 進(jìn) 行 每 一 個(gè) 節(jié) 點(diǎn) 的 遍 歷 3.通 過 深 度 優(yōu) 先 遍 歷 來 進(jìn) 行 圖 的 連 通 性 的 判 斷如 果 該 圖 是 聯(lián) 通 的 連 通 分 量 為 其 本 身 ， 否 則 輸出 該 圖 不 是 連 通 的 并 計(jì) 算 出 連 通 分 量 致 謝 ！