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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：15 大?。?53.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告　　題目：哈夫曼編/譯碼器　　院系名稱：計(jì)算機(jī)學(xué)院　　專業(yè)名稱：軟件工程　　班級(jí)： 1101班　　學(xué)生姓名：

2、 　　學(xué)號(hào)（8位）： 　　指導(dǎo)教師： 　　設(shè)計(jì)起止時(shí)間：2012年12月3日~2012年12月14日　　一. 設(shè)計(jì)目的　　1.鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用

3、本課程所學(xué)知識(shí)的能力；　　2.深化對算法課程中基本概念、理論和方法的理解；　　3.鞏固構(gòu)造哈夫曼樹的算法；　　4.設(shè)計(jì)試驗(yàn)用程序?qū)嶒?yàn)哈夫曼樹的構(gòu)造，編碼和譯碼。　　二. 設(shè)計(jì)內(nèi)容　　利用哈夫曼

4、編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編/譯碼器。　　三．概要設(shè)計(jì)　　1．功能模塊圖；<

5、p>　　2．各個(gè)模塊詳細(xì)的功能描述。　?。?）主程序模塊　　打印菜單；　　讓用戶選擇是編碼還是譯碼；　　讓用戶決定是否觀看一些信息。

6、;　　密碼模塊　　void Login()　　密碼函數(shù)，用戶輸入用戶名和密碼，密碼正確方能進(jìn)入系統(tǒng)，否則重新輸入。　　（3）編碼模塊　　void OpenSourceFile(char s[])

7、;　　打開源文件，并將其內(nèi)容存到s[]中　　void Code(char s[],char str[],char code[],int freq[],HFMTree *HT,CodeNode HC[])　　編碼函數(shù)，調(diào)用編碼所需的所有函數(shù)　　void Search(char s[],char

8、 str[],int freq[])　　查找各個(gè)字符，將其存到str[]中，并統(tǒng)計(jì)其出現(xiàn)的頻數(shù)，即權(quán)值，存放在freq[]中　　void CreateHFMTree(HFMTree *HT,int freq[])　　創(chuàng)建哈夫曼樹　　v

9、oid HFMCode(HFMTree HT,CodeNode HC[],char str[])　　按左0右1的順序進(jìn)行編碼　　AllCode(s,HC,code)　　將所有字符的編碼連起來，存放到code[]中　　Save(code)<p&

10、gt;　　將編碼結(jié)果保存到文件code.txt中　　（4）譯碼模塊　　void DeCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[]) 　　譯碼函數(shù)，調(diào)用譯碼所需的所有函數(shù)&

11、lt;p>　　void OpenCodeFile(char code[])　　打開編碼文件　　Decoding(code,*HT,str,ss)　　從根結(jié)點(diǎn)開始按編碼順序進(jìn)行譯碼　　Save(ss)</b

12、>　　將譯碼結(jié)果保存到文件decode.txt中　　四．詳細(xì)設(shè)計(jì)　　1．功能函數(shù)的調(diào)用關(guān)系圖　　2.各功能函數(shù)的數(shù)據(jù)流程圖　?。?）創(chuàng)建哈夫曼樹函數(shù)<p&g

13、t;　　是　　否　　否　　是　?。?）編碼函數(shù)<p&

14、gt;　　是　　否　　是　　是否　　3．重點(diǎn)設(shè)計(jì)及編碼

