赫夫曼編碼及譯碼器設(shè)計(jì)文檔

1、滁州學(xué)院課程設(shè)計(jì)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目 ：赫夫曼編碼與解碼器系 另計(jì)算機(jī)科學(xué)與技術(shù)專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)組 別：第二組起止日期：11年5月25日 11年6月10日指導(dǎo)教師：胡成祥計(jì)算機(jī)科學(xué)與技術(shù)系二OO九年制課程設(shè)計(jì)題目赫夫曼編碼和解碼組長(zhǎng)陸偉學(xué)號(hào)2010211108班級(jí) 計(jì)科（2）班系別計(jì)算機(jī)系專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)組員李夢(mèng) 2010211102林川 2010211105彭祥 2010211112馬巖 2010211109指導(dǎo)教師胡成祥課程設(shè)計(jì)目的設(shè)計(jì)一個(gè)赫夫曼編碼和解碼程序課程設(shè)計(jì)所需環(huán)境Microsoft Visual C+6.0課程設(shè)計(jì)任務(wù)要求通過設(shè)計(jì)的程序?qū)χ付ǖ奈募M(jìn)行編碼

2、和解碼課程設(shè)計(jì)工作進(jìn)度計(jì)劃序號(hào)起止日期工作內(nèi)容分工情況5-255-27商討問題的解決路徑和初 步實(shí)施方案。本小組組員根據(jù)個(gè)人所學(xué)情況，對(duì)問題 認(rèn)真分析，想出自己特色的實(shí)施方案， 為下次會(huì)議的方案選擇做準(zhǔn)備。5-286-6針對(duì)問題提出自己的見解， 并根據(jù)實(shí)際情況采取行動(dòng)。林川、李夢(mèng)編寫赫夫曼樹的生成及初始 化；馬巖編寫編碼；彭祥編寫界面和主 函數(shù)；陸偉編寫譯碼以及負(fù)責(zé)最后的程 序代碼的綜合和檢查修補(bǔ)。6-76-10完成文檔的編寫并對(duì)個(gè)人 工作進(jìn)行分析，發(fā)表自己的 見解。林川、李夢(mèng)：需求分析；馬巖：概要設(shè) 計(jì)及調(diào)試操作；彭祥：目錄和總結(jié)、體 會(huì)；陸偉：需求分析和致謝、參考文獻(xiàn)。指導(dǎo)教師簽字：年月日

3、教研室審核意見：教研室主任簽字：年月日目錄1 引言 4.1.1 課程設(shè)計(jì)目的 4.1.2 課程設(shè)計(jì)背景 4.1.3 課程設(shè)計(jì)主要內(nèi)容 52. 需求分析 52.1 課程設(shè)計(jì)題目 5.2.2 課程設(shè)計(jì)任務(wù) 5.2.3 要求 62.4 課程設(shè)計(jì)思想 6.2.5 軟硬件運(yùn)行環(huán)境 62.6 開發(fā)工具 63. 概要設(shè)計(jì) 63.1 課程設(shè)計(jì)的流程圖 63.2 主要的數(shù)據(jù)結(jié)構(gòu) 73.3 完成本課程設(shè)計(jì)所用方法及其原理 84 詳細(xì)設(shè)計(jì) 85 調(diào)試與操作說明 215.1 首先進(jìn)行初始化操作 215.2 譯碼、編碼等操作實(shí)現(xiàn) 225.2.1 譯碼操作 225.2.2 編碼操作 235.2.3 退出程序的運(yùn)行操作 2

