哈夫曼課程設(shè)計(jì)報(bào)告哈夫曼編譯碼器

1、西安郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目： 哈夫曼編/譯碼器院系名稱： 計(jì)算機(jī)學(xué)院 專業(yè)名稱： 軟件工程班 級(jí)： 1101班 學(xué)生姓名： 武妍娜學(xué)號(hào)（8位）： 04113027指導(dǎo)教師： 李培 設(shè)計(jì)起止時(shí)間：2012年12月3日2012年12月14日15 / 15文檔可自由編輯打印一. 設(shè)計(jì)目的1.鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力；2.深化對(duì)算法課程中基本概念、理論和方法的理解；3.鞏固構(gòu)造哈夫曼樹(shù)的算法；4.設(shè)計(jì)試驗(yàn)用程序?qū)嶒?yàn)哈夫曼樹(shù)的構(gòu)造，編碼和譯碼。二. 設(shè)計(jì)內(nèi)容利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送

2、端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼的編/譯碼器。 主程序模塊三概要設(shè)計(jì)1功能模塊圖； 編碼模塊 譯碼模塊 文件模塊 密碼模塊2各個(gè)模塊詳細(xì)的功能描述。（1）主程序模塊打印菜單；讓用戶選擇是編碼還是譯碼；讓用戶決定是否觀看一些信息。（2） 密碼模塊void Login()密碼函數(shù)，用戶輸入用戶名和密碼，密碼正確方能進(jìn)入系統(tǒng)，否則重新輸入。（3）編碼模塊void OpenSource s)打開(kāi)源文件，并將其內(nèi)容存到s中void Code(char s,char str,char code,int freq,HFMTree *

3、HT,CodeNode HC)編碼函數(shù)，調(diào)用編碼所需的所有函數(shù)void Search(char s,char str,int freq)查找各個(gè)字符，將其存到str中，并統(tǒng)計(jì)其出現(xiàn)的頻數(shù)，即權(quán)值，存放在freq中void CreateHFMTree(HFMTree *HT,int freq)創(chuàng)建哈夫曼樹(shù)void HFMCode(HFMTree HT,CodeNode HC,char str)按左0右1的順序進(jìn)行編碼AllCode(s,HC,code)將所有字符的編碼連起來(lái)，存放到code中Save(code)將編碼結(jié)果保存到文件code.txt中（4）譯碼模塊void DeCode(char

4、code,char str,char ss,HFMTree *HT,CodeNode HC) 譯碼函數(shù)，調(diào)用譯碼所需的所有函數(shù)void OpenCode code)打開(kāi)編碼文件Decoding(code,*HT,str,ss)從根結(jié)點(diǎn)開(kāi)始按編碼順序進(jìn)行譯碼Save(ss)將譯碼結(jié)果保存到文件decode.txt中查找權(quán)值查找字符四詳細(xì)設(shè)計(jì)創(chuàng)建哈夫曼樹(shù)密碼1功能函數(shù)的調(diào)用關(guān)系圖編碼連接編碼編碼主函數(shù)保存編碼打開(kāi)源文件菜單打開(kāi)文件譯碼顯示哈夫曼信息保存譯碼譯碼開(kāi)始2.各功能函數(shù)的數(shù)據(jù)流程圖（1）創(chuàng)建哈夫曼樹(shù)函數(shù) int i=0;HFMTree p,HT1,HT2;p=*HT=(HFMTree)ma