15、;　　（1）密碼設(shè)計(jì)：　　void Login()　　{　　char username[15];　　char password[9];

16、;　　char c;　　int i = 0;　　printf("\n\n請輸入用戶名:");　　gets(username);　　printf("\n請輸入密碼:");&

17、lt;p>　　while ((c=getch())!='\r')　　{　　if (i<8 && isprint(c))　　{　　password[i++

18、] = c;　　putchar('*');　　}　　}　　putchar('\n');　　password[i] = &#

19、39;\0';　　if(!(strcmp(password,"04113027")))　　{　　printf("\n\n恭喜您，登陸成功!\n\n歡迎使用該系統(tǒng)!\n\n");　　sys

20、tem("pause");　　}　　else　　{　　printf("\n\n密碼錯(cuò)誤,您無權(quán)使用該系統(tǒng)!\n\n請重新輸入!

21、\n\n");　　system("pause");　　system("cls");　　Login();　　}<p&

22、gt;　　}　　創(chuàng)建哈夫曼樹：　　void CreateHFMTree(HFMTree *HT,int freq[])　　{　　int i

23、;　　HFMTree p,HT1,HT2;　　p=*HT=(HFMTree)malloc(sizeof(HFMNode)); 　　p->next=p->LChild=p->RChild=p->Parent=NULL;　　for

24、(i=1;i<2*n-1;i++)　　{　　p->next=(HFMTree)malloc(sizeof(HFMNode));　　p=p->next;　　p->next=p->LChild=p->

25、RChild=p->Parent=NULL;　　}　　for(i=0,p=*HT;i<n;i++)　　{　　p->weight=freq[i];<

26、p>　　p=p->next;　　}　　for(i=n;i<2*n-1;i++)　　{　　Select(*HT,i,&HT1,&HT2);

27、　　HT1->Parent=HT2->Parent=p;　　p->LChild=HT1;　　p->RChild=HT2;　　p->weight=HT1->weight+HT2->weight;　　p=p-

28、>next; 　　} 　　}　　測試數(shù)據(jù)及運(yùn)行結(jié)果　　1．正常測試數(shù)據(jù)和運(yùn)行結(jié)果　　2.異常測試數(shù)據(jù)及運(yùn)行結(jié)果

29、　　六．調(diào)試情況，設(shè)計(jì)技巧及體會(huì)　　改進(jìn)方案　　通過一周的課程設(shè)計(jì)使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。　　由于時(shí)間問題，對于哈夫曼的壓縮和解壓縮暫時(shí)不能實(shí)現(xiàn)了。這也

30、是我比較遺憾的一件事了。不過在空閑時(shí)間我還會(huì)繼續(xù)研究這個(gè)問題的。　　2．體會(huì)　　開始的時(shí)候，代碼中有許多的錯(cuò)誤，讓我束手無策，最后我耐心的一步一步慢慢地改正錯(cuò)誤才讓我看到了希望。在實(shí)現(xiàn)文章的讀入時(shí)，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式編寫。許多的錯(cuò)誤讓我明白了細(xì)心是非常重要的。同時(shí)，對于編程者而言，思

31、路清晰也是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。及時(shí)的向老師請教也是很有幫助的，因?yàn)楫吘刮覀兪切率?，對于某些問題很難弄清楚。而且，某些錯(cuò)誤對于我們來說有時(shí)候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。　　這次課程設(shè)計(jì)不但讓我又學(xué)得了一些編程知識(shí)，還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，學(xué)會(huì)了如何更好的畫流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！

32、　　通過這次課程設(shè)計(jì)，我看清楚了自己的編程功底和動(dòng)手能力還不如人意，這主要是平時(shí)實(shí)踐太少的緣故。我想，在即將到來的寒假中，我會(huì)努力嘗試編寫一些較大的程序。由于我們是軟件工程專業(yè)的學(xué)生，就應(yīng)該更加嚴(yán)格要求自己。　　七．參考文獻(xiàn)　　1. 耿國華主編，《數(shù)據(jù)結(jié)構(gòu)——C語言描述》，高

33、等教育出版社，2005年　　2. 陳銳，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版社 2012年　　附錄　　#include <stdio.h> 　　#include <stdlib.h>&

34、lt;p>　　#include <string.h> 　　#include <conio.h>　　#include <ctype.h>　　#define M 500 　　#define N 128<p

