哈夫曼樹(shù)與文件解壓壓縮C言代碼

1.問(wèn)題描述哈弗曼樹(shù)的編碼與譯碼—功能：實(shí)現(xiàn)對(duì)任何類(lèi)型文件的壓縮與解碼—輸入：源文件，壓縮文件—輸出：解碼正確性判定，統(tǒng)計(jì)壓縮率、編碼與解碼速度—要求：使用邊編碼邊統(tǒng)計(jì)符號(hào)概率的方法（自適應(yīng)Huffman編碼）和事先統(tǒng)計(jì)概率的方法（靜態(tài)Huffman編碼）2.1程序清單程序書(shū)簽：main函數(shù)壓縮函數(shù)select函數(shù)encode函數(shù)解壓函數(shù)#include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>#include<time.h>structnode{longweight;//權(quán)值unsignedcharch;〃字符intparent,lchild,rchild;charcode[256]；//編碼的位數(shù)最多為256位intCodeLength;〃編碼長(zhǎng)度}hfmnode[512];voidcompress();voiduncompress();//主函數(shù)voidmain(){intchoice;printf("請(qǐng)選擇1~3:\n");printf("1.壓縮文件\n");printf("2廨壓文件\n");printf("3.退出！\n");scanf("%d",&choice);if(choice==1)compress();elseif(choice==2)uncompress();elseif(choice==3)return;elseprintf("輸入錯(cuò)誤！");//壓縮函數(shù)voidcompress(){inti,j;charinfile[20],outfile[20];FILE*ifp,*ofp;unsignedcharc;//longFileLength,filelength=0;intn,m;〃葉子數(shù)和結(jié)點(diǎn)數(shù)ints1,s2;//權(quán)值最小的兩個(gè)結(jié)點(diǎn)的標(biāo)號(hào)charcodes[256];longsumlength=0;floatrate,speed;intcount=0;clock_tstart1,start2,finish1,finish2;doubleduration1,duration2;voidencode(structnode*nodep,intn);//編碼函數(shù)intselect(structnode*nodep,intpose);〃用于建哈弗曼樹(shù)中選擇權(quán)值最小的結(jié)點(diǎn)的函數(shù)printf("請(qǐng)輸入要壓縮的文件名:")；scanf("%s",infile);{{{{{{ifp=fopen(infile,"rb");if(ifp==NULL){printf("文件名輸入錯(cuò)誤，文件不存在!\n");return;}printf("請(qǐng)輸入目標(biāo)文件名：”)；scanf("%s",outfile);ofp=fopen(outfile,"wb");if(ofp==NULL){printf("文件名輸入錯(cuò)誤，文件不存在!\n");return;}start1=clock();//開(kāi)始計(jì)時(shí)1//統(tǒng)計(jì)文件中字符的種類(lèi)以及各類(lèi)字符的個(gè)數(shù)〃先用字符的ASCII碼值代替結(jié)點(diǎn)下標(biāo)FileLength=0;while(!feof(ifp))fread(&c,1,1,ifp);hfmnode[c].weight++;FileLength++;}FileLength--;//文件中最后一個(gè)字符的個(gè)數(shù)會(huì)多統(tǒng)計(jì)一次，所以要減一hfmnode[c].weight--;〃再將ASCII轉(zhuǎn)換為字符存入到結(jié)點(diǎn)的ch成員里，同時(shí)給雙親、孩子賦初值-1n=0;for(i=0;i<256;i++)if(hfmnode[i].weight!=0){hfmnode[i].ch=(unsignedchar)i;門(mén)++；//葉子數(shù)hfmnode[i].lchild=hfmnode[i].rchild=hfmnode[i].parent=-1;}m=2*n-1;〃哈弗曼樹(shù)結(jié)點(diǎn)總數(shù)j=0;for(i=0;i<256;i++)〃去掉權(quán)值為0的結(jié)點(diǎn)if(hfmnode[i].weight!=0)hfmnode[j]=hfmnode[i];j++;}for(i=n;i<m;i++)〃初始化根結(jié)點(diǎn){hfmnode[i].lchild=hfmnode[i].rchild=-1;hfmnode[i].parent=-1;}//建立哈弗曼樹(shù)for(i=n;i<m;i++){s1=select(hfmnode,i-1);hfmnode[i].lchild=s1;hfmnode[s1].parent=i;s2=select(hfmnode,i-1);hfmnode[i].rchild=s2;hfmnode[s2].parent=i;hfmnode[i].weight=hfmnode[s1].weight+hfmnode[s2].weight;}//編碼encode(hfmnode,n);finish1=clock();duration1=(double)(finish1-start1)/CLOCKS_PER_SEC;/*printf("哈弗曼樹(shù)編碼用時(shí)為：%fseconds\n",durationl);*/printf("編碼完成，是否查看編碼信息:yorn?\n");c=getch();if(c=='y'){printf("\n");printf("葉子數(shù)為％d,結(jié)點(diǎn)數(shù)為％d\n”,n,m);for(i=0;i<n;i++)printf("%d號(hào)葉子結(jié)點(diǎn)的權(quán)值為：％&雙親為%d,左右孩子:％d,編碼為：%s\n”,i,hfmnode[i].weight,hfmnode[i].parent,hfmnode[i].lchild,hfmnode[i].code);}start2=clock();//開(kāi)始計(jì)時(shí)2fseek(ifp,0,SEEK_SET);〃將ifp指針移到文件開(kāi)頭位置fwrite(&FileLength,4,1,ofp);〃將FileLength寫(xiě)入目標(biāo)文件的前4個(gè)字節(jié)的位置fseek(ofp,8,SEEK_SET);〃再將目標(biāo)文件指針ofp移到距文件開(kāi)頭8個(gè)字節(jié)位置codes[0]=0;//將編碼信息寫(xiě)入目標(biāo)文件while(!feof(ifp)){fread(&c,1,1,ifp);filelength++;for(i=0;i<n;i++)if(c==hfmnode[i].ch)break；//ch必須也為unsigned型strcat(codes,hfmnode[i].code);while(strlen(codes)>=8){for(i=0;i<8;i++)〃將codes的前8位01代碼表示的字符存入c{if(codes[i]=='1')c=(c<<1)|1;elsec=c<<1;}fwrite(&c,1,1,ofp);//將新的字符寫(xiě)入目標(biāo)文件sumlength++;strcpy(codes,codes+8);//更新codes的值}if(filelength==FileLength)break;//再將剩余的不足8位的01代碼補(bǔ)全8位，繼續(xù)寫(xiě)入if(strlen(codes)>0){strcat(codes,"00000000");for(i=0;i<8;i++){if(codes[i]=='1')c=(c<<1)|1;elsec=c<<1;}fwrite(&c,1,1,ofp);sumlength++;}sumlength+=8;printf("編碼區(qū)總長(zhǎng)為：％ld個(gè)字節(jié)\n”,sumlength-8);〃將sumlength和n的值寫(xiě)入目標(biāo)文件，為的是方便解壓fseek(ofp,4,SEEK_SET);fwrite(&sumlength,4,1,ofp);/"Fsumlength寫(xiě)進(jìn)目標(biāo)文件的第5-8個(gè)字節(jié)里{{{{fseek(ofp,sumlength,SEEK_SET);fwrite(&n,4,Lofp)d^F葉子數(shù)n寫(xiě)進(jìn)編碼段后面的4個(gè)字節(jié)的位置〃為方便解壓，把編碼信息存入n后面的位置//存儲(chǔ)方式為：n*(字符值(1個(gè)字節(jié))+該字符的01編碼的位數(shù)(1個(gè)字節(jié))+編碼(字節(jié)數(shù)不確定，用count來(lái)計(jì)算總值))for(i=0;i<n;i++){fwrite(&(hfmnode[i].ch),1,1,ofp);c=hfmnode[i].CodeLength;〃編碼最長(zhǎng)為256位，因此只需用一個(gè)字節(jié)存儲(chǔ)fwrite(&c,1,1,ofp);//寫(xiě)入字符的編碼if(hfmnode[i].CodeLength%8!=0)for(j=hfmnode[i].CodeLength%8;j<8;j++)//把編碼不足8位的在低位補(bǔ)0,賦值給C,再把C寫(xiě)入strcat(hfmnode[i].code,"0");while(hfmnode[i].code[0]!=0)〃開(kāi)始存入編碼，每8位二進(jìn)制數(shù)存入一個(gè)字節(jié){c=0;for(j=0;j<8;j++)}}if(hfmnode[i].code[j]=='1')c=(c<<1)|1;elsec=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_SEC;/*printf("寫(xiě)入目標(biāo)文件用時(shí)為：％fseconds\n",duration2);*/printf("壓縮用時(shí)為：％fseconds\n",duration1+duration2);speed=(float)FileLength/(duration1+duration2)/1000;printf("\n壓縮速率為：％5.2fKB/S\n”,speed);printf("\n");printf("源文件長(zhǎng)度為：%ld個(gè)字節(jié)\n”,FileLength);sumlength=sumlength+4+n*2+count;//計(jì)算壓縮后文件的長(zhǎng)度printf("壓縮后文件長(zhǎng)度為：%ld個(gè)字節(jié)\n”,sumlength);rate=(float)sumlength/(float)FileLength;printf("壓縮率(百分比)為：％4.2f%%%\n”,rate*100);fclose(ifp);fclose(ofp);return;}〃返回書(shū)簽//建立哈弗曼樹(shù)中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)intselect(structnode*nodep,intpose){inti;ints1;longmin=2147483647;//s初值為long型的最大值for(i=0;i<=pose;i++){if(nodep[i].parent!=-1)continue;if(nodep[i].weight<min){min=nodep[i].weight;s1=i;returns1;〃返回書(shū)簽//哈弗曼編碼函數(shù)voidencode(structnode*nodep,intn){ //從葉子向根求每個(gè)字符的哈弗曼編碼intstart;inti,f,c;charcodes[256];codes[n-1]='\0';//編碼結(jié)束符for(i=0;i<n;i++)//逐個(gè)字符求哈弗曼編碼{start=n-1;for(c=i,f=nodep[i].parent;f!=-1;c=f,f=nodep[f].parent){start--;if(nodep[f].lchild==c)codes[start]='0';elsecodes[start]='1';strcpy(nodep[i].code,&codes[start]);nodep[i].CodeLength=strlen(nodep[i].code);}}〃返回書(shū)簽//解壓函數(shù)voiduncompress()//解壓文件{clock_tstart,finish;doubleduration;FILE*ifp,*ofp;charinfile[20],outfile[20];longFileLength,sumlength,filelength;intn,m;inti,j,k;charbuf[256],codes[256];unsignedcharc;intmaxlength;floatspeed;printf("請(qǐng)輸入要解壓的文件名：”)；scanf("%s",infile);ifp=fopen(infile,"rb");if(ifp==NULL){printf("文件名輸入錯(cuò)誤，文件不存在!\n");return;}printf("請(qǐng)輸入目標(biāo)文件名：”)；scanf("%s",outfile);ofp=fopen(outfile,"wb");if(ofp==NULL){printf("文件名輸入錯(cuò)誤，文件不存在!\n");return;}start=clock();//開(kāi)始計(jì)時(shí)fread(&FileLength,4,1,ifp);//從壓縮文件讀出FileLength、sumlengthfread(&sumlength,4,1,ifp);fseek(ifp,sumlength,SEEK_SET); 〃利用sumlength讀出n的值fread(&n,4,1,ifp);printf("\n解碼信息：源文件長(zhǎng)度為％~個(gè)字節(jié)，字符種類(lèi)n=%d\n",FileLength,n);for(i=0;i<n;i++)〃讀結(jié)點(diǎn)信息{fread(&hfmnode[i].ch,1,1,ifp);〃字符fread(&c,1,1,ifp);〃編碼長(zhǎng)度hfmnode[i].CodeLength=c;hfmnode[i].code[0]=0;if(hfmnode[i].CodeLength%8>0)m=hfmnode[i].CodeLength/8+1;//m為編碼占的字節(jié)數(shù)elsem=hfmnode[i].CodeLength/8;for(j=0；j<m；j++)〃根據(jù)字節(jié)長(zhǎng)度m讀出編碼{fread(&c,1,1,ifp);〃此處c為01編碼轉(zhuǎn)換成的字符itoa(c,buf,2);〃字符型編碼轉(zhuǎn)換成二進(jìn)制型(首位為1)〃如果編碼不夠8位，則說(shuō)明缺少了8-k位0，因此應(yīng)先在前面空缺位寫(xiě)0for(k=8;k>strlen(buf);k--){strcat(hfmnode[i].code,"0");}〃再把二進(jìn)制編碼存進(jìn)hfmnode.code中strcat(hfmnode[i].code,buf);hfmnode[i].code[hfmnode[i].CodeLength]=0;〃去掉編碼中多余的0}//找出編碼長(zhǎng)度的最大值maxlength=0;for(i=0;i<n;i++)if(hfmnode[i].CodeLength>maxlength)maxlength=hfmnode[i].CodeLength;//開(kāi)始寫(xiě)入目標(biāo)文件fseek(ifp,8,SEEK_SET);//指針指向編碼區(qū)，開(kāi)始解碼filelength=0;codes[0]=0;buf[0]=0;while(1){while(strlen(codes)<maxlength)//codes小于編碼長(zhǎng)度的最大值時(shí)，繼續(xù)讀碼{fread(&c,1,1,ifp);itoa(c,buf,2);//還原編碼for(k=8;k>strlen(buf);k--)strcaUcodesJO,)/AF缺掉的0補(bǔ)上strcat(codes,buf)；//codes中此時(shí)存的為一串01編碼}for(i=0;i<n;i++){//在codes中查找能使其前weight位和hfmnode.code相同的i值，weight即為codelengthif(memcmp(hfmnode[i].code,codes,(unsignedint)hfmnode[i].CodeLength)==0)break;}strcpy(codes,codes+hfmnode[i].CodeLength);〃更新codes的值c=hfmnode[i].ch;fwrite(&c,1,1,ofp);filelength++;if(filelength==FileLength)breakd/寫(xiě)入結(jié)束}finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("\n解壓完成，解壓用時(shí)為：％fseconds\n",duration);fseek(ifp,0,SEEK_SET);FileLength=0;while(!feof(ifp)){fread(&c,1,1,ifp);FileLength++;}FileLength--;speed=(float)FileLength/duration/1000;/*printf(“此文件長(zhǎng)度為：%ld個(gè)字節(jié)\n”,FileLength);*/printf("\n解壓速度為：％5.2fKB/S\n”,speed);fclose(ifp);fclose(ofp);return;}2.2程序運(yùn)行結(jié)果：.對(duì)文件”測(cè)試.txt”進(jìn)行壓縮，壓縮后存儲(chǔ)在文件“目標(biāo)不碇”中，壓縮速率為：2055.00KB/S，壓縮率為64.92%。程序運(yùn)行結(jié)果截圖如下：如下：如下：如下：如下："C:\USERS\DELL\DESKTOP\Mt\Debuq\yasuo.exe"試a

