梁贊文數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報(bào)告

1、實(shí)訓(xùn)報(bào)告題 目： 哈夫曼編碼與譯碼院 系： 信息科技學(xué)院專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)姓 名： 梁贊文學(xué) 號(hào)： 1151210118指導(dǎo)教師： 趙瑩瑩 日 期： 2013年6月25日 桂林電子科技大學(xué)信息科技學(xué)院目 錄1 問題定義 12 系統(tǒng)設(shè)計(jì) 121 總體設(shè)計(jì)122 詳細(xì)設(shè)計(jì)22.2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 22.2.2 主控流程 22.2.3 函數(shù)功能描述 33 系統(tǒng)實(shí)現(xiàn) 43.1 源程序代碼 43.2 程序測試 144 歸納總結(jié) 16 4.1 開發(fā)經(jīng)驗(yàn) 16 4.2 實(shí)訓(xùn)中遇到的問題及解決方法 16 4.3 設(shè)計(jì)中的不足之處16 4.4 感想和心得體會(huì) 165 參考資料 16數(shù)據(jù)結(jié)構(gòu)C+實(shí)現(xiàn) 哈

2、夫曼編碼與譯碼哈夫曼編碼和譯碼本題目設(shè)計(jì)目的是訓(xùn)練學(xué)生的基本編程能力和對一些算法的了解，了解哈夫曼編碼和譯碼的算法流程。本程序中涉及結(jié)構(gòu)體、樹、指針、循環(huán)、哈夫曼樹、樹的遍歷、數(shù)組等方面的知識(shí)。通過這一次實(shí)訓(xùn)讓我們更加了解面向?qū)ο蟮木幊?，為進(jìn)一步開發(fā)出高質(zhì)量的系統(tǒng)軟件打下堅(jiān)實(shí)的基礎(chǔ)，讓我們了解算法的一些特性，其實(shí)我們學(xué)的很多東西都是要便于人們的生活，源于生活的。1、問題定義創(chuàng)建一個(gè)哈夫曼編碼和譯碼程序。程序中的功能主要有1.密碼，2編碼，3.譯碼, 4.結(jié)束程序。程序的運(yùn)行效果如下圖所示，選擇任意菜單后，實(shí)現(xiàn)相應(yīng)功能。圖1.1 哈夫曼編碼和譯碼程序基本功能在問題定義階段要考慮題目的可行性和需求

3、分析，簡單的說你這個(gè)程序需要的是什么功能，接下來進(jìn)入開發(fā)階段，完成程序的設(shè)計(jì)和系統(tǒng)實(shí)現(xiàn)的任務(wù)。2、程序設(shè)計(jì)21 總體設(shè)計(jì) 我們在實(shí)現(xiàn)一個(gè)相應(yīng)程序時(shí)，往往是將一個(gè)整體的實(shí)現(xiàn)分成若干的功能模塊再進(jìn)行相互調(diào)用和實(shí)現(xiàn)程序總體的功能，要學(xué)會(huì)將一個(gè)大問題分成若干個(gè)小問題去解決該哈夫曼編碼和譯碼程序由類和數(shù)組來實(shí)現(xiàn)，它由如下三大功能模塊組成：l 輸入模塊：將要編碼的字符輸入，存在相應(yīng)的字符數(shù)組里面。l 編碼模塊：將輸入的字符進(jìn)行編碼，將字符和他相應(yīng)的權(quán)值和代碼存放到相應(yīng)的數(shù)組和類當(dāng)中。l 顯示編碼模塊：進(jìn)行編碼過程后，就會(huì)輸出相應(yīng)的信息，如：字符的權(quán)值和相應(yīng)的字符代碼。l 查找模塊：輸入要譯碼的二進(jìn)制代碼進(jìn)

