【正文】 山東建筑大學 計算機科學與技術學院 課程設計說明書 題 目： 雙向鏈表的創(chuàng)建和操作的實現(xiàn) 樹的創(chuàng)建及相關操作的實現(xiàn) 課 程： 數(shù)據(jù)結構與算法 院 （部）： 計算機學院 專 業(yè)： 網(wǎng)絡工程 班 級： 網(wǎng)絡 101 學生姓名： 王天未 學 號： 2020202000 指導教師： 伊靜 完成日期： 202076山東建筑大學計算機學院課程設計說明書 I 目 錄 課程設計任務書 1................................................ II 課程設計任務書 2............................................... III 雙向循環(huán)鏈表的創(chuàng)建及相關操作的實現(xiàn) .............................. 4 一、問題描述 ................................................. 4 二、數(shù)據(jù)結構 ................................................. 4 三、邏輯設計 ................................................. 5 四、編碼 ..................................................... 6 五、 測試數(shù)據(jù) ............................................... 11 六、測試情況 ................................................ 11 樹的創(chuàng)建及相關操作的實現(xiàn) ....................................... 15 一、問題描述 ................................................ 15 二、數(shù)據(jù)結構 ................................................ 15 三、邏輯設計 ................................................ 16 四、編碼 .................................................... 19 五、 測試數(shù)據(jù) ............................................... 26 六、測試情況 ................................................ 26 結 論 .......................................................... 28 參考文獻 ....................................................... 29 課程設計指導教師評語 ........................................... 30 山東建筑大學計算機學院課程設計說明書 II 山東建筑大學計算機科學與技術學院 課程設計任務書 1 指導教師（簽字）： 教研室主任（簽字） 設計題目 雙向循環(huán)鏈表的創(chuàng)建及相關操作的實現(xiàn) 已知技術參數(shù)和設計要求 建立一個空表 插入第 i個結點。 刪除第 i個結點。 插入第 1個結點。 插入最后一個結點。 逆置 設計內(nèi)容與步驟 設計存儲結構 設計算法 編寫程序，進行調(diào)試 總結并 進行演示、講解 設計工作計劃與進度安排 做雙向鏈表創(chuàng)建方法 做雙向鏈表各種操作方法 設計考核要求 考勤 20% 課程設計說明書 50% 成果展示 30% 山東建筑大學計算機學院課程設計說明書 III 山東建筑大學計算機科學與技術學院 課程設計任務書 2 指導教師（簽字）： 教研室主任（簽字）設計題目 樹的創(chuàng)建及相關操作的實現(xiàn) 已知技術參數(shù)和設計要求 利用先序遍歷和層次遍歷的結果建立二叉樹 實現(xiàn)二叉樹的層次遍歷 統(tǒng)計二叉樹葉子結點的個數(shù)（遞歸）。 將二叉樹左右子樹相互交換（遞歸） 設計內(nèi)容與步驟 立結點類 BinaryTree（） 設計工作計劃與進度安排 6月 13日，實驗課下完成先序遍歷建樹， 16月 14日課程設計時間完成層次遍歷建樹 6月 16日課下完成層次遍歷和葉子節(jié)點個數(shù)統(tǒng)計 6月 18日課程設計時間完成二叉樹左右子樹相互交換 6月 19日完成測試函數(shù)及糾錯 設計考核要求 考勤 20% 課程設計說明書 50% 成果展示 30% 山東建筑大學計算機學院課程設計說明書 4 雙向循環(huán)鏈表的創(chuàng)建及相關操作的實現(xiàn) 一、問題描述 每個節(jié)點的 next域構成了一個循環(huán)單鏈表 每個節(jié)點的 prev域構成了另一個循環(huán)單鏈表 二、數(shù)據(jù)結構 針對所處理的樹： 畫出雙向循環(huán)鏈表的存儲結構 使用所選用語言的功能，描述該存儲結構的實現(xiàn) private static class NodeAnyType { AnyType data。 NodeAnyType prev。 NodeAnyType next。 } a0 a1 a2 a3 a4 prev data next 山東建筑大學計算機學院課程設計說明書 5 三、 邏輯設計 總體思路 對于雙向循環(huán)鏈表，建立一個空表，然后實現(xiàn)雙向循環(huán)鏈表的插入，刪除操作。 為了便于逆置的操作，選擇建立一個帶頭節(jié)點的雙向循環(huán)鏈表，插入第一個節(jié)點和插入最后一個節(jié)點，只需要在 0號位置和 size()位置插入節(jié)點就行。 模塊劃分（以圖示的方法給出各個函數(shù)的調(diào)用關系） 函數(shù)或類的具體定義和功能 class NodeAnyType//節(jié)點類定義 public class DlList AnyType//循環(huán)鏈表主類 public boolean add(int idex, AnyType x)//鏈表插入操作 public AnyType remove(int idex )//鏈表刪除操作 private void inverse()//鏈表逆置 建立一個空表 刪除節(jié)點 插入節(jié)點 逆置 主函數(shù) 山東建筑大學計算機學院課程設計說明書 6 四、編碼 import 。 class NodeAnyTy