35、>　　typedef struct node 　　{　　int weight;//權(quán)值　　struct node *Parent,*LChild,*RChild;//雙親結(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)　　struct nod

36、e *next;//下一個(gè)結(jié)點(diǎn)　　}HFMNode,*HFMTree;　　typedef struct 　　{　　char ch;//字符　　char code[N+1];//編碼&

37、lt;/p>　　int flag;//標(biāo)記　　}CodeNode;　　int n;//葉子結(jié)點(diǎn)個(gè)數(shù)　　//密碼　　void Login()

38、　　{　　char username[15];　　char password[9];　　char c;　　int i = 0;　　printf("\n\n請輸入用

39、戶名:");　　gets(username);　　printf("\n請輸入密碼:");　　while ((c=getch())!='\r')　　{

40、;　　if (i<8 && isprint(c))　　{　　password[i++] = c;　　putchar('*');　　}&

41、lt;p>　　}　　putchar('\n');　　password[i] = '\0';　　if(!(strcmp(password,"04113027")))<b&g

42、t;　　{　　printf("\n\n恭喜您，登陸成功!\n\n歡迎使用該系統(tǒng)!\n\n");　　system("pause");　　}　　else<

43、/b>　　{　　printf("\n\n密碼錯(cuò)誤,您無權(quán)使用該系統(tǒng)!\n\n請重新輸入!\n\n");　　system("pause");　　system("cls"

44、);　　Login();　　}　　}　　void Menu(void)//菜單　　{</

45、b>　　printf("\t\t****************************************\n");　　printf("\t\t***** *****\n");　　printf("

46、;\t\t***** 歡迎進(jìn)入 *****\n");　　printf("\t\t***** 哈夫曼編/譯碼系統(tǒng) *****\n");　　printf("\t\t***** *****\n"

47、;);　　printf("\t\t***** 1.顯示源文件。 *****\n");　　printf("\t\t***** 2.編碼。 *****\n");　　printf("\t\t*****

48、 3.譯碼。 *****\n");　　printf("\t\t***** 4.顯示哈夫曼信息。 *****\n");　　printf("\t\t***** 0.退出。 *****\n");

49、　　printf("\t\t***** *****\n");　　printf("\t\t****************************************\n");　　printf("\t\t*****

50、 *****\n");　　printf("\t\t***** 請輸入相應(yīng)操作的序號(hào)(0-3) *****\n");　　printf("\t\t***** *****\n");

51、　　printf("\t\t****************************************\n");　　}　　//打開源文件　　void OpenSourceFile(char

52、s[])　　{　　FILE *fp;　　int i=0;　　system("cls");　　i

53、f((fp=fopen("source.txt","rt"))==NULL)//打開文件source.txt　　{　　printf("打開文件失??！\n");　　exit(1);

54、;　　}　　s[i++]=fgetc(fp);　　while(s[i-1]!=EOF)//將文件中的字符串存入s[]中　　s[i++]=fgetc(fp);　　s[i]='\0

55、9;; 　　fclose(fp);　　}　　//存儲(chǔ)文件　　void Save(char s[])　　{</

56、p>　　char name[10];　　FILE *fp;　　printf("請輸入要保存的文件名：");　　gets(name);　　if((fp=fopen(name,"w

57、t"))==NULL)　　{ 　　printf("存儲(chǔ)文件失?。n");　　exit(1);　　}&l

58、t;p>　　fputs(s,fp);　　printf("\n文件保存成功，文件名為:%s。\n\n",name);　　system("pause");　　fclose(fp);　　}<

59、;/p>　　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[]</

60、p>　　freq[i]=0; 　　for(i=0;s[i];i++)　　{　　for(j=0;j<k;j++)//統(tǒng)計(jì)各個(gè)字符出現(xiàn)的頻數(shù)，即權(quán)值，并將其存放在freq[]　　if(str[j]==

61、s[i]) 　　{ 　　freq[j]++; 　　break; 　　}　　if(j==k)//查找各個(gè)字符，并將其

62、存放在str[]中　　{　　str[k]=s[i];　　freq[k++]++; 　　}　　}

63、　　str[k]='\0';　　n=k-1;//n為查找后字符的總個(gè)數(shù)　　}　　void Select(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)//查找權(quán)值最小的兩個(gè)結(jié)點(diǎn)

64、　　{　　inti,min;　　HFMTreep;　　min=1000;　　for(i=0,p=HT;i<k;i++,p=p->next)//查找權(quán)值最小

65、的結(jié)點(diǎn)　　if(p->weight<min&&p->Parent==0)　　{　　min=p->weight;　　*HT1=p;&l

66、t;p>　　}　　min=1000;　　for(i=0,p=HT;i<k;i++,p=p->next)//查找權(quán)值次小的結(jié)點(diǎn)　　if(p->weight<min&&p->Parent

67、==0&&p!=*HT1)　　{　　min=p->weight;　　*HT2=p;　　}<

68、;b>　　}　　void CreateHFMTree(HFMTree *HT,int freq[])//創(chuàng)建哈夫曼樹　　{　　int i;　　HFMTree p,HT1

