哈夫曼課程設計報告--哈夫曼編譯碼器

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：15 大?。?53.50KB 人氣指數：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構課程設計報告　　題目：哈夫曼編/譯碼器　　院系名稱：計算機學院　　專業(yè)名稱：軟件工程　　班級： 1101班　　學生姓名：

2、 　　學號（8位）： 　　指導教師： 　　設計起止時間：2012年12月3日~2012年12月14日　　一. 設計目的　　1.鞏固和加深對數據結構的理解，提高綜合運用

3、本課程所學知識的能力；　　2.深化對算法課程中基本概念、理論和方法的理解；　　3.鞏固構造哈夫曼樹的算法；　　4.設計試驗用程序實驗哈夫曼樹的構造，編碼和譯碼。　　二. 設計內容　　利用哈夫曼

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

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

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

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

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

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

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

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

12、>　　將譯碼結果保存到文件decode.txt中　　四．詳細設計　　1．功能函數的調用關系圖　　2.各功能函數的數據流程圖　　（1）創(chuàng)建哈夫曼樹函數<p&g

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

14、gt;　　是　　否　　是　　是否　　3．重點設計及編碼

15、;　?。?）密碼設計：　　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密碼錯誤,您無權使用該系統(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; 　　} 　　}　　測試數據及運行結果　　1．正常測試數據和運行結果　　2.異常測試數據及運行結果

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

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

31、路清晰也是相當重要的。在適當的時候和同學一起交流探討是一個十分好的學習機會。及時的向老師請教也是很有幫助的，因為畢竟我們是新手，對于某些問題很難弄清楚。而且，某些錯誤對于我們來說有時候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時間。　　這次課程設計不但讓我又學得了一些編程知識，還學會了系統(tǒng)的做一份課程設計報告，學會了如何更好的畫流程圖，明白了做事情只有認真，才能真正做得更好！

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

33、等教育出版社，2005年　　2. 陳銳，《數據結構（C語言版）》，清華大學出版社 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;//權值　　struct node *Parent,*LChild,*RChild;//雙親結點，左孩子結點，右孩子結點　　struct nod

36、e *next;//下一個結點　　}HFMNode,*HFMTree;　　typedef struct 　　{　　char ch;//字符　　char code[N+1];//編碼&

37、lt;/p>　　int flag;//標記　　}CodeNode;　　int n;//葉子結點個數　　//密碼　　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密碼錯誤,您無權使用該系統(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***** 歡迎進入 *****\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***** 請輸入相應操作的序號(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);　　}　　//存儲文件　　void Save(char s[])　　{</

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

57、t"))==NULL)　　{ 　　printf("存儲文件失??！\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[])//查找各個字符，并統(tǒng)計其出現的頻數　　{　　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)計各個字符出現的頻數，即權值，并將其存放在freq[]　　if(str[j]==

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

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

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

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

65、的結點　　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)//查找權值次小的結點　　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++)//申請空間，并初始化所有結點

70、，共2n-1個　　{　　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個結點賦權值　　{　　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、權值最小的兩個結點　　HT1->Parent=HT2->Parent=p;　　p->LChild=HT1;　　p->RChild=HT2;　　p->weight=HT1->weight+HT2->weight;//更改雙親結

74、點的權值　　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';//處理編碼的結束符　　}　　for(i=0;i<n;i++)//開始解碼　　{&

77、lt;/p>　　HC[i].flag=n-1;//根結點　　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); //從根結點開始按編碼順序進行譯碼　　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];//到根結點時將該字符存放到ss[]中　　p=root;//回到根結點　　}　　} 　　ss[k]='\0'; <p

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

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

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

89、;b>　　}　　void DeCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[]) //譯碼函數　　{　　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)建好的哈弗曼樹的字符，權值和密碼存入文件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("打開文件出錯！\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)計后的所有字符　　int i,freq[N];//存放統(tǒng)計后的各個字符出現的頻數，即權值　　char code[M];//存放從文件code.txt中讀取的編碼　　int choice;　　HFMTree HT;

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

100、t;　　printf("\n"); 　　Menu();//調用菜單函數　　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文件中各個字符及其權值的情況如下所示：\n");　　printf("\n字符\t權值\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)建好的哈弗曼樹的字符，權值和密碼存入文件　　system("pause");

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

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

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

溫馨提示

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

哈夫曼課程設計報告--哈夫曼編譯碼器

文檔簡介

溫馨提示

最新文檔

評論

哈夫曼課程設計報告--哈夫曼編譯碼器

文檔簡介

溫馨提示

最新文檔

評論

免費下載