數(shù)據(jù)結構 實驗報告四赫夫曼編碼的應用

1、實驗課程名稱 數(shù)據(jù)結構課程設計 專 業(yè) 班 級 學 生 姓 名 學 號 指 導 教 師 2012 至 2013 學年第 一 學期第 1 至 18 周目錄一、 概 述21.1課程設計的背景21.2 赫夫曼樹21.3 課程設計目的2二、系統(tǒng)分析32.1 課程設計的主要內容32.2功能設計3三、概要設計43.1 設計思想43.2 函數(shù)間的關系4四、詳細設計5五、運行于測試8六、總結與心得11附錄：程序代碼12試驗題目：赫夫曼編碼的應用一、 概 述1.1課程設計的背景當下，如何采用有效的數(shù)據(jù)壓縮技術節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡傳送時間已越來越引起人們的重視，赫夫曼編碼正是一種運用廣泛且非常有效的

2、數(shù)據(jù)壓縮技術。1.2 赫夫曼樹 赫夫曼編碼就是利用赫夫曼樹求得用于通信的二進制編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示為“0碼”，指向右子樹的分支表示為“1”碼，取每條路徑上的“0”和“1”的序列作為和各個葉子對應的字符的編碼，這就是所謂的赫夫曼編碼。1.3 課程設計目的本試驗就是通過先建立赫夫曼樹，然后利用建好的赫夫曼樹生成赫夫曼編碼后進行譯碼。二、系統(tǒng)分析2.1 課程設計的主要內容本實驗要求完成發(fā)送端對等待傳送數(shù)據(jù)的編碼和接收端對傳送來的數(shù)據(jù)的譯碼。要實現(xiàn)五個功能：接受原始數(shù)據(jù)、編碼、譯碼、輸出編碼、譯碼存檔。通過系統(tǒng)的提示要建立赫夫曼樹并對載入的原

3、文件進行編碼，并保存到txtfile.tet文件中，同時輸出到屏幕。最后將建立的赫夫曼樹用某種的存儲方式存儲后輸出。 2.2功能設計（1）初始化（initialization） 從終端讀入字符集大小n，以及n個字符和n個權值，建立赫夫曼樹。并將它存放于文件htmtree.tx中。 （2）編 碼（encoding） 利用已經(jīng)建立好的赫夫曼樹（如不在內存，則從文件hfmtree.txe中讀入，對文件tobetree.txt中的正文進行編碼。然后將結果存在文件codefile.txt中。 （3）譯 碼（decoding） 利用已經(jīng)建立好的赫夫曼樹將文件codefile.txt中的代碼進行譯碼，將結果

4、存入文件textfile.txt中。 （4）輸出譯碼（print） 將文件codefile.txt以緊湊格式顯示在終端上。同時將字符型式寫入到文件codeprint.txt中。 （5）顯示赫夫曼樹（treeprint） 將已經(jīng)在內存中的赫夫曼樹以直觀的方式顯示在屏幕上，同時將此字符型的赫夫曼樹寫入文件treeprint.txt中。三、概要設計 3.1 設計思想 赫夫曼樹用鄰接矩陣來作為存儲結構，借助靜態(tài)鏈表來實現(xiàn)遍歷。3.2 函數(shù)間的關系 四、詳細設計1赫夫曼樹的抽象數(shù)據(jù)類型定義ADT HuffmanCoding數(shù)據(jù)對象 T：具有相同特征的數(shù)據(jù)元素的集合數(shù)據(jù)關系 R：滿足最優(yōu)二叉樹的關系基本操

5、作 P：Init （&t）操作結果：構造一個空赫夫曼樹t。Encode（）操作結果：利用赫夫曼樹進行編碼Decode（）操作結果：利用赫夫曼進行譯碼2主函數(shù)void mian（）打印表頭：while（選擇選項不為0）輸入選項：switch(選擇項)case 1：初始化；break；case 2：輸入編碼字符；break；case 3：編碼字符；break；case 4：譯碼操作；break；case 5：輸出譯碼；break；case 6：顯示赫夫曼樹；break；default ：輸入錯誤，重新選擇；3求赫夫曼編碼if(tj.weightk&tj.parent=0) k=tj.weight,

