Lab05 樹結構的應用學號： 姓名： 實驗時間：2011.5.241.問題描述哈弗曼樹的編碼與譯碼 功能：實現(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 <time.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.退出！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; /權值最小的兩個結點的標號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",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;start1=clock() ;/開始計時1/統(tǒng)計文件中字符的種類以及各類字符的個數(shù)/先用字符的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.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=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?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指針移到文件開頭位置 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)>=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"); 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,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.CodeLength%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ù)存入編碼 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+duration2)/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); 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 *nodep,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); nodepi.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("請輸入要解壓的文件名:"); 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() ;/開始計時 fread(&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,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>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); /指針指向編碼區(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位和hfmnode.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) / 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.對文件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)計完成之后，建立哈弗曼樹：每次選取權值最小且無parent的結點作為左右孩子，建成一棵二叉樹，且設置新的二叉樹的根結點的權值為其左右孩子的權值之和。直至建成含有2*n-1個結點的哈弗曼樹。給每種字符進行編碼。按照從葉子到根的順序求其編碼。算法和圖示如下：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);編碼完成之后，開始對源文件進行壓縮。1. 從源文件讀一個字符，從葉子結點中找出和此字符相同的字符結點，將其編碼寫入一個臨時字符組codes；2. 當codes的長度大于等于8時，將其前8位轉換成字符寫入目標文件中；3. 重復1和2此過程，直至讀完源文件中的所有字符；4. 若codes最后還有剩余的不足8位的01代碼，則將其低位補0至8位，再寫入目標文件。 同時為了便于解碼，將源文件的長度FileLength、編碼區(qū)的長度以及葉子結點的個數(shù)n、每個葉子結點的信息也存入目標文件。存儲方式如下圖所示：FileLength4BSumlength4B源文件編碼區(qū)葉子數(shù)n4B葉子結點信息字符值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相同。