哈夫曼編碼譯碼報(bào)告

煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院課程設(shè)計(jì)（數(shù)據(jù)結(jié)構(gòu)與OOP）設(shè)計(jì)題目：班級(jí)姓名學(xué)號(hào)指導(dǎo)教師成績年月日目錄1題目 31.1問題描述 31.2基本要求 31.3進(jìn)一步完成 32內(nèi)容 32.1基本需求 32.2.我的設(shè)計(jì) 43算法設(shè)計(jì) 43.1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 43.1.1存放哈夫曼樹的存儲(chǔ)結(jié)構(gòu)： 43.1.2存放哈夫曼編碼的存儲(chǔ)結(jié)構(gòu)： 43.1.3存放哈夫曼樹每個(gè)節(jié)點(diǎn)位置的存儲(chǔ)結(jié)構(gòu)： 53.2生成哈弗曼樹的算法 53.3生成哈弗曼編碼的算法 73.4譯碼的算法 93.5打印哈弗曼樹的算法 103.6其他算法 114程序正確性驗(yàn)證 114.1輸入數(shù)據(jù)的控制 114.2打印哈弗曼樹 124.3哈弗曼編碼 124.4哈弗曼譯碼 135遇到的問題 136課程設(shè)計(jì)的主要收獲 137對(duì)今后課程設(shè)計(jì)的建議 131題目1.1問題描述設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理項(xiàng)目，直到選擇退出為止。1.2基本要求1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目中2)分別采用動(dòng)態(tài)和靜態(tài)存儲(chǔ)結(jié)構(gòu)3)初始化：鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼5)輸出編碼6)設(shè)字符集及頻度如下表：字符空格ABCDEFGHIJKLM

頻度1866413223210321154757153220

字符NOPQRSTUVWXYZ