6、flag=j; /flag為標志符，為不小于可能的值tflag.parent=1;4新建赫夫曼樹HTs1.parent=HTs2.parent=i;/將選好的兩個結點設置成有同一個雙親結點 HTi.lchild=s1;/左孩子的權值 HTi.rchild=s2;/右孩子的權值HTi.weight=HTs1.weight+HTs2.weight;/將兩個權值相加作為新的權值 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/為赫夫曼代碼分配空間5將赫夫曼編碼寫入文件用fputs(HCi,htmTree); fputs(r,htmTree);fclose(htm

7、Tree) 這些函數(shù)來實現(xiàn)編碼寫入文件;6完成譯碼功能并將譯碼寫入文件因為赫夫曼樹建好后是左孩子結點旁標上0，右孩子結點上標上1 所以碰到1是用左孩子結點，2是用右孩子結點，可以用條件語句來實現(xiàn)。 if(i2=0) m=HTm.lchild; if(i2=1) m=HTm.rchild; fputs(outext,txtfile);/將譯碼寫入文件五、運行于測試1.程序運行后，出現(xiàn)如下主界面：2.執(zhí)行其它操作之前必須進行初始化，選擇“1”執(zhí)行，并輸入結點數(shù)3.依次按提示輸入字符集并輸入相應的權值,輸入后會自動寫入根目錄下htmTree.txt文件中。4輸入要編碼的字符，如下圖：6編碼，對目錄下

8、tobetran.txt文件進行編碼，編碼完成后將寫入目錄下codefile.txt文件中。7.譯碼，即對目錄下codefile.txt文件中的字符進行譯碼，譯碼完成后，內容將會被寫入到目錄下txtfile.txt文件中。 8輸出譯碼，即將CodePrint.txt中的編碼字符。9顯示赫夫曼樹：六、總結與心得 通過兩個學期對數(shù)據(jù)結構課程設計的學習，從中認識到怎樣將知識遷移運用，深刻的知道了理論應用和實際相互間的密切聯(lián)系，感受到了理論知識的重要，在今后的學習中一定會更加努力，認真，并且將理論與實踐相結合。在做這個課程設計論文的時候，我遇到過許多的問題，比如說，寫程序以及調試程序時，有很多地方的錯

9、誤都搞不懂，不過在同學的幫助下，我成功的調試出了程序，并運行出了結果，當時我感覺非常有成就感。還有就是論文格式上，之前都沒有學習過，不過通過老師講解以及網(wǎng)上百度，最終我還是把它搞懂了，總之，覺得這門課程我收獲了很多課堂外不能學到的東西。非常讓我受益匪淺！ 通過這門課程的學習，我也確實體會到了自己的知識還有很多不足之處和個人能力的十分有限，只有通過同學、老師間的密切配合才能完成一項不錯的工作。 不過從中我也體會到了在學習中也有無限的樂趣，可以將現(xiàn)實生活中某一問題用程序編寫出來并將以調試，得出結果。 在這里也要感謝老師和同學們對我的幫助，有你們的幫助，我才會學得更好。附錄：程序代碼#include

10、 #include #include #include #include typedef int TElemType; const int UINT_MAX=999;typedef struct int weight; /權值 int parent,lchild,rchild; /父節(jié)點，左孩子結點，右孩子結點 HTNode,* HuffmanTree; typedef char *HuffmanCode; /-全局變量- HuffmanTree HT; /代表赫夫曼樹 HuffmanCode HC; /代表赫夫曼編碼 int *w,i,j,n; char *z; int flag=0; in

11、t numb=0; / -求赫夫曼編碼- void line()coutn=n; int min(HuffmanTree t,int i) int j,flag; int k=UINT_MAX; / 取k為不小于可能的值 for(j=1;j=i;j+) if(tj.weights2)/ s1為最小的兩個值中序號小的那個 j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd;

12、if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0號單元未用 for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建赫夫曼樹 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC

13、=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 從葉子到根逆向求編碼 if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); /-初始化赫夫曼鏈表- vo

