哈夫曼編碼譯碼系統(tǒng)(樹應(yīng)用)

1、實(shí)驗(yàn)三 哈夫曼編碼/譯碼系統(tǒng)（樹應(yīng)用）一、實(shí)驗(yàn)?zāi)康?. 幫助讀者復(fù)習(xí)C+語言程序設(shè)計(jì)中的知識(shí)。2.哈夫曼樹的建立，哈夫曼編碼的生成，對(duì)編碼信息的翻譯的熟悉和運(yùn)用。需求分析 利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時(shí)間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。二、實(shí)驗(yàn)內(nèi)容和要求問題要求利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時(shí)間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信

2、息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。問題分析在本例中設(shè)置發(fā)送者和接受者兩個(gè)功能，發(fā)送者的功能包括：輸入待傳送的字符信息；統(tǒng)計(jì)字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；利用以上哈夫曼樹求出各字符的哈夫曼編碼；將字符信息轉(zhuǎn)換成對(duì)應(yīng)的編碼信息進(jìn)行傳送。接受者的功能包括：接收發(fā)送者傳送來的編碼信息；利用上述哈夫曼樹對(duì)編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。本實(shí)驗(yàn)首先從文件中讀取數(shù)據(jù)，然后分析數(shù)據(jù)對(duì)不同的元素依次存入一字符數(shù)組并統(tǒng)計(jì)其出現(xiàn)的次數(shù)并當(dāng)做其權(quán)值，然后根據(jù)這些信息建立哈弗曼

3、樹，并對(duì)各個(gè)字符進(jìn)行哈弗曼編碼然后根據(jù)各個(gè)字符的編碼對(duì)所有輸入的一組字符進(jìn)行哈弗曼編碼。譯碼是根據(jù)哈弗曼樹和接收到的一組編碼進(jìn)行譯碼操作。譯碼也就是對(duì)哈弗曼樹的遍歷三、算法設(shè)計(jì)首先讀入一組字符，然后統(tǒng)計(jì)這些字符中不同字符出現(xiàn)的次數(shù)，并當(dāng)做其權(quán)值，然后根據(jù)不同字符及其權(quán)值建立哈弗曼樹。建立哈弗曼樹后即可得到這些不同字符的哈弗曼編碼，然后即可根據(jù)這些哈弗曼編碼對(duì)那組輸入的一串字符進(jìn)行哈弗曼編碼。譯碼是根據(jù)一組編碼翻譯成一組字符的操作，其算法就是根據(jù)這一串編碼來對(duì)哈弗曼樹進(jìn)行遍歷，每遍歷到一個(gè)葉子結(jié)點(diǎn)即輸出一個(gè)字符，直至將編碼操作完即可完成多編碼的翻譯操作。四、調(diào)試分析及數(shù)據(jù)測(cè)試輸入編碼五、測(cè)試結(jié)果

4、程序符合算法要求，能正確編碼#include#include#include#include#includetypedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn)int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;brea

5、k;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /選出最小的節(jié)點(diǎn)for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return

6、;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化n個(gè)葉子結(jié)點(diǎn)printf(請(qǐng)輸入第%d字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i

7、=m;+i) /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給n個(gè)字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c

8、)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 計(jì)算機(jī)科學(xué)與技術(shù) 201200814212 董方園n;while(choice!=Q&choice!=q)

9、 /當(dāng)choice的值不為q且不為Q時(shí)循環(huán)cout *赫夫曼編碼/譯碼器*n;cout I.Init E.Encoding D.Decoding Q.Exitn;coutchoice;if(choice=I|choice=i) /初始化赫夫曼樹coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);out

10、put_file.close();cout赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!endl;else if(choice=E|choice=e) /進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf(請(qǐng)輸入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt)

11、;if(!output_file)coutcant oen file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout編碼完畢，并且已經(jīng)存入CodeFile.txt文件！n;input_file.open(CodeFile.txt); /從CodeFile.txt中讀入編碼，輸出在終端if(!input_file)coutcant oen file!code;cout編碼碼值為：codeendl;input

12、_file.close();else if(choice=D|choice=d) /讀入CodeFile.txt中的編碼進(jìn)行譯碼，將譯出來的字符放入Textfile.txt中input_file.open(CodeFile.txt);if(!input_file)coutcant oen file!h;input_file.close();output_file.open(Textfile.txt);if(!output_file)coutcant oen file!endl;return 1;k=0;while(hk!=0) /先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移for(i=1;i=n;i+)l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)output_fileHTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open(Textfile.txt);if(!input_f