哈夫曼樹與文件解壓壓縮C言代碼

1、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 <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#include <ti

2、me.h>struct nodelong weight; /權值unsigned char ch;/字符int parent,lchild,rchild;char code256;/編碼的位數(shù)最多為256位 int CodeLength;/編碼長度hfmnode512;void compress();void uncompress(); /主函數(shù)void main()int choice; printf("請選擇13：n"); printf("1.壓縮文件n"); printf("2.解壓文件n"); printf("

3、3.退出！n");scanf("%d",&choice);if(choice=1)compress();else if(choice=2)uncompress(); else if(choice=3)return; else printf("輸入錯誤！");/壓縮函數(shù) void compress()int i,j;char infile20,outfile20;FILE *ifp,*ofp; unsigned char c;/long FileLength,filelength=0;int n,m;/葉子數(shù)和結點數(shù)int s1,s2;

4、/權值最小的兩個結點的標號char codes256;long sumlength=0;float rate,speed;int count=0;clock_t start1, start2,finish1,finish2; double duration1,duration2;void encode(struct node *nodep,int n);/編碼函數(shù)int select(struct node *nodep,int pose);/用于建哈弗曼樹中選擇權值最小的結點的函數(shù) printf("請輸入要壓縮的文件名:"); scanf("%s",i

5、nfile); ifp=fopen(infile,"rb");if(ifp=NULL) printf("文件名輸入錯誤，文件不存在!n"); return; printf("請輸入目標文件名:"); scanf("%s",outfile); ofp=fopen(outfile,"wb");if(ofp=NULL) printf("文件名輸入錯誤，文件不存在!n"); return;start1=clock() ;/開始計時1/統(tǒng)計文件中字符的種類以及各類字符的個數(shù)/先用字符的

6、ASCII碼值代替結點下標FileLength=0; while(!feof(ifp) fread(&c,1,1,ifp); hfmnodec.weight+; FileLength+;FileLength-; /文件中最后一個字符的個數(shù)會多統(tǒng)計一次，所以要減一hfmnodec.weight-;/再將ASCII轉換為字符存入到結點的ch成員里，同時給雙親、孩子賦初值-1 n=0; for(i=0;i<256;i+)if(hfmnodei.weight!=0)hfmnodei.ch=(unsigned char)i; n+;/葉子數(shù) hfmnodei.lchild=hfmnodei

7、.rchild=hfmnodei.parent=-1; m=2*n-1;/哈弗曼樹結點總數(shù) j=0; for(i=0;i<256;i+)/去掉權值為0的結點 if(hfmnodei.weight!=0) hfmnodej=hfmnodei; j+; for(i=n;i<m;i+)/初始化根結點hfmnodei.lchild=hfmnodei.rchild=-1;hfmnodei.parent=-1;/建立哈弗曼樹 for(i=n;i<m;i+) s1=select(hfmnode,i-1); hfmnodei.lchild=s1; hfmnodes1.parent=i; s2

8、=select(hfmnode,i-1); hfmnodei.rchild=s2; hfmnodes2.parent=i; hfmnodei.weight=hfmnodes1.weight+hfmnodes2.weight; /編碼encode(hfmnode,n); finish1=clock();duration1=(double)(finish1- start1) / CLOCKS_PER_SEC; /*printf( "哈弗曼樹編碼用時為：%f secondsn", duration1 );*/ printf("編碼完成，是否查看編碼信息: y or n?

9、n"); c=getch(); if(c='y')printf("n"); printf("葉子數(shù)為%d,結點數(shù)為%dn",n,m); for(i=0;i<n;i+)printf("%d號葉子結點的權值為：%ld,雙親為：%d,左右孩子：%d,編碼為：%sn",i,hfmnodei.weight,hfmnodei.parent,hfmnodei.lchild,hfmnodei.code);start2=clock() ;/開始計時2 fseek(ifp,0,SEEK_SET);/將ifp指針移到文件開頭

10、位置 fwrite(&FileLength,4,1,ofp);/將FileLength寫入目標文件的前4個字節(jié)的位置 fseek(ofp,8,SEEK_SET);/再將目標文件指針ofp移到距文件開頭8個字節(jié)位置 codes0=0;/將編碼信息寫入目標文件 while(!feof(ifp) fread(&c,1,1,ifp); filelength+; for(i=0;i<n;i+) if(c=hfmnodei.ch) break;/ch必須也為unsigned 型 strcat(codes,hfmnodei.code); while(strlen(codes)>=

11、8) for(i=0;i<8;i+)/將codes的前8位01代碼表示的字符存入c if(codesi='1') c=(c<<1)|1; else c=c<<1; fwrite(&c,1,1,ofp); /將新的字符寫入目標文件sumlength+; strcpy(codes,codes+8);/更新codes的值 if(filelength=FileLength) break; /再將剩余的不足8位的01代碼補全8位，繼續(xù)寫入 if(strlen(codes)>0) strcat(codes,"00000000"

12、); for(i=0;i<8;i+) if(codesi='1') c=(c<<1)|1; else c=c<<1; fwrite(&c,1,1,ofp); sumlength+; 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,

13、sumlength,SEEK_SET); fwrite(&n,4,1,ofp);/把葉子數(shù)n寫進編碼段后面的4個字節(jié)的位置/為方便解壓，把編碼信息存入n后面的位置/存儲方式為：n*（字符值（1個字節(jié)）+該字符的01編碼的位數(shù)（1個字節(jié)）+編碼（字節(jié)數(shù)不確定，用count來計算總值） for(i=0;i<n;i+) fwrite(&(hfmnodei.ch),1,1,ofp); c=hfmnodei.CodeLength;/編碼最長為256位，因此只需用一個字節(jié)存儲 fwrite(&c,1,1,ofp); /寫入字符的編碼 if(hfmnodei.CodeLengt

14、h%8!=0) for(j=hfmnodei.CodeLength%8;j<8;j+)/把編碼不足8位的在低位補0,賦值給C，再把C寫入 strcat(hfmnodei.code,"0"); while(hfmnodei.code0!=0)/開始存入編碼，每8位二進制數(shù)存入一個字節(jié) c=0; for(j=0;j<8;j+) if(hfmnodei.codej='1') c=(c<<1)|1; else c=c<<1; strcpy(hfmnodei.code,hfmnodei.code+8);/編碼前移8位，繼續(xù)存入編碼

15、count+; /編碼占的字節(jié)數(shù)的總值 fwrite(&c,1,1,ofp); printf("n"); finish2=clock(); duration2=(double)(finish2- start2) / CLOCKS_PER_SEC; /*printf( "寫入目標文件用時為：%f secondsn", duration2);*/ printf( "壓縮用時為：%f secondsn", duration1+duration2); speed=(float)FileLength/(duration1+duratio

16、n2)/1000; printf("n壓縮速率為：%5.2f KB/Sn",speed);printf("n"); printf("源文件長度為：%ld個字節(jié)n",FileLength);sumlength=sumlength+4+n*2+count; /計算壓縮后文件的長度printf("壓縮后文件長度為：%ld個字節(jié)n",sumlength);rate=(float)sumlength/(float)FileLength;printf("壓縮率(百分比)為：%4.2f%n",rate*100

17、); fclose(ifp); fclose(ofp); return;/返回書簽/建立哈弗曼樹中用于選擇最小權值結點的函數(shù)int select(struct node *nodep,int pose) int i;int s1;long min=2147483647;/s初值為long型的最大值for(i=0;i<=pose;i+)if(nodepi.parent!=-1)continue;if(nodepi.weight<min)min=nodepi.weight; s1=i;return s1;/返回書簽/哈弗曼編碼函數(shù)void encode(struct node *nod

18、ep,int n) /從葉子向根求每個字符的哈弗曼編碼int start;int i,f,c;char codes256;codesn-1='0' /編碼結束符for(i=0;i<n;i+) /逐個字符求哈弗曼編碼 start=n-1; for(c=i,f=nodepi.parent;f!=-1;c=f,f=nodepf.parent) start-; if(nodepf.lchild=c) codesstart='0' else codesstart='1' strcpy(nodepi.code,&codesstart); nod

19、epi.CodeLength=strlen(nodepi.code); /返回書簽/解壓函數(shù)void uncompress() /解壓文件 clock_t start, finish; double duration;FILE *ifp,*ofp; char infile20,outfile20; long FileLength,sumlength,filelength;int n,m; int i,j,k;char buf256,codes256; unsigned char c;int maxlength;float speed; printf("請輸入要解壓的文件名:"

20、;); scanf("%s",infile); ifp=fopen(infile,"rb");if(ifp=NULL) printf("文件名輸入錯誤，文件不存在!n"); return; printf("請輸入目標文件名:"); scanf("%s",outfile); ofp=fopen(outfile,"wb");if(ofp=NULL) printf("文件名輸入錯誤，文件不存在!n"); return;start=clock() ;/開始計時 f

21、read(&FileLength,4,1,ifp);/從壓縮文件讀出FileLength、sumlength fread(&sumlength,4,1,ifp); fseek(ifp,sumlength,SEEK_SET); /利用sumlength讀出n的值 fread(&n,4,1,ifp); printf("n解碼信息:源文件長度為%d個字節(jié),字符種類n=%dn",FileLength,n); for(i=0;i<n;i+)/讀結點信息 fread(&hfmnodei.ch,1,1,ifp);/字符 fread(&c,1,

22、1,ifp);/編碼長度 hfmnodei.CodeLength=c; hfmnodei.code0=0; if(hfmnodei.CodeLength%8>0) m=hfmnodei.CodeLength/8+1;/m為編碼占的字節(jié)數(shù) else m=hfmnodei.CodeLength/8; for(j=0;j<m;j+)/根據(jù)字節(jié)長度m讀出編碼 fread(&c,1,1,ifp);/此處c為01編碼轉換成的字符 itoa(c,buf,2);/字符型編碼轉換成二進制型（首位為1） /如果編碼不夠8位，則說明缺少了8-k位0，因此應先在前面空缺位寫0 for(k=8;k&

23、gt;strlen(buf);k-) strcat(hfmnodei.code,"0"); /再把二進制編碼存進hfmnode.code中 strcat(hfmnodei.code,buf); hfmnodei.codehfmnodei.CodeLength=0;/去掉編碼中多余的0 /找出編碼長度的最大值 maxlength=0; for(i=0;i<n;i+) if(hfmnodei.CodeLength>maxlength) maxlength=hfmnodei.CodeLength;/開始寫入目標文件 fseek(ifp,8,SEEK_SET); /指針

24、指向編碼區(qū)，開始解碼 filelength=0; codes0=0; buf0=0; while(1) while(strlen(codes)<maxlength)/codes小于編碼長度的最大值時，繼續(xù)讀碼 fread(&c,1,1,ifp); itoa(c,buf,2);/還原編碼 for(k=8;k>strlen(buf);k-) strcat(codes,"0");/把缺掉的0補上 strcat(codes,buf);/codes中此時存的為一串01編碼 for(i=0;i<n;i+) /在codes中查找能使其前weight位和hfmno

25、de.code相同的i值，weight即為codelength if(memcmp(hfmnodei.code,codes,(unsigned int)hfmnodei.CodeLength)=0) break; strcpy(codes,codes+hfmnodei.CodeLength);/更新codes的值 c=hfmnodei.ch; fwrite(&c,1,1,ofp); filelength+; if(filelength=FileLength) break;/寫入結束 finish = clock(); duration = (double)(finish - start

26、) / CLOCKS_PER_SEC; printf( "n解壓完成，解壓用時為：%f secondsn", duration ); 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/Sn",speed); fclose(ifp); fclose(ofp); return;2.2程序運行結果：1.對文件”測試.txt”進行壓縮，壓縮后存儲在文件”目標.doc”中，壓縮速率為：2055.00KB/S，壓縮率為64.92%。程序運行結果截圖如下：2.再對”測試.txt“文件進行解壓，目標文件為“目標1.doc “。程序運行結果如下：2.3算法描述（1） 壓縮文件壓縮文件時要先對源文件進行統(tǒng)計，統(tǒng)計字符的種類及出現(xiàn)的次數(shù)（即權值）。統(tǒng)計完成之后，建立哈弗曼樹：每次選取權值最小且無p