14、id init() flag=1; int num; int num2; cout赫夫曼鏈表初始化完成 !endl=nnum; n=num; line(); w=(int*)malloc(n*sizeof(int);/weight z=(char*)malloc(n*sizeof(char);/word coutn請依次輸入n個字符(字符型)n按Enter結束：endl; char temp2; line(); for(i=0;in;i+) cout第i+1個字符:endl; gets(temp); *(z+i)=*temp; line(); for(i=0;i=n-1;i+) coutset

15、w(6)*(z+i); line(); coutn請依次輸入n個權值n按Enter結束：endl; line(); for(i=0;i=n-1;i+) coutendl第i+1num2; *(w+i)=num2; /輸入部分結束- HuffmanCoding(HT,HC,w,n); line(); cout字符對應的編碼為:endl; for(i=1;i=n;i+) /cout字符*(z+i-1)的編碼; puts(HCi); /-將赫夫曼編碼寫入文件- line(); /cout下面將赫夫曼編碼寫入文件endl.endl; FILE *htmTree; char r= ,0; if(htmT

16、ree=fopen(htmTree.txt,w)=NULL) cout文件打開失敗endl; return; fputs(z,htmTree); for(i=0;in+1;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout已將字符與對應編碼寫入根目錄下文件htmTree.txt中endlendl; /init /-獲取字符并寫入文件- void inputcode() /cout請輸入你想要編碼的

17、字符endl; FILE *virttran,*tobetran; char str100; if(tobetran=fopen(tobetran.txt,w)=NULL) cout不能打開文件endl; return; cout請輸入你想要編碼的字符endl; gets(str); fputs(str,tobetran); cout獲取字符成功endl; fclose(tobetran); void encode() /完成譯碼功能 cout下面對目錄下文件tobetran.txt中的字符進行編碼endl; FILE *tobetran,*codefile; if(tobetran=fope

18、n(tobetran.txt,rb)=NULL) cout不能打開文件endl; if(codefile=fopen(codefile.txt,wb)=NULL) cout不能打開文件endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); /為tuan分配100個字節(jié) while(i=99) if(fgets(tran,100,tobetran)=NULL) cout不能打開文件endl; break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) cout字符錯誤，無法編碼!endl; break;

19、 cout編碼工作完成endl編碼寫入目錄下的codefile.txt中endlendl; fclose(tobetran); fclose(codefile); free(tran); void decode() /完成譯碼功能 cout下面對根目錄下文件codefile.txt中的字符進行譯碼endl; FILE *codef,*txtfile; if(txtfile=fopen(Textfile.txt,w)=NULL) cout不能打開文件endl; if (codef=fopen(codefile.txt,r)=NULL) cout不能打開文件endl; char *tbdc,*ou

20、text,i2; int io=0,i,m; unsigned long length=10000; tbdc=(char*)malloc(length*sizeof(char); /分配空間 fgets(tbdc,length,codef); outext=(char*)malloc(length*sizeof(char); /分配空間 m=2*n-1; for(i=0;*(tbdc+i)!=0;i+) /進入循環(huán) i2=*(tbdc+i); if(HTm.lchild=0) *(outext+io)=*(z+m-1); io+; m=2*n-1; i-; else if(i2=0) m=H

21、Tm.lchild; else if(i2=1) m=HTm.rchild; *(outext+io)=0; fputs(outext,txtfile); cout譯碼完成endl內容寫入根目錄下的文件txtfile.txt中endlendl; free(tbdc); free(outext); fclose(txtfile); fclose(codef); void printcode() /打印代碼 cout下面打印根目錄下文件CodePrin.txt中編碼字符endl=n; FILE * CodePrin,* codefile; if(CodePrin=fopen(CodePrin.tx

22、t,w)=NULL) cout不能打開文件endl; return; if(codefile=fopen(codefile.txt,r)=NULL) cout不能打開文件endl; return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout不能讀取文件endl; break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); line(); cout打印工作結

23、束endlendl; fclose(CodePrin); fclose(codefile); /-打印赫夫曼樹的函數(shù)- void coprint(HuffmanTree start,HuffmanTree HT) char t= ; if(start!=HT) FILE * TreePrint; if(TreePrint=fopen(TreePrint.txt,a)=NULL) cout創(chuàng)建文件失敗rchild,HT); if(start-lchild!=NULL&start-rchild!=NULL) t=; coutsetw(5*numb)weighttweight); coprint(HT+start-lchild,HT); numb-; fclose(TreePrint); void