用赫夫曼編碼完成文件壓縮

1、實(shí)驗(yàn)報(bào)告題目：用赫夫曼編碼實(shí)現(xiàn)文件壓縮班級(jí)：理科實(shí)驗(yàn)四班 姓名：王渭森學(xué)號(hào)：2015201992 完成日期：2016.6.101、 需求分析1.現(xiàn)實(shí)需求：1）通信線路中實(shí)現(xiàn)信息的最大傳送，利用變長(zhǎng)編碼的方式，可以有效充分利用帶寬，實(shí)現(xiàn)信息傳送前的壓縮。2).在文件保存時(shí)，利用哈夫曼編碼的方式，壓縮文件,可以實(shí)現(xiàn)硬盤存儲(chǔ)最大的信息量。2.程序執(zhí)行的命令包括：1） 讀取文件。2） 新建并寫入文件。3） 將文件中的字符轉(zhuǎn)換為哈夫曼編碼。4） 將哈夫曼編碼八位一組專戶為十進(jìn)制，在通過十進(jìn)制的ASCII碼轉(zhuǎn)換為字符。5） 翻譯過程現(xiàn)將字符轉(zhuǎn)為01串，再將01串翻譯為原來的文件。3.測(cè)試數(shù)據(jù)1）2）3）4

2、）5）新建一個(gè)文件并壓縮。2、 概要設(shè)計(jì)1.串的抽象數(shù)據(jù)類型定義為：ADT String數(shù)據(jù)對(duì)象：D=ai|aiCharacterSet,i=1,2,.,n,n=0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=1,2,.,n基本操作：strcpy(String &S1,String S2)初始條件：串S2存在。操作結(jié)果：由串S2復(fù)制得串S1.strlen(SString S)初始條件：串S存在。操作結(jié)果：返回S的元素個(gè)數(shù)，稱為串的長(zhǎng)度。/ADT String2. 二叉樹的抽象數(shù)據(jù)類型定義為：ADT BinaryTree數(shù)據(jù)對(duì)象D：是具有相同特性的元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空二叉樹；若

3、D僅含一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H,H是如下二元關(guān)系：1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；2）若Droot，則存在Droot的一個(gè)劃分DlDr，DlDr=；3）若Dl,則Dl中存在惟一的數(shù)據(jù)元素x，H，且存在Dl上的關(guān)系HlH；若Dr,則Dr中存在惟一的數(shù)據(jù)元素xr，H，且存在Dr上的關(guān)系HrCompressFile()-HuffmanCoding()-Select() -WriteFile()-CoToCh() -DeCompressFile()-ChToCo(CName); -translation()3、 調(diào)試分析1. 文件中字符數(shù)目可能非常大，不能

4、用一個(gè)整的數(shù)組來存，所以需要從文件中一個(gè)字符一個(gè)字符來讀取處理。2. 為解決文件中字符出現(xiàn)的不確定性，用數(shù)組character256來記錄相應(yīng)ASCII的字符出現(xiàn)次數(shù)，統(tǒng)計(jì)完后，將出現(xiàn)次數(shù)非零的字符存在數(shù)組v中，并將它們的權(quán)值存在數(shù)組w中。3. 在將赫夫曼編碼翻譯為字符中，translation（）中函數(shù)的變量ch，在運(yùn)算中應(yīng)該變它的對(duì)應(yīng)的值，即為，傳參應(yīng)為 char &ch，而不應(yīng)為char ch。4.將哈夫曼八位一組轉(zhuǎn)為十進(jìn)制時(shí)，01串中個(gè)數(shù)不一定為8的倍數(shù)，先遍歷文件，統(tǒng)計(jì)01串中元素個(gè)數(shù)，將該個(gè)數(shù)除以8的余數(shù)拿出來，放入壓縮文件的第一位，在依次將等于余數(shù)個(gè)數(shù)的01字符直接放入壓縮文件，

