huffman編碼課程設(shè)計(jì)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：34 大小：481.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩33頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》　　課程設(shè)計(jì)任務(wù)書　　以Java編程語言，要求軟件帶有簡單的GUI（利用AWT或者Swing實(shí)現(xiàn)）；　　附：報(bào)告格式　　數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程設(shè)計(jì)<

2、;/p>　　【設(shè)計(jì)題目】哈弗曼編碼　　【問題描述】 　　哈弗曼編碼在數(shù)據(jù)壓縮方面應(yīng)用十分廣泛.本課程設(shè)計(jì)主要是用哈弗曼樹(最優(yōu)二叉樹)實(shí)現(xiàn)字符串編碼及哈弗曼樹的GUI輸出,并驗(yàn)證哈弗曼編碼能否與實(shí)際應(yīng)用相吻合,進(jìn)而總結(jié)哈弗曼樹的實(shí)際應(yīng)用價值.<p&

3、gt;　　【軟件功能】　　1) 實(shí)現(xiàn)哈弗曼樹的構(gòu)建；　　2）利用哈弗曼樹生成葉結(jié)點(diǎn)字符的哈弗曼編碼；　　3) 實(shí)現(xiàn)各字符哈弗曼編碼及哈弗曼樹的GUI界面輸出.　　【算法思想】

4、　?。ㄒ唬┕ヂ幋a利用的抽象數(shù)據(jù)存儲結(jié)構(gòu)是鏈表、數(shù)組和基于鏈表的二叉樹。在實(shí)現(xiàn)過程中先將各字符根據(jù)權(quán)值從小到大存儲于在邏輯上連續(xù)葉節(jié)點(diǎn)的鏈表中，然后根據(jù)鏈表比較選取最小和次小兩權(quán)值建立子二叉樹，且子二叉樹根節(jié)點(diǎn)保存其子節(jié)點(diǎn)權(quán)值之和，通過子二叉樹根節(jié)點(diǎn)權(quán)值與鏈表上其他節(jié)點(diǎn)權(quán)值再比較，進(jìn)而合并，重組，循環(huán)最終構(gòu)建成基于鏈表的最優(yōu)二叉樹即哈弗曼樹。最后，使左分支為0，右分支為1，從葉節(jié)點(diǎn)向上直到根節(jié)點(diǎn)循環(huán)遍歷哈弗曼樹，獲

5、得各字符哈弗曼編碼，并保存于相應(yīng)字符的哈弗曼樹葉節(jié)點(diǎn)的順序存儲結(jié)構(gòu)數(shù)組中。 　?。ǘ┕δ軐?shí)現(xiàn)模塊： 　　1) 調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)和排序函數(shù)，根據(jù)權(quán)值從小到大生成List<TreeNode>類型的鏈表；　　2) 調(diào)用建樹函數(shù)，根據(jù)鏈表比較選取最小和次小兩權(quán)值建立二叉樹，記錄節(jié)點(diǎn)的左右孩子及雙親的位置

6、關(guān)系，最終構(gòu)建成哈弗曼樹，且記錄的左孩子權(quán)值小于右孩子；　　3) 調(diào)用編碼函數(shù)，根據(jù)已建立的哈夫曼樹，從葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)建立哈夫曼編碼，并保存于相應(yīng)字符的哈弗曼樹葉結(jié)點(diǎn)的順序存儲結(jié)構(gòu)中。　　4) 調(diào)用遍歷函數(shù)和打印函數(shù)，遍歷各字符的哈弗曼編碼并打印在GUI界面上；　　【邏輯結(jié)構(gòu)設(shè)計(jì)】<