4、行譯碼，將輸入的二進(jìn)制和之前存入的二進(jìn)制編碼進(jìn)行比較和輸出相應(yīng)的字符。l 顯示譯碼模塊：將進(jìn)行譯碼比較后得到的字符進(jìn)行輸出。22 詳細(xì)設(shè)計(jì)2.2.2 主控main( )函數(shù)執(zhí)行流程開始輸入kK=?輸入密碼生成一個(gè)密碼樹K=1進(jìn)行譯碼，輸入相應(yīng)的代碼K=2結(jié)束K=4譯碼K=3輸出相應(yīng)的字符查找字符 main()函數(shù)的流程圖2.2.3 函數(shù)功能描述l void CreateWeight(char ch,int *s,WeightNode CW,int *p) /*產(chǎn)生葉子結(jié)點(diǎn)的字符和權(quán)值的功能函數(shù)*/ l void CreateHuffmanTree(Huffman ht,WeightNode w

5、,int n) /*創(chuàng)建HuffmanTree的功能函數(shù)*/ l void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n) /*葉子結(jié)點(diǎn)的編碼的功能函數(shù)*/l void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m) /*所有字符的編碼的功能函數(shù)*/ l void TrsHuffmanTree(HuffmanCode h,WeightNode w,char ch

6、,int n) /*解碼的功能函數(shù)*/ l int main( ) /*主函數(shù)*/ 完成在上述系統(tǒng)設(shè)計(jì)后，即可著手進(jìn)行系統(tǒng)實(shí)現(xiàn)的工作，開始程序代碼的編寫。3、程序的實(shí)現(xiàn)3.1 源程序代碼#include <iostream>#include <conio.h>#include <iomanip>#include <string.h>#include <malloc.h>#include <stdlib.h>using namespace std; #define N 1000#define M 2*N-1char chN;

7、typedef char * HuffmanCode2*M; /*haffman編碼*/typedef classpublic:int weight; /*權(quán)值*/int parent; /*父結(jié)點(diǎn)*/int LChild; /*左子結(jié)點(diǎn)*/int RChild; /*右子結(jié)點(diǎn)*/HTNode,HuffmanM+1; /*huffman樹*/typedef class Nodepublic:int weight; /*葉子結(jié)點(diǎn)的權(quán)值*/char c; /*葉子結(jié)點(diǎn)編碼*/int num; /*葉子結(jié)點(diǎn)的二進(jìn)制碼的長度*/WNode,WeightNodeN; /*產(chǎn)生葉子結(jié)點(diǎn)的字符和權(quán)值*/ v

8、oid CreateWeight(char ch,int *s,WeightNode CW,int *p) /*s 指向字符串長度 *p指向節(jié)點(diǎn)個(gè)數(shù) */int i,j,k;int tag; /*起標(biāo)記的作用*/ *p=0; /*葉子結(jié)點(diǎn)個(gè)數(shù)*/*統(tǒng)計(jì)字符出現(xiàn)個(gè)數(shù),放入CW*/for(i=0;chi!='0'i+) tag=1;for(j=0;j<i;j+)/*進(jìn)行比較*/if(chj=chi)tag=0;break;if(tag)CW+*p.c=chi; /*保留葉子結(jié)點(diǎn)的字符*/CW*p.weight=1; /*初始給該字符的權(quán)值*/for(k=i+1;chk!=&#

9、39;0'k+) /*和往后的字符進(jìn)行比較*/if(chi=chk)CW*p.weight+; /*權(quán)值累加*/*s=i; /*字符串長度*/ /*創(chuàng)建HuffmanTree*/ void CreateHuffmanTree(Huffman ht,WeightNode w,int n) int i,j;int s1,s2; /*s1,s2分別為左右子結(jié)點(diǎn)*/*初始化哈夫曼樹*/for(i=1;i<=n;i+) /*葉子結(jié)點(diǎn)初始化*/ hti.weight =wi.weight; hti.parent=0; hti.LChild=0; hti.RChild=0;for(i=n+1;

10、i<=2*n-1;i+) /*非葉子結(jié)點(diǎn)初始化*/ hti.weight=0; hti.parent=0; hti.LChild=0; hti.RChild=0;for(i=n+1;i<=2*n-1;i+) /*從非葉子結(jié)點(diǎn)找*/for(j=1;j<=i-1;j+)if(!htj.parent)break;s1=j; /*找到雙親為零的結(jié)點(diǎn)*/for(;j<=i-1;j+)if(!htj.parent)s1=hts1.weight>htj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j<=i-1;j+)if

11、(!htj.parent)break;s2=j; /*找到雙親為零的結(jié)點(diǎn)*/for(;j<=i-1;j+)if(!htj.parent)s2=hts2.weight>htj.weight?j:s2;hts2.parent=i;hti.RChild=s2; hti.weight=hts1.weight+hts2.weight; /*權(quán)值累加生成新的結(jié)點(diǎn)*/ /*葉子結(jié)點(diǎn)的編碼*/ void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int m2) int i,c,p,star