4、46課程設(shè)計(jì)總結(jié)與體會(huì) 257致謝 2. 68參考文獻(xiàn) 2. 69附錄 2. 71 引言當(dāng)今社會(huì)，計(jì)算機(jī)技術(shù)和通信技術(shù)已經(jīng)不斷發(fā)展， 處理和傳輸?shù)臄?shù)據(jù)量越來 越龐大。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。 從而產(chǎn)生了赫夫 曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)， 該技術(shù)一般可將數(shù)據(jù)壓 縮 20%至 90%，通常我們將壓縮技術(shù)稱為編碼，將解壓過程稱為解碼。樹狀結(jié)構(gòu)簡(jiǎn)稱為數(shù)， 是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)， 是十分重要的 非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。1.1 課程設(shè)計(jì)目的本課程設(shè)計(jì)是為了讓同學(xué)們了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的作用和意義。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué) 與

5、技術(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.2 課程設(shè)計(jì)背景當(dāng)今社會(huì)，計(jì)算機(jī)技術(shù)和通信技術(shù)已經(jīng)不斷發(fā)展， 處理和傳輸?shù)臄?shù)據(jù)量越來 越龐大。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。 從而產(chǎn)生了赫夫 曼編

6、碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)， 該技術(shù)一般可將數(shù)據(jù)壓 縮 20%至 90%，通常我們將壓縮技術(shù)稱為編碼，將解壓過程稱為解碼。樹狀結(jié)構(gòu)簡(jiǎn)稱為數(shù)， 是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)， 是十分重要的 非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。在這個(gè)信息量發(fā)達(dá)的時(shí)代， 隨著社會(huì)的進(jìn)步， 信息不斷地增多和更新， 為了使信息更加 快速、準(zhǔn)確有效的傳輸，那就需要一個(gè)編碼和解碼的程序來完成。1.3 課程設(shè)計(jì)主要內(nèi)容本課程設(shè)計(jì)要求完成發(fā)送端對(duì)待傳送數(shù)據(jù)的編碼和接收端對(duì)傳送來的數(shù)據(jù)的譯碼。 要實(shí) 現(xiàn)五個(gè)功能：接收原始數(shù)據(jù)、編碼、譯碼、將編碼和譯碼存檔。通過系統(tǒng)的提示建立赫夫曼 樹并對(duì)

7、載入的原文件進(jìn)行編碼， 并保存到指定的文件中， 同時(shí)輸出到屏幕。 另一方面， 對(duì)原 文件進(jìn)行譯碼， 并將譯碼的結(jié)果保存到指定的文件中， 同時(shí)輸?shù)狡聊弧?對(duì)于編碼和譯碼的操 作中的文件導(dǎo)入，分為鍵盤輸入和文件輸入兩種。2. 需求分析2.1 課程設(shè)計(jì)題目赫夫曼編 /譯碼器。2.2 課程設(shè)計(jì)任務(wù)設(shè)計(jì)一個(gè)赫夫曼編碼和解碼程序。2.3 要求根據(jù)赫夫曼編碼和解碼算法，將指定的文件中的赫夫曼編碼進(jìn)行譯碼，并輸出到文件中，還要實(shí)現(xiàn)對(duì)文件中支付的編碼，并輸出編碼到文件中。2.4 課程設(shè)計(jì)思想輸入字符的和字符出現(xiàn)的頻率，并將字符作為葉子節(jié)點(diǎn)，頻率作為節(jié)點(diǎn)權(quán)值建立哈夫曼樹， 再根據(jù)在哈夫曼樹中， 由葉子結(jié)點(diǎn)逐步走到

8、根節(jié)點(diǎn)的路徑對(duì)葉子節(jié)點(diǎn)進(jìn)行編碼，碼時(shí)，從根節(jié)點(diǎn)找到葉子節(jié)點(diǎn)完成譯碼過程。2.5 軟硬件運(yùn)行環(huán)境Microsoft Windows XP 版本 2002 Service Pack 3或Microsoft Windows 7 旗艦版2.6 開發(fā)工具M(jìn)icrosoft Visual C+6.03. 概要設(shè)計(jì)3.1 課程設(shè)計(jì)的流程圖課程設(shè)計(jì)中算法的函數(shù)模塊生成哈夫曼樹' void haffman(int weight,char ch,int n,HafNode haffTree)void Haffma nCode (HafNode haffTree, int n,HCode haffCode)