5、之后的 01串為8的整數(shù)倍。5. 讀取壓縮后的亂碼是，可能讀出負(fù)數(shù)，若讀出負(fù)數(shù)，讓這個(gè)負(fù)數(shù)加上256再轉(zhuǎn)化為2進(jìn)制的01串。4、 測(cè)試結(jié)果1.如圖，4為余數(shù)。壓縮率：125%可見，當(dāng)文件中元素個(gè)數(shù)小于8時(shí)，壓縮文件反而會(huì)增大。2.壓縮率：7/303.壓縮率：9/30。4.原文件大小為：21.2KB壓縮文件大小為11.3KB壓縮率接近百分之五十?？偤?、3、4可見，可見，相同大小的文件，其中元素分布越集中，壓縮率越大。5.五、附錄源程序文件清單：#define MAXWEIGHT 2147483647#define MAXASCII 255#define MAXNAME 100#include

6、#include#include#includetypedef struct char data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹 typedef char *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼。 void Select(HuffmanTree HT,int index,int &s1,int &s2)/從序號(hào)為1index的結(jié)點(diǎn)中選出兩個(gè)最小的且沒有雙親的結(jié)點(diǎn)。 int w1,w2,t,i;s1=0;s2=0;w1=MAXWEIGHT;w2=MAXWEIGHT;for(

