數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告哈夫曼編碼器

1、計算機工程學(xué)院 課程設(shè)計報告 課程名稱：課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計題目設(shè)計題目： 哈夫曼編碼器 院院 系：系： 計算機工程學(xué)院 班班 級：級： 軟件 1102 組組 別：別： 15 學(xué)生姓名學(xué)生姓名: : 吳超 學(xué)學(xué) 號號: 1101306229 起止日期起止日期: 2011 年 12 月 26 日 31 日 目目 錄錄 1、設(shè)計目的、設(shè)計目的.2 2、需求分析、需求分析.3 2.1 選題的意義及背景 2.2 基本要求 2.3運行環(huán)境及開發(fā)工具 3、概要設(shè)計、概要設(shè)計.4 3.1 設(shè)計思想 3.2 程序框圖 3.3 方法及原理 3.4 主要數(shù)據(jù)結(jié)構(gòu) 4、詳細設(shè)計、詳細設(shè)計.7 4.1 創(chuàng)

2、建哈夫曼樹 4.2 編碼 4.3 源程序 5、調(diào)試與操作說明、調(diào)試與操作說明.14 6、總結(jié)與體會、總結(jié)與體會.15 7、致謝、致謝.16 設(shè)計目的設(shè)計目的 1、 利用學(xué)過的數(shù)據(jù)結(jié)構(gòu)知識設(shè)計一個簡單的哈夫曼編/譯 碼器系統(tǒng)。 2 2、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分 析和設(shè)計能力； 3、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、 測試等基本方法和技能； 4、提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的 能力； 5、訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng) 軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。 2 2 需求分析需求分析 2.1、選題的意義和

3、背景、選題的意義和背景 利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信 息傳輸時間，降低傳輸成本。但是，這是要求在發(fā)送端通過一個編 碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù) 原） 。對于雙工信道（即可以雙向傳輸信息的信道） ，每端都需要一 個完整的編/譯碼系統(tǒng)。 2.2、基本要求、基本要求 (1)初始化：鍵盤輸入字符集大小 n、n 個字符和 n 個權(quán)值，建 立哈夫曼樹； (2)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； (3)輸出編碼； (4)設(shè)字符集及頻度如下表： 字 符 a b c d e f g h i j k l m 頻 度 186 64 13 22 32 103

4、 21 15 47 57 1 5 32 20 字 符 n o p q r s t u v w x y z 頻 度 57 63 15 1 48 51 80 23 8 18 1 16 1 2.3、運行環(huán)境及開發(fā)工具、運行環(huán)境及開發(fā)工具 本程序采用 visual c+6.0 編程實現(xiàn)。 3 概要設(shè)計概要設(shè)計 3.1 設(shè)計思想設(shè)計思想 本程序的主要功能是實現(xiàn)對用戶輸入的字符編碼，然 后再把編碼結(jié)果翻譯成原字符。但在進行這些操作之前必 須做一項工作，就是創(chuàng)建 huffman 樹。哈夫曼樹又稱最優(yōu) 二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的 帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到 根結(jié)點的

5、路徑長度（若根結(jié)點為 0 層，葉結(jié)點到根結(jié)點 的路徑長度為葉結(jié)點的層數(shù)）。樹的帶權(quán)路徑長度記為 wpl=(w1*l1+w2*l2+w3*l3+.+wn*ln)，n 個權(quán)值 wi(i=1,2,.n)構(gòu)成一棵有 n 個葉結(jié)點的二叉樹，相應(yīng) 的葉結(jié)點的路徑長度為 li(i=1,2,.n)?？梢宰C明哈夫 曼樹的 wpl 是最小的。哈夫曼在上世紀五十年代初就提 出這種編碼時，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最 短的編碼。它是一種變長的編碼。在編碼中，若各碼字 長度嚴格按照碼字所對應(yīng)符號出現(xiàn)概率的大小的逆序排 列，則編碼的平均長度是最小的 。 4 3.2 程序框圖及流程圖程序框圖及流程圖 哈夫曼編哈夫曼編

6、/譯碼器譯碼器 初始化初始化退出退出編碼編碼 3.33.3 方法及原理方法及原理 3.3.13.3.1創(chuàng)建創(chuàng)建 huffmanhuffman 樹樹 本文創(chuàng)建 huffman 樹是在順序鏈表的基礎(chǔ)上進行的，建樹原理如下： 1、根據(jù)給定的 n 個權(quán)值w1,w2,w3,wn，構(gòu)造具有 n 棵二叉樹的森 林 f=t1,t2,t3,tn，其中每棵二叉樹 ti 只有一個帶權(quán)值 wi 的根結(jié)點， 其左右子樹均為空。 2、重復(fù)以下步驟，直到 f 中僅剩下一棵樹為止： (1)在 f 中選取兩棵根結(jié)點的權(quán)值最小的二叉樹，作為左右子樹構(gòu)造一棵 新的二叉樹。使新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之 和。