頻度57631514851802381811611.3進(jìn)一步完成1)譯碼功能2)顯示哈夫曼樹3)界面設(shè)計(jì)的優(yōu)化2內(nèi)容2.1基本需求編寫一個(gè)哈夫曼編碼/譯碼器，次編碼/譯碼器有兩大主要功能：一是對(duì)一段文本進(jìn)行編碼，比如在利用電報(bào)機(jī)發(fā)送信息時(shí)，需要將文字“ABACCDA”轉(zhuǎn)換成類似“00110111001”這樣的二進(jìn)制組成的字符串；二是對(duì)一段密文進(jìn)行譯碼，比如在接收電報(bào)后，需要對(duì)“0101110100101”這樣的二進(jìn)制密文通過某種標(biāo)準(zhǔn)譯碼成看得懂的文字信息。另外還有一些輔助功能，比如可以打印一些簡單的哈夫曼樹的簡圖、有基本的主菜單、簡潔的操作界面、文件的讀寫。2.2.我的設(shè)計(jì)哈夫曼編碼/譯碼器主要有五個(gè)功能：初步編碼、文件編碼、手動(dòng)譯碼、文件譯碼、退出。初步編碼：實(shí)現(xiàn)基本的編碼，打印簡單的哈夫曼樹。輸入N個(gè)字符和N個(gè)權(quán)值，輸出每個(gè)字符對(duì)應(yīng)的編碼并打印哈夫曼樹。注意此功能只是對(duì)哈夫曼編碼的初探，只完成了生成哈夫曼樹和哈夫曼編碼的功能并沒有實(shí)現(xiàn)文件的編碼。文件編碼：對(duì)一個(gè)特定的文件進(jìn)行編碼，注意編碼標(biāo)準(zhǔn)可以使用保存在data.txt中的默認(rèn)標(biāo)準(zhǔn)也可以使用自己定義的標(biāo)準(zhǔn)。手動(dòng)譯碼：對(duì)手動(dòng)輸入的密文進(jìn)行譯碼，譯碼標(biāo)準(zhǔn)可自定義或默認(rèn)。文件譯碼：對(duì)存放密文的文件進(jìn)行譯碼，與手動(dòng)譯碼的主要區(qū)別就是在密文的獲取方法上。退出：哈夫曼編碼/譯碼器運(yùn)行結(jié)束。3算法設(shè)計(jì)3.1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3.1.1存放哈夫曼樹的存儲(chǔ)結(jié)構(gòu)：typedefstruct//存放樹節(jié)點(diǎn){chardata;//節(jié)點(diǎn)代表的字符intweight;//權(quán)值intparent;//父節(jié)點(diǎn)intlchild;//左孩子節(jié)點(diǎn)intrchild;//右孩子節(jié)點(diǎn)}HTNode;3.1.2存放哈夫曼編碼的存儲(chǔ)結(jié)構(gòu)：typedefstruct//存放編碼{charcd[60];//intstart;//編碼在數(shù)組中的開始下標(biāo)}HCode;3.1.3存放哈夫曼樹每個(gè)節(jié)點(diǎn)位置的存儲(chǔ)結(jié)構(gòu)：typedefstruct//節(jié)點(diǎn)位置{chardata;intn;//在完全二叉樹中的位置序號(hào)}tree;此存儲(chǔ)結(jié)構(gòu)的主要目的是記錄哈弗曼樹的每一個(gè)節(jié)點(diǎn)在完全二叉樹上的位置序號(hào)，便于輸出哈弗曼樹的大致圖形。3.2生成哈弗曼樹的算法算法思想：先將存有每個(gè)節(jié)點(diǎn)權(quán)值和數(shù)據(jù)的數(shù)組初始化，將每個(gè)節(jié)點(diǎn)的左右節(jié)點(diǎn)和父節(jié)點(diǎn)初始化為-1，保證每個(gè)節(jié)點(diǎn)都是獨(dú)立的。假設(shè)有n個(gè)節(jié)點(diǎn)，在建樹時(shí)需要比較n-1次；在每一次的比較中，先找出兩個(gè)權(quán)值最小的節(jié)點(diǎn)，將這兩個(gè)節(jié)點(diǎn)作為孩子節(jié)點(diǎn)形成一個(gè)雙親節(jié)點(diǎn)并修改相應(yīng)的屬性值，形成的雙親節(jié)點(diǎn)的權(quán)值等于兩孩子節(jié)點(diǎn)的和，雙親節(jié)點(diǎn)繼續(xù)參加下一次的比較。最后得到的那個(gè)節(jié)點(diǎn)就是樹的根節(jié)點(diǎn)。算法流程圖：代碼實(shí)現(xiàn):voidCreateHT(intn,HTNodeht[60])//構(gòu)造哈夫曼樹{inti,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++){ht[i].parent=ht[i].lchild=ht[i].rchild=-1;}for(i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1){if(ht[k].weight<min1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}}3.3生成哈弗曼編碼的算法算法思想：算法前提是哈弗曼樹已經(jīng)建立完成，假設(shè)有n個(gè)節(jié)點(diǎn)，這時(shí)每個(gè)節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，只需從葉子節(jié)點(diǎn)向上找到根節(jié)點(diǎn)就可得到哈弗曼編碼；此過程需要進(jìn)行n次循環(huán)，在每次循環(huán)中順著葉子節(jié)點(diǎn)向上遍歷。如果它為左孩子它所代表的編碼數(shù)組增加一個(gè)字符1，右孩子則增加一個(gè)字符0，以此規(guī)律直到找到根節(jié)點(diǎn)，注意編碼數(shù)組是從下標(biāo)為n的位置開始依次向前存的。算法流程圖：代碼實(shí)現(xiàn):voidCreateHCode(intn,HTNodeht[60],HCodehcd[60])//得到哈弗曼編碼{inti,f,c;HCodehc;for(i=0;i<n;i++){hc.start=n;c=i;f=ht[i].parent;while(f!=-1){if(ht[f].lchild==c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;hcd[i]=hc;}}3.4譯碼的算法算法思想：算法前提是哈弗曼樹已經(jīng)建立完成，假設(shè)待譯碼的密文為“01010101001010”，這時(shí)就可以利用密文和哈弗曼樹進(jìn)行譯碼；密文從開頭開始，哈弗曼樹從根節(jié)點(diǎn)開始一一對(duì)應(yīng)向前向下推進(jìn)，如果密文為0則向該節(jié)點(diǎn)的右節(jié)點(diǎn)推進(jìn)，為1則向左節(jié)點(diǎn)推進(jìn)，當(dāng)走到葉子節(jié)點(diǎn)時(shí)說明譯碼出了一個(gè)字符；之后再次返回根節(jié)點(diǎn)繼續(xù)上一次的操作直到密文結(jié)束，注意密文必須連續(xù)且不重復(fù)使用。算法流程圖：代碼實(shí)現(xiàn):voiddecipher(intn,HTNodeht[60],stringcode)//解碼{inti,j=0;i=2*n-2;//根節(jié)點(diǎn)的下標(biāo)cout<<"譯碼結(jié)果：\n";intmi=1;for(intj=0;j<code.length();j++){if(code[j]=='0')i=ht[i].lchild;//向下左elseif(code[j]=='1')i=ht[i].rchild;//向下右else{mi=0;break;}if(ht[i].lchild==-1){cout<<ht[i].data;i=2*n-2;}}if(mi==0)cout<<"密文有誤\n";if(ht[i].lchild!=-1&&i!=2*n-2)cout<<"密文不完整\n";}3.5打印哈弗曼樹的算法算法思想:要想打印哈弗曼樹的大致圖形，首先要計(jì)算出哈弗曼樹的每個(gè)節(jié)點(diǎn)在相應(yīng)的二叉樹中的序號(hào)，然后是控制節(jié)點(diǎn)間的空格和每行開始的空格。節(jié)點(diǎn)位置通過哈弗曼編碼得到，位置f初始為1，對(duì)于每個(gè)節(jié)點(diǎn)從編碼的第一個(gè)開始依次向后，如果為0則f=f*2+1,為1則f=f*2,一直到編碼結(jié)束即可算出最終位置?？崭竦慕鉀Q方法是從最后一行到第一行節(jié)點(diǎn)間空格的數(shù)量分別是1、3、7…..2^i-1個(gè),每行開頭的空格分別是1、4、8……2^i個(gè)。算法流程圖：3.6其他算法除了以上復(fù)雜的算法，還有一些簡單的算法。比如限制輸入的算法，只有當(dāng)控制臺(tái)輸入某幾個(gè)特定的字符時(shí)才會(huì)做出相應(yīng)的反應(yīng)；數(shù)據(jù)拆分算法，將從文件讀入的數(shù)據(jù)進(jìn)行拆分，把數(shù)字和非數(shù)字分別存入各自的數(shù)組里。4程序正確性驗(yàn)證4.1輸入數(shù)據(jù)的控制圖1：主界面選擇控制圖2：返回界面控制