「哈夫曼文件压缩实验报告」.doc

数据结构实验报告三哈夫曼文件压缩实验题目：哈夫曼文件压缩实验目标：输入一个有10k单词的英文文档。输出压缩后的二进制文件，并计算压缩比。数据结构：栈和哈夫曼树。1. 定义栈（）typedef structchar *elem;int stacksize;int top;STACK;2. 定义哈夫曼树（）typedef structint weight;int left,right;int parent;HTNode;需要的操作有：1.初始化栈（Initstack）void Initstack(STACK *s)s-elem=(char *)malloc(sizeof(int)*1000);s-stacksize=1000;s-top=-1;2.压栈（push）void push(STACK *s,int e)s-elem+s-top=e;3.弹栈（pop）void pop(STACK *s,int *e)if(s-top!=-1)*e=s-elems-top-;4.构造哈夫曼树（Inithuffman）void Inithuffman(int wsetn,int k,HuffTree HT) /构造哈夫曼树int i,m;int s1,s2;m=k*2-1;for(i=0;iweight=(iparent=-1;HTi-left=HTi-right=-1;for(i=k;ileft=s1;HTi-right=s2;HTi-weight=HTs1-weight+HTs2-weight;HTs1-parent=HTs2-parent=i;其中用到另一个基本操作：找到哈夫曼树中最小和次小的结点（select）5.找到哈夫曼树中最小和次小的结点（select）void select(HuffTree HT255,int a,int i,int *p,int *q)int j=0,k=0,*HT1,temp;HT1=(int *)malloc(sizeof(int)*(i-1); /存放权值for(j=0;jparent=-1)HT1k=HTj-weight; /把没有parent的结点的权值放在HT1中k+;/printf(%4d%4d%4d%4d%4dn,HTj-parent,HTj-left,HTj-right,HTj-weight,HT1k-1);j=0;while(j2) /找到权值最小和第二小的结点for(k=j;kHT1k) temp=HT1k;HT1k=HT1j;HT1j=temp;j+;k=0;for(j=0;jparent=-1)if(HTj-weight=HT10&k1) /将最小的权值赋到*p中*p=j;k+;j+;for(j=0;jparent=-1)if(j!=*p)if(HTj-weight=HT11&kparent,HTi-left,HTi-right,HTi-weight);6.根据哈夫曼树得到各字符对应的哈夫曼编码（Huffman）void Huffman(HuffTree HT2*n-1,int k,char str20) int i,j,e,t1=0,t2=0;char c;STACK st;for(i=0;iright=-1&HTi-left=-1) /找一个叶子结点Initstack(&st);HTi-right=HTi-left=-2; j=i; /记录其下标while(HTj-parent!=-1) if(HTHTj-parent-right=j) /找到一个叶子结点，如果他是其parent结点的右结点，就将此边记为1push(&st,1); elsepush(&st,0); /在左边记为0j=HTj-parent; /循环操作直到到达根结点c=i;printf(t%c ,c); /打印此字符for(;st.top!=-1;)pop(&st,&e);printf(%c,e); /打印其二进制编码strt1t2=e; /将二进制编码存放在str中t2+;putchar(n);strt1t2=0; t2=0; t1+;算法设计：1.从文件中逐个读取字符，记录其出现次数以及文件总字符数，由此确定其频率高低。2.根据字符频率创建哈夫曼树，然后求出哈夫曼编码。3.将哈夫曼编码输出到另一个文件中，并统计字数，求出压缩率。源程序#include#include#include#define n 127typedef structint weight;int left,right;int parent;HTNode;/哈夫曼数组结构类型typedef HTNode *HuffTree;typedef structchar *elem;int stacksize;int top;STACK;/栈的结构类型void Initstack(STACK *s)s-elem=(char *)malloc(sizeof(int)*1000);s-stacksize=1000;s-top=-1;/初始化栈void push(STACK *s,int e)s-elem+s-top=e;/压栈void pop(STACK *s,int *e)if(s-top!=-1)*e=s-elems-top-;/弹栈void select(HuffTree HT255,int a,int i,int *p,int *q)/找到哈夫曼树中权值最小和次小的结点并返回指针int j=0,k=0,*HT1,temp;HT1=(int *)malloc(sizeof(int)*(i-1); /存放权值for(j=0;jparent=-1)HT1k=HTj-weight; /把没有parent的结点的权值放在HT1中k+;/printf(%4d%4d%4d%4d%4dn,HTj-parent,HTj-left,HTj-right,HTj-weight,HT1k-1);j=0;while(j2) /找到权值最小和第二小的结点for(k=j;kHT1k) temp=HT1k;HT1k=HT1j;HT1j=temp;j+;k=0;for(j=0;jparent=-1)if(HTj-weight=HT10&k1) /将最小的权值赋到*p中*p=j;k+;j+;for(j=0;jparent=-1)if(j!=*p)if(HTj-weight=HT11&kparent,HTi-left,HTi-right,HTi-weight);void Inithuffman(int wsetn,int k,HuffTree HT) /构造哈夫曼树int i,m;int s1,s2;m=k*2-1;for(i=0;iweight=(iparent=-1;HTi-left=HTi-right=-1;for(i=k;ileft=s1;HTi-right=s2;HTi-weight=HTs1-weight+HTs2-weight;HTs1-parent=HTs2-parent=i;void Huffman(HuffTree HT2*n-1,int k,char str20) /根据哈夫曼树得到各字符对应的哈夫曼编码int i,j,e,t1=0,t2=0;char c;STACK st;for(i=0;iright=-1&HTi-left=-1) /找一个叶子结点Initstack(&st);HTi-right=HTi-left=-2; j=i; /记录其下标while(HTj-parent!=-1) if(HTHTj-parent-right=j) /找到一个叶子结点，如果他是其parent结点的右结点，就将此边记为1push(&st,1); elsepush(&st,0); /在左边记为0j=HTj-parent; /循环操作直到到达根结点c=i;printf(t%c ,c); /打印此字符for(;st.top!=-1;)pop(&st,&e);printf(%c,e); /打印其二进制编码strt1t2=e; /将二进制编码存放在str中t2+;putchar(n);strt1t2=0; t2=0; t1+;void main()FILE *fp1,*fp2; HuffTree HT2*n-1;int i=0,sum1=0,sum2=0;float compress;char strn20;char elem,ch;int countn=0; if(fp1=fopen(text1.txt,r)=NULL)printf(cant open the file!n);exit(0);while(!feof(fp1) /读取文件中字符elem=fgetc(fp1);i=elem;counti+; /记录字符频率Inithuffman(count,n,HT);/for(i=0;iparent,HTi-left,HTi-right,HTi-weight);Huffman(HT,2*n-1,str); /对文章进行哈夫曼编码 if(fp1=fopen(text1.txt,r)=NULL)printf(cant open the file!n);exit(0); if(fp2=fopen(text2.txt,w)=NULL)printf(cant open the file!n);exit(0);while(!feof(fp1)ch=fgetc(fp1); /读取text1中字符i=ch;fputs(stri,fp2); /将此字符的二进制编码输出到text2中sum1+; if(fp2=fopen(text2.txt,r)=NULL)printf(cant open the file!n);exit(0);while(!feof(fp2)ch=fgetc(fp2);sum2+;compress=(float)sum2/(float)(sum1*8)