12、t;char *cd;cd=(char *)malloc(m2*sizeof(char); /*根據(jù)字符串長度開辟空間n*/cdm2-1='0' /*末尾置0*/for(i=1;i<=m2;i+) start=m2-1; /*cd串每次從末尾開始*/ c=i; p=hti.parent; /*p在n+1至2n-1*/ while(p) /*沿父親方向遍歷,直到為0 */ start-; /*依次向前置值*/ if(htp.LChild=c) /*與左子相同,置0 */ cdstart='0' else /*否則置1*/ cdstart='1'

13、; c=p; p=htp.parent; weighti.num=m2-start; /*二進(jìn)制碼的長度(包含末尾0) */ /*為i字符開辟存放二進(jìn)制編碼空間*/hi=(char *)malloc(m2-start)*sizeof(char); strcpy(hi,&cdstart); /*將二進(jìn)制字符串拷貝到指針數(shù)組h中*/ /*所有字符的編碼*/void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)int i,k;for(i=0;i<m;i+)/*從wei

14、ghtk.c中查找與chi相等的下標(biāo)K*/for(k=1;k<=n;k+) if(chi=weightk.c) break;hci=(char *)malloc(weightk.num)*sizeof(char);/ char hcweight.numstrcpy(hci,hk); /*拷貝二進(jìn)制編碼*/ printf(" 字符串的編碼為：n"); /*輸出字符串的編碼*/ for(i=0;i<m;i+)printf("%s",hci);printf(" "); /*解碼*/ void TrsHuffmanTree(Huf

15、fmanCode h,WeightNode w,char ch,int n)/*ch是要譯碼的編碼字符，n是結(jié)點(diǎn)的個(gè)數(shù)*/int j=0,k=0,y=0,x=0;char s1N;cout<<endl<<"該二進(jìn)制代碼的字符譯碼為："<<endl;k=strlen(ch); /*要譯碼字符的字符串的個(gè)數(shù)*/for(; y< k; y+) /*循環(huán)查找相應(yīng)的譯碼*/*復(fù)制和比較*/for(int j = 0; j<k;j+,y+) /printf("%d|n %d| %d",j,y,); int flag =

16、 0; /*控制循環(huán)，跳出本循環(huán)*/s1j=chy; /*將字符chy復(fù)制到s1j中*/s1j+1 = '0' /*字符數(shù)組最后一個(gè)賦值*/for(int i = 1; i<= n; i+) /*用S1和字符二進(jìn)制編碼hi進(jìn)行比較*/if(strcmp(s1,hi)=0)/當(dāng)s1=s2時(shí)，返回值=0printf("%c",wi.c); /*相同就輸出*/flag =1; /*標(biāo)記，這個(gè)是讓其之后可以用來跳出下下個(gè)循環(huán)*/break;if (flag) /*之前說的跳出的下下個(gè)循環(huán)的作用*/break;char mima()char ch0N;char

17、ch111;int ch12;char ch261="qwertyuioasdfghjklzxcvbnm,.1234567890 /?:qwertyuiop45678|+-="int i=0,m1=0,m2=0;printf("n輸入字符串: "); cin>>ch1; for(i=0;i<m1;i+)printf("%d",ch1); FILE* fp=fopen("mima.txt","w"); /只寫打開文件夾codefil fprintf(fp,"%s&quo

18、t;,&ch2); fprintf(fp,"%s",&ch1); fclose(fp); printf("n字符串的二進(jìn)制編碼以存進(jìn)默認(rèn)文件夾yimaiwenjian.txt中");i=0; FILE *fp1=fopen("mima.txt","r");/只讀打開文件夾codefilewhile(ch12=fgetc(fp1)!=EOF)ch0i=ch12;i+;ch0i='0' / printf("%s",ch0); fclose(fp1); for(int

19、k=0;k<i;k+)chk=ch0k; chk='0'/printf("%s",ch);return 0;void main( ) system("color f0");int i,k,n=0,xun=0;char HuffmancharN; /*n為葉子結(jié)點(diǎn)的個(gè)數(shù)*/ int m=0,m2;/*m為字符串ch的長度*/char ch2N;/*chN存放輸入的字符串*/ Huffman ht;/*Huffman樹*/HuffmanCode h,hc;/*h存放葉子結(jié)點(diǎn)的編碼，hc 存放所有結(jié)點(diǎn)的編碼*/WeightNode wei

20、ght;/*存放葉子結(jié)點(diǎn)的信息*/ docout<<"nn"cout<<""<<endl;cout<<" "<<endl; cout<<" <哈夫曼編碼和譯碼> "<<endl;cout<<" "<<endl;cout<<" 1.密碼 2.編碼 "<<endl;cout<<" "<<endl

