哈夫曼文件压缩实验报告

1、数据结构实验报告三一哈夫曼文件压缩实验题目：哈夫曼文件压缩实验目标：输入一个有10k单词的英文文档。输出压缩后的二进制文件，并计算 压缩比。数据结构：栈和哈夫曼树。1 .定义栈。typedef structint stacksize；int top；STACK；2 .定义哈夫曼树（）typedef structint weight；int left,right；int parent；HTNode；需要的操作有:L初始化栈(Initstack)void Initstack(STACK *s) s->elem=(char *)malloc (sizeof(int)*1000)；s->s

2、tacksize=1000；s->top=-l； 2 .压栈(push)void push(STACK *s,int e) s->elem+s->top=e；3 .弹栈(pop)void pop (STACK *s,int *e) if(s->top!=-l)*e=s->elems->top-；4 .构造哈夫曼树(Inithuffman)构造/初始void Inithuffman(int wsetn,int k,HuffTree HT)哈夫曼树int i,m；int si,s2；m = k*2T；for(i=0；i<m；i+)化HT数组HTi = (H

3、uf fTree)ma1loc(s i zeof(HTNode)；HTi->weight=(i<k?wseti：0)；HTi->parent=-l ；HTi->left=HTi->right=-l；for (i=k； i<m； i+) /主循环，完成n-1次合并select(HT,k, i,&sl,&s2)；在HT1. i-1中选择parent为0且weight为最小的两个结点，其下 标分别为si和s2HTi->left=sl；HTi->right=s2；HTi->weight=HTsi->weight+HTs2-&g

4、t;weight；HTsl->parent=HTs2->parent=i；其中用到另一个基本操作：找到哈夫曼树中最小和次小的结点 (select)5 .找到哈夫曼树中最小和次小的结点(select)void select(HuffTree HT255,int a,int i,int *p,int *q)int j=O,k=O,*HTl,temp；HTl=(int *)malloc(sizeof (int)*(i-1)； 存放权值for(j=0；j<i；j+)if(HTj->parent=-l) HT1 k=HTj->weight；把没有 parent 的i/i文档

5、可自由编辑结点的权值放在HT1中k+；/printf(',%4d%4d%4d%4d%4dn',HTj->parent,HTj->left,HT j->right,HTj->we ight,HT1k-1)；)j=0；while(j<2) 找到权值最小和第二小的结点for (k=j ； k< (i- (i-a) *2) ； k+) if(HTlj>HTlk)temp=HTlk；HTlk=HTlj；HT1j=temp；j+；k=0；for(j=0；j<i；)i f(HTj->parent=-1)if (HTj->weight

6、=HT 1 0&&k< 1) 将最小的权值赋到*p中*P=j；k+；j+；)for(j=0；j<i；)if(HTj->parent=-l)将第if(HTj->weight=HTll&&k<2) 二小的权值赋到*q中*q=j;k+；j+；/printf(',%4d%4d%4d%4dnn,HTi->parent,HTi->left,HTi->r i gh t,HTi->we i ght)；)6.根据哈夫曼树得到各字符对应的哈夫曼编码(Huffman)i/i文档可自由编辑void Huffman(HuffT

7、ree HT2*n-l,int k,char str20) int itj,e,tl=0,t2=0；char c；STACK st；for(i=0；i<k；i+) if(HTi->right=-l&&HTi->left=-l)找一个叶子结点Initstack(&st)；HTi->right=HTi->left=-2； J=l;下标while(HTj->parent!=-l)if(HTHTj->parent->right=j)记录其找到一个叶子结点，如果他是其parent结点的右结点,就将此边记为1push(&st,

8、r1')；elsepush(&st,1 O')；为0j=HTj->parent；直到到达根结点在左边记循环操作c=i;打印printf (，ft%c ",c)；此字符for (； st. top!=-l；) pop (&st,&e)；printf ("%c'(,e)；打印其二进制编码strtl t2=e；将二进制编码存放在str中t2+；putchar('n')；strtlt2=，0f；t2=0；tl+；)算法设计：1 .从文件中逐个读取字符，记录其出现次数以及文件总字符数，由此 确定其频率高低。2 .根

9、据字符频率创建哈夫曼树，然后求出哈夫曼编码。3 .将哈夫曼编码输出到另一个文件中，并统计字数，求出压缩率。源程序#include<stdio.h>#include<malloc. h>#include<process.h>#define n 127typedef structint weight；int left,right；int parent； HTNode； 哈夫曼数组结构类型typedef HTNode *HuffTree；typedef structchar *elem；int stacksize；int top；STACK；栈的结构类型void

10、Initstack(STACK *s)s->elem=(char *)malloc (sizeof(int)*1000)；s->stacksize=1000；s->top=-l； 初始化栈void push(STACK *s,int e) s->elem+s-> top=e； 压栈 void pop (STACK *s,int *e)if(s->top!=-l)*e=s->elems->top-； 弹栈void select(HuffTree HT255,int a,int i,int *p,int *q)/ 找到哈夫曼树中权值最小和次小的结点并

11、返回指针int j=0,k=0,*HT1,temp；HTl=(int *)malloc(sizeof (int)*(i-l) ；/存放权值for(j=0；j<i；j+)if(HTj->parent=-l)HT1 k=HTj->weight；把没有 parent 的结点的权值放在HT1中k+；/printf(',%4d%4d%4d%4d%4dn',HTj->parent,HTj->left,HT j->right,HTj->weight,HTlk-l)；)j=0；while(j<2) 找到权值最小和第二小的结点for (k=j； k

12、< (i- (i-a) *2) ；k+) if(HTlj>HTlk)tenip=HTl k；HTlk=HTlj；HT1j=temp；j+；)k=0；for(j=0；j<i；)if(HTj->parent=-l)if (HTj->weight=HT 1 0&&k< 1) 将最小的权值赋到*p中*P=j；k+；j+；)for(j=0；j<i；)if(HTj->parent=-l)if(j!=*p)将第if(HTj->weight=HTll&&k<2) 二小的权值赋到*q中*q=j;k+；j+；/printf