7、 (2)在 f 中刪去這兩棵二叉樹，把新的二叉樹加入 f。 最后得到的就是 huffman 樹。 3.3.23.3.2 編碼編碼 編碼操作需在建立好 huffman 樹的基礎(chǔ)上進行。二叉樹的葉子結(jié)點標記 字符，由根結(jié)點沿著二叉樹路徑下行，左分支標記為 0，右分支標記為 1， 則每條從根結(jié)點到葉子結(jié)點的路徑唯一表示了該葉結(jié)點的二進制編碼。編碼 的時候，我們采用從葉子結(jié)點向上回溯的方法編碼，如果當前結(jié)點是其父結(jié) 點的左孩子，則編碼為 0，如果是右孩子，則編碼為 1，如此回溯，直到父 結(jié)點為空時，該字符的編碼就結(jié)束了，對應(yīng)編碼結(jié)構(gòu)中的編碼數(shù)組就是該字 符的編碼。如此操作，直到所有葉子結(jié)點都掃描一遍為

8、止，即編碼結(jié)束。 3.43.4 主要的數(shù)據(jù)結(jié)構(gòu)主要的數(shù)據(jù)結(jié)構(gòu) 3.4.13.4.1 huffmanhuffman 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) huffman 結(jié)點結(jié)構(gòu)是本程序的基本結(jié)構(gòu)，所有操作都在此上進行。其中 包括存儲字符的元素 data，字符的權(quán)值 weight，以及左右孩子指針和父指 針。 typedef struct char ch;/結(jié)點值 int weight;/權(quán)值 int parent;/父結(jié)點指針 int lchild; /左孩子結(jié)點指針 int rchild;/右孩子結(jié)點指針 huffnode; 詳細設(shè)計詳細設(shè)計 4.14.1 創(chuàng)建創(chuàng)建 huffmanhuffman 樹樹 4.1.

9、14.1.1 功能描述功能描述 huffman 樹是整個程序的核心部分，是編碼譯碼操作的前提。哈 夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。根 據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的 編碼。在編碼中，若各碼字長度嚴格按照碼字所對應(yīng)符號出現(xiàn)概 率的大小的逆序排列，則編碼的平均長度是最小的 。 4.1.24.1.2 算法原理算法原理 首先根據(jù)用戶輸入創(chuàng)建 n 棵子樹的森林，然后對所有子樹掃描， 找出權(quán)值最小的兩個子樹，把它們合并成一棵新的子樹，同時把它 們的權(quán)值之和作為新樹的權(quán)值。把這兩棵子樹刪掉，再把新樹加如 到森林中，然后再掃描出權(quán)值最小的兩棵子樹，接著進行同樣的

10、操 作，直到只剩下一棵樹即為 huffman 樹。 4.1.34.1.3 算法流程算法流程 7 7 4.24.2 編碼編碼 4.2.14.2.1 功能描述功能描述 編碼的功能就是把字符轉(zhuǎn)換成二進制數(shù)來存儲 4.2.24.2.2 算法原理算法原理 編碼的時候，我們采用從葉子結(jié)點向上回溯的方法編碼，如果當前結(jié)點 是其父結(jié)點的左孩子，則編碼為 0，如果是右孩子，則編碼為 1，如此回溯， 直到父結(jié)點為空時，該字符的編碼就結(jié)束了，對應(yīng)編碼結(jié)構(gòu)中的編碼數(shù)組就 是該字符的編碼。如此操作，直到所有葉子結(jié)點都掃描一遍為止，即編碼結(jié) 束。 4.2.34.2.3 算法流程算法流程 4.44.4 源程序源程序 #in

11、clude#include #include#include #include#include #include#include #include#include typedeftypedef structstruct /哈夫曼樹的結(jié)構(gòu)體哈夫曼樹的結(jié)構(gòu)體 charchar ch;ch; intint weight;weight; /權(quán)值權(quán)值 intint parent,lchild,rchild;parent,lchild,rchild; htnode,*hfmtree;htnode,*hfmtree; typedeftypedef charchar *hfmcode;*hfmcode; vo

