《哈夫曼編碼》課程設(shè)計

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

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

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

文檔簡介

1、　　課程設(shè) 計報告　　題目：《哈夫曼編碼》 　　院系：計算機(jī)科學(xué)與應(yīng)用系　　專業(yè)年級：計算機(jī)科學(xué)與技術(shù) 　　學(xué) 號：

2、學(xué)生姓名：　 　　指導(dǎo)老師：　 　　2013年06月25日　　目錄　　1．設(shè)計任務(wù)書………………………………………………………………3&

3、lt;p>　　1.1題目與要求…………………………………………………………3　　1.2涉及知識點…………………………………………………………3　　1.3輸入輸出分析………………………………………………………3　　1.4測試數(shù)據(jù)分析………………………………………………………3<p

4、>　　2．概要設(shè)計…………………………………………………………………4　　2.1結(jié)構(gòu)體類型定義及函數(shù)聲明………………………………………4　　2.2主程序流程…………………………………………………………5　　3．詳細(xì)設(shè)計…………………………………………………………………7<p&g

5、t;　　3.1數(shù)據(jù)類型實現(xiàn)………………………………………………………7　　3.2程序偽碼……………………………………………………………　　3.3程序主要流程圖……………………………………………………　　4．調(diào)試分析…………………………………………………………………　　4.

6、1問題分析及回顧……………………………………………………　　4.2算法時空分析………………………………………………………　　4.3設(shè)想改進(jìn)……………………………………………………………　　4.4經(jīng)驗和體會…………………………………………………………　　5．用戶使用說明……

7、………………………………………………………　　5.1操作說明及詳細(xì)步驟………………………………………………　　6．測試結(jié)果…………………………………………………………………　　6.1測試數(shù)據(jù)及結(jié)果……………………………………………………　　7．參考文獻(xiàn)…………………………

8、………………………………………　　8．致謝………………………………………………………………………　　設(shè)計任務(wù)書　　1.1題目與要求　　題目：哈夫曼編碼<

9、/p>　　要求：　　1、I：初始化（Initialization），從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。2、E：編碼（Encoding），利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀人），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeF

10、ile中。3、D：譯碼（Decoding），利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。4、P：輸出代碼文件（Print），將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。5、T：輸出哈夫曼樹（TreePrinting），將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹人表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入

11、文件TreePrint中。　　1.2設(shè)計知識點　　哈夫曼樹的建立，哈夫曼編碼的生成，對編碼信息的翻譯，文件、結(jié)構(gòu)體、指針、鏈表、數(shù)組、循環(huán)語句、選擇語句、輸入輸出控制等。　　1.3輸入輸出分析

12、　對于用戶輸入數(shù)據(jù)進(jìn)行存儲，統(tǒng)計各字符出現(xiàn)的頻率，然后通過Huffman編碼得到的各種字符的Huffman編碼。此時程序需要輸入一串Huffman代碼串。輸入完畢程序會判斷輸入的代碼串是否合法，若合法則輸出譯碼結(jié)果。　　1.4測試數(shù)據(jù)分析　　用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯

13、碼：“aabbccdd”。字符 a b c d e f g h ij k l m n o p q r s t u v w x y z權(quán)值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26　　概要設(shè)計　　2.1結(jié)構(gòu)體類型及

14、函數(shù)聲明　　1. 哈夫曼樹類型（樹形結(jié)構(gòu)）：　　void main(void){ int i; void settree(void); //建立樹 void code(void); //對文件編碼 void decode(void); // 譯碼 void disp(void); root=(s

15、truct node*)malloc(sizeof(struct node)); puts("*******************哈夫曼編/譯碼器演示******************************");　　建立編碼　　void settree(void){ int

16、 i,j,k; struct node *p1,*p2,*tmp,*p; void go(struct node *); void setcode(struct node *);//建立每一個字符的編碼 void printtree(struct node *); puts("輸入字符集的大?。?quot;); scanf("%d",&n)

17、; while(getchar()!='\n') continue;　　}　　詳細(xì)設(shè)計　　3.1數(shù)據(jù)類型實現(xiàn)　　1、哈夫

18、曼編碼采用一個字符串?dāng)?shù)組存儲。2、用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。3、在程序的一次執(zhí)行過程中，第一次執(zhí)行I、D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。　　3.Main函數(shù)流程圖<

19、;/p>　　問題分析及回顧　　4.1　　問題一：哈夫曼樹的建立　　問題二：編譯進(jìn)行　　4.4經(jīng)驗與體會</