5、lloc(sizeof(HFMNode);p->next=p->LChild=p->RChild=p->Parent=NULL;i<2n-1 是 否i+;p=*HT;p->next=(HFMTree)malloc(sizeof(HFMNode);p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;i+; i<ni<2n-1 否p->weight=freqi;p=p->next;i+; 是Select(*HT,i,&HT1,&HT2);H

6、T1->Parent=HT2->Parent=p;p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight;p=p->next; i+;開(kāi)始（2）編碼函數(shù) int i=0;HFMTree q,p=HT; i<n 是HCi.ch=stri;HCi.coden-1='0'i=0; i<nHCi.flag=n-1;p=q;q->Parent!=Null; 否 是q=q->Parent->Lchild HCi.code-HCi.flag=

7、9;0'q=q->Parent; 是 否HCi.code-HCi.flag='1'p=p->next3重點(diǎn)設(shè)計(jì)及編碼（1）密碼設(shè)計(jì)：void Login()char username15;char password9; char c; int i = 0; printf("nn請(qǐng)輸入用戶名:");gets(username);printf("n請(qǐng)輸入密碼:"); while (c=getch()!='r') if (i<8 && isprint(c) passwordi+ = c;

8、 putchar('*'); putchar('n'); passwordi = '0'if(!(strcmp(password,"04113027")printf("nn恭喜您，登陸成功!nn歡迎使用該系統(tǒng)!nn");system("pause");elseprintf("nn密碼錯(cuò)誤,您無(wú)權(quán)使用該系統(tǒng)!nn請(qǐng)重新輸入!nn");system("pause");system("cls");Login();（2） 創(chuàng)建哈夫曼樹(shù)：

9、void CreateHFMTree(HFMTree *HT,int freq)int i;HFMTree p,HT1,HT2;p=*HT=(HFMTree)malloc(sizeof(HFMNode); p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=1;i<2*n-1;i+)p->next=(HFMTree)malloc(sizeof(HFMNode);p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=0,p

10、=*HT;i<n;i+)p->weight=freqi;p=p->next;for(i=n;i<2*n-1;i+)Select(*HT,i,&HT1,&HT2);HT1->Parent=HT2->Parent=p;p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight;p=p->next; 5 測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1正常測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果 2.異常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果 六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)1 改進(jìn)方案通過(guò)一周的課程設(shè)計(jì)使我對(duì)哈夫曼樹(shù)以及哈

11、夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。由于時(shí)間問(wèn)題，對(duì)于哈夫曼的壓縮和解壓縮暫時(shí)不能實(shí)現(xiàn)了。這也是我比較遺憾的一件事了。不過(guò)在空閑時(shí)間我還會(huì)繼續(xù)研究這個(gè)問(wèn)題的。2體會(huì)開(kāi)始的時(shí)候，代碼中有許多的錯(cuò)誤，讓我束手無(wú)策，最后我耐心的一步一步慢慢地改正錯(cuò)誤才讓我看到了希望。在實(shí)現(xiàn)文章的讀入時(shí)， 由于對(duì)文件不是太熟悉，只好翻開(kāi)C語(yǔ)言書(shū)本仿照其模式編寫(xiě)。許多的錯(cuò)誤讓我明白了細(xì)心是非常重要的。同時(shí)，對(duì)于編程者而言，思路清晰也是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。及時(shí)的向老師請(qǐng)教也是很有幫助的，因?yàn)楫吘刮覀兪切率?，?duì)于某些問(wèn)題很難弄清

12、楚。而且，某些錯(cuò)誤對(duì)于我們來(lái)說(shuō)有時(shí)候想半天都弄不來(lái)，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。這次課程設(shè)計(jì)不但讓我又學(xué)得了一些編程知識(shí)，還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告， 學(xué)會(huì)了如何更好的畫(huà)流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！通過(guò)這次課程設(shè)計(jì)，我看清楚了自己的編程功底和動(dòng)手能力還不如人意，這主要是平時(shí)實(shí)踐太少的緣故。我想，在即將到來(lái)的寒假中，我會(huì)努力嘗試編寫(xiě)一些較大的程序。由于我們是軟件工程專業(yè)的學(xué)生，就應(yīng)該更加嚴(yán)格要求自己。七參考文獻(xiàn)1. 耿國(guó)華主編，數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述，高等教育出版社，2005年2. 陳銳，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社 2012年8 附錄#inc

13、lude <stdio.h> #include <stdlib.h>#include <string.h> #include <conio.h>#include <ctype.h>#define M 500 #define N 128typedef struct node int weight;/權(quán)值struct node *Parent,*LChild,*RChild;/雙親結(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)struct node *next;/下一個(gè)結(jié)點(diǎn)HFMNode,*HFMTree;typedef struct char ch;/字

14、符 char codeN+1;/編碼 int flag;/標(biāo)記CodeNode;int n;/葉子結(jié)點(diǎn)個(gè)數(shù)/密碼void Login()char username15;char password9; char c; int i = 0; printf("nn請(qǐng)輸入用戶名:");gets(username);printf("n請(qǐng)輸入密碼:"); while (c=getch()!='r') if (i<8 && isprint(c) passwordi+ = c; putchar('*'); putch

15、ar('n'); passwordi = '0'if(!(strcmp(password,"04113027")printf("nn恭喜您，登陸成功!nn歡迎使用該系統(tǒng)!nn");system("pause");elseprintf("nn密碼錯(cuò)誤,您無(wú)權(quán)使用該系統(tǒng)!nn請(qǐng)重新輸入!nn");system("pause");system("cls");Login();void Menu(void)/菜單printf("tt*n&quo

16、t;);printf("tt* *n");printf("tt* 歡迎進(jìn)入 *n");printf("tt* 哈夫曼編/譯碼系統(tǒng) *n");printf("tt* *n");printf("tt* 1.顯示源文件。 *n");printf("tt* 2.編碼。 *n");printf("tt* 3.譯碼。 *n");printf("tt* 4.顯示哈夫曼信息。 *n");printf("tt* 0.退出。 *n");

17、printf("tt* *n");printf("tt*n");printf("tt* *n");printf("tt* 請(qǐng)輸入相應(yīng)操作的序號(hào)(0-3) *n");printf("tt* *n");printf("tt*n");/打開(kāi)源文件void OpenSource s)FILE *fp;int i=0;system("cls");if(fp=fopen("source.txt","rt")=NULL)/打開(kāi)文件

18、source.txtprintf("打開(kāi)文件失??！n");exit(1);si+=fgetc(fp);while(si-1!=EOF)/將文件中的字符串存入s中si+=fgetc(fp);si='0' fclose(fp);/存儲(chǔ)文件void Save(char s)char name10;FILE *fp;printf("請(qǐng)輸入要保存的文件名：");gets(name);if(fp=fopen(name,"wt")=NULL) printf("存儲(chǔ)文件失??！n");exit(1);fputs(s,

19、fp);printf("n文件保存成功，文件名為:%s。nn",name);system("pause");fclose(fp);void Search(char s,char str,int freq)/查找各個(gè)字符，并統(tǒng)計(jì)其出現(xiàn)的頻數(shù)int i,j,k=0;for(i=0;i<N;i+)/初始化freq freqi=0; for(i=0;si;i+)for(j=0;j<k;j+)/統(tǒng)計(jì)各個(gè)字符出現(xiàn)的頻數(shù)，即權(quán)值，并將其存放在freqif(strj=si) freqj+; break; if(j=k)/查找各個(gè)字符，并將其存放在str中 s

20、trk=si;freqk+; strk='0'n=k-1;/n為查找后字符的總個(gè)數(shù)void Select(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)/查找權(quán)值最小的兩個(gè)結(jié)點(diǎn)inti,min;HFMTreep;min=1000;for(i=0,p=HT;i<k;i+,p=p->next)/查找權(quán)值最小的結(jié)點(diǎn)if(p->weight<min&&p->Parent=0)min=p->weight;*HT1=p;min=1000;for(i=0,p=HT;i<k;i+,p=p->

21、next)/查找權(quán)值次小的結(jié)點(diǎn)if(p->weight<min&&p->Parent=0&&p!=*HT1)min=p->weight;*HT2=p;void CreateHFMTree(HFMTree *HT,int freq)/創(chuàng)建哈夫曼樹(shù)int i;HFMTree p,HT1,HT2;p=*HT=(HFMTree)malloc(sizeof(HFMNode); /申請(qǐng)空間p->next=p->LChild=p->RChild=p->Parent=NULL;/初始化for(i=1;i<2*n-1;i+)/

22、申請(qǐng)空間，并初始化所有結(jié)點(diǎn)，共2n-1個(gè)p->next=(HFMTree)malloc(sizeof(HFMNode);p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=0,p=*HT;i<n;i+)/給前n個(gè)結(jié)點(diǎn)賦權(quán)值p->weight=freqi;p=p->next;for(i=n;i<2*n-1;i+)/開(kāi)始創(chuàng)建哈夫曼樹(shù)Select(*HT,i,&HT1,&HT2);/查找權(quán)值最小的兩個(gè)結(jié)點(diǎn)HT1->Parent=HT2->Paren

23、t=p;p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight;/更改雙親結(jié)點(diǎn)的權(quán)值p=p->next; void HFMCode(HFMTree HT,CodeNode HC,char str)/編碼int i; HFMTree q,p=HT; for(i=0;i<n;i+)HCi.ch=stri;HCi.coden-1='0'/處理編碼的結(jié)束符for(i=0;i<n;i+)/開(kāi)始解碼HCi.flag=n-1;/根結(jié)點(diǎn)for(q=p;q->Parent;q

24、=q->Parent)if(q=q->Parent->LChild)HCi.code-HCi.flag='0'/左0else HCi.code-HCi.flag='1'/右1 p=p->next; void AllCode(char s,CodeNode HC,char code)/所有的編碼int i,j;code0='0'for(i=0;si;i+)for(j=0;j<n;j+) if(si=HCj.ch)strcpy(code+strlen(code),HCj.code+HCj.flag);/將所有字符的編碼連

25、接起來(lái)存放到code中 void Decoding(char code,HFMTree HT,char str,char ss)/譯碼int i,j,k=0;HFMTree root,p,q; for(root=HT;root->Parent;root=root->Parent); /從根結(jié)點(diǎn)開(kāi)始按編碼順序進(jìn)行譯碼for(i=0,p=root;codei;i+)if(codei='0')p=p->LChild; elsep=p->RChild;if(p->LChild=NULL&&p->RChild=NULL)for(j=0,

26、q=HT;q!=p;q=q->next,j+); ssk+=strj;/到根結(jié)點(diǎn)時(shí)將該字符存放到ss中p=root;/回到根結(jié)點(diǎn) ssk='0' void Code(char s,char str,char code,int freq,HFMTree *HT,CodeNode HC) /編碼函數(shù) system("cls");Search(s,str,freq);/查找各個(gè)字符，并統(tǒng)計(jì)其出現(xiàn)的頻數(shù)CreateHFMTree(HT,freq);/創(chuàng)建哈夫曼樹(shù)HFMCode(*HT,HC,str);/編碼AllCode(s,HC,code);/將各個(gè)字符的編

27、碼連起來(lái)printf("n哈夫曼編碼為:nn");puts(code);/輸出編碼printf("n保存編碼,"); Save(code);void DeCode(char code,char str,char ss,HFMTree *HT,CodeNode HC) /譯碼函數(shù)FILE *fp;int i=0;system("cls");if(fp=fopen("code.txt","rt")=NULL)/打開(kāi)編碼文件code.txtprintf("打開(kāi)文件失??！n");ex

28、it(1);fclose(fp);Decoding(code,*HT,str,ss);/譯碼 printf("n譯碼后的字符串為:nn"); puts(ss);/輸出譯碼后的字符串printf("n保存譯碼，");Save(ss);/將創(chuàng)建好的哈弗曼樹(shù)的字符，權(quán)值和密碼存入文件hfmtree.txt中void HFM freq,CodeNode HC)int i;FILE *fp;if (fp=fopen("hfmtree.txt","wt")=NULL)printf("打開(kāi)文件出錯(cuò)！n");exit(0);for(i=0;i<n;i+)fprintf(fp,"%ct%dt%sn",HCi.ch,freqi,&(HCi.codeHCi.flag);printf("n哈夫曼樹(shù)創(chuàng)建成功，并已存入文件hfmtree.txt中。nn");fclose(fp);void main() char sM;/存放從文件source.txt中讀取的字符串char ssM;/存放譯碼后的字符串char s