數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)報(bào)告四赫夫曼編碼的應(yīng)用

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

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

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

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

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

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

7、mTree);fclose(htmTree) 這些函數(shù)來實(shí)現(xiàn)編碼寫入文件;6完成譯碼功能并將譯碼寫入文件因?yàn)楹辗蚵鼧浣ê煤笫亲蠛⒆咏Y(jié)點(diǎn)旁標(biāo)上0，右孩子結(jié)點(diǎn)上標(biāo)上1 所以碰到1是用左孩子結(jié)點(diǎn)，2是用右孩子結(jié)點(diǎn)，可以用條件語句來實(shí)現(xiàn)。 if(i2='0') m=HTm.lchild; if(i2='1') m=HTm.rchild; fputs(outext,txtfile);/將譯碼寫入文件五、運(yùn)行于測(cè)試1.程序運(yùn)行后，出現(xiàn)如下主界面：2.執(zhí)行其它操作之前必須進(jìn)行初始化，選擇“1”執(zhí)行，并輸入結(jié)點(diǎn)數(shù)3.依次按提示輸入字符集并輸入相應(yīng)的權(quán)值,輸入后會(huì)自動(dòng)寫入根目錄下

8、htmTree.txt文件中。4輸入要編碼的字符，如下圖：6編碼，對(duì)目錄下tobetran.txt文件進(jìn)行編碼，編碼完成后將寫入目錄下codefile.txt文件中。7.譯碼，即對(duì)目錄下codefile.txt文件中的字符進(jìn)行譯碼，譯碼完成后，內(nèi)容將會(huì)被寫入到目錄下txtfile.txt文件中。 8輸出譯碼，即將CodePrint.txt中的編碼字符。9顯示赫夫曼樹：六、總結(jié)與心得 通過兩個(gè)學(xué)期對(duì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的學(xué)習(xí)，從中認(rèn)識(shí)到怎樣將知識(shí)遷移運(yùn)用，深刻的知道了理論應(yīng)用和實(shí)際相互間的密切聯(lián)系，感受到了理論知識(shí)的重要，在今后的學(xué)習(xí)中一定會(huì)更加努力，認(rèn)真，并且將理論與實(shí)踐相結(jié)合。在做這個(gè)課程設(shè)計(jì)論

9、文的時(shí)候，我遇到過許多的問題，比如說，寫程序以及調(diào)試程序時(shí)，有很多地方的錯(cuò)誤都搞不懂，不過在同學(xué)的幫助下，我成功的調(diào)試出了程序，并運(yùn)行出了結(jié)果，當(dāng)時(shí)我感覺非常有成就感。還有就是論文格式上，之前都沒有學(xué)習(xí)過，不過通過老師講解以及網(wǎng)上百度，最終我還是把它搞懂了，總之，覺得這門課程我收獲了很多課堂外不能學(xué)到的東西。非常讓我受益匪淺！ 通過這門課程的學(xué)習(xí)，我也確實(shí)體會(huì)到了自己的知識(shí)還有很多不足之處和個(gè)人能力的十分有限，只有通過同學(xué)、老師間的密切配合才能完成一項(xiàng)不錯(cuò)的工作。 不過從中我也體會(huì)到了在學(xué)習(xí)中也有無限的樂趣，可以將現(xiàn)實(shí)生活中某一問題用程序編寫出來并將以調(diào)試，得出結(jié)果。 在這里也要感謝老師和同學(xué)

10、們對(duì)我的幫助，有你們的幫助，我才會(huì)學(xué)得更好。附錄：程序代碼#include <iostream.h> #include <iomanip.h> #include <string.h> #include <malloc.h>#include <stdio.h> typedef int TElemType; const int UINT_MAX=999;typedef struct int weight; /權(quán)值 int parent,lchild,rchild; /父節(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn) HTNode,* HuffmanTree

11、; typedef char *HuffmanCode; /-全局變量- HuffmanTree HT; /代表赫夫曼樹 HuffmanCode HC; /代表赫夫曼編碼 int *w,i,j,n; char *z; int flag=0; int numb=0; / -求赫夫曼編碼- void line()cout<<"n=n" int min(HuffmanTree t,int i) int j,flag; int k=UINT_MAX; / 取k為不小于可能的值 for(j=1;j<=i;j+) if(tj.weight<k&&

12、tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag; /返回標(biāo)識(shí)符 /- void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i); s2=min(t,i); if(s1>s2)/ s1為最小的兩個(gè)值中序號(hào)小的那個(gè) j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,s

13、tart; int c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0號(hào)單元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0; for(i=n+1;i<=m;+i) / 建赫夫曼樹 select(HT,i-1,

14、s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(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)

15、cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); /-初始化赫夫曼鏈表- void init() flag=1; int num; int num2; cout<<"赫夫曼鏈表初始化完成 !"<<endl<<"=n"<<"請(qǐng)輸入結(jié)點(diǎn)數(shù)：" cin>>num; n=num; line

16、(); w=(int*)malloc(n*sizeof(int);/weight z=(char*)malloc(n*sizeof(char);/word cout<<"n請(qǐng)依次輸入"<<n<<"個(gè)字符(字符型)n按Enter結(jié)束：<<endl; char temp2; line(); for(i=0;i<n;i+) cout<<"第"<<i+1<<"個(gè)字符:"<<endl; gets(temp); *(z+i)=*temp

17、; line(); for(i=0;i<=n-1;i+) cout<<setw(6)<<*(z+i); line(); cout<<"n請(qǐng)依次輸入"<<n<<"個(gè)權(quán)值n按Enter結(jié)束："<<endl; line(); for(i=0;i<=n-1;i+) cout<<endl<<"第"<<i+1<<"個(gè)字符的權(quán)值:" cin>>num2; *(w+i)=num2; /輸入

18、部分結(jié)束- HuffmanCoding(HT,HC,w,n); line(); cout<<"字符對(duì)應(yīng)的編碼為:"<<endl; for(i=1;i<=n;i+) /cout<<"字符"<<*(z+i-1)<<"的編碼" puts(HCi); /-將赫夫曼編碼寫入文件- line(); /cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"."<<endl; FILE *htm

19、Tree; char r=' ','0' if(htmTree=fopen("htmTree.txt","w")=NULL) cout<<"文件打開失敗"<<endl; return; fputs(z,htmTree); for(i=0;i<n+1;i+) fprintf(htmTree,"%6d",*(w+i); fputs(r,htmTree); for(i=1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmT

20、ree); fclose(htmTree); cout<<"已將字符與對(duì)應(yīng)編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl; /init /-獲取字符并寫入文件- void inputcode() /cout<<"請(qǐng)輸入你想要編碼的字符"<<endl; FILE *virttran,*tobetran; char str100; if(tobetran=fopen("tobetran.txt","w")=NULL) cout<&

21、lt;"不能打開文件"<<endl; return; cout<<"請(qǐng)輸入你想要編碼的字符"<<endl; gets(str); fputs(str,tobetran); cout<<"獲取字符成功"<<endl; fclose(tobetran); void encode() /完成譯碼功能 cout<<"下面對(duì)目錄下文件tobetran.txt中的字符進(jìn)行編碼"<<endl; FILE *tobetran,*codefile;

22、if(tobetran=fopen("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個(gè)字節(jié) while(i=99)

23、if(fgets(tran,100,tobetran)=NULL) cout<<"不能打開文件"<<endl; break; for(i=0;*(tran+i)!='0'i+) for(j=0;j<=n;j+) if(*(z+j-1)=*(tran+i) fputs(HCj,codefile); puts(HCj); if(j>n) cout<<"字符錯(cuò)誤，無法編碼!"<<endl; break; cout<<"編碼工作完成"<<end

24、l<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl; fclose(tobetran); fclose(codefile); free(tran); void decode() /完成譯碼功能 cout<<"下面對(duì)根目錄下文件codefile.txt中的字符進(jìn)行譯碼"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("Textfile.txt","w")=NULL) cout<&l

25、t;"不能打開文件"<<endl; if (codef=fopen("codefile.txt","r")=NULL) cout<<"不能打開文件"<<endl; char *tbdc,*outext,i2; int io=0,i,m; unsigned long length=10000; tbdc=(char*)malloc(length*sizeof(char); /分配空間 fgets(tbdc,length,codef); outext=(char*)malloc(le

26、ngth*sizeof(char); /分配空間 m=2*n-1; for(i=0;*(tbdc+i)!='0'i+) /進(jìn)入循環(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=HTm.lchild; else if(i2='1') m=HTm.rchild; *(outext+io)='0' fputs(outext,txtfile); cout<<"譯碼完成"&l

27、t;<endl<<"內(nèi)容寫入根目錄下的文件txtfile.txt中"<<endl<<endl; free(tbdc); free(outext); fclose(txtfile); fclose(codef); void printcode() /打印代碼 cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl<<"=n" FILE * CodePrin,* codefile; if(CodePrin=fopen("Co

28、dePrin.txt","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<

29、;<"不能讀取文件"<<endl; break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); line(); cout<<"打印工作結(jié)束"<<endl<<endl; fclose(CodePrin); fclose(codefile); /-打印赫夫曼樹的函數(shù)- void coprint(HuffmanTree start,HuffmanTree HT) char t=' ' if(

30、start!=HT) FILE * TreePrint; if(TreePrint=fopen("TreePrint.txt","a")=NULL) cout<<"創(chuàng)建文件失敗"<<endl; return; numb+;/該變量為已被聲明為全局變量 coprint(HT+start->rchild,HT); if(start->lchild!=NULL&&start->rchild!=NULL) t='<' cout<<setw(5*numb

31、)<<start->weight<<t<<endl; fprintf(TreePrint,"%dn",start->weight); coprint(HT+start->lchild,HT); numb-; fclose(TreePrint); void printree(HuffmanTree HT,int w) /打印赫夫曼樹 HuffmanTree p; p=HT+w; cout<<"下面打印赫夫曼樹"<<endl; / 輸出“打印赫夫曼樹”語句 line(); coprint(p,HT); line(); cout<<"打印工作結(jié)束"<<endl; /輸出“打印工作結(jié)束” void printhead() cout<<"ntt" cout<<"*ntt" cout<<