20、b>　　此次課程設(shè)計，我編寫程序的時候遇到了不少問題，在攻克這些問題，最終實現(xiàn)課題任務(wù)的過程中，我學(xué)到了不少東西：　　首先，在完成一個課題之前，要仔細(xì)理解課題要求。通過這次課程設(shè)計，我更加深入了理解了哈夫曼編碼的過程，以及利用哈夫曼編碼對數(shù)據(jù)進(jìn)行壓縮的優(yōu)越性，并且使我能夠更熟練地運(yùn)用樹形的數(shù)據(jù)結(jié)構(gòu)。并且體會到了在學(xué)習(xí)中，要嚴(yán)格要求自己，不能因為一點

21、點的成功就驕傲自滿，停止不前。　　5．用戶使用說明　　進(jìn)入程序：　　圖 1.程序開始　　程序提示：

22、　　圖2. 輸入字符集的大小　　輸入　　編譯　　參考文獻(xiàn)　　1.《數(shù)據(jù)結(jié)構(gòu)（C語言描述）》；出版社：中國水利水電出版社；主編：馬秋菊；&l

23、t;/p>　　2.嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》（C語言版）清華大學(xué)出版社　　3.wenku.baidu.com ；百度文庫　　源程序：　　#include<stdio.h>　　#include<

24、string.h>　　#include<stdlib.h>　　#include<ctype.h>　　int n;　　struct node{

25、int w;　　int flag;　　char c;　　struct node *plink,*llink,*rlink;　　char code[20];

26、　　}*num[20],*root;　　FILE *fp;　　char tmpcode[20];　　int t=0;　　void main(void)&

27、lt;p>　　{　　int i;　　void settree(void); //建立樹　　void code(void); //對文件編碼　　void decode(void);

28、 // 譯碼　　void disp(void);　　root=(struct node*)malloc(sizeof(struct node));　　puts("*******************哈夫曼編/譯碼器演示******************************");&l

29、t;/p>　　while(1){　　start:　　puts("1. 初始化 2.顯示編碼表 3. 退出");　　while(scanf("%d",

30、&i)!=1)　　{　　while(getchar()!='\n')　　continue;　　puts("輸入錯誤!");<

31、;p>　　puts("請重新輸入！");　　puts("1. 初始化 2.顯示編碼表 3. 退出");　　}　　switch (i)　　{</b&g

32、t;　　case 1:　　settree();　　break;　　case 2: 　　disp()

33、;　　break;　　case 3:　　exit(0);　　break;&l

34、t;p>　　default:　　puts("輸入錯誤！");　　puts("請重新輸入！");　　goto start;　　}

35、　　}　　}　　void settree(void)　　{　　int i,j,k;　　struct

36、 node *p1,*p2,*tmp,*p;　　void go(struct node *);　　void setcode(struct node *);//建立每一個字符的編碼　　void printtree(struct node *);　　puts("輸入

37、字符集的大小：");　　scanf("%d",&n);　　while(getchar()!='\n')　　continue;　　for(i=0;i<n;i++)</p&

38、gt;　　{　　p=(struct node *)malloc(sizeof(struct node));　　puts("請輸入一個字符");　　scanf("%c",&p->c);

39、;　　while(getchar()!='\n')　　continue;　　puts("請輸入該字符的權(quán)值:");　　scanf("%d",&p->w);<

40、;p>　　while(getchar()!='\n')　　continue;　　p->plink=NULL;　　p->rlink=NULL;　　p->llink=NULL;

41、　　num[i]=p;　　}　　for(i=0;i<n-1;i++) //（遞增）排序　　{　　for(j=i+1;j<n;

42、j++)　　{　　if(num[i]->w>num[j]->w)　　{　　tmp=num[i];　　num[i]=num[j];<

43、/p>　　num[j]=tmp;　　}　　}　　}　　/*******************************開始建立樹*

44、**********************/　　num[n]=NULL; //結(jié)束標(biāo)志　　k=n;　　while(num[1]!=NULL)　　{

45、　　p=(struct node *)malloc(sizeof(struct node));　　p1=num[0];　　p2=num[1];　　p->llink=p1;　　p->rlink=p2;　　p->pl

46、ink=NULL;　　p1->plink=p;　　p2->plink=p;　　p->w=p1->w+p2->w;　　for(i=1;i<k;i++)　　{&

47、lt;/p>　　num[i]=num[i+1];　　}　　k--;　　num[0]=p;　　for(i=0;i<k-1;i+

48、+) //排序　　{　　for(j=i+1;j<k;j++)　　{　　if(num[i]->w>num[j]->w)<b&

49、gt;　　{　　tmp=num[i];　　num[i]=num[j];　　num[j]=tmp;　　}　　}&

50、lt;p>　　}　　}　　root=num[0];　　/*建立完畢*/　　/*寫入文件，前序*/　　if((f

51、p=fopen("c:\\hfmtree.wxl","wb"))==NULL)　　{　　puts("文件打開錯誤！");　　getchar();　　exit

52、(0);　　}　　setcode(root);　　go(root);　　fclose(fp);　　}</b&g