69、,HT2;　　p=*HT=(HFMTree)malloc(sizeof(HFMNode)); //申請空間　　p->next=p->LChild=p->RChild=p->Parent=NULL;//初始化　　for(i=1;i<2*n-1;i++)//申請空間，并初始化所有結(jié)點(diǎn)

70、，共2n-1個(gè)　　{　　p->next=(HFMTree)malloc(sizeof(HFMNode));　　p=p->next;　　p->next=p->LChild=p->RChild=p->P

71、arent=NULL;　　}　　for(i=0,p=*HT;i<n;i++)//給前n個(gè)結(jié)點(diǎn)賦權(quán)值　　{　　p->weight=freq[i];<p&g

72、t;　　p=p->next;　　}　　for(i=n;i<2*n-1;i++)//開始創(chuàng)建哈夫曼樹　　{　　Select(*HT,i,&HT1,&HT2);//查找

73、權(quán)值最小的兩個(gè)結(jié)點(diǎn)　　HT1->Parent=HT2->Parent=p;　　p->LChild=HT1;　　p->RChild=HT2;　　p->weight=HT1->weight+HT2->weight;//更改雙親結(jié)

74、點(diǎn)的權(quán)值　　p=p->next; 　　} 　　}　　void HFMCode(HFMTree HT,CodeNode HC[],char str[])//編碼&l

75、t;p>　　{　　int i; 　　HFMTree q,p=HT; 　　for(i=0;i<n;i++)　　{<p&

76、gt;　　HC[i].ch=str[i];　　HC[i].code[n-1]='\0';//處理編碼的結(jié)束符　　}　　for(i=0;i<n;i++)//開始解碼　　{&

77、lt;/p>　　HC[i].flag=n-1;//根結(jié)點(diǎn)　　for(q=p;q->Parent;q=q->Parent)　　if(q==q->Parent->LChild)　　HC[i].code[--HC[i].flag]='0';//左0

78、　　else 　　HC[i].code[--HC[i].flag]='1';//右1 　　p=p->next; 　　}<b&

79、gt;　　}　　void AllCode(char s[],CodeNode HC[],char code[])//所有的編碼　　{　　int i,j;　　code[0]=&

80、#39;\0';　　for(i=0;s[i];i++)　　for(j=0;j<n;j++) 　　if(s[i]==HC[j].ch)　　strcpy(code+strlen(code),HC[j].code+HC[j].flag);&

81、lt;p>　　//將所有字符的編碼連接起來存放到code[]中　　} 　　void Decoding(char code[],HFMTree HT,char str[],char ss[])//譯碼　　{&

82、lt;p>　　int i,j,k=0;　　HFMTree root,p,q; 　　for(root=HT;root->Parent;root=root->Parent); //從根結(jié)點(diǎn)開始按編碼順序進(jìn)行譯碼　　for(i=0,p=root;code[i];i++)<

83、p>　　{　　if(code[i]=='0')　　p=p->LChild; 　　else　　p=p->RChild;

84、if(p->LChild==NULL&&p->RChild==NULL)　　{　　for(j=0,q=HT;q!=p;q=q->next,j++)　　; 　　s

85、s[k++]=str[j];//到根結(jié)點(diǎn)時(shí)將該字符存放到ss[]中　　p=root;//回到根結(jié)點(diǎn)　　}　　} 　　ss[k]='\0'; <p

86、>　　}　　void Code(char s[],char str[],char code[],int freq[],HFMTree *HT,CodeNode HC[]) //編碼函數(shù)　　{ 　　system("cls&

87、quot;);　　Search(s,str,freq);//查找各個(gè)字符，并統(tǒng)計(jì)其出現(xiàn)的頻數(shù)　　CreateHFMTree(HT,freq);//創(chuàng)建哈夫曼樹　　HFMCode(*HT,HC,str);//編碼　　AllCode(s,HC,code);//將

88、各個(gè)字符的編碼連起來　　printf("\n哈夫曼編碼為:\n\n");　　puts(code);//輸出編碼　　printf("\n保存編碼,"); 　　Save(code);<

89、;b>　　}　　void DeCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[]) //譯碼函數(shù)　　{　　FILE *fp;</p