7、/b>　　本課程設(shè)計(jì)應(yīng)用的邏輯結(jié)構(gòu)設(shè)計(jì)包括：線性非連續(xù)的的鏈?zhǔn)酱鎯Y(jié)構(gòu)、線性連續(xù)的數(shù)組存儲結(jié)構(gòu)和基于鏈表的二叉樹。 　　【存儲結(jié)構(gòu)設(shè)計(jì)】　?。?）哈弗曼樹結(jié)點(diǎn)存儲結(jié)構(gòu)設(shè)計(jì)類： 　　class TreeNode{</p&

8、gt;　　private int weight; //統(tǒng)計(jì)該節(jié)點(diǎn)的字符屬性在文件中出現(xiàn)得頻率　　private char ch; //節(jié)點(diǎn)的字符屬性　　private TreeNode right;//右節(jié)點(diǎn)　　private TreeNode left; //左節(jié)點(diǎn)</p&

9、gt;　　private TreeNode parent; //父節(jié)點(diǎn)　　private String hfmcode=""; //保存編碼的屬性　　private static final int width=60; //JButton的寬度　　private

10、static final int height=20; //JButton的高度　　private int x,y; //節(jié)點(diǎn)的定位坐標(biāo)　　private int depth=1; //默認(rèn)節(jié)點(diǎn)處位置的深度　　.....及其屬性設(shè)置　　}</b

11、>　　利用ArrayList<TreeNode>順序鏈?zhǔn)酱鎯Y(jié)構(gòu)先存儲各字符及其權(quán)重，再根據(jù)權(quán)重構(gòu)建哈弗曼樹（最優(yōu)二叉樹）　　二叉樹如下：　　【基本操作設(shè)計(jì)】　　構(gòu)造哈夫曼樹的主

12、要實(shí)現(xiàn)方法：　　public List<TreeNode> creatNodeList(String str)　　//傳入字符串，生成一個結(jié)點(diǎn)鏈表；　　public List<TreeNode> sortListW(List<TreeNode> list)

13、　　//按權(quán)重給結(jié)點(diǎn)從小到大排序；　　public void sortListWofF(List<TreeNode> list)　　//按父結(jié)點(diǎn)權(quán)重從小到大排序；　　public void toList(TreeNode root, List<TreeNode> lis

14、t)　　// 遍歷樹，生成存儲樹各結(jié)點(diǎn)的鏈表；　　public TreeNode creatTree(List<TreeNode> nodeList, Graphics g,JFrame jf) 　　//根據(jù)權(quán)重創(chuàng)建哈弗曼樹；　　顯示哈弗曼樹主要方法：<

15、/p>　　public void creatUI() //創(chuàng)建操作界面界面及用于哈弗曼樹的顯示；　　public void setNodeXYofRoot( TreeNode node,int a,int b）　　//設(shè)置各結(jié)點(diǎn)位置；　　public void drawNode(Lis

16、t<TreeNode> list, Graphics g)　　//畫出各結(jié)點(diǎn)；　　public void drawLine(TreeNode root, Graphics g)　　//畫出各結(jié)點(diǎn)之間的連線；　　哈弗曼編碼獲

17、取主要方法：　　public void setHfmcode(TreeNode root)　　//設(shè)置根結(jié)點(diǎn)哈弗曼編碼；　　public String hfmcodeofSting(String s, TreeNode root)　　//通過字符獲得哈弗曼編碼；</

18、p>　　public String Stingofhfmcode(String s, TreeNode root)　　//通過哈弗曼編碼獲得字符。　　【模塊流程圖】　　TreeNode類

19、　　Line類 　　Shape類 　　Shape類

20、　ActionListener內(nèi)部類監(jiān)聽按鈕　　點(diǎn)擊點(diǎn)擊點(diǎn)擊 　　creatTree() getText() getText()　　【生成樹圖】 hfmcodeofSting() St

21、ingofhfmcode（）　　setHfmcode() setText() setText()　　【界面設(shè)計(jì)】　　【用戶手冊】　　第一步：先將程序在eclipse運(yùn)行

22、，產(chǎn)生上述界面；　　第二步：在“請輸入要創(chuàng)建的樹碼”文本框輸入字符串，點(diǎn)擊“顯示哈弗曼樹”按鈕，在顯示區(qū)域?qū)@示樹圖；　　第三步：在“請輸入查詢字符”文本框輸入待查詢字符，點(diǎn)擊“查詢”按鈕，即可在查詢結(jié)果文本框輸出字符的哈弗曼編碼；　　第四步：在“請輸入哈弗編碼”文本框輸入哈弗曼編碼，點(diǎn)擊“檢驗(yàn)”按鈕，即可在“檢

