數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)赫夫曼編碼實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告 赫夫曼編碼實(shí)驗(yàn)課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 專 業(yè) 班 級 11級計(jì)科（2）班 學(xué) 生 姓 名 王琦 學(xué) 號 114090102036 指 導(dǎo) 教 師 馮 韻 實(shí) 驗(yàn) 時(shí) 間 ： 2013 年 9 月 24 日 2013至 2014學(xué)年第 1 學(xué)期第 1 至 9 周目 錄一、概述1二、系統(tǒng)分析1三、概要設(shè)計(jì)2四、詳細(xì)設(shè)計(jì)44.1 赫夫曼樹的建立44.1.1 選擇選擇parent 為0 且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法54.1.2 統(tǒng)計(jì)字符串中字符的種類以及各類字符的個(gè)數(shù)74.1.3構(gòu)造赫夫曼樹84.2赫夫曼編碼104.2.1赫夫曼編碼算法104.2.2建立正文的編碼文件11

2、五、運(yùn)行與測試12六、總結(jié)與心得1313 / 15文檔可自由編輯打印一、概述 本設(shè)計(jì)是對輸入的一串電文字符實(shí)現(xiàn)赫夫曼編碼，再對赫夫曼編碼生產(chǎn)的代碼串進(jìn)行譯碼，輸出 電文字符串。 在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí) 間越來越引起人們的重視，赫夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。二、系統(tǒng)分析 赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進(jìn)制編碼成為赫夫曼編碼。樹中從根到 每個(gè)葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示 “1”碼，取每條路徑上的“0”或“1”的序列作為和每個(gè)葉

3、子對應(yīng)的字符的編碼，這就是赫夫曼編碼。 通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式 的字符串，但在信息傳遞時(shí)，總希望總長度能盡可能短，即采用最短碼。 假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為W i ,編碼長度為L i ，電文中有n 種字符，則電文編碼總長為W i L i 。 若將此對應(yīng)到二叉樹上，W i 為葉節(jié)點(diǎn)的權(quán) ，L i 為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑長度。那么，W i L i 恰好為二叉 樹上帶權(quán)路徑長度。 因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n 種子符出現(xiàn)的頻率作權(quán)，構(gòu)造一刻赫夫曼樹， 此構(gòu)造過程成為赫夫曼編碼。 根據(jù)設(shè)計(jì)要求和分析，要實(shí)現(xiàn)設(shè)計(jì)

4、，必須實(shí)現(xiàn)以下方面的功能： （1） 赫夫曼樹的建立； （2） 赫夫曼編碼的生成； （3） 編碼文件的譯碼；三、概要設(shè)計(jì) void main()void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)/編碼部分char *decode(HuffmanCode Hc)/譯碼void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) /生成Huffman樹void select(HufmanTree HT,int k,int &s1,int &s2) /找尋pare

5、nt為0,權(quán)最小的兩個(gè)節(jié)點(diǎn)其流程圖如下：進(jìn)行相應(yīng)的操作輸出結(jié)果結(jié)束構(gòu)造赫夫曼樹程序結(jié)束退出對編碼串譯碼對字符串編碼開始進(jìn)行相應(yīng)的操作四、詳細(xì)設(shè)計(jì) 4.1 赫夫曼樹的建立 由赫夫曼算法的定義可知，初始森林中共有 n 棵只含根節(jié)點(diǎn)的二叉樹。算法的第二步是：將當(dāng)前森林 中的兩顆根節(jié)點(diǎn)的二叉樹，合并成一顆新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個(gè)新 節(jié)點(diǎn)。顯然要進(jìn)行 n-1 次合并，所以共產(chǎn)生 n-1 個(gè)新節(jié)點(diǎn)，它們都是具有兩個(gè)孩子分支結(jié)點(diǎn)。由此可 知，最新求得的赫夫曼樹中一共有2n-1 個(gè)結(jié)點(diǎn)，其中n 個(gè)結(jié)點(diǎn)是初始森林的n 個(gè)孤立結(jié)點(diǎn)。并且赫夫 曼樹中沒有度數(shù)為1 的分支結(jié)點(diǎn)。我們可用一個(gè)

6、大小為2n-1 的一維數(shù)組來存儲赫夫曼樹中的結(jié)點(diǎn)。因 此，赫夫曼樹的存儲結(jié)構(gòu)描述為： #define n 100 #define m 2*n-1 typedef struct int weight; int lchild,rchild,parent; HTNode; T typedef HTNode HuffmanTreem+1; 開始結(jié)束第i個(gè)結(jié)點(diǎn)權(quán)值i=num?創(chuàng)建赫夫曼樹輸出字符統(tǒng)計(jì)情況第i個(gè)根結(jié)點(diǎn)i=2*num-1?i=num?否是否是否是4.1.1 選擇選擇parent 為0 且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法 void select(HuffmanTree T,int k,int *s1