9、務(wù)始化操作，、生成哈夫曼樹及哈夫曼編碼VoidIn it( int weighty char ch)Void哈夫曼編碼的函數(shù)，用于將文件編碼Bia n_ ma()哈夫曼譯碼過' 程的函數(shù)，用 于將文件譯碼void Yi_ma()界面設(shè)計(jì)void print()3.2主要的數(shù)據(jù)結(jié)構(gòu)#define M 100#define MAX 10000typedef struct int weight;int flag;int pare nt; char ch;int lchild;int rchild; HafNode; typedef structint bitM;int start;int w

10、eight;char ch;HCode;typedef structchar bitM;char ch;int weight;Coding;譯碼3.3 完成本課程設(shè)計(jì)所用方法及其原理 輸入字符的和字符出現(xiàn)的頻率，并將字符作為葉子節(jié)點(diǎn)，頻率作為節(jié)點(diǎn)權(quán)值建立哈夫 曼樹， 再根據(jù)在哈夫曼樹中， 由葉子結(jié)點(diǎn)逐步走到根節(jié)點(diǎn)的路徑對(duì)葉子節(jié)點(diǎn)進(jìn)行編碼， 時(shí)，從根節(jié)點(diǎn)找到葉子節(jié)點(diǎn)完成譯碼過程。4 詳細(xì)設(shè)計(jì)程序源代碼：#include <stdio.h>#include <stdlib.h>#include <string.h>#define M 100#define MAX