23、驗(yàn)結(jié)果”中顯示對應(yīng)字符，即可驗(yàn)證哈弗曼編碼與字符是否對應(yīng)。　　程序上機(jī)調(diào)試報(bào)告　　【語法錯誤及其排除】　?。?）終端輸出的漢字為亂碼。　　解決方法：重新設(shè)置工程和各類編碼格式均為GBK，使工程內(nèi)所有文件編碼格式保持一致；</p&

24、gt;　?。?）圖形界面處理時，組建的層次繼承關(guān)系出現(xiàn)錯誤。　　解決方法：查找API和參考java圖形界面設(shè)計(jì)章節(jié)的例題。　?。?）字符串的相關(guān)函數(shù)使用有誤，為真正明白相關(guān)函數(shù)的原理　　解決方法：利用編程測試字符串各函數(shù)的功能，找出穩(wěn)定可靠的函數(shù)，用于自己的代碼中。&

25、lt;p>　　【算法錯誤及其排除】　?。?）如在設(shè)置哈弗曼樹結(jié)點(diǎn)位置用setNodeXYofRoot(TreeNode node,int a,int b）函數(shù)時未考慮遞歸的算法思想，出現(xiàn)結(jié)點(diǎn)位置設(shè)置混亂和部分結(jié)點(diǎn)無法在界面顯示且不穩(wěn)定。　　解決方法：采用遞歸算法并與鏈表結(jié)點(diǎn)的字符的深度相結(jié)合設(shè)置節(jié)點(diǎn)的位置坐標(biāo)。<p&g

26、t;　　（2）根據(jù)哈弗曼編碼檢測對應(yīng)的字符時無法將鏈表list<TreeNode>每一個結(jié)點(diǎn)的哈弗曼編碼與輸入檢測的哈弗曼編碼相匹配，在監(jiān)聽類內(nèi)部未能實(shí)現(xiàn)。　　解決方法：不在監(jiān)聽類內(nèi)部實(shí)現(xiàn)匹配操作，而是在Demo類中定義Stingofhfmcode(String s, List<TreeNode> list)函數(shù)用于測試并獲得哈弗曼編碼對應(yīng)的字符。

27、　　當(dāng)字符串較多時會出現(xiàn)畫出的哈弗曼樹過于密集而不夠清晰的現(xiàn)象，在原來的基礎(chǔ)上再次繪制會覆蓋原先的樹，出現(xiàn)混亂。　　解決方法：調(diào)整結(jié)點(diǎn)間距，使其結(jié)點(diǎn)距離適中。出現(xiàn)的覆蓋現(xiàn)象是因?yàn)槊看卫L制沒有刷新界面，通過繼承JFrame中的update()函數(shù)并調(diào)用。　　統(tǒng)計(jì)的字符時用連續(xù)數(shù)組存儲實(shí)現(xiàn)具有局限性，且不利于進(jìn)一步構(gòu)建哈弗曼樹。</p

28、>　　解決方法：利用鏈?zhǔn)酱鎯Y(jié)構(gòu)，調(diào)用庫類 ArrayList<TreeNode>實(shí)現(xiàn)。　　3、程序測試結(jié)果　　【測試數(shù)據(jù)】任意輸入字符串例如： jghjfgjfghjfjhjh,jk.m.,hj,mnvnvvnvvnvn<b&

29、gt;　　【輸出結(jié)果】　　1、顯示界面圖　　2、查j的編碼： 01　　3、實(shí)驗(yàn)匹配01 對應(yīng) j　　4、如果不存在實(shí)驗(yàn)的如：11111110000 對應(yīng)路徑不存在，匹配不成功<