53、t;　　void setcode(struct node *p)　　{　　if(p->llink==NULL&&p->rlink==NULL)　　{

54、　　tmpcode[t]='\0';　　strcpy(p->code,tmpcode);　　}　　else　　{&

55、lt;/p>　　tmpcode[t++]='0';　　setcode(p->llink);　　t--;　　tmpcode[t++]='1';　　setcode(p-&g

56、t;rlink);　　t--;　　}　　}　　void go(struct node *p)　　{

57、　　if(p->llink==NULL&&p->rlink==NULL)　　{　　fputc('(',fp);　　fputc(p->c,fp);

58、　　fputs(p->code,fp);　　fputc(')',fp);　　}　　else　　{

59、;　　go(p->llink);　　go(p->rlink);　　}　　}　　void code(void)<b&

60、gt;　　{　　FILE *fp1,*fp2,*fp3;　　char ch1,ch2,c;　　if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)　　{&l

61、t;/b>　　puts("文件打開錯誤！");　　getchar();　　exit(0);　　}　　if((fp2=fopen(

62、"c:\\tobetrans.txt","wb"))==NULL)　　{　　puts("文件打開錯誤！");　　getchar();　　exit(0);&l

63、t;/b>　　}　　if((fp3=fopen("c:\\codefile.wxl","wb"))==NULL)　　{　　puts("文件打

64、開錯誤！");　　getchar();　　exit(0);　　}　　while((ch1=fgetc(fp2))!=EOF)

65、　{　　t=0;　　while((ch2=fgetc(fp1))!=EOF)　　{　　if(ch1==ch2)　　{

66、　　while((c=fgetc(fp1))!=')')　　{　　tmpcode[t++]=c;　　}　　tmpcod

67、e[t]='\0';　　fputs(tmpcode,fp3);　　fputc('@',fp3);　　rewind(fp1);　　break;

68、　}　　}　　}　　fclose(fp1);　　fclose(fp2);　　fclose(fp3);<p

69、>　　}　　void decode(void)　　{　　FILE *fp1,*fp2,*fp3;　　char ch1,ch2,ch3;　　char

70、temp_3[20];　　char temp_1[20];　　int t1,t3;　　if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)　　{</p

71、>　　puts("文件打開錯誤！");　　getchar();　　exit(0);　　}　　if((fp2=fopen("c:\\text

72、file.txt","wb"))==NULL)　　{　　puts("文件打開錯誤！");　　getchar();　　exit(0);</p&

73、gt;　　}　　if((fp3=fopen("c:\\codefile.wxl","rb"))==NULL)　　{　　puts("文件打開錯誤！");<

74、;/p>　　getchar();　　exit(0);　　}　　while((ch3=fgetc(fp3))!=EOF)　　{<

75、;/p>　　t3=0;　　while(ch3!='@')　　{　　temp_3[t3++]=ch3;　　ch3=fgetc(fp3);

76、;　　}　　temp_3[t3]='\0';　　while((ch1=fgetc(fp1))!=EOF)　　{　　if(isalpha(ch1))</p

77、>　　{　　ch2=ch1;　　t1=0;　　while((ch1=fgetc(fp1))!=')')<b&

78、gt;　　{　　temp_1[t1++]=ch1;　　}　　temp_1[t1]='\0';　　if(strcmp(temp_1,temp_3)==0)&l

79、t;b>　　{　　fputc(ch2,fp2);　　rewind(fp1);　　break;　　}　　}<

80、;/b>　　}　　}　　fclose(fp1);　　fclose(fp2);　　fclose(fp3);&

81、lt;b>　　}　　void disp(void)　　{　　FILE *fp1,*fp2;　　char ch1,ch2;　　char tmp[20];</p&g

82、t;　　int t;　　if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)　　{　　puts("文件打開錯誤！");

83、　　getchar();　　exit(0);　　}　　if((fp2=fopen("c:\\hfmcode.txt","wb"))==NULL)</p

84、>　　{　　puts("文件打開錯誤！");　　getchar();　　exit(0);　　}</p&g

85、t;　　while((ch1=fgetc(fp1))!=EOF)　　{　　if(ch1=='(')　　{　　t=0;&l

86、t;/p>　　ch1=fgetc(fp1);　　ch2=ch1;　　while((ch1=fgetc(fp1))!=')')　　{　　tmp[t++]=

87、ch1;　　}　　tmp[t]='\0';　　printf("%c-----%s\n",ch2,tmp);　　fputc(ch2,fp2);　　fputc(

88、'-',fp2);　　fputc('-',fp2);　　fputc('-',fp2);　　fputs(tmp,fp2);　　fputc('\n',fp2);<b

89、>　　}　　}　　fclose(fp1);　　fclose(fp2);　　}　　《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》評分標(biāo)準(zhǔn)

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

溫馨提示

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

《哈夫曼編碼》課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

《哈夫曼編碼》課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費下載