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

1、a,1,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì),-成果展示 網(wǎng)絡(luò)122 -張艷升,a,2,目錄,一 . 雙向循環(huán)鏈表 二 . 二叉樹 三.有向圖,a,3,雙向循環(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)鏈表,a,4,雙向循環(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

2、） 5.就地逆置的方法：transfer（） 6打印鏈表的方法：print（）,a,5,雙向循環(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.就地逆置通過改變指針指向逆向輸出,a,6,二叉樹,功能： 1.實(shí)現(xiàn)二叉樹的創(chuàng)建 2.實(shí)現(xiàn)二叉樹的層次遍歷 3.計(jì)算出二叉樹的葉子節(jié)點(diǎn)數(shù) 4.通過建立一個(gè)哈夫曼樹，實(shí)現(xiàn)哈夫曼算法,a,7,二叉樹,方法： 1.創(chuàng)建二叉樹的方法：createTree（） 2.層次遍歷的方法：leavelOrder（

3、） 3.計(jì)算葉子節(jié)點(diǎn)的方法：countLeafNode（） 4.創(chuàng)建哈夫曼樹的方法：compareNum（） 5.計(jì)算碼長的方法：print（）,a,8,二叉樹,思路： 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,a,9,有向圖,功能： 1.創(chuàng)建一個(gè)有向圖 2.實(shí)現(xiàn)有向圖的深度優(yōu)先遍歷 3.實(shí)現(xiàn)有向圖的廣度優(yōu)先遍歷 4.

4、實(shí)現(xiàn)實(shí)現(xiàn)有向圖的增加邊的功能 5.實(shí)現(xiàn)有向圖的刪除邊的功能 6.實(shí)現(xiàn)有向圖的連通性判斷及求連通分量,a,10,有向圖,方法： 1.有向圖的構(gòu)造方法實(shí)現(xiàn)圖的創(chuàng)建：adjDWGraph（） 2.深度優(yōu)先遍歷的方法：DFSTransfer（） 3.廣度優(yōu)先遍歷的方法：BFSTransfer（） 4.增加變得方法：addArc（） 5.刪除邊的方法：deleteArc（） 6.判斷圖的連通性及求連通分量：isConnect(),a,11,有向圖,思路： 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.通