30、p>　　【程序性能評價】　　由于哈弗曼編碼在數(shù)據(jù)壓縮方面應(yīng)用十分廣泛.本程序用哈弗曼樹(最優(yōu)二叉樹)實(shí)現(xiàn)字符串編碼及哈弗曼樹的GUI輸出,直觀，簡約，并成功驗(yàn)證了哈弗曼編碼能與實(shí)際編碼的構(gòu)想完全吻合,為哈弗曼編碼的推廣及應(yīng)用提供了一定的參考價值。在程序設(shè)計(jì)時，充分考慮到各項(xiàng)異常，遇到不符合的事項(xiàng)，都會彈出對話框，給予提示，大大增強(qiáng)了人機(jī)交互的能力，更有

31、利于實(shí)驗(yàn)的檢測和驗(yàn)證。　　【性能改進(jìn)方向】　　本程序雖然能直觀的為驗(yàn)證哈弗曼編碼的實(shí)際應(yīng)用價值提供一定參考價值，但功能相對簡單。由于網(wǎng)絡(luò)安全及數(shù)據(jù)壓縮是現(xiàn)今社會談?wù)摰臒衢T話題，因此，在數(shù)據(jù)傳送時，對壓縮傳送數(shù)據(jù)及加密數(shù)據(jù)，已成為哈弗曼編碼思想的重要應(yīng)用領(lǐng)域之一。此程序可向?qū)?shù)據(jù)加密及數(shù)據(jù)解壓的方向改進(jìn)，以便于驗(yàn)證哈弗

32、曼編碼在數(shù)據(jù)壓縮及加密等領(lǐng)域的應(yīng)用，進(jìn)而推廣哈弗曼編碼的重要應(yīng)用價值。　　【收獲及體會】　　通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就不加思索地做，而

33、是首先要先對它有個大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。　　這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時忘記應(yīng)該怎樣保存保存數(shù)據(jù)，在不斷分析后明確并改正了錯誤和疏漏，使我的程序有了更高的質(zhì)量。這不僅是程序設(shè)計(jì),更是鍛煉我們處理問題的能力,同時也使我們了解到團(tuán)隊(duì)合作的可貴.編寫程序是件細(xì)心活,稍不留神

34、就會出錯,這就必須要求我們對待事情要認(rèn)真!在編寫程序的過程中,錯誤不斷出現(xiàn),不同的類型(如少寫了一個符號,寫錯了字母,用錯了函數(shù)等等)層出不窮,這考驗(yàn)我們待事細(xì)心,耐心,能不能堅(jiān)持到底,不能半途而廢。　　三人行必有我?guī)?遇到問題我們一起討論,研究,錯了再寫,寫了在改.經(jīng)過多次的修改,調(diào)試,運(yùn)行,添加,終于最后在大家的歡呼聲中,完成了我們的任務(wù).雖說是累了點(diǎn)，但我們也從中找到了自己的快樂，每當(dāng)完成

35、一個新的函數(shù)時，那心情是激動啊,這畢竟是自己弄出來的,同時也使我感受到了學(xué)習(xí)的快樂！　　一個成功的項(xiàng)目必須在寫代碼前，先要對課題有充分的思考和規(guī)劃，否則即使完成了項(xiàng)目也會浪費(fèi)很多的時間和精力。所以，我覺，科學(xué)合理的編程方法是我這次課程設(shè)計(jì)的最大收獲。　　源程序代碼（要求有盡可能多的注釋語句）

36、　　Haffman 類　　package hTreeDemo;　　import java.awt.Graphics;　　import java.util.*;　　import javax.swing.JFrame;<p&

37、gt;　　import javax.swing.JOptionPane;　　/*　　* 給出一個字符串，統(tǒng)計(jì)每個字符在字符串中出現(xiàn)的次數(shù)，并返回一個TreeNode類型的數(shù)組　　* 用TreeNode類型的數(shù)組創(chuàng)建一個霍夫曼樹，并制定每個葉節(jié)點(diǎn)的霍夫曼編碼

38、　　* 給出字符要求輸出該字符的霍夫曼編碼（或者給出字符串，給出該字符串的霍夫曼編碼）　　* 畫出一個界面，輸入字符串，然后輸出這段字符串的哈弗曼碼以及畫出哈弗曼樹：　　* 建一個界面類，在main方法里調(diào)用：實(shí)現(xiàn)字符串輸入和畫出哈樹及輸出哈弗曼碼的功能。　　* </

39、b>　　* 最終是先從一個文件中傳入數(shù)據(jù)壓縮存儲到另一可選位置，并可以解壓縮的功能。　　* @author Administrator　　*　　*/