90、>　　int i=0;　　system("cls");　　if((fp=fopen("code.txt","rt"))==NULL)//打開編碼文件code.txt

91、　{　　printf("打開文件失?。n");　　exit(1);　　}　　fclose(fp);　　Decod

92、ing(code,*HT,str,ss);//譯碼 　　printf("\n譯碼后的字符串為:\n\n"); 　　puts(ss);//輸出譯碼后的字符串　　printf("\n保存譯碼，");　　Save(s

93、s);　　}　　//將創(chuàng)建好的哈弗曼樹的字符，權(quán)值和密碼存入文件hfmtree.txt中　　void HFMFile(int freq[],CodeNode HC[])　　{&

94、lt;/p>　　int i;　　FILE *fp;　　if ((fp=fopen("hfmtree.txt","wt"))==NULL)　　{</

95、b>　　printf("打開文件出錯(cuò)！\n");　　exit(0);　　}　　for(i=0;i<n;i++)　　fpri

96、ntf(fp,"%c\t%d\t%s\n",HC[i].ch,freq[i],&(HC[i].code[HC[i].flag]));　　printf("\n哈夫曼樹創(chuàng)建成功，并已存入文件hfmtree.txt中。\n\n");　　fclose(fp);<b&g

97、t;　　}　　void main() 　　{　　char s[M];//存放從文件source.txt中讀取的字符串　　char ss[M];//存放譯碼后的字符串

98、char str[N];//存放統(tǒng)計(jì)后的所有字符　　int i,freq[N];//存放統(tǒng)計(jì)后的各個(gè)字符出現(xiàn)的頻數(shù)，即權(quán)值　　char code[M];//存放從文件code.txt中讀取的編碼　　int choice;　　HFMTree HT;

99、　　CodeNode HC[N];　　Login();　　do　　{　　system("cls");</p&g

100、t;　　printf("\n"); 　　Menu();//調(diào)用菜單函數(shù)　　printf("\n");　　scanf("%d",&choice);//選擇要執(zhí)行的操作　　getc

101、har();　　switch(choice)　　{　　case 1:OpenSourceFile(s);//打開源文件　　printf("\n源文件source.txt中的字符串為:\n\n"); </p&

102、gt;　　puts(s);//輸出要編譯的字符串　　printf("\n");　　system("pause");　　break;　　case 2:Code(s,str,

103、code,freq,&HT,HC);//編碼　　break;　　case 3:DeCode(code,str,ss,&HT,HC);//譯碼　　break;　　case 4:

104、system("cls");　　printf("\n文件中各個(gè)字符及其權(quán)值的情況如下所示：\n");　　printf("\n字符\t權(quán)值\t編碼\n");　　for(i=0;i<n;i++)　　printf

105、("%c\t%d\t%s\n",HC[i].ch,freq[i],&(HC[i].code[HC[i].flag]));　　HFMFile(freq,HC);//將創(chuàng)建好的哈弗曼樹的字符，權(quán)值和密碼存入文件　　system("pause");

106、break;　　case 0:system("cls");　　printf("\n感謝您的使用，再見！\n\n");//退出　　break; 　　default :syst

107、em("cls");　　printf("\n抱歉，您輸入錯(cuò)誤!\n請重新開始輸入哦！\n\n"); 　　system("pause");　　}　　}while(choice

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載