數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告——哈夫曼編譯器

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

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　設(shè)計說明書　　計算機與通信學(xué)院　　2011年 6月 23 日　　一、課題任務(wù)與說明</b&g

2、t;　　1．編輯一個哈夫曼編譯器系統(tǒng)程序　　2．問題描述　　設(shè)某編碼系統(tǒng)共有n個字符，使用頻率分別為{w1,w2,…,wn}，設(shè)計一個不等長編碼方案，使得該編碼系統(tǒng)的空間效率最好。　　3.所具有的功能：</b&

3、gt;　　(1) 為一字符文本編碼功能：將一字符文本復(fù)制到指定的文本中，并保存到指定路徑，讓程序自動為它編碼。　　(2) 為部分字符編碼功能：輸入部分字符與對應(yīng)的字符頻率，讓程序為之編碼（需注意輸入格式）。　　(3) 保存輸出到文本功能：將編碼結(jié)果輸出到文本。　　(4)

4、輸出保存文本信息功能：將功能3保存的文本信息輸出到屏幕上，用于查看結(jié)果是否正確。　　4.設(shè)計要求　?。?）設(shè)計數(shù)據(jù)結(jié)構(gòu)；　　（2）設(shè)計編碼算法；　?。?）分析時間復(fù)雜度和空間復(fù)雜度。　?。?）

5、字符和頻度如下：　　字符空格 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z　　頻度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 48 51 80 23 8 18 1 16

6、5.設(shè)計內(nèi)容與步驟　?。?）選擇合適的數(shù)據(jù)結(jié)構(gòu)　?。?）結(jié)點結(jié)構(gòu)的設(shè)計　?。?）算法設(shè)計與分析　?。?）程序設(shè)計、實現(xiàn)、調(diào)試　?。?）課程設(shè)計說明書　　6.設(shè)計工作計劃

7、與進度安排　?。?）設(shè)計工作4學(xué)時　?。?）實現(xiàn)與調(diào)試16學(xué)時　?。?）課程設(shè)計說明書4學(xué)時　　二、算法設(shè)計　　Huffman編碼是一種可變長編碼方式，是由美國數(shù)學(xué)家David Huffman

8、創(chuàng)立的，是二叉樹的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長度較短的代碼，而使用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計的(字符的統(tǒng)計數(shù)字*字符的編碼長度)為最小，也就是權(quán)值(字符的統(tǒng)計數(shù)字*字符的編碼長度)的和最小。　　三、程序的功能設(shè)計　　為實現(xiàn)系統(tǒng)功能，本程序主要分為五個模塊。

9、它們分別為：　　1.初始化功能模塊　　此功能模塊的功能為從鍵盤接收字符集大小n,以及n各字符和n個權(quán)值。　　2.建立哈弗曼樹的功能模塊　　此模塊功能為使用1中或從一文本中得到的數(shù)據(jù)按照教材的構(gòu)造哈夫曼樹的算法構(gòu)造哈夫曼樹。</p

10、>　　3.建立哈夫曼編碼與譯碼的功能模塊　　此模塊功能為讀入相關(guān)的字符信息進行哈夫曼編碼，并將譯碼結(jié)果輸出，在必要時也可保存到文件中。　　其中各個函數(shù)的功能分別如下：　　notesave函數(shù)用于保存輸出的結(jié)果；　　hfmtree函數(shù)用于建立結(jié)點

11、哈夫曼樹并輸出最終結(jié)果；　　readnote函數(shù)用于讀取目標文本字符信息；　　4.流程圖：　　四、函數(shù)編碼及調(diào)試　　由于本人能力有限難免不會在編碼與調(diào)試過程中遇到這樣或那樣的問題，但通過長時間的改

12、正，查詢資料與詢問，終于能將出現(xiàn)一些致命錯誤得以修正。例如：在輸入編碼結(jié)果信息時由于少了一個很不明顯的Getchar（）的接收Enter的函數(shù)，后面的就全亂了使程序出現(xiàn)了不能達到意料之中的效果。還有先是運行完一個函數(shù)后就跳出了整個運行程序不能再繼續(xù)，后來通過查閱書籍，明白再主函數(shù)中加一個For語句就可以避免這一問題。第三個問題就是由于調(diào)用完一個函數(shù)后顯示的信息還是留在運行界面，但它們的確有沒什么用且占用界面，不美觀，后來通過詢問同學(xué)得知

13、，在每個要調(diào)用的函數(shù)后加一個system("cls")語句就可達到清除上屏信息的功能。　　五、總結(jié)　　該程序主要用于哈夫曼編碼，并在必要時保存數(shù)據(jù)。做法主要是用一個主函數(shù)MAIN，用它達到顯示歡迎界面，提示選擇操作與調(diào)用其它函數(shù)功能（用到Switch函數(shù)），這樣使得程序簡單，易讀，運行效果也好。但