40、　　public class Huffman {　　/**　　* 程序入口　　* 　　* @param args

41、* //　　*/　　public static void main(String[] args) {　　Interface face = new Interface();　　//Graphics g = nul

42、l;　　//Huffman demo = new Huffman();　　face.creatUI();　　//List<TreeNode> list = demo.creatNodeList("asdsa");　　//

43、　　//for (int i = 0; i < list.size(); i++) {　　//System.out.println(list.get(i).getCh() + " 次數(shù):"　　//+ list.get(i).getWeight());<

44、/p>　　//}　　//TreeNode root = demo.creatTree(list, g,face);　　//System.out.println(root);　　//demo.print(root);&l

45、t;p>　　//demo.setHfmcode(root);　　//System.out.println("已經(jīng)設(shè)置了哈夫曼碼");　　//String hfmcode1 = demo.hfmcodeofSting("w", root);　　//System.

46、out.println(hfmcode1);　　//String s = "";　　//demo.set(root, s);　　//String hfmcode = demo.hfmcodeofSting("e", root);

47、;　　////System.out.println(hfmcode);　　}　　/*　　* 傳入字符串，生成一個節(jié)點(diǎn)隊(duì)列。因?yàn)橐话阄淖侄际钦加袃蓚€字節(jié)，所以輸入的字符串都能轉(zhuǎn)變?yōu)閱蝹€文字。<

48、;b>　　* 　　* @param str：字符串　　* 　　* @return 樹節(jié)點(diǎn)類型的隊(duì)列　　*/　　Set<St

49、ring> saveChar= new HashSet<String>();　　public List<TreeNode> creatNodeList(String str) {　　String[] sr=str.split("");　　for (int i =

50、0; i < sr.length; i++) {　　if(sr[i].equals("")){　　continue; 　　}　　saveChar.add(sr[i].toString());

51、;　　}　　// System.out.println(saveChar.size());　　/*for(String s:saveChar){　　System.out.print(s+" ");<

52、;p>　　}*/　　List<TreeNode> list = new ArrayList<TreeNode>(); // 自定義隊(duì)列，接受字符串中的字符　　for (int h = 0; h < str.length(); h++) {

53、　int count = 0; // 計(jì)算下面的這個循環(huán)循環(huán)次數(shù)　　for (int i = 0; i < list.size(); i++) { // 遍歷chars隊(duì)列，看新的字符是不是在其中　　if (str.charAt(h) == list.get(i).getCh()) {//ok　　// 如果

54、str中去除的字符已經(jīng)在節(jié)點(diǎn)隊(duì)列中了　　list.get(i).setWeight(list.get(i).getWeight() + 1); // 讓權(quán)重增加一　　break;　　}<b&

55、gt;　　count++;　　}　　if (count == list.size()) {　　// 如果從str取出的新的char不在隊(duì)列中　　//System.out.println("-------

56、---");　　TreeNode newNode = new TreeNode(str.charAt(h));　　newNode.setWeight(1);　　list.add(newNode);　　}

57、　　}　　// System.out.println(count01);　　return list;　　}　　/**

58、　　* 按權(quán)重給節(jié)點(diǎn)隊(duì)列排序　　* 　　* @return weight屬性從小到大排序的節(jié)點(diǎn)隊(duì)列　　*/　　public List<TreeNode> sortL

59、istW(List<TreeNode> list) {　　for (int i = 0; i < list.size(); i++) {　　for (int j = i + 1; j < list.size(); j++) {　　if (list.get(j).getWeight() &l

60、t; list.get(i).getWeight()) {　　// 如果第j個節(jié)點(diǎn)元素的權(quán)重屬性小于第i個元素的權(quán)重屬性　　TreeNode newNode = list.set(i, list.get(j));// 用指定元素替換以前在該位置的元素　　list.set(j, newNode);

61、;　　}　　}　　}　　return list;　　}&

62、lt;b>　　/**　　* 按父節(jié)點(diǎn)權(quán)重給節(jié)點(diǎn)隊(duì)列排序　　* 　　* @return weight:屬性從小到大排序的節(jié)點(diǎn)隊(duì)列　　*/<p&

63、gt;　　public void sortListWofF(List<TreeNode> list) {　　for (int i = 0; i < list.size(); i++) {　　for (int j = i + 1; j < list.size(); j++) {<b&g

64、t;　　// 排序　　if (list.get(j).getParent().getWeight() < list.get(i)　　.getParent().getWeight()) {　　// 如果第j個節(jié)點(diǎn)元素的權(quán)重屬性小于第i個元素的權(quán)重屬性

65、;　　TreeNode newNode = list.set(i, list.get(j));// 用指定元素替換以前在該位置的元素　　list.set(j, newNode);　　}　　}<

66、;b>　　}　　}　　/**　　* 生成一個霍夫曼樹，并給這個哈樹節(jié)點(diǎn)的depth屬性　　* <p&g

67、t;　　* @param nodeList　　* ：按權(quán)重從小到大排好序的樹節(jié)點(diǎn)類型的隊(duì)列　　* @param g　　* :畫布對象　　* @param jf　　*

68、：在這個界面上加組件　　* @return 霍夫曼樹的根節(jié)點(diǎn)　　*/　　public TreeNode creatTree(List<TreeNode> nodeList, Graphics g,JFrame jf) {

69、　　if(saveChar.size()==1){　　JOptionPane.showMessageDialog(null,"一個字符創(chuàng)建不了哈弗曼樹，請輸入多個不同的字符！");　　return null;　　}

70、　　while (true)　　{　　nodeList = sortListW(nodeList);　　TreeNode left = nodeList.remove(0);　　TreeNode right = nodeList.re

71、move(0);　　TreeNode root = new TreeNode('F');　　root.setWeight(right.getWeight() + left.getWeight());　　// 手動確定三者之間的關(guān)系　　left.setPar

72、ent(root);　　right.setParent(root);　　root.setLeft(left);　　root.setRight(right);　　//System.out.println("組合了"+(++j));

73、　　nodeList.add(0, root); // 將根節(jié)點(diǎn)加到隊(duì)列中　　if (nodeList.size() == 1) 　　{　　List<TreeNode> newList = new ArrayList<TreeNode&g

74、t;();　　toList(root, newList); // 把樹轉(zhuǎn)變?yōu)殛?duì)列　　//給每個節(jié)點(diǎn)加深度　　for (int i = 0; i < newList.size(); i++)　　{<p

75、>　　TreeNode ran = newList.get(i);　　TreeNode newNode = ran;　　while (ran.getParent() != null) 　　{　　newNode.setDepth(

76、newNode.getDepth() + 1);　　ran = ran.getParent();　　}　　}　　sortListD(newList); // 按depth排序

77、　　drawNode(newList, g);　　drawLine(root, g);　　return root;　　}　　}<

78、b>　　}　　/**　　* 遍歷樹，生成樹節(jié)點(diǎn)的隊(duì)列　　* 　　* @param root　　* @retur

79、n　　*/　　public void toList(TreeNode root, List<TreeNode> list) {　　if (root != null) {　　toList(root.get

80、Left(), list);　　toList(root.getRight(), list);　　list.add(root);　　//System.out.println("加了一次");　　}

81、;　　}　　/**　　* 按節(jié)點(diǎn)擁有的子樹的最大深度depth來排序（用插入排序），引用傳遞，是否返回都無所謂　　* 　　* @para

82、m list　　* :要排序的樹節(jié)點(diǎn)隊(duì)列　　*/　　public void sortListD(List<TreeNode> list) {　　for (int i = 1; i < list.

83、size(); i++) {　　for (int j = i; j > 0; j--) {　　if (list.get(j).getDepth() > list.get(j - 1).getDepth()) { // 互換　　TreeNode tem = list.set(j, list.get(j

84、- 1));　　list.set(j - 1, tem);　　}　　// System.out.println(list.get(j).getCh()+" 深度 "+list.get(j).getDepth());

85、;　　}　　}　　}　　/**　　* 設(shè)置各節(jié)點(diǎn)位置<

86、;p>　　* 　　* @param node ：要設(shè)置位置的結(jié)點(diǎn)　　* @param a: x位置　　* @param b： y位置 　　*/<

