哈弗曼編碼實現(xiàn)無損壓縮實驗報告

1、哈弗曼編碼實現(xiàn)無損壓縮實驗報告院系：自動化 學號：1010200249 姓名：王江鵬 指導老師：何新一、 實驗內(nèi)容通過C+編程實現(xiàn)。要求：1) 字符串的輸入是手工輸入的；2) 通過程序?qū)崿F(xiàn)編碼，最終在屏幕上顯示編碼結果，例如，如果選用huffman編碼，則要顯示字符串的編碼以及平均碼長；二、 源代碼#include<stdio.h>#include<string>#define MAXVALUE 100000#define MAXLEAF 256#define MAXNODE MAXLEAF*2-1char a100000=0;int qq=0,coun=0;/qq是統(tǒng)

2、計文本中有多少個不同的字符，coun是統(tǒng)計文本中有多少個字符float avlen=0;/*FILE *f;f=fopen("D:hafuman1.text","r");*/建立文本函數(shù)void creat_save()int i=0;printf("please input textn");gets(a); while(ai!=NULL) i+; coun+; printf("coun=%d",coun);/統(tǒng)計字符頻率函數(shù)int s256=0;/s0到s255分別對應字母的ASCII碼由0到255的統(tǒng)計個數(shù)vo

3、id count()int i=0,f=0;char m;while(i<coun)/不能用cout<<a;進行輸出會將a的指針移動m=0;for(int j=0;ai!=m;j+)m+;sm+;i+;printf(" n");/*for(i=0;i<256;i+)printf("%3d",si);*/while(f!=255)if(sf!=0)qq+;f+;printf("nqq=%dn",qq);/構造Huffman樹*3typedef structint weight;int parent;int lch

4、ild;int rchild;char num;HNodeType;HNodeType HuffNodeMAXNODE;/MAXNODE代表所有結點的個數(shù)int n;/葉子結點個數(shù)void HuffmanTree()int i,j,m1,m2,x1,x2;n=qq;/葉子結點的個數(shù)for(i=0;i<MAXNODE;i+)HuffNodei.weight=0;HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;HuffNodei.num=-1;/cout<<"請分別輸入各個葉子結點的權值:"

5、;<<endl;j=0;for(i=0;i<256;i+)if(si!=0)HuffNodej.weight=si;HuffNodej.num=i;j+;for(i=0;i<n-1;i+)/構造哈弗曼樹m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j+)/選取最小和次小的兩個權值，其中n+i中的i代表已經(jīng)多加了i個非葉子結點if(HuffNodej.parent=-1&&HuffNodej.weight<m1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;else if(HuffNode

6、j.parent=-1&&HuffNodej.weight<m2)m2=HuffNodej.weight;x2=j;/將第找出的倆棵子樹合并為一棵新子樹HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;/Huffman編碼算法*4#define MAXBIT 200typedef structint bitMAXBIT;int start;

7、HCodeType;HCodeType HuffCodeMAXLEAF,cd;void HaffmanCode()int i,j,c,p;HuffmanTree();/建立哈弗曼樹for(i=0;i<qq;i+)/求每個葉子結點的編碼int load=0;cd.start=qq-1;c=i;p=HuffNodec.parent;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HuffNodec.parent;printf("n%c:頻率為%d:編碼為",HuffNodei.num,sHuffNodei.num);for(j=cd.start+1;j<qq;j+)/將編碼的葉子結點賦給編碼數(shù)組保存load+; /求葉子節(jié)點路徑長HuffCodei.bitj=cd.bitj;printf("%d",cd.bitj);avlen+=load*sHuffNodei.num; HuffCodei.start=cd.start;printf(" ");avlen=avlen/coun;printf("nnn*n 平均碼長為 %