21、;cout<<" 3.譯碼 4.結(jié)束 "<<endl;cout<<" "<<endl;cout<<""<<endl;cout<<"n 請輸入你的選擇(1,2,3,4)"cin>>k;cout<<endl;switch(k)case 1:printf(" 請輸入你要生成密碼數(shù)的字符串 :"); mima(); printf("nn"); CreateWeight(ch,&

22、amp;m,weight,&n);/*產(chǎn)生葉子結(jié)點(diǎn)信息，m為字符串ch的長度 n為葉子結(jié)點(diǎn)的個(gè)數(shù) */printf(" 葉子結(jié)點(diǎn)的字符與權(quán)值為：n結(jié)點(diǎn):"); for(i=1;i<=n;i+)/*輸出葉子結(jié)點(diǎn)的字符與權(quán)值*/printf(" %c ",weighti.c); /*c存放葉子結(jié)點(diǎn)*/printf("n權(quán)值:");for(i=1;i<=n;i+)printf(" %d ",weighti.weight);printf("nn");CreateHuffmanTree

23、(ht,weight,n); /*產(chǎn)生Huffman樹*/ CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*葉子結(jié)點(diǎn)的編碼*/printf(" 葉子結(jié)點(diǎn)的編碼為：n"); /*輸出葉子結(jié)點(diǎn)的編碼*/ for(i=1;i<=n;i+) printf("t%c:",weighti.c); printf("%s n",hi);CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的編碼*/ xun+; break;case 2:printf("輸入編碼的字符串

24、 n"); cin>>ch2;m2=strlen(ch2); CrtHuffmanCode(ch2,h,hc,weight,n,m2); FILE* fp=fopen("yimaiwenjian.txt","w"); /只寫打開文件夾codefile for(i=0;i<m2;i+) fprintf(fp,"%s",hci); fclose(fp); printf("n字符串的二進(jìn)制編碼以存進(jìn)默認(rèn)文件夾yimaiwenjian.txt中");break;case 3: if(xun=0)

25、 cout<<"請先按主界面功能 1 編碼;再安 2 譯碼"<<endl; break; cout<<"解密文件yimaiwenjian.txt請按1n要輸入二進(jìn)制代碼解密請按0"<<endl; int w=0; cin>>w; if(w) FILE *fp;int i=0,ch1; fp=fopen("yimaiwenjian.txt","r");/只讀打開文件夾codefileif(feof(fp)printf("無文件");bre

26、ak;while(ch1=fgetc(fp)!=EOF)Huffmanchari=ch1;i+;Huffmanchari='0' printf("要解密的二進(jìn)制代碼為:"); printf("%s",Huffmanchar);TrsHuffmanTree(h,weight,Huffmanchar,n); /*解碼*/break; else cout<<"請輸入要解密的2進(jìn)制代碼"<<endl; cin>>Huffmanchar; TrsHuffmanTree(h,weight,Huf

27、fmanchar,n); /*解碼*/ break; case 4:printf("1: 退出 請?jiān)侔?4 號(hào)鍵;n2: 繼續(xù) 請按任意數(shù)字n ");cin>>k; break;default:printf("輸入有誤，請選擇數(shù)值14!");break;cout<<endl;/cout<<"n-操作完成- "<<endl;while(k!=4);cout<<"n 再見!"cout<<"n 按任意鍵，將退出程序!n"3.2 程

28、序測試l 在主菜單中選擇1.編碼當(dāng)用戶輸入1并按回車鍵后，即可進(jìn)入1功能的界面。將要進(jìn)行編碼的字符輸入到其中，其編碼過程如圖3.1所示，圖3.1 編碼l 在主菜單中選擇2.譯碼當(dāng)用戶輸入2并按回車鍵后，即可進(jìn)入編碼界面。這里要譯碼的二進(jìn)制代碼分別為“過程分別如圖3.2.1, 3.2.2所示。 l 在主菜單中選擇3.幫助當(dāng)用戶輸入3并按回車鍵后，即可進(jìn)入譯碼界面。其界面如圖3.3所示。圖3.3 幫助l 在主菜單中選擇4.結(jié)束程序當(dāng)用戶輸入4并按回車鍵后，即可退出程序。其過程如圖3.4所示。圖3.4 結(jié)束程序4、歸納總結(jié)41 開發(fā)經(jīng)驗(yàn)通過對本題目的開發(fā)，體會(huì)到要掌握以下幾點(diǎn)內(nèi)容:1.在進(jìn)行編程前，要學(xué)會(huì)先畫流程圖；2.在進(jìn)行編程時(shí)，要學(xué)會(huì)運(yùn)用編程環(huán)境的調(diào)試功能進(jìn)行查錯(cuò)，這會(huì)讓我們學(xué)到很多東西，同時(shí)調(diào)試在編程中有著重要的作用，這是一個(gè)