87、;/p>　　public void setNodeXYofRoot( TreeNode node,int a,int b) { 　　if((node!=null)&&node.getDepth()==0)　　{　　node.

88、setX(a);　　node.setY(b);　　}　　else　　{　　if(node.getLeft()!=nu

89、ll)　　{　　setNodeXYofRoot(node.getLeft(),node.getX()-10,node.getY()+60); 　　}　　if(node.getRight()!=nu

90、ll)　　{　　setNodeXYofRoot(node.getRight(),node.getX()+10,node.getY()+60); 　　} 　　}</b&g

91、t;　　}　　/*　　*畫出一個哈樹的節(jié)點(diǎn)，并設(shè)置每個節(jié)點(diǎn)的x,y屬性　　* 　　* @param list<

92、/p>　　* ：排好序的，設(shè)置了depth的節(jié)點(diǎn)隊(duì)列　　* @param jf　　* ：把組件加到這個界面上　　*/　　public void drawNode(

93、List<TreeNode> list, Graphics g) {　　while (true) 　　{　　int depth = 0;　　int newDepth = 0;　　L

94、ist<TreeNode> newList = new ArrayList<TreeNode>();// 創(chuàng)建一個隊(duì)列用來接收同層次的節(jié)點(diǎn);　　depth = list.get(0).getDepth(); // 取出第一個節(jié)點(diǎn)的depth，就是說一層一層的畫　　newDepth = depth;<p

95、>　　while (newDepth == depth)　　{　　if (list.size() != 0) 　　{　　// System.out.println(list.get(0).g

96、etCh()+"深度：————————————————"+list.get(0).getDepth());　　newList.add(list.remove(0)); // 移到新的隊(duì)列里　　if (list.size() != 0)　　{</p&g

97、t;　　newDepth = list.get(0).getDepth();// list中下一個元素的depth　　// System.out.println("移除了一個");　　} 　　else </b&

98、gt;　　{　　break;　　}　　}　　}</b&

99、gt;　　sortListWofF(newList); // 給一層的節(jié)點(diǎn)按父節(jié)點(diǎn)的權(quán)重排序　　int x=210+newList.get(0).getX()+5*getDepthofLeft(newList.get(0));　　int y=60*depth+60;//

100、　// 遍歷newList畫出一個深度的所有節(jié)點(diǎn)　　for (int j = 0; j < newList.size(); j++)　　{　　if((newList.get(j).getDepth()==0))

101、　　{　　setNodeXYofRoot(newList.get(j),x,y );　　} 　　else　　{<

102、;p>　　newList.get(j).setX(x);　　newList.get(j).setY(y);　　}　　// 畫出節(jié)點(diǎn)，即在桌面上加上JButton　　if (newList.get(j).getLeft() !=

103、null)　　{　　newList.get(j).draw(g, "父", newList.get(j).getX()+3,　　newList.get(j).getY()+5);　　}</b

