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

2、）3）4）5）新建一個文件并壓縮。2、 概要設計1.串的抽象數據類型定義為：ADT String數據對象：D=ai|aiCharacterSet,i=1,2,.,n,n>=0數據關系：R1=<ai-1,ai>|ai-1,aiD,i=1,2,.,n基本操作：strcpy(String &S1,String S2)初始條件：串S2存在。操作結果：由串S2復制得串S1.strlen(SString S)初始條件：串S存在。操作結果：返回S的元素個數，稱為串的長度。/ADT String2. 二叉樹的抽象數據類型定義為：ADT BinaryTree數據對象D：是具有相同特性的

3、元素的集合。數據關系R：若D為空集，則稱為空二叉樹；   若D僅含一個數據元素，則R為空集，否則R = H, H是如下二元關系： 1）在D中存在唯一的稱為根的數據元素root，它在關系H下無前驅； 2） 若D  root  ，則存在D  root 的一個劃分Dl Dr ，DlDr =；3） 若Dl,則Dl 中存在惟一的數據元素x，<root, xl> &#

4、160;H，且存在Dl 上的關系Hl < H；若Dr  ,則Dr 中存在惟一的數據元素xr ，<root, xr>  H，且存在Dr 上的關系Hr < H； 4）（Dl， Hl、）是一棵符合本定義的二叉樹，稱為根root的左子樹，（Dr， Hr、）是一棵符合本定義的二叉樹，稱為根root的右子樹。基本操作P：InitBitree(&T)；操作結果：構造空二叉樹。 CreateBitree(&am

5、p;T)；初始條件：二叉樹存在。操作結果：按輸入格式構造二叉樹。  Value(T, e)；初始條件：二叉樹存在，e是T中某個結點。操作結果：返回結點e的值。 Assign(&T, &e, value)； 初始條件：二叉樹存在，e是T中某個結點。操作結果：結點e賦值為value 。 Parent(T, e)；初始條件：二叉樹存在，e是T中某個結點。操作結果：若e是T的非根結點，則返回它的雙親，否則返回“空”。LeftChild(T, e)；初始條件：二叉樹存在，e是T中

6、某個結點。操作結果：返回e的左孩子。若e無左孩子，則返回“空”。RightChild(T, e)；初始條件：二叉樹存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子，則返回“空”。 ADT BinaryTree3. 赫夫曼樹和赫夫曼編碼的存儲表示：typedef struct char data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/動態安排數組存儲赫夫曼樹 typedef char *HuffmanCode;/動態安排數組存儲赫夫曼編碼。 4.函數的調用關系圖：main()->C

7、ompressFile()->HuffmanCoding()->Select() ->WriteFile()->CoToCh() ->DeCompressFile()->ChToCo(CName); ->translation()3、 調試分析1. 文件中字符數目可能格外大，不能用一個整的數組來存，所以需要從文件中一個字符一個字符來讀取處理。2. 為解決文件中字符消滅的不確定性，用數組character256來記錄相應ASCII的字符消滅次數，統計完后，將消滅次數非零的字符存在數組v中，并將它們的權值存在數組w中。3. 在將赫夫曼編碼翻譯為字符中，tr

8、anslation（）中函數的變量ch，在運算中應當變它的對應的值，即為，傳參應為 char &ch，而不應為char ch。4.將哈夫曼八位一組轉為十進制時，01串中個數不肯定為8的倍數，先遍歷文件，統計01串中元素個數，將該個數除以8的余數拿出來，放入壓縮文件的第一位，在依次將等于余數個數的01字符直接放入壓縮文件，之后的 01串為8的整數倍。5. 讀取壓縮后的亂碼是，可能讀出負數，若讀出負數，讓這個負數加上256再轉化為2進制的01串。4、 測試結果1.如圖，4為余數。壓縮率：125%可見，當文件中元素個數小于8時，壓縮文件反而會增大。2.壓縮率：7/303.壓縮率：9/30。4

9、.原文件大小為：21.2KB壓縮文件大小為11.3KB壓縮率接近百分之五十。總和2、3、4可見，可見，相同大小的文件，其中元素分布越集中，壓縮率越大。5.五、附錄源程序文件清單：#define MAXWEIGHT 2147483647#define MAXASCII 255#define MAXNAME 100#include<stdio.h> #include<stdlib.h>#include<string.h>#include<memory.h>typedef struct char data;int weight;int parent,l

10、child,rchild;HTNode,*HuffmanTree;/動態安排數組存儲赫夫曼樹 typedef char *HuffmanCode;/動態安排數組存儲赫夫曼編碼。 void Select(HuffmanTree HT,int index,int &s1,int &s2)/從序號為1index的結點中選出兩個最小的且沒有雙親的結點。 int w1,w2,t,i;s1=0;s2=0;w1=MAXWEIGHT;w2=MAXWEIGHT;for(i=1;i<=index;i+)if(HTi.parent=0)if(HTi.weight<w1)s2=s1;w2=

