《哈弗曼樹的文件壓縮和解壓實驗報告(C語言)》由會員分享，可在線閱讀，更多相關《哈弗曼樹的文件壓縮和解壓實驗報告(C語言)（13頁珍藏版）》請在裝配圖網上搜索。
1、
Lab05 樹結構的應用
學號： 姓名： 實驗時間：2011.5.24
1.問題描述
哈弗曼樹的編碼與譯碼
— 功能：實現(xiàn)對任何類型文件的壓縮與解碼
— 輸入：源文件，壓縮文件
— 輸出：解碼正確性判定，統(tǒng)計壓縮率、編碼與解碼速度
— 要求： 使用邊編碼邊統(tǒng)計符號概率的方法（自適應Huffman編碼） 和事先統(tǒng)計概率的方法（靜態(tài)Huffman編碼） 。
2.1程序清單
程序書簽：
1. main函數(shù)
2. 壓縮函數(shù)
3. select函數(shù)
4. encode函數(shù)
5. 解壓函數(shù)
#include <
2、stdio.h>
#include
#include
#include
#include
struct node{
long weight; //權值
unsigned char ch;//字符
int parent,lchild,rchild;
char code[256];//編碼的位數(shù)最多為256位
int CodeLength;//編碼長度
}hfmnode[512];
void compress();
void uncompress();
//主函數(shù)
v
3、oid main()
{
int choice;
printf("請選擇1~3：\n");
printf("1.壓縮文件\n");
printf("2.解壓文件\n");
printf("3.退出！\n");
scanf("%d",&choice);
if(choice==1)compress();
else if(choice==2)uncompress();
else if(choice==3)return;
else printf("輸入錯誤！");
}
//壓縮函數(shù)
voi
4、d compress()
{
int i,j;
char infile[20],outfile[20];
FILE *ifp,*ofp;
unsigned char c;//
long FileLength,filelength=0;
int n,m;//葉子數(shù)和結點數(shù)
int s1,s2; //權值最小的兩個結點的標號
char codes[256];
long sumlength=0;
float rate,speed;
int count=0;
clock_t start1, start2,finish
5、1,finish2;
double duration1,duration2;
void encode(struct node *nodep,int n);//編碼函數(shù)
int select(struct node *nodep,int pose);//用于建哈弗曼樹中選擇權值最小的結點的函數(shù)
printf("請輸入要壓縮的文件名:");
scanf("%s",infile);
ifp=fopen(infile,"rb");
if(ifp==NULL)
{
printf("文件名輸入錯誤，文件不存在!
6、\n");
return;
}
printf("請輸入目標文件名:");
scanf("%s",outfile);
ofp=fopen(outfile,"wb");
if(ofp==NULL)
{
printf("文件名輸入錯誤，文件不存在!\n");
return;
}
start1=clock() ;//開始計時1
//統(tǒng)計文件中字符的種類以及各類字符的個數(shù)
//先用字符的ASCII碼值代替結點下標
FileLength=0;
7、
while(!feof(ifp))
{
fread(&c,1,1,ifp);
hfmnode[c].weight++;
FileLength++;
}
FileLength--; //文件中最后一個字符的個數(shù)會多統(tǒng)計一次，所以要減一
hfmnode[c].weight--;
//再將ASCII轉換為字符存入到結點的ch成員里，同時給雙親、孩子賦初值-1
n=0;
for(i=0;i<256;i++)
if(hfmnode[i].weight!=0)
{
hfm
8、node[i].ch=(unsigned char)i;
n++;//葉子數(shù)
hfmnode[i].lchild=hfmnode[i].rchild=hfmnode[i].parent=-1;
}
m=2*n-1;//哈弗曼樹結點總數(shù)
j=0;
for(i=0;i<256;i++)//去掉權值為0的結點
if(hfmnode[i].weight!=0)
{
hfmnode[j]=hfmnode[i];
j++;
}
for(i=n;i
9、始化根結點
{
hfmnode[i].lchild=hfmnode[i].rchild=-1;
hfmnode[i].parent=-1;
}
//建立哈弗曼樹
for(i=n;i
10、node[i].weight=hfmnode[s1].weight+hfmnode[s2].weight;
}
//編碼
encode(hfmnode,n);
finish1=clock();
duration1=(double)(finish1- start1) / CLOCKS_PER_SEC;
/*printf( "哈弗曼樹編碼用時為：%f seconds\n", duration1 );*/
printf("編碼完成，是否查看編碼信息: y or n?\n");
c=getch();
if(c==y)
{ printf("\
11、n");
printf("葉子數(shù)為%d,結點數(shù)為%d\n",n,m);
for(i=0;i
12、,1,ofp);//將FileLength寫入目標文件的前4個字節(jié)的位置
fseek(ofp,8,SEEK_SET);//再將目標文件指針ofp移到距文件開頭8個字節(jié)位置
codes[0]=0;
//將編碼信息寫入目標文件
while(!feof(ifp))
{
fread(&c,1,1,ifp);
filelength++;
for(i=0;i
13、 while(strlen(codes)>=8)
{
for(i=0;i<8;i++)//將codes的前8位01代碼表示的字符存入c
{
if(codes[i]==1)
c=(c<<1)|1;
else c=c<<1;
}
fwrite(&c,1,1,ofp); //將新的字符寫入目標文件
sumlength++;
strcpy(codes,codes+8);//更新codes的值
}
14、 if(filelength==FileLength) break;
}
//再將剩余的不足8位的01代碼補全8位，繼續(xù)寫入
if(strlen(codes)>0)
{
strcat(codes,"00000000");
for(i=0;i<8;i++)
{
if(codes[i]==1)
c=(c<<1)|1;
else c=c<<1;
}
fwrite(&c,1,1,ofp);
sum
15、length++;
}
sumlength+=8;
printf("編碼區(qū)總長為：%ld個字節(jié)\n",sumlength-8);
//將sumlength和n的值寫入目標文件，為的是方便解壓
fseek(ofp,4,SEEK_SET);
fwrite(&sumlength,4,1,ofp);//把sumlength寫進目標文件的第5-8個字節(jié)里
fseek(ofp,sumlength,SEEK_SET);
fwrite(&n,4,1,ofp);//把葉子數(shù)n寫進編碼段后面的4個字節(jié)的位置
16、//為方便解壓，把編碼信息存入n后面的位置
//存儲方式為：n*（字符值（1個字節(jié)）+該字符的01編碼的位數(shù)（1個字節(jié)）+編碼（字節(jié)數(shù)不確定，用count來計算總值））
for(i=0;i
17、8!=0)
for(j=hfmnode[i].CodeLength%8;j<8;j++)//把編碼不足8位的在低位補0,賦值給C，再把C寫入
strcat(hfmnode[i].code,"0");
while(hfmnode[i].code[0]!=0)//開始存入編碼，每8位二進制數(shù)存入一個字節(jié)
{
c=0;
for(j=0;j<8;j++)
{
if(hfmnode[i].code[j]==1)
18、 c=(c<<1)|1;
else c=c<<1;
}
strcpy(hfmnode[i].code,hfmnode[i].code+8);//編碼前移8位，繼續(xù)存入編碼
count++; //編碼占的字節(jié)數(shù)的總值
fwrite(&c,1,1,ofp);
}
}
printf("\n");
finish2=clock();
duration2=(double)(finish2- start2) / CLOCKS_PER_
19、SEC;
/*printf( "寫入目標文件用時為：%f seconds\n", duration2);*/
printf( "壓縮用時為：%f seconds\n", duration1+duration2);
speed=(float)FileLength/(duration1+duration2)/1000;
printf("\n壓縮速率為：%5.2f KB/S\n",speed);
printf("\n");
printf("源文件長度為：%ld個字節(jié)\n",FileLength);
sumlength=sumlen
20、gth+4+n*2+count; //計算壓縮后文件的長度
printf("壓縮后文件長度為：%ld個字節(jié)\n",sumlength);
rate=(float)sumlength/(float)FileLength;
printf("壓縮率(百分比)為：%4.2f%%%\n",rate*100);
fclose(ifp);
fclose(ofp);
return;
}
//返回書簽
//建立哈弗曼樹中用于選擇最小權值結點的函數(shù)
int select(struct node *nodep,int pose)
{
int
21、i;
int s1;
long min=2147483647;//s初值為long型的最大值
for(i=0;i<=pose;i++)
{
if(nodep[i].parent!=-1)continue;
if(nodep[i].weight
22、art;
int i,f,c;
char codes[256];
codes[n-1]=\0; //編碼結束符
for(i=0;i
23、 strcpy(nodep[i].code,&codes[start]);
nodep[i].CodeLength=strlen(nodep[i].code);
}
}
//返回書簽
//解壓函數(shù)
void uncompress() //解壓文件
{
clock_t start, finish;
double duration;
FILE *ifp,*ofp;
char infile[20],outfile[20];
long FileLength,sumlength,filelength;
int n,m;
24、
int i,j,k;
char buf[256],codes[256];
unsigned char c;
int maxlength;
float speed;
printf("請輸入要解壓的文件名:");
scanf("%s",infile);
ifp=fopen(infile,"rb");
if(ifp==NULL)
{
printf("文件名輸入錯誤，文件不存在!\n");
return;
}
printf("請輸入目標文件名:");
scan
25、f("%s",outfile);
ofp=fopen(outfile,"wb");
if(ofp==NULL)
{
printf("文件名輸入錯誤，文件不存在!\n");
return;
}
start=clock() ;//開始計時
fread(&FileLength,4,1,ifp);//從壓縮文件讀出FileLength、sumlength
fread(&sumlength,4,1,ifp);
fseek(ifp,sumlength,SEEK_SET); //利用sumlength讀出
26、n的值
fread(&n,4,1,ifp);
printf("\n解碼信息:源文件長度為%d個字節(jié),字符種類n=%d\n",FileLength,n);
for(i=0;i0) m=hfmn
27、ode[i].CodeLength/8+1;//m為編碼占的字節(jié)數(shù)
else m=hfmnode[i].CodeLength/8;
for(j=0;jstrlen(buf);k--)
28、 {
strcat(hfmnode[i].code,"0");
}
//再把二進制編碼存進hfmnode.code中
strcat(hfmnode[i].code,buf);
}
hfmnode[i].code[hfmnode[i].CodeLength]=0;//去掉編碼中多余的0
}
//找出編碼長度的最大值
maxlength=0;
for(i=0;imaxleng
29、th)
maxlength=hfmnode[i].CodeLength;
//開始寫入目標文件
fseek(ifp,8,SEEK_SET); //指針指向編碼區(qū)，開始解碼
filelength=0;
codes[0]=0;
buf[0]=0;
while(1)
{
while(strlen(codes)strlen(buf
30、);k--)
{
strcat(codes,"0");//把缺掉的0補上
}
strcat(codes,buf);//codes中此時存的為一串01編碼
}
for(i=0;i
31、des,codes+hfmnode[i].CodeLength);//更新codes的值
c=hfmnode[i].ch;
fwrite(&c,1,1,ofp);
filelength++;
if(filelength==FileLength) break;//寫入結束
}
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "\n解壓完成，解壓用時為：%f seconds\n", duration );
32、
fseek(ifp,0,SEEK_SET);
FileLength=0;
while(!feof(ifp))
{
fread(&c,1,1,ifp);
FileLength++;
}
FileLength--;
speed=(float)FileLength/duration/1000;
/*printf("此文件長度為：%ld個字節(jié)\n",FileLength);*/
printf("\n解壓速度為：%5.2fKB/S\n",speed);
fclose(ifp);
33、 fclose(ofp);
return;
}
2.2程序運行結果：
1.對文件xue.doc（45，056字節(jié)）進行壓縮，壓縮后存儲在文件b.txt中，壓縮速率為：3003.73KB/S，壓縮率為75.50%。
程序運行結果截圖如下：
2.再對b.txt文件進行解壓，目標文件為pp.doc,解壓后的文件PP.doc與源文件xue.doc完全相同，解壓速度為180.94 KB/S。程序運行結果如下：
2.3算法描述
（1） 壓縮文件
壓縮文件時要先對源文件進行統(tǒng)計，統(tǒng)計字符的種類及出現(xiàn)的次數(shù)（即權值）。統(tǒng)計完成之后，建立哈弗曼樹：每次選取權值最小
34、且無parent的結點作為左右孩子，建成一棵二叉樹，且設置新的二叉樹的根結點的權值為其左右孩子的權值之和。直至建成含有2*n-1個結點的哈弗曼樹。
給每種字符進行編碼。按照從葉子到根的順序求其編碼。算法和圖示如下：
for(i=0;i
35、s[start]=1;
}
strcpy(nodep[i].code,&codes[start]);
}
編碼完成之后，開始對源文件進行壓縮。
1. 從源文件讀一個字符，從葉子結點中找出和此字符相同的字符結點，將其編碼寫入一個臨時字符組codes；
2. 當codes的長度大于等于8時，將其前8位轉換成字符寫入目標文件中；
3. 重復1和2此過程，直至讀完源文件中的所有字符；
4. 若codes最后還有剩余的不足8位的01代碼，則將其低位補0至8位，再寫入目標文件。
同時為了便于解碼，將源文件的長度FileLength、編碼
36、區(qū)的長度以及葉子結點的個數(shù)n、每個葉子結點的信息也存入目標文件。存儲方式如下圖所示：
FileLength
4B
Sumlength
4B
源文件編碼區(qū)
葉子數(shù)n
4B
葉子結點信息
字符值1B
字符的編碼位數(shù)1B
字符的編碼
...............
|—— 1個結點的信息——|
sumlength
（2）解壓文件
從被壓縮的文件中讀出FileLength、n的值，以及每個葉子結點的信息：字符、字符對應的編碼。
開始解碼：
1.從被壓縮的文件編碼區(qū)讀出一個字符，將其值轉化成二進制形式（不足8位的高位要補0），存入codes中，直至codes的長度不小于所有葉子結點的編碼的長度；
2.用for循環(huán)查找出第一個和codes的01字符串匹配的葉子結點編碼，將該葉子結點的字符寫入目標文件，并將codes的字符串前移，前移位數(shù)=該葉子結點編碼的長度。
3.重復1和2過程，直至寫入的字符數(shù)與源文件的長度FileLength相同。
哈弗曼樹的文件壓縮和解壓實驗報告(C語言)