14、由于能力有限，該程序在時間與空間復(fù)雜度上有待作改正。　　參考文獻：　?。?）劉振鵬、張小莉等編著；數(shù)據(jù)結(jié)構(gòu)（第二版）.中國鐵道出版社。　?。?）石強、羅文浩等編著；數(shù)據(jù)結(jié)果習題解答與實驗指導(dǎo)（第二版）.中國鐵道出版社。　?。?）

15、劉克成主編；C語言程序設(shè)計.中國鐵道出版社。　　附全部代碼(正常運行VC++6.0)：　　#include<stdio.h>　　#include<conio.h>　　#include<string.h><

16、p>　　#include<stdlib.h>　　#define MAXLEAF 27　　#define MAXNODE MAXLEAF*2-1　　#define MAXBIT 25　　#define MAXVALUE 2000&l

17、t;p>　　#define H "\t\t =======================================\n"　　typedef struct{　　int parent;　　int weight;　　int lchild

18、;　　int rchild;　　}hfm_n;　　typedef struct{　　int bit[MAXBIT];　　int start;<b

19、>　　}hfm_c;　　void notesave(int n,char a[],hfm_c hfm_code[])　　{　　FILE *fp;　　int i=0,j;&

20、lt;/p>　　char c;　　if((fp=fopen("d:\\notesave.txt","w"))==NULL)　　{　　printf("\n Can

21、not open file!\n");　　getchar();　　exit(1);　　}　　for(i=0;i<n;i++)<b&g

22、t;　　{　　fputc(a[i],fp);　　fputs("-->",fp);　　for(j=hfm_code[i].start+1;j<n;j++)　　{

23、　　c=char(48+hfm_code[i].bit[j]);　　fputc(c,fp);　　}　　fputs(" ",fp);　　if((i+1)%3==0) fputs("\n&

24、quot;,fp);　　}　　fclose(fp);　　printf("\n 保存成功!\n");　　}　　hfm_n *hfmtre

25、e(int n,char a[],int s[])　　{　　hfm_n hfm_node[MAXNODE];　　hfm_c hfm_code[MAXLEAF],cd;　　int i,j,m1,m2,x1,x2,c,p;</p&g

26、t;　　char ch1;　　for(i=0;i<2*n-1;i++)　　{　　hfm_node[i].weight=0;　　hfm_node[i].parent=-1

27、;　　hfm_node[i].lchild=-1;　　hfm_node[i].rchild=-1;　　}　　for(i=0;i<n;i++)　　hfm_node[i].weight=s[

28、i];　　for(i=0;i<n-1;i++)　　{　　m1=m2=MAXVALUE;　　x1=x2=0;　　for(j=0;j<n+i;j+

29、+)　　{　　if(hfm_node[j].parent==-1&&hfm_node[j].weight<m1)　　{　　m2=m1;&

30、lt;/p>　　x2=x1;　　m1=hfm_node[j].weight;　　x1=j;　　}　　else&l

31、t;/b>　　if(hfm_node[j].parent==-1&&hfm_node[j].weight<m2)　　{　　m2=hfm_node[j].weight;　　x2=j;<

32、/b>　　}　　}　　hfm_node[x1].parent=hfm_node[x2].parent=n+i;　　hfm_node[n+i].weight=hfm_node[x1].weig

33、ht+hfm_node[x2].weight;　　hfm_node[n+i].lchild=x1;　　hfm_node[n+i].rchild=x2;　　}　　for(i=0;i<n;i++)<p&

34、gt;　　{　　cd.start=n-1;　　c=i;　　p=hfm_node[c].parent;　　while(p!=-1)　　{&

35、lt;/b>　　if(hfm_node[p].lchild==c)　　cd.bit[cd.start]=0;　　else　　cd.bit[cd.start]=1;　　cd.start--

36、;　　c=p;　　p=hfm_node[c].parent;　　}　　for(j=cd.start+1;j<n;j++)　　hfm_code[i].

37、bit[j]=cd.bit[j];　　hfm_code[i].start=cd.start;　　}　　printf("\n\n 所有編碼:\n ");　　for(i=0;i<n;i++)

38、　　printf("%c",a[i]);　　printf("<===>");　　for(i=0,c=0;i<n;i++)　　for(j=hfm_code[i].start+1;j<n;j++)<p&g

39、t;　　{　　printf("%d",hfm_code[i].bit[j]);　　c++;　　if(c==48||(c-48)%78==0) printf("\n ");&l

40、t;p>　　}　　printf("\n\n 各字符對應(yīng)的編碼:\n");　　for(i=0;i<n;i++)　　{　　printf(" ");&

41、lt;/p>　　printf("%c-->",a[i]);　　for(j=hfm_code[i].start+1;j<n;j++)　　printf("%d",hfm_code[i].bit[j]);　　printf(" &

42、quot;);　　if((i+1)%5==0) printf("\n");　　}　　printf("\n\n 是否將結(jié)果保存到--->路徑D:\\ notesave (y/n)?");

43、ch1=getchar();getchar();　　if(ch1=='y'||ch1=='Y')　　notesave(n,a,hfm_code);　　return NULL;　　}

44、　　int readnote()　　{　　FILE *fp;　　int i,j,b[26],s[26],k;　　char a[26],ch,ch1='n';&l

45、t;/p>　　memset(b,0,sizeof(b));　　if((fp=fopen("d:\\note.txt","r"))==NULL)　　{　　printf("\n Cannot open

46、the file of note!");　　printf("\n Please creat a new text!\n");　　ch1='y';　　}

47、　　if(ch1=='y')　　{　　printf("\n 此功能你要做的只是將要編碼的字符文本復(fù)制到下面文本并將它命名為note并\　　\n 保存到--->D:\\...\　　\n 需注意的是一定要是

48、字符文本且文本保存路徑是D盤下.\n ");　　system("notepad");printf("\n 保存好文本后，請按任意鍵繼續(xù)....");　　getchar();　　if((fp=fopen("d:\\note.txt","

49、r"))==NULL)　　{　　printf("\n Open files fail!");　　getchar();　　exit(1);<

50、;p>　　}　　}　　while((ch=fgetc(fp))!=EOF)　　{　　if(sizeof(ch)!=1) break;

51、　　k=int(ch);　　if(k>=65&&k<=90)　　b[k-65]++;　　if(k>=97&&k<=122) 　　b[k-97]++;&l

52、t;b>　　}　　fclose(fp);　　printf("\n 文本中各字符的頻率為:\n");　　for(i=0,j=0;i<26;i++)　　if(b[i]!=0) &l

53、t;b>　　{　　ch=char(i+65); a[j]=ch;s[j]=b[i];　　printf(" %c--->%d ",a[j],s[j]); j++;　　if(j%6==0) printf("\n");<

54、;p>　　}　　hfmtree(j,a,s);　　return 1;　　}　　void main()<b

55、>　　{　　int i,h,n=0,b[26];　　char a[26],c[30],ch,ch1;　　for(;;)　　{

56、printf("\n\n\n\t\t <<-\1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1 \1->>\n");　　printf("\t\t =======* * * * * * * * * * * * * *=======\n");&

57、lt;p>　　printf("\t\t =====>>*歡迎使用本哈夫曼編碼系統(tǒng)!*<<=====\n");　　printf("\t\t = *__*__*__*__*__*__*__*__* =\n");　　printf("\t\t

58、 = |_ _ _ _ 功能選項!_ _ _ _| =\n");　　printf("\t\t = ------------/ \\----------- =\n");　　printf("\t\t = |

62、　　printf("\t\t = | | =\n");　　printf("\t\t = ------------------------------------- =\n");　　printf(H);</p&

63、gt;　　printf("\n\t\t 請選擇某功能選項(1~4):");　　scanf("%d",&h);getchar();　　switch(h)　　{</

64、p>　　case 1: system("cls");printf("\n 功能1:為一字符文本編碼!\n");readnote();break;　　case 2: system("cls");printf("\n 功能2:輸入部分字符與相應(yīng)頻率為之編碼!\n");&

65、lt;p>　　printf("\n ===>輸入格式應(yīng)為:字符+空格\n ===>例如:a b c.....\　　\n ===>對應(yīng)的字符頻率格式也應(yīng)如此.\n");　　do　　{</p&

66、gt;　　printf("\n 請輸入葉子結(jié)點個數(shù):");　　if(scanf("%d",&n)!=1||sizeof(n)!=4)　　{　　ch='s';</b&g

67、t;　　printf("\n Input worry!\n Please input again.\n");　　}　　else ch='n';　　getchar();<

68、p>　　}while(ch=='s');　　do　　{　　printf("\n =======>請輸入相應(yīng)個字符:");　　for(i=0;i<

69、;n;i++)　　{　　a[i]=getchar();　　ch1=getchar();　　}　　if(ch1!='\n') gets(c)

70、;　　printf("\n 請輸入相應(yīng)字符對應(yīng)的頻率:");　　for(i=0;i<n;i++)　　scanf("%d",&b[i]);　　ch1=getchar();　　if

71、(ch1!='\n') gets(c);　　printf("\n 確認所有數(shù)據(jù)無誤后請按'Enter'(否則按'y')");　　ch=getchar();　　}while(ch=='y'||ch=='Y');<

72、;/p>　　hfmtree(n,a,b);break;　　case 3: printf("\n\n\n");printf(H);printf("\t\t\t\t \1歡迎下次使用\1\n");printf(H);　　printf("\t\t");return;<

73、/p>　　case 4: printf("\nNotesave 中的信息:\n");system("type d:\\notesave.txt");break;　　default: printf("\t\t \a輸入有誤!\t");getchar();break;&

74、lt;b>　　}　　printf("\n ");　　system("pause");　　system("cls");　　}&

眾賞文庫> 全部分類> 畢業(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)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告——哈夫曼編譯器

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告——哈夫曼編譯器

文檔簡介

溫馨提示

最新文檔

評論

免費下載