11、w1;s1=i;w1=HTi.weight;else if(HTi.weight<w2)s2=i;w2=HTi.weight; int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *v,int *w,int n)/v存放需要編碼的n個字符，w存放對應的權值， /構造赫夫曼樹，并求出n個字符的赫夫曼編碼。 if(n=0)/沒有合法字符時 printf("沒有需要編碼的字符!");return -1; if(n=1)/只有一個合法字符時 HC=(HuffmanCode)malloc(n+1)*siz

12、eof(char*);HC1=(char*)malloc(3*sizeof(char);HC10=*v;HC11='0'HC12=0;HT=(HuffmanTree)malloc(2*sizeof(HTNode);HT1.parent=0;HT1.lchild=0;HT1.rchild=0;HT1.weight=*w;HT1.data=*v;return 0;int s1,s2,m,i;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HuffmanTree p;HT->weight=m;for(p=HT+1,i=1;i

13、<=n;i+,p+,w+,v+)p->weight=*w;p->lchild=0;p->rchild=0;p->parent=0;p->data=*v;for(;i<=m;i+,p+)p->weight=0;p->lchild=0;p->rchild=0;p->parent=0;for(i=n+1;i<=m;i+)/在HT1.i-1選擇parent為0而且weight最小的/兩個結點且weight最小的兩個結點，其序號分別/為s1和s2Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.pare

14、nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/-從葉子到根逆向求每個字符的霍夫曼編碼-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.parent) if(HTf.lchild=c)cd-start='0&#

15、39; 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)/若為葉子結點，則成功翻譯一個字符，將它輸入到解壓文件中 fputc(HTi

16、.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

17、,asc;/八個01一組放入Bin串;二進制對應的ASCII值 int i,j,num=0,r;printf("請輸入你期望得到的壓縮后的文件名:");gets(DName);fp1=fopen(CName,"rb");fp2=fopen(DName,"wb");while(!feof(fp1)/計算0，1的數量 ch=fgetc(fp1);num+;num-;rewind(fp1);r=num%8;/八個一組多余出來的01 fputc(r+'0',fp2);/將多出來的數量的值放在壓縮文件第一位 for(j=1;j&

18、lt;=r;j+)/后面r位原封不動的將01復制進來 ch=fgetc(fp1);fputc(ch,fp2);while(!feof(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("壓縮后的文件名為:"

19、);puts(DName);void WriteFile(HuffmanCode HC,char FName,int k,char v)/將被壓縮的文件內容寫入另一個文件 FILE *fp1,*fp2;char CNameMAXNAME=0,ch;strcpy(CName,"CP");strcpy(CName+2,FName);/哈夫曼編碼文件命名為"'CP'+原文件名"fp1=fopen(FName,"rb");fp2=fopen(CName,"wb");while(1)int i;ch=fget

20、c(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 &HT,HuffmanCode &HC,int &k)/讀取文件中的字符，構造哈夫曼曼樹，得到每個字符的哈夫曼編碼 FILE *fp;int flag;char ch,vMAXASCII+1,FNameMAXNAME;/v存放消滅的字符 int ch

21、aracterMAXASCII+1=0;/統計每種字符消滅的次數 int wMAXASCII+1;/w放字符的權值 printf("請鍵入要運行的操作編號：n1.壓縮已有的文件n2.建立新文件，輸入內容并進行壓縮n");scanf("%d",&flag);/選擇操作 getchar();if(flag=1)printf("請鍵入需要壓縮的文件名：");gets(FName); fp=fopen(FName,"r"); else if(flag=2)printf("請鍵入需要壓縮的文件名："

22、;);gets(FName);printf("請鍵入文件內容：n");fp=fopen(FName,"w");while(ch!='n')scanf("%c",&ch);fputc(ch,fp);fclose(fp);fp=fopen(FName,"r");else printf("警告：無此操作項！");return; while(1)/逐個讀取文件中的字符,數組character對應字符位置上+1int i;ch=fgetc(fp);if(feof(fp)break;

23、 characterch+;for(int i=0;i<=MAXASCII-1;i+) /若某字符在在文件中消滅，則把它放入v，并把權值計入相同序號的w if(characteri!=0) vk=i;wk+=characteri;printf("文件中消滅的字符及它們的權值:n");for(int i=0;i<=k-1;i+) printf("%c-%d;n",vi,wi);HuffmanCoding(HT,HC,v,w,k); fclose(fp);printf("上述字符對應的哈夫曼編碼：n"); for(int i=

24、1;i<=k;i+) puts(HCi);WriteFile(HC,FName,k,v);void ChToCo(char 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)asc+=256;for(i=7;i>=0;i-)Bi