13、(',%4d%4d%4d%4dn,',HTi->parent,HTi->left,HTi->ri ght, HT i ->wei ght)；)void Inithuffman(int wsetn, int k,HuffTree HT) /构造哈夫曼树int i,m；int sl,s2；m = k*2T；for(i=0；i<m；i+) /初始化HT数组HTi=(HuffTree)malloc(sizeof(HTNode)；HTi->weight=(i<k?wseti：0)；HTi->parent=l；HTi->left=HTi

14、->right=-l；主循for(i=k；i<m；i+) 环，完成nl次合并select(HT,k, i,&sl,&s2)；在HT1. iT中选择parent为0且weight为最小的两个结点，其下标分别为si和s2HTi->left=sl；HTi->right=s2；HTi->weight=HTsi->weight+HTs2->weight；HTsl->parent=HTs2->parent=i；)void Huffman(HuffTree HT2*n-l,int k,char str20) /根据哈夫曼树得到各字符对应的

15、哈夫曼编码int i,j,e,tl=0,t2=0；char c；STACK st；for(i=0；i<k；i+) if(HTi->right=-l&&HTi->left=-l) 找一个叶 子结点Initstack(&st)；HTi->right=HTi->left=-2；记录其 J=l;1/1文档可自由编辑下标while(HTj->parent!=-1)if (HTHTj ->parent ->r i ght=j)/ 找到一个叶子结点，如果他是其parent结点的右结点，就将此边记为1push(&st,11'

16、;);elsepush(&st, O,)； 为。j=HTj->parent； 直到到达根结点c=i；printf(nt%c ",c)； 此字符for (； st. top!=-l ；) pop (&st,&e)；printf("%c",e)；二进制编码strtlt2=e； 进制编码存放在str中在左边记循环操作打印打印其将二t2+；putchar('n')；strtlt2=，Of；t2=0；tl+；)void main() FILE *fpl,*fp2；HuffTree HT2*n-l；int i=0,suml=0,s

17、um2=0；float compress；char strn20；char elem,ch；int countn=0；if(fpl二fopen("text1. txt","r")=NULL) printf ("can't open the file!n'r)； exit (0)；while(!feof(fpl)读取文件中字符elem=fgetc(fpl)； i=elem；i/i文档可自由编辑记录字符频率Inithuffman(count,n,HT)；/for(i=0；i<253；i+)/printf(M%4d%4d%4d%

18、4dnw,HTi->parent,HTi->left,HTi->right,HTi->weight)；Huffman(HT, 2*n-l, str)；对文章进行哈夫曼编码if (fpl=fopen(,rtextl. txt", "r")=二NULL) printf ("can* t open the file! n'r)；exit (0)；if (fp2=fopen(,rtext2. txt' ",w")=NULL) printf ("can* t open the file! n&#

19、39;r)；exit (0)；)while(!feof(fpl) ch=fgetc(fpl)；读取 textl 中字符i=ch；fputs(stri,fp2);将此字符的二进制编码输出到text2中SUH11+； G:Visual C+文件数据给孙Debug、哈夫艮exe3回1B11011UO1MO111M0001UO00 1 fii 1011 am Bfii 11BR0B1 am0 10110110010011100001010 10110110010011100001011 10110110010011100001100 空 10110110010011100001101 10110110

20、010011100001110101101100100111000011111011O11U01OMI11UUU1UUD0mil fillBR1 0B1110Rfl1 RflRl11M111Wd 10110110010011100010010? 1011011001001110001001110110110010011100010100fl 101101100100111000101014 10110110010011100010110 > 101101100100111600101114 10118110010811160011000 ：IBllMllWWlMUlllMMMllMlil

21、 ! 1B11 011 0B1BB111R0011 010 51 10110110010011100011011§ 10110110010011100011100 10110110010011160011101 1 10110110010011100011110 G：Wisual C+ +文件做茯匍级Debug'胎大曼.exe1句回T IWllUllMWlUkJlllUWUlllll x i ri i hiirriii fiRi fiRRnn。10110110010011100100001 -10110110010011100100010 10110110010011100100011 * 10110110010011100100100 10110110010011100100101 10110110010011100100110 111? 101101111011“ 10110110U1(4M111O01OM111 tt 10110110010011100101000 $ 10110110010011100101001 X 10110110010011100101010 & 10110110010011100101011 ,