7、i=1;i=index;i+)if(HTi.parent=0)if(HTi.weightw1)s2=s1;w2=w1;s1=i;w1=HTi.weight;else if(HTi.weightweight=m;for(p=HT+1,i=1;iweight=*w;p-lchild=0;p-rchild=0;p-parent=0;p-data=*v;for(;iweight=0;p-lchild=0;p-rchild=0;p-parent=0;for(i=n+1;i=m;i+)/在HT1.i-1選擇parent為0而且weight最小的/兩個(gè)結(jié)點(diǎn)且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別/為s1和s

8、2Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/-從葉子到根逆向求每個(gè)字符的霍夫曼編碼-char *cd;int start,c,f;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.

9、parent) if(HTf.lchild=c)cd-start=0; else cd-start=1;HCi=(char*)malloc(n-start+1)*sizeof(char);strcpy(HCi+1,&cdstart);HCi0=vi-1-n; free(cd);return 1; void translation(FILE *fp1,FILE *fp2,char &ch,HuffmanTree HT,int i,int f)/逐字翻譯壓縮文件中的赫夫曼編碼 if(HTi.lchild=0&HTi.rchild=0)/若為葉子結(jié)點(diǎn)，則成功翻譯一個(gè)字符，將它輸入到解壓文件中 fpu

10、tc(HTi.data,fp2);if(f=0)ch=fgetc(fp1);return;if(ch=0)/若為0，則探索左孩子 f=1;ch=fgetc(fp1);translation(fp1,fp2,ch,HT,HTi.lchild,f);else if(ch=1)/若為1，則探索左孩子f=1;ch=fgetc(fp1);translation(fp1,fp2,ch,HT,HTi.rchild,f);void CoToCh(char CName)FILE *fp1,*fp2;char DNameMAXNAME=0,ch;/存放壓縮后的文件名int Bin7=0,asc;/八個(gè)01一組放入

11、Bin串;二進(jìn)制對(duì)應(yīng)的ASCII值 int i,j,num=0,r;printf(請(qǐng)輸入你希望得到的壓縮后的文件名:);gets(DName);fp1=fopen(CName,rb);fp2=fopen(DName,wb);while(!feof(fp1)/計(jì)算0，1的數(shù)量 ch=fgetc(fp1);num+;num-;rewind(fp1);r=num%8;/八個(gè)一組多余出來的01 fputc(r+0,fp2);/將多出來的數(shù)量的值放在壓縮文件第一位 for(j=1;j=r;j+)/后面r位原封不動(dòng)的將01復(fù)制進(jìn)來 ch=fgetc(fp1);fputc(ch,fp2);while(!fe

12、of(fp1)i=0;asc=0;memset(Bin,0,sizeof(Bin);while(!feof(fp1)&i=7)ch=fgetc(fp1);Bini=ch-0;i+; if(feof(fp1)break;for(j=0;j=i-1;j+) asc=asc*2+Binj;fputc(asc,fp2);fclose(fp1);fclose(fp2); printf(壓縮后的文件名為:);puts(DName);void WriteFile(HuffmanCode HC,char FName,int k,char v)/將被壓縮的文件內(nèi)容寫入另一個(gè)文件 FILE *fp1,*fp2;c

13、har CNameMAXNAME=0,ch;strcpy(CName,CP);strcpy(CName+2,FName);/哈夫曼編碼文件命名為CP+原文件名fp1=fopen(FName,rb);fp2=fopen(CName,wb);while(1)int i;ch=fgetc(fp1);if(feof(fp1)break;for(int i=0;i=k-1;i+)if(ch=vi)fputs(HCi+1+1,fp2);/將赫夫曼編碼寫入哈夫曼編碼文件 fclose(fp1);fclose(fp2);CoToCh(CName);void CompressFile(HuffmanTree &

14、HT,HuffmanCode &HC,int &k)/讀取文件中的字符，構(gòu)造哈夫曼曼樹，得到每個(gè)字符的哈夫曼編碼 FILE *fp;int flag;char ch,vMAXASCII+1,FNameMAXNAME;/v存放出現(xiàn)的字符 int characterMAXASCII+1=0;/統(tǒng)計(jì)每種字符出現(xiàn)的次數(shù) int wMAXASCII+1;/w放字符的權(quán)值 printf(請(qǐng)鍵入要運(yùn)行的操作編號(hào)：n1.壓縮已有的文件n2.建立新文件，輸入內(nèi)容并進(jìn)行壓縮n);scanf(%d,&flag);/選擇操作 getchar();if(flag=1)printf(請(qǐng)鍵入需要壓縮的文件名：);gets(

15、FName); fp=fopen(FName,r); else if(flag=2)printf(請(qǐng)鍵入需要壓縮的文件名：);gets(FName);printf(請(qǐng)鍵入文件內(nèi)容：n);fp=fopen(FName,w);while(ch!=n)scanf(%c,&ch);fputc(ch,fp);fclose(fp);fp=fopen(FName,r);else printf(警告：無此操作項(xiàng)！);return; while(1)/逐個(gè)讀取文件中的字符,數(shù)組character對(duì)應(yīng)字符位置上+1int i;ch=fgetc(fp);if(feof(fp)break; characterch+;

16、for(int i=0;i=MAXASCII-1;i+) /若某字符在在文件中出現(xiàn)，則把它放入v，并把權(quán)值計(jì)入相同序號(hào)的w if(characteri!=0) vk=i;wk+=characteri;printf(文件中出現(xiàn)的字符及它們的權(quán)值:n);for(int i=0;i=k-1;i+) printf(%c-%d;n,vi,wi);HuffmanCoding(HT,HC,v,w,k); fclose(fp);printf(上述字符對(duì)應(yīng)的哈夫曼編碼：n); for(int i=1;i=k;i+) puts(HCi);WriteFile(HC,FName,k,v);void ChToCo(ch

17、ar DName,char CName)FILE *fp1,*fp2;int r,i,j,Bin7=0,asc;char ch;fp1=fopen(DName,rb);strcpy(CName,RCP);strcpy(CName+3,DName);fp2=fopen(CName,wb);r=fgetc(fp1)-0;for(i=1;i=r;i+)ch=fgetc(fp1);fputc(ch,fp2);while(1)ch=fgetc(fp1);if(feof(fp1)break;asc=(int)ch;if(asc=0;i-)Bini=asc%2;asc=asc/2;for(i=0;i=7;i

18、+) fputc(Bini+0,fp2);fclose(fp1);fclose(fp2);void DecompressFile(HuffmanTree HT,int k)/解壓函數(shù) FILE *fp1,*fp2;char DNameMAXNAME,FNameMAXNAME,CNameMAXNAME=0,ch;int r;printf(請(qǐng)鍵入需要解壓的文件名：（注意：文件中的字符權(quán)值需與上述相同?。?;gets(DName);printf(請(qǐng)輸入解壓后希望得到的文件名：);gets(FName); printf(解壓后的文件名為：);puts(FName); ChToCo(DName,CName);fp1=fopen(CName,rb);fp2=fopen(FName,wb);ch=fgetc(fp1);while(!feof(fp1)/到