《数据结构与算法》课程设计报告——赫夫曼编码/译码器
-
題目
赫夫曼編碼/譯碼器
-
實(shí)驗(yàn)?zāi)康?/h3>
本課程設(shè)計(jì)是為了讓同學(xué)們了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的作用和意義。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，想要更好地運(yùn)用計(jì)算機(jī)來解決實(shí)際問題，僅僅掌握幾門計(jì)算機(jī)程序設(shè)計(jì)語言是遠(yuǎn)遠(yuǎn)難以應(yīng)付當(dāng)前眾多復(fù)雜的課題，想要有效地使用計(jì)算機(jī)，充分發(fā)揮它的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)，打好數(shù)據(jù)結(jié)構(gòu)這門課的扎實(shí)基礎(chǔ)，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)其它的課程，如操作系統(tǒng)、軟件工程、編譯原理、數(shù)據(jù)庫、人工智能等十分有益。
?
-
需求分析
(1)初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。
(2)編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。
(3)譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。
(4)打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。
(5)打印赫夫曼樹（Tree printing）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時(shí)將此字符形式的赫夫曼樹寫入文件TreePrint 中。
(6)網(wǎng)絡(luò)通信（Network）。通過赫夫曼編碼的形式作為加密方式，進(jìn)行網(wǎng)絡(luò)通信。
?
-
概要設(shè)計(jì)
?
?
建立赫夫曼樹
?
編碼
?
?
譯碼
?
-
詳細(xì)設(shè)計(jì)
?
?
建立赫夫曼樹
/*** @param code - 字符集* @param weight - 頻數(shù)*/public void create(char[] code,double[] weight) {num=code.length;?? //獲取字符集字符總數(shù)node_tot=2*num-1;? //總共需要2num－1個(gè)節(jié)點(diǎn)PriorityQueue<HTNode> Q = new PriorityQueue<HTNode>();?? //優(yōu)先隊(duì)列排序HT=new HTNode[node_tot+1];HT[0]=new HTNode(0);//給葉子結(jié)點(diǎn)賦值for(int i=1;i<=num;i++) {HT[i]=new HTNode(i,code[i-1],weight[i-1]);Q.add(HT[i]);}int id=num;//Huffman編碼while(Q.size()>=2) {//找到兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹的根節(jié)點(diǎn)構(gòu)造新的二叉樹。HTNode s1=Q.remove();HTNode s2=Q.remove();id++;//創(chuàng)建新的節(jié)點(diǎn)//新節(jié)點(diǎn)的權(quán)值是兩個(gè)子節(jié)點(diǎn)之和HT[id]=new HTNode(id,s1,s2);?????s1.parent=s2.parent=id;??????? //將兩個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為 id;//新節(jié)點(diǎn)重新放入隊(duì)列Q.add(HT[id]);}}?
建立編碼表
/*** 從葉子到根逆向求每個(gè)字符的Huffman編碼*/public void createHuffmanCode() {int start,c,f;char[] cd=new char[num];HuffmanCodeList=new String[num+1]; //分配內(nèi)存空間//依次對(duì)所有字符編碼for(int i=1; i<=num; i++){start=num;//從葉子到根逆向求編碼for(c=i,f=HT[i].parent;f!=-1;c=f,f=HT[f].parent) {if(HT[f].lchild==c) {cd[--start]='0';}else{cd[--start]='1';}}//復(fù)制編碼到Huffman編碼表HuffmanCodeList[i]=new String(cd,start,num-start);}}?
編碼
/*** 從葉子到根逆向求每個(gè)字符的Huffman編碼*/public void createHuffmanCode() {int start,c,f;char[] cd=new char[num];HuffmanCodeList=new String[num+1]; //分配內(nèi)存空間//依次對(duì)所有字符編碼for(int i=1; i<=num; i++){start=num;//從葉子到根逆向求編碼for(c=i,f=HT[i].parent;f!=-1;c=f,f=HT[f].parent) {if(HT[f].lchild==c) {cd[--start]='0';}else{cd[--start]='1';}}//復(fù)制編碼到Huffman編碼表HuffmanCodeList[i]=new String(cd,start,num-start);}}?
譯碼
/*** @param code_str - 需要譯碼的字符串* @return encode - 完成Huffman譯碼的字符串*/public String deCode(String code_str) {int len=code_str.length();String decode=new String();String temp=new String();//依次與所有字符編碼開始匹配for(int i=0;i<len;i++) {temp=temp+code_str.charAt(i);for(int j=1;j<=num;j++) {//匹配成功if(HuffmanCodeList[j].equals(temp)) {decode=decode+HT[j].code;temp="";break;}}if(temp.length()>128)return null;}if(!temp.equals(""))return null;return decode;}?
文件分析
FileDialog jf=new FileDialog(this,"選擇文本文件",FileDialog.LOAD);jf.setVisible(true);String path=getAllPath(jf);if(path==null) {return;}String str=readFileToString(path);int len=str.length();char[] code = new char[128];double[] weight =new double[128];for(int i=0;i<128;i++) {code[i]=(char)i;}int num=0;for(int i=0;i<len;i++) {char ch=str.charAt(i);if(ch<0||ch>128) {JOptionPane.showMessageDialog(null, "文件讀取錯(cuò)誤", "錯(cuò)誤提示",JOptionPane.ERROR_MESSAGE);return;}if(weight[ch]==0)num++;weight[ch]+=1;}char[] new_code = new char[num];double[] new_weight =new double[num];for(int i=0,j=0;i<128;i++) {if(weight[i]!=0.0) {new_code[j]=code[i];new_weight[j++]=weight[i];}}initHuffmanTree(new_code,new_weight,textArea,textArea_3);?
樹圖繪制
/*** @param root HuffmanTree ROOT* @param g Graphics**/public void paintTree(int root,Graphics g,int x,int y){if(root!=-1){if(HT[root].code=='\0')g.drawString(new Double(HT[root].weight).toString(),x-10,y+10);elseg.drawString(chartoString(HT[root].code)+(new Double(HT[root].weight).toString()),x-10,y+10);if(HT[root].lchild!=-1||HT[root].rchild!=-1){int width=7*HT[root].leaf;g.drawLine(x, y+10, x-width, y+30);paintTree(HT[root].lchild, g,x-width,y+30);g.drawLine(x, y+10, x+width, y+30);paintTree(HT[root].rchild, g,x+width,y+30);}}}??網(wǎng)絡(luò)通信 /*** @param port 監(jiān)聽端口* @param ta JTextArea對(duì)象* @throws IOException 如果發(fā)生I / O錯(cuò)誤*/public void startReceive(int port,JTextArea ta) throws IOException{// TODO 自動(dòng)生成的方法存根ssk = new ServerSocket(port);isStop=false;ssk.setSoTimeout(5*1000);new Thread(()-> {while(!isStop) {Socket sk=null;try {sk = ssk.accept();} catch (IOException e) {// TODO 自動(dòng)生成的 catch 塊e.printStackTrace();}new Thread(new ReceiveThread(sk,ta)).start();}try {ssk.close();} catch (IOException e) {// TODO 自動(dòng)生成的 catch 塊e.printStackTrace();}}).start();}?
-
調(diào)試分析
GUI布局
使用Windows Builder插件和代碼調(diào)整的方式進(jìn)行GUI布局，以達(dá)到快速建立GUI和精確布局的目的。
初始化
初始化過程中，會(huì)以默認(rèn)編碼形式生成哈夫曼樹并生成編碼表。
編碼控制
采用三種編碼產(chǎn)生方式以達(dá)到多樣性的需求。
?
樹圖繪制
遞推法實(shí)行的樹圖繪制。
?
文本編碼
?
即時(shí)編碼
錯(cuò)誤提醒：
網(wǎng)絡(luò)通信
多線程同步問題
synchronized(ta) {if(destr==null)ta.append("Oh,My God! "+ip+" send a message but it isn\'t Huffman Code!"+"\r\n");elseta.append("Remote Host["+ip+"]:"+destr+"\r\n");}Synchronized同步以解決多線程問題。
-
總結(jié)
我認(rèn)為，在這學(xué)期的實(shí)驗(yàn)中，在收獲知識(shí)的同時(shí)，還收獲了閱歷，收獲了成熟，在此過程中，我們通過查找大量資料，請(qǐng)教老師，以及不懈的努力，不僅培養(yǎng)了獨(dú)立思考、動(dòng)手操作的能力，在各種其它能力上也都有了提高。更重要的是，在實(shí)驗(yàn)課上，我們學(xué)會(huì)了很多學(xué)習(xí)的方法。而這是日后最實(shí)用的，真的是受益匪淺。要面對(duì)社會(huì)的挑戰(zhàn)，只有不斷的學(xué)習(xí)、實(shí)踐，再學(xué)習(xí)、再實(shí)踐。
通過設(shè)計(jì)并編寫有關(guān)赫夫曼編碼與解碼，鍛煉自己的編程能力，養(yǎng)成良好的編程風(fēng)格。不管怎樣，這些都是一種鍛煉，一種知識(shí)的積累，能力的提高。完全可以把這個(gè)當(dāng)作基礎(chǔ)東西，只有掌握了這些最基礎(chǔ)的，才可以更進(jìn)一步，取得更好的成績(jī)。很少有人會(huì)一步登天吧。永不言棄才是最重要的。
與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖總結(jié)
以上是生活随笔為你收集整理的《数据结构与算法》课程设计报告——赫夫曼编码/译码器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Eclipse——UML类图插件
- 下一篇： 《数据结构与算法》实验报告——快速排序