7、,int *s2)/在HT1k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號分別為S1和S2 int i,j; int min1=100; for(i=1;i<=k;i+)/查找s1 if(Ti.weight<min1 && Ti.parent=0) j=i;min1=Ti.weight; *s1=j; min1=32767; for(i=1;i<=k;i+)/查找s2,不和s1相同 if(Ti.weight<min1 && Ti.parent=0 && i!=(*s1) j=i; min1=Ti.weight; *

8、s2=j;4.1.2 統(tǒng)計(jì)字符串中字符的種類以及各類字符的個(gè)數(shù)假設(shè)電子文件字符串全是大寫字母，那么該算法的實(shí)現(xiàn)思想是：先定義一個(gè)含有26個(gè)元素的臨時(shí)整型數(shù)組，用來存儲各種字母出現(xiàn)的次數(shù)。應(yīng)為大寫字母的ASCII碼與整數(shù)126個(gè)元素之間相差64，因此在算法中使用字母減去64作為統(tǒng)計(jì)數(shù)組的下標(biāo)對號入座，無須循環(huán)判斷來實(shí)現(xiàn)，從而提高了效率；另外，要求出電文字符串中有多少種字符，并保存這些字符以供編碼時(shí)使用。統(tǒng)計(jì)和保存都比較容易，用一個(gè)循環(huán)來判斷先前統(tǒng)計(jì)好的各類字符個(gè)數(shù)的數(shù)組元素是否為零，若不為零，則將其值存入一個(gè)數(shù)組對應(yīng)的元素中，同時(shí)將其對應(yīng)的字符也存入另一個(gè)數(shù)組元素中。具體實(shí)現(xiàn)如下：int jsq

9、(char *s,int cnt,char str) /統(tǒng)計(jì)各字符串中各種字母的個(gè)數(shù)以及字符的種類 char *p; int i,j,k; int temp27; for(i=1;i<=26;i+) tempi=0; for(p=s;*p!='0'p+) /統(tǒng)計(jì)各種字符個(gè)數(shù) if(*p>='A' && *p<='Z') k=*p-64; tempk+; j=0; for(i=1,j=0;i<=26;i+)/統(tǒng)計(jì)有多少種字符 if(tempi!=0) j+; strj=i+64;/將對應(yīng)的數(shù)組送到數(shù)組中 cn

10、tj=tempi;/存入對應(yīng)數(shù)組的權(quán)值 return j;4.1.3構(gòu)造赫夫曼樹void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str)/構(gòu)造赫夫曼樹HT int i,s1,s2; for(i=1;i<=2*num-1;i+)/初始化HT，左右孩子，雙親，權(quán)值都為0 HTi.lchild=0; HTi.rchild=0; HTi.parent=0; HTi.weight=0; for(i=1;i<=num;i+)/輸入num個(gè)葉節(jié)點(diǎn)的權(quán)值 HTi.weight=cnti; for(i=num+1;i<=

11、2*num-1;i+)/從numd后面開始新建結(jié)點(diǎn)存放新生成的父節(jié)點(diǎn) select(HT,i-1,&s1,&s2);/在HT1i-1中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號分別為s1和s2 HTs1.parent=i;HTs2.parent=i;/將s1和s2的parent賦值 HTi.lchild=s1; HTi.rchild=s2;/新結(jié)點(diǎn)的左右孩子 HTi.weight=HTs1.weight+ HTs2.weight;/新結(jié)點(diǎn)的權(quán)值 for(i=0;i<=num;i+)/輸入字符集中的字符 HCi.ch=stri; i=1; while(i<=n

12、um) printf("字符 %c,次數(shù)為: %dn",HCi.ch,cnti+);4.2赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設(shè)計(jì)要求和實(shí)際需要定義的類型如下： typedef struct char ch; char bitsn+1; int start ; CodeNode; typedef CodeNode HuffmanCoden; 4.2.1赫夫曼編碼算法 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) /根據(jù)赫夫曼樹HT 求赫夫曼編碼表 int c,p,i; char cdn;

13、int start; cdnum='0' for(i=1;i<=num;i+) start=num; c=i; while(p=HTc.parent)>0)/直至上訴到htc是樹根為止 /若HTc是HTp的孩子，則生成0；否則生成代碼1 cd-start=(HTp.lchild= =c)? '0':'1' :c=p; /end of while strcpy(HCi.bits,&cdstart); HCi.len=num-start; 4.2.2建立正文的編碼文件 建立編碼文件的基本思想是：將要編碼的字符串中的字符逐一與預(yù)先生成赫夫曼樹時(shí)保保存的 字符編碼對照表進(jìn)行比較，找到之后，對該字符的編碼寫入代碼文件，直至所有字符處理完畢為止。 具體算法如下： viod coding(huffmanCode HC,char *str) int i,j; FILE *fp; fp =fopen(“code”,”w”); while(*str)/對電文中字符逐一生成編碼并寫入文件 for(i=1;i<=num;i+) if(HCi.ch= =*str) for(j=0;j<=HCi.len;j+) fputc (HCi.bitsj,