《數據結構課程設計》PPT課件.ppt

1、a,1,數據結構課程設計,-成果展示 網絡122 -張艷升,a,2,目錄,一 . 雙向循環(huán)鏈表 二 . 二叉樹 三.有向圖,a,3,雙向循環(huán)鏈表,功能 : 1. 實現雙向循環(huán)鏈表空表創(chuàng)建 2. 實現雙向循環(huán)鏈表添加節(jié)點 3. 實現雙向循環(huán)鏈表刪除節(jié)點 4 實現雙向循環(huán)鏈表就地逆置 5 打印出雙向循環(huán)鏈表,a,4,雙向循環(huán)鏈表,方法 ： 1.構造方法建立空表:DoubleCircularLinked() 2.插入節(jié)點的方法：insert（AnyType x） 3.在某個位置插入節(jié)點的方法：insert（int idx，AnyType x） 4.刪除某個位置的節(jié)點方法：remove（int idx

2、） 5.就地逆置的方法：transfer（） 6打印鏈表的方法：print（）,a,5,雙向循環(huán)鏈表,思路： 1.建立頭節(jié)點headNode和尾節(jié)點endNode的雙向循環(huán)鏈表 2.從鍵盤上直接輸入節(jié)點數和節(jié)點值添加到鏈表 3.執(zhí)行插入方法可以實現某個位上的插入 4.通過刪除方法刪除某個位置上的節(jié)點 5.就地逆置通過改變指針指向逆向輸出,a,6,二叉樹,功能： 1.實現二叉樹的創(chuàng)建 2.實現二叉樹的層次遍歷 3.計算出二叉樹的葉子節(jié)點數 4.通過建立一個哈夫曼樹，實現哈夫曼算法,a,7,二叉樹,方法： 1.創(chuàng)建二叉樹的方法：createTree（） 2.層次遍歷的方法：leavelOrder（

3、） 3.計算葉子節(jié)點的方法：countLeafNode（） 4.創(chuàng)建哈夫曼樹的方法：compareNum（） 5.計算碼長的方法：print（）,a,8,二叉樹,思路： 1.通過從鍵盤上讀取利用先序遍歷結果創(chuàng)建一顆二叉樹 2.層次遍歷：通過利用隊列思想看訪問的節(jié)點不是空時進隊列，然后訪問下一個節(jié)點，頭一個節(jié)點出隊列。 3.通過判斷訪問節(jié)點左右孩子為空來計算葉子節(jié)點 4.通過輸入一數組找出該數組中最小的兩個，然后相加得到的數為這兩個最小數的根節(jié)點依次類推，哈弗曼編碼是向右拐加1向左拐加0,a,9,有向圖,功能： 1.創(chuàng)建一個有向圖 2.實現有向圖的深度優(yōu)先遍歷 3.實現有向圖的廣度優(yōu)先遍歷 4.

4、實現實現有向圖的增加邊的功能 5.實現有向圖的刪除邊的功能 6.實現有向圖的連通性判斷及求連通分量,a,10,有向圖,方法： 1.有向圖的構造方法實現圖的創(chuàng)建：adjDWGraph（） 2.深度優(yōu)先遍歷的方法：DFSTransfer（） 3.廣度優(yōu)先遍歷的方法：BFSTransfer（） 4.增加變得方法：addArc（） 5.刪除邊的方法：deleteArc（） 6.判斷圖的連通性及求連通分量：isConnect(),a,11,有向圖,思路： 1.通過從鍵盤上輸入來創(chuàng)建有向圖 2.通過節(jié)點是否被訪問過來進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，廣度優(yōu)先遍歷通過隊列的思想訪問過的進隊列，訪問下一個是頭一個出來來進行每一個節(jié)點的遍歷 3.通