11、 10000typedef structint weight;int flag;int parent;char ch;int lchild;int rchild;HafNode;typedef structint bitM;int start;int weight;char ch;HCode;typedef structchar bitM;char ch;int weight;Coding;void haffman(int weight,char ch,int n,HafNode haffTree)int i,j,m1,m2,x1,x2;for (i=0;i<2*n-1;i+)if(i&

12、lt;n)haffTreei.weight=weighti;haffTreei.ch=chi;elsehaffTreei.weight=0;haffTreei.parent=-1;haffTreei.flag=0;haffTreei.lchild=-1;haffTreei.rchild=-1;for (i=0;i<n-1;i+)m1=m2=MAX;x1=x2=0;for (j=0;j<n+i;j+)if (haffTreej.weight<m1&&haffTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;els

13、e if(haffTreej.weight<m2 && haffTreej.flag=0) m2=haffTreej.weight;x2=j;haffTreex1.parent= n + i;haffTreex2.parent = n + i;haffTreex1.flag = 1;haffTreex2.flag = 1;haffTreen+i.weight = haffTreex1.weight + haffTreex2.weight;haffTreen+i.lchild = x1;haffTreen+i.rchild = x2;FILE *fp;fp=fopen(&q

14、uot;huffman.txt","w+");printf("%dn",n);fprintf(fp,"%dn",n);for (i=0;i<n;i+)fprintf(fp,"%c %d %d%dn",haffTreei.ch,haffTreei.parent,haffTreei.lchild,haffTreei.rchild);for (i=n;i<2*n-1;i+)fprintf(fp,"% %d %dn",haffTreei.parent,haffTreei.lchil

15、d,haffTreei.rchild);fclose(fp);void HaffmanCode (HafNode haffTree,int n,HCode haffCode) HCode *cd=( HCode *) malloc (sizeof (HCode); int i,j,child,parent;for (i=0; i<n; i+)cd->start=n-1;cd->weight=haffTreei.weight; cd->ch=haffTreei.ch;child=i;parent=haffTreechild.parent;while (parent !=-

16、1)if (haffTreeparent.lchild=child) cd->bitcd->start=0;elsecd->bitcd->start=1;cd->start-;child =parent;parent=haffTreechild.parent;for (j=cd->start+1; j<n; j+) haffCodei.bitj=cd->bitj;haffCode i.start = cd->start+1;haffCode i.weight=cd->weight;haffCode i.ch=cd->ch;voi

17、d Init(int weight,char ch)FILE *fp;int i,j,n;char ch1,wj15;printf(”進(jìn)行初始化操作 n請(qǐng)選擇你要進(jìn)行的操作：nJ.鍵盤輸入.W.文件輸入.n");scanf("%c",&ch1);if (ch1='J')printf(" 請(qǐng)輸入字符集的大小 n：n");scanf("%d",&n);if (ch1='W')printf(" 請(qǐng)輸入文件名 ：n");scanf("%s",wj

18、);fp=fopen(wj,"r");fscanf(fp,"%d",&n);HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);HCode *myHaffCode =(HCode *)malloc (sizeof (HCode)*n);for (i=0;i<n;i+)if (ch1='J')printf(" 請(qǐng)輸入字符和權(quán)值 :n");scanf("%s %d",&chi,&weighti);if

19、 (ch1='W')fscanf(fp,"%s %d",&chi,&weighti);if (ch1='W')fclose(fp);haffman(weight,ch,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode); fp=fopen("hfmtree.txt","w+");for (i=0;i<n;i+)printf("%c %d ",myHaffCodei.ch,myHaffCodei.weight);

20、fprintf(fp,"%c %d ",myHaffCodei.ch,myHaffCodei.weight); for ( j=myHaffCodei.start; j<n; j+)printf("%d",myHaffCodei.bitj); fprintf(fp,"%d",myHaffCodei.bitj);printf("n");fprintf(fp,"n");fclose(fp);printf(" 初始化成功 !n");void Bian_ma()FILE *fp

21、,*fp1,*fp2;char zf500;fp=fopen("hfmtree.txt","r");Coding ch100;char c;int i=0;while (feof(fp)=0)fscanf(fp,"%s %d %s",&chi.ch,&chi.weight,&chi.bit);i+;fclose(fp);printf(”現(xiàn)在進(jìn)行編碼操作。n請(qǐng)選擇：nJ鍵盤輸入.W.文件輸入.n");scanf("%s",&c);if (c='J')scanf

22、("%s",zf);printf(" 請(qǐng)輸入字符串 ：n");char ch120,ch220;int j;if (c='W')printf(" 請(qǐng)輸入正文的文件名 :n" scanf("%s",&ch1);fp1=fopen(ch1,"r");:n");printf(" 請(qǐng)輸入保存結(jié)果的文件名scanf("%s",&ch2);fp2=fopen(ch2,"w+");if (c='J')i

23、nt len,k;len=strlen(zf);for (k=0;k<len;k+)for (j=0;j<i;j+)if (chj.ch=zfk)fprintf(fp2,"%s",chj.bit);printf("%s",chj.bit);printf("n");if (c='W')while(feof(fp1)=0)fscanf(fp1,"%c",&c);for (j=0;j<i;j+) / 對(duì)文件中的每一個(gè)字符進(jìn)行編碼if (chj.ch=c)fprintf(fp2,&

24、quot;%s",chj.bit); printf("%s",chj.bit);fprintf(fp2,"n");printf("n");fclose(fp1);fclose(fp2);printf(" 提示：編碼過程完成 !已將結(jié)果存入 %s 中 .nn",ch2); void Yi_ma()FILE *fp,*fp1;fp=fopen("huffman.txt","r");int i,n; fscanf(fp,"%d",&n);Haf

25、Node *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);for (i=0;i<n;i+)fscanf(fp,"%s%d%d%dn",&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&m yHaffTreei.rchild);for (i=n;i<2*n-1;i+)fscanf(fp,"%d%d%dn",&myHaffTreei.parent,&myHaffTreei.l

26、child,&myHaffTreei.rchild); fclose(fp);printf(" 請(qǐng)輸入譯碼文件的文件名 :n");char ch120,ch220;scanf("%s",ch1);printf(" 請(qǐng)輸入結(jié)果文件的文件名 :n");scanf("%s",ch2);fp=fopen(ch1,"r");fp1=fopen(ch2,"w+");char ch;i=2*n-2;while (!feof(fp)fscanf(fp,"%c",&

27、amp;ch);if (ch='0')i=myHaffTreei.lchild;if (ch='1')i=myHaffTreei.rchild;if (i<n)printf("%c",myHaffTreei.ch);fprintf(fp1,"%c",myHaffTreei.ch);i=2*n-2;printf("n");fprintf(fp1,"n");fclose(fp);fclose(fp1);printf(" 提示：譯碼過程完成 !已將結(jié)果存入 %s 中 .nn

28、",ch2);void print()printf(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì));printf(H*滁州學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（2）班printf("*【陸偉李夢(mèng)林川彭祥馬巖】設(shè)計(jì)*n");printf("*歡迎使用哈夫曼編碼器和譯碼器*n");printf("*操作菜單如下所示););*n");printf(H*n");int main()int i,j,n=4;int weight100;char ch100,cha;print();Init(weight,ch);while (1)printf(”請(qǐng)輸入要執(zhí)行的操作：

29、nA.編碼B.譯碼C.退出n");printf(" 請(qǐng)輸入要執(zhí)行的操作 :n");scanf("%s",&cha);if (cha='C')break;switch (cha)case 'A'：Bian_ma();break; / 執(zhí)行編碼操作case 'B'：Yi_ma();break; / 執(zhí)行譯碼操作return 0;5 調(diào)試與操作說明5.1 首先進(jìn)行初始化操作輸入字符 Z ,X ,C ,V ,B ,N ,M , 并輸入每個(gè)字符的相應(yīng)權(quán)值 1 ,1 ,22 ,8 ,13 ,57 ,2

30、0 ，然后對(duì) 輸入的字符構(gòu)造哈夫曼樹，并對(duì)每個(gè)字符進(jìn)行編碼。運(yùn)行結(jié)果如圖所示：5.2譯碼、編碼等操作實(shí)現(xiàn)5.2.1譯碼操作將計(jì)算機(jī)硬盤中存儲(chǔ)的名為“待譯碼.txt ”的文件譯碼，并肩結(jié)果保存在相應(yīng)的文件夾下的名為“譯碼后.txt ”的文件中。5.2.2 編碼操作首先用鍵盤輸入字符串 ZXCVBNMMNBZZ, 讓程序?qū)ζ溥M(jìn)行編碼，并將編碼結(jié)果 保存在相應(yīng)文件夾下名為“鍵盤輸入字符的編碼.txt ”這個(gè)文件中。再將計(jì)算機(jī)硬盤中存儲(chǔ)的名為“待編碼的文件.txt ”的文件進(jìn)行編碼，并將編碼后的結(jié)果保存在相應(yīng)的文件夾下名為“待編碼的文件編碼后.txt ”的文件中。在進(jìn)行譯碼和編碼的時(shí)候，將保存到計(jì)算機(jī)硬盤中的文件中的結(jié)果也顯示在控制 臺(tái)的屏幕上，以便觀看。程序結(jié)果如圖所示：乍:譚程設(shè)計(jì)刑目灣嗖代碼D品吋囲夫曼軍嗎勒尋.e討碼作 行-執(zhí)成要要化入碼人比只a<j刖dr > 1 : 初請(qǐng)A.請(qǐng)R 嗚譯ZX提文文 成 的的 完 件件 程 疚文 過 m t m. t 3J- 亦X蘇X 帀 譯.t結(jié).t譯 入碼-<U5NB 4 世?瑜yCM- T請(qǐng)G 退出情輸入要執(zhí)行的操作： 蛙進(jìn)儲(chǔ)碼操作。 請(qǐng)選年：J 犍盤站入.譏