12、idvoid select(hfmtreeselect(hfmtree i,j,x,y; for(j=1;j=a;+j)for(j=1;j=a;+j) if(htj.parent=0)if(htj.parent=0) x=j;x=j; break;break; for(i=j+1;i=a;+i)for(i=j+1;i=a;+i) if(hti.weighthtx.weightx=i; /選出最小的節(jié)點選出最小的節(jié)點 for(j=1;j=a;+j)for(j=1;j=a;+j) if(htj.parent=0y=j; break;break; for(i=j+1;i=a;+i)for(i=j+1

13、;i=a;+i) if(hti.weighthty.weight*p1=y; *p2=x;*p2=x; elseelse *p1=x;*p1=x; *p2=y;*p2=y; voidvoid hfmcoding(hfmtreehfmcoding(hfmtree i,start,c,f,m,w; intint p1,p2;p1,p2; charchar *cd,z;*cd,z; if(n=1)if(n=1) return;return; m=2*n-1;m=2*n-1; ht=(hfmtree)malloc(m+1)*sizeof(htnode);ht=(hfmtree)malloc(m+1)*

14、sizeof(htnode); for(i=1;i=n;+i)for(i=1;i=n;+i) /初始化初始化 n n 個葉子結(jié)點個葉子結(jié)點 printf(printf(請輸入第請輸入第%d%d 字符信息和權(quán)值：字符信息和權(quán)值：,i);,i); scanf(%c%d,scanf(%c%d, while(getchar()!=n)while(getchar()!=n) continue;continue; hti.ch=z;hti.ch=z; hti.weight=w;hti.weight=w; hti.parent=0;hti.parent=0; hti.lchild=0;hti.lchild=

15、0; hti.rchild=0;hti.rchild=0; for(;i=m;+i)for(;i=m;+i) /初始化其余的結(jié)點初始化其余的結(jié)點 hti.ch=0;hti.ch=0; hti.weight=0;hti.weight=0; hti.parent=0;hti.parent=0; hti.lchild=0;hti.lchild=0; hti.rchild=0;hti.rchild=0; for(i=n+1;i=m;+i)for(i=n+1;i=m;+i) /建立哈夫曼樹建立哈夫曼樹 select(ht,i-1,select(ht,i-1, htp1.parent=i;htp2.par

16、ent=i;htp1.parent=i;htp2.parent=i; hti.lchild=p1;hti.rchild=p2;hti.lchild=p1;hti.rchild=p2; hti.weight=htp1.weight+htp2.weight;hti.weight=htp1.weight+htp2.weight; hc=(hfmcode)malloc(n+1)*sizeof(charhc=(hfmcode)malloc(n+1)*sizeof(char *);*); cd=(charcd=(char *)malloc(n*sizeof(char);*)malloc(n*sizeof(

17、char); cdn-1=0;cdn-1=0; for(i=1;i=n;+i)for(i=1;i=n;+i) /給給 n n 個字符編碼個字符編碼 start=n-1;start=n-1; for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) if(htf.lchild=c)if(htf.lchild=c) cd-start=0;cd-start=0; elseelse cd-start=1;cd-start=1; hci=(char*)malloc(n-start)*siz

18、eof(char);hci=(char*)malloc(n-start)*sizeof(char); strcpy(hci,strcpy(hci, free(cd);free(cd); intint main()main() charchar code100,h100,hl100;code100,h100,hl100; intint n,i,j,k,l;n,i,j,k,l; ifstreamifstream input_file;input_file; /文件輸入輸出文件輸入輸出 ofstreamofstream output_file;output_file; charchar choice

19、,str100;choice,str100; hfmtreehfmtree ht;ht; hfmcodehfmcode hc;hc; coutn;coutn; coutcout 軟件軟件 11021102 班班 11013062291101306229 吳超吳超n;n; while(choice!=q*n; coutcout i.initi.init e.encodinge.encoding q.exitn;q.exitn; coutcoutchoice;cinchoice; if(choice=i|choice=i)if(choice=i|choice=i) /初始化哈夫曼初始化哈夫曼 樹樹

20、 coutcoutn;cinn; hfmcoding(ht,hc,n);hfmcoding(ht,hc,n); for(i=1;i=n;+i)for(i=1;i=n;+i) couthti.ch:hciendl;couthti.ch:hciendl; output_file.open(hfmtree.txt);output_file.open(hfmtree.txt); if(!output_file)if(!output_file) coutcantcoutcant oenoen file!endl;file!endl; returnreturn 1;1; for(i=1;i=n;i+)fo

21、r(i=1;i=n;i+) output_file(hti.chhci);output_file(hti.chhci); output_file.close();output_file.close(); coutcout哈夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入哈夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入 hfmtree.txthfmtree.txt 文文 件中件中!endl;!endl; elseelse if(choice=e|choice=e)if(choice=e|choice=e) /進行編碼，進行編碼， 并將字符放入并將字符放入 tobetran.txttobetran.txt，碼值放入，碼值放入

22、codefile.txtcodefile.txt 中中 printf(printf(請輸入字符：請輸入字符：);); gets(str);gets(str); output_file.open(tobetran.txt);output_file.open(tobetran.txt); if(!output_file)if(!output_file) coutcantcoutcant oenoen file!endl;file!endl; returnreturn 1;1; output_filestrendl;output_filestrendl; output_file.close();ou

23、tput_file.close(); output_file.open(codefile.txt);output_file.open(codefile.txt); if(!output_file)if(!output_file) coutcantcoutcant openopen file!endl;file!endl; returnreturn 1;1; for(i=0;istrlen(str);i+)for(i=0;istrlen(str);i+) for(j=0;j=n;+j)for(j=0;j=n;+j) if(htj.ch=stri)if(htj.ch=stri) output_fi

24、lehcj;output_filehcj; break;break; output_file.close();output_file.close(); coutn;coutn; coutcout編碼完畢，并且已經(jīng)存入編碼完畢，并且已經(jīng)存入 codefile.txtcodefile.txt 文件！文件！n;n; input_file.open(codefile.txt);input_file.open(codefile.txt); /從從 codefile.txtcodefile.txt 中讀入編碼，輸出在終端中讀入編碼，輸出在終端 if(!input_file)if(!input_file) coutcantcoutcant oenoen file!endl;file!code;input_filecode; coutc