哈弗曼編碼實(shí)現(xiàn)無損壓縮實(shí)驗(yàn)報(bào)告

1、哈弗曼編碼實(shí)現(xiàn)無損壓縮實(shí)驗(yàn)報(bào)告院系：自動(dòng)化 學(xué)號(hào)：1010200249 姓名：王江鵬 指導(dǎo)老師：何新一、 實(shí)驗(yàn)內(nèi)容通過C+編程實(shí)現(xiàn)。要求：1) 字符串的輸入是手工輸入的；2) 通過程序?qū)崿F(xiàn)編碼，最終在屏幕上顯示編碼結(jié)果，例如，如果選用huffman編碼，則要顯示字符串的編碼以及平均碼長(zhǎng)；二、 源代碼#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、計(jì)文本中有多少個(gè)不同的字符，coun是統(tǒng)計(jì)文本中有多少個(gè)字符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)計(jì)字符頻率函數(shù)int s256=0;/s0到s255分別對(duì)應(yīng)字母的ASCII碼由0到255的統(tǒng)計(jì)個(gè)數(shù)vo

3、id count()int i=0,f=0;char m;while(i<coun)/不能用cout<<a;進(jìn)行輸出會(huì)將a的指針移動(dòng)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);/構(gòu)造Huffman樹*3typedef structint weight;int parent;int lch

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

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+)/構(gòu)造哈弗曼樹m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j+)/選取最小和次小的兩個(gè)權(quán)值，其中n+i中的i代表已經(jīng)多加了i個(gè)非葉子結(jié)點(diǎn)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+)/求每個(gè)葉子結(jié)點(diǎn)的編碼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+)/將編碼的葉子結(jié)點(diǎn)賦給編碼數(shù)組保存load+; /求葉子節(jié)點(diǎn)路徑長(zhǎng)HuffCodei.bitj=cd.bitj;printf("%d",cd.bitj);avlen+=load*sHuffNodei.num; HuffCodei.start=cd.start;printf(" ");avlen=avlen/coun;printf("nnn*n 平均碼長(zhǎng)為 %