104、>　　else 　　{　　newList.get(j).draw(g, "" + newList.get(j).getCh(),　　newList.get(j).getX

105、()+3, newList.get(j).getY()+5);　　}　　// System.out.println("畫出了一個節(jié)點(diǎn) "+x+" "+y);　　x+=20;</

106、p>　　}　　// System.out.println("畫出了一組");　　// 死循環(huán)的出口　　if (list.size() == 0) {

107、　　return;　　}　　}　　}　　/**<p&

108、gt;　　* 取得一個子樹的最左的葉節(jié)點(diǎn)的x值（僅適用于哈弗曼樹）　　* 　　* @param root　　* ：子樹根節(jié)點(diǎn)　　* @return 最左的葉節(jié)點(diǎn)的x值&l

109、t;b>　　*/　　public int getDepthofLeft(TreeNode root) {　　if (root.getLeft() == null) {　　return root.getX();　　}</b&

110、gt;　　if (root != null) {　　getDepthofLeft(root.getLeft());　　}　　return 0; // 不會執(zhí)行這一步　　}&l

111、t;/b>　　/**　　* 畫出每個節(jié)點(diǎn)間的連線　　* 　　* @param root　　* ：樹的根節(jié)點(diǎn)

112、　　* @param g　　* ：在這個布上畫　　*/　　public void drawLine(TreeNode root, Graphics g) {　　if (root != nul

113、l) {　　drawLine(root.getLeft(), g);　　drawLine(root.getRight(), g);　　if (root.getLeft() != null) {　　Line line = new Line( root.getX() ,<

114、;/p>　　root.getY(), 　　root.getLeft().getX(),　　root.getLeft().getY());　　// root.getY()+40);root.getX()-5,　　//

115、 root.getLeft().setX(root.getX()-5);　　// root.getLeft().setY(root.getY()+40);　　//　　line.draw(g);　　//System.out.pr

116、intln(root.getCh()+"畫出了一條線"+root.getLeft().getCh());　　}　　if (root.getRight() != null) {　　Line line = new Line(root.getX(),</p

117、>　　root.getY(),　　root.getRight().getX(),　　root.getRight().getY());　　line.draw(g);　　//System.out.println(root.getCh()+&q

118、uot;畫出了一條線"+root.getRight().getCh());　　}　　}　　}　　/**<

119、/p>　　* 設(shè)置一個哈夫曼樹的哈夫曼編碼　　* 　　* @param root　　*/　　public void setHfmcode(TreeNode root)

120、{　　//System.out.println("開始設(shè)置葉節(jié)點(diǎn)的哈弗曼編碼");　　if (root != null)　　{　　setHfmcode(root.getLeft());&l

121、t;p>　　setHfmcode(root.getRight());　　if (root.getLeft() == null && root.getRight() == null)　　{ // 是葉節(jié)點(diǎn)　　TreeNode newRoot = root;

122、　　while (root.getParent() != null) 　　{　　TreeNode newNode = root;　　root = root.getParent();　　if (

123、root.getLeft().equals(newNode))　　{// 左節(jié)點(diǎn)　　newRoot.setHfmcode(0 + newRoot.getHfmcode());　　} <b&g

124、t;　　else 　　{　　newRoot.setHfmcode(1 + newRoot.getHfmcode());　　}　　}<

125、/p>　　// System.out.println("設(shè)置了一個葉節(jié)點(diǎn)的哈弗曼編碼");　　}　　}　　}

126、　//public void set(TreeNode root, String code) { //設(shè)置各節(jié)點(diǎn)的哈弗曼編碼　　//if (root.getLeft() != null) {　　//set(root.getLeft(), code + 0);　　//}</

127、b>　　//if (root.getRight() != null) {　　//set(root.getRight(), code + 1);　　//}　　//if (root.getLeft() == nul

128、l && root.getRight() == null) {　　// 葉節(jié)點(diǎn)　　//root.setHfmcode(code);　　//}　　//

129、}　　/*　　* 獲取字符串的哈弗曼編碼　　* 　　* @param s：傳入的字符串　　*

130、　　* @param root:傳入哈夫曼樹的根節(jié)點(diǎn)　　* 　　* @return 字符串的哈弗曼編碼　　*/　　public String hfmcod

131、eofSting(String s, TreeNode root) {　　// System.out.println("調(diào)用toString ");　　String code = "";　　int j=0;<

132、;p>　　for (String charstr:saveChar) 　　if(charstr.equals(s))　　{　　j++;　　}</

133、p>　　if(j==0) //字符不在樹形圖內(nèi)　　{　　JOptionPane.showMessageDialog(null,"字符不在查找范圍內(nèi)，請重新輸入有效字符！");　　return null;

134、　　}　　for (int i = 0; i < s.length(); i++) {　　char c = s.charAt(i);　　StringBuffer sc = new StringBuffer();

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

huffman編碼課程設(shè)計(jì)

文檔簡介

溫馨提示

最新文檔

評論

huffman編碼課程設(shè)計(jì)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載