鼎碼X名查

耳.---.試a

鼎碼X名查

耳.---.口3:*□文文！靠壓出運(yùn)|+1土標(biāo)-要人人完通物叫情」Q.3.1請(qǐng)請(qǐng)、'C:\USERS\UELL\DESKTQP\rag\Debijg\yasuo.exe"眄碼區(qū)總長(zhǎng)為：mi個(gè)字節(jié)壓縮用時(shí)為?0.007000seconds壓縮速率為：2055.00KBZS幅羲滬.5個(gè)字節(jié)PressanyJseytocontinue2.再對(duì)"測(cè)試.txt”文件進(jìn)行解壓，目標(biāo)文件為“目標(biāo)1.doc"。程序運(yùn)行結(jié)果"C:\USERS\DELL\DESKT0P\J5^\Debug\yasuo.exe"-txt翻錯(cuò)酷酷就嗑解碼信息:源文件長(zhǎng)度為"C:\USERS\DELL\DESKT0P\J5^\Debug\yasuo.exe"-txt翻錯(cuò)酷酷就嗑解碼信息:源文件長(zhǎng)度為166&18白25,個(gè)宇節(jié)，字符種類(lèi)11=-858州346目2.3算法描述(1)壓縮文件壓縮文件時(shí)要先對(duì)源文件進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)字符的種類(lèi)及出現(xiàn)的次數(shù)(即權(quán)值)。統(tǒng)計(jì)完成之后，建立哈弗曼樹(shù)：每次選取權(quán)值最小且無(wú)parent的結(jié)點(diǎn)作為左右孩子，建成一棵二叉樹(shù)，且設(shè)置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右孩子的權(quán)值之和。直至建成含有2*n-1個(gè)結(jié)點(diǎn)的哈弗曼樹(shù)。給每種字符進(jìn)行編碼。按照從葉子到根的順序求其編碼。算法和圖示