哈夫曼編碼算法實現(xiàn)完整版.doc

實驗三 樹的應用一.實驗題目：樹的應用哈夫曼編碼二.實驗內(nèi)容：利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r間，降低傳輸成本。根據(jù)哈夫曼編碼的原理，編寫一個程序，在用戶輸入結(jié)點權值的基礎上求哈夫曼編碼。要求：從鍵盤輸入若干字符及每個字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點的權值，建立哈夫曼樹，然后對各個字符進行哈夫曼編碼，最后打印輸出字符及對應的哈夫曼編碼。三、程序源代碼:#include #include #include #include typedef struct char data; int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char * * HuffmanCode;void Select(HuffmanTree &HT,int n,int m) HuffmanTree p=HT; int tmp; for(int j=n+1;j=m;j+) int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x=j-1;x+) if(px.parent=0&px.weighttag1) tag1=px.weight;s1=x; for(int y=1;y=j-1;y+) if(py.parent=0&y!=s1&py.weights2) /將選出的兩個節(jié)點中的序號較小的始終賦給s1 tmp=s1; s1=s2; s2=tmp;ps1.parent=j;ps2.parent=j;pj.lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) int m=2*n-1; if(n=1) return; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); HuffmanTree p=HT; for(int i=1;i=n;i+) pi.data=w1i-1; pi.weight=w2i; pi.parent=pi.lchild=pi.rchild=0; for(;i=m;i+) pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m); ofstream outfile; /生成hfmTree文件 outfile.open(hfmTree.txt,ios:out); for (i=1;i=m;i+)outfileHTi.weighttHTi.parenttHTi.lchild tHTi.rchildtendl; outfile.close(); cout初始化結(jié)果已保存在hfmTree文件中n;void ToBeTree() /將正文寫入文件ToBeTree中ofstream outfile;outfile.open(ToBeTree.txt,ios:out);outfileTHIS PROGRAM IS MYFAVORITE;outfile.close();void Encoding(HuffmanTree &HT,int n) /編碼 HuffmanCode HC; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(int k=1;k=n;k+) int start=n-1; for(int c=k,f=HTk.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCk=(char *)malloc(n-start)*sizeof(char); strcpy(HCk,&cdstart); cout輸出哈夫曼編碼:endl; for(int h=1;h=n;h+) /輸出編碼 coutHTh.data:; coutHCh; cout ; if (h%8=0) coutendl; coutendl輸出正文編碼:endl; ToBeTree(); /讀取TOBETREE文件里的正文，并進行編碼 fstream infile; infile.open(ToBeTree.txt,ios:in); char s80; while(!infile.eof() infile.getline(s,sizeof(s); infile.close(); fstream outfile; outfile.open(CodeFile.txt,ios:out); int count=0; for (h=0;sh!=0;h+) for(k=1;k=n;k+) if (sh=HTk.data) coutHCk; cout ; count+; outfileHCk; break; if (count%9=0) coutendl; /每輸出7個換行 outfile.close(); coutn編碼結(jié)果已保存在文件CodeFile中.; coutendl;void Decoding(HuffmanTree &HT,int n) /譯碼 int f=2*n-1; fstream infile; infile.open(CodeFile.txt,ios:in); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); infile.close(); int i=0; int j=0; fstream outfile; outfile.open(TextFile.txt,ios:out); while(si!=0) f=2*n-1;while(HTf.lchild!=0)/以f對應的節(jié)點的左孩子的值=0作為結(jié)束 if (sj=0) f=HTf.lchild;else f=HTf.rchild;j+; i=j; coutHTf.data; outfileHTf.data; outfile.close();coutn譯碼結(jié)果已保存在文件TextFile中.;coutendl;void Print() /印代碼文件 int count=0; fstream infile; infile.open(CodeFile.txt,ios:in); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); for(int i=0;si!=0;i+) coutsi;count+;if (count%50=0) coutendl; /在終端上每行顯示50個代碼 infile.close();coutendl;char menu() /菜單函數(shù) cout功能菜單如下:endl; cout* * * * * * * * * * * * * * * * * * * * *endl; cout I:初始化(Initialization) endl; cout E:編碼(Encoding) endl; cout D:譯碼(Decoding) endl; cout P:印代碼文件(Print) endl; cout Q:退出(Exit) endl; cout* * * * * * * * * * * * * * * * * * * * *endl; coutch;return ch;void main() int n; int Array100; char cArray100; HuffmanTree HT; cout輸入n個字符:; cin.getline(cArray,100); n=strlen(cArray); cout一共n個字符.n; cout依次輸入各個字符的權值:endl; for (int i=1;iArrayi; int tag; char x=menu(); while(1) switch (x) case I:HuffmanCoding(HT,n,cArray,Array);break; case E:Encoding(HT,n);break; case D:Decoding(HT,n);break; case P:Print();break; case Q:tag=0;cout結(jié)束endl;break; default:cout你輸入錯誤!endl; if(tag=0) break; couty(繼續(xù)) or n(退出)ch; if (ch=y) coutc; x=c; else exit(1); 測試數(shù)據(jù)： 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的譯碼和編碼:THIS PROGRAM IS MY FAVORITE. 字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 四.測試結(jié)果：如圖一所示五.實驗體會 通過本次實驗，尤其在自己對程序的調(diào)試過程中，感覺對樹的存儲結(jié)構，終結(jié)狀態(tài)，還有編碼，譯碼的過程都有了比較清晰的認識。在做本次實驗時，其他