第四次数据结构作业

1、07092030刘言明数据结构作业之Huffman二叉树的使用班级：070921姓名：刘言明学号：07092030报告名称：Huffman二叉树的使用上机时间：2010/10/22报告时间：2010/10/24摘要实验目的：?加深理解树及二叉树的逻辑结构、存储结构?掌握树及二叉树上基本运算的实现?学会使用Huffman编码对数据进行无损压缩的原理?理解Huffman二叉树的概念? 一步理解和熟练掌握课本中所学的各种数据结构， 学会如何把学到的知识用于解决实际问题实验方法:利用哈夫曼二叉树用关知识，和最优二叉树解法，综合考虑各种因素，定 义结构体变量，和其它函数的综合运用来实现对输入的数字考虑权

2、值用二叉树方 法表示，并利用哈夫曼编码的知识，将其转化成为最优二叉树，求出编码表示数, 输入字符将其转化为编码，并进行译码，并用函数输入最后结果。实验结果:1. 读入输入字符的总数2. 分别读入每个结点的值和权值3. 构造最优二叉树，输出哈夫曼编码4. 读入一串字符，将字符转化成编码形式5. 再通过编码进行译码，得到翻译后的字符并比对内容问题重述?读入个一个ASCII文件?统计文档中字符出现的频度，并根据频度对每个字符生成Huffman 编码?打印原始数据、每个字符对应的Huffman编码以及原文档的Huffman 编码? 按Huffman树对编码后的数据进行解码?验证解码的结果?输出一些统计

3、数据：总编码长度、编码效率等算法描述首先，定义结构体变量，实现对哈夫曼二叉树的构造。其次，构造其他函数，分别实现输入，输出，排序，转化等方法。最后，通过函数和结构体的综合调用，实现题目的要求。函数说明一、结构体定义说明1.动态分配数组储存哈夫曼树typedef structint weight;char ch;int pare nt,lchild,rchild;HTNode,*Huffma nTree;2哈夫曼编码结构体typedef structchar ch;char *chs;Huffma nCode;3哈夫曼结构体typedef structchar ch;int weight;sw;

4、typedef structHuffma nTree HT;Huffma nCode *HC;huf;二、其它函数说明void select(HTNode * HT,int n,int *n 1,int *n2)函数：选择在给定权值的两个结点中选择最小的权值的结点，其中*n1和*n2分别用来储存两个结点huf * Huffma nCodi ng(Huffma nTree HT,Huffma nCode *HC,sw *w,i nt n ,huf *HUF)函数：主要进行哈夫曼编码，其中 w存放n个字符的权值(均0),构造哈夫曼树 HT,并求出n个字符的哈夫曼编码HC。void tran sco

5、de(Huffma nTree ht,char *chars2,char*chars3) 函数：进行译码的工作，将输入的字符根据哈夫曼编码进行译码执行结果in put the mount of char:6in put the 1th char and weight:e 45in put the 2th char and weight:f 34in put the 3th char and weight:a 58in put the 4th char and weight:c 32in put the 5th char and weights 51in put the 6th char and

6、 weight:k 18 e -001f -101a 01c -000s -11k -100in put chars to tran slate:efacskkscafe#the chars tran slate are:00110101000111001001100001101001 the chars are: efacskkscafe问题&解决在对于哈夫曼二叉树的讨论中，最难的问题应该在于建立最优二叉树的和将 输入的数和其权值转化并输出。问题的解决方法当然是来源于网络，网络确实给了我很多的帮助，让我可以在困扰之中突然看到了光明，顿感网络的力量。其中二叉树的建立还好，从书上 看到了不少例子

7、，而对于转化的问题，在网上搜寻，并寻问其他会的人，其他的 人最后得到方法，并得以完成报告。附录程序：#i nclude#i nclude#i nclude #i nclude/*节点定义*/typedef structint weight;char ch;int pare nt,lchild,rchild;HTNode,*Huffma nTree;/*动态分配数组存贮哈夫曼树*/typedef structchar ch;char *chs;Huffma nCode;typedef structchar ch;int weight;sw;typedef struct/*哈夫曼树结构体*/Huf

8、fma nTree HT;Huffma nCode *HC;huf;/*从HTi-1选择pare nt为零且weight最小的两个节点，分别编号为 n 1, n2.*/ void select(HTNode * HT,int n,int *n1,int *n2)int i=1;int n3;while(HTi.pare nt!=0)i+;*n 1=i;i+;while(HTi.pare nt!=0)i+;*n 2=i;if(HT* n1.weightHT* n2.weight)n3=*n1;=*n2;*n 2=n3;for(i+;i=n ;i+)if(HTi.pare nt=0)if(HTi.

9、weightHT* n1.weight)*n 1=i;else if(HTi.weight0),构造哈夫曼树HT,并求出n个字符的哈夫曼编 码 HC.*/int m,i,s1,s2,start,c,f;Huffma nTree p;char *cd;if(n=1) return 0;m=2* n-1;HT=(Huffma nTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;iweight=w-weight; p-ch=w-ch; p-pare nt=0; p-lchild=0; p-rchild=0;for(;iweight=0;p-ch=A;p-p

10、are nt=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;i+)/*建立哈夫曼树 */select(HT,i-1,&s1,&s2);HTs1.pare nt=i;HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode *)malloc(n+1)*sizeof(char);/* 为哈夫曼编码审请空间 */cd=(char *)malloc( n*sizeof(char);cdn-1=0;for(i=1;iHT=HT;HUF-HC=HC

11、;return HUF;char *conv ert(char *chars,char *chars1,Huffma nCode *hc,i nt n)char *p=chars;int i;while(*p)i=1;while(hci.ch!=*p&i=n)i+；strcat(chars1,hci.chs); p+；prin tf(the chars tran slate are:%sn,chars1); retur n chars1;/*译码*/void tran scode(Huffma nTree ht,char *chars2,char*chars3)int i=1,p;char *

12、q=chars2;char *r=chars3;while(hti.pare nt!=0)i+;p=i;while(*q)while(htp.lchild!=0 & *q)if(*q=0)p=htp.lchild;else p=htp.rchild;q+;if(htp.lchild=0)*r=htp.ch;r+;p=i;*r=0;printf(the chars are:);/*打印出译码后的字符*/puts(chars3);void in put(i nt *n,sw *w)int i;printf(input the mount of char:);/* 输入要编码的字符数量 */sca nf(%d, n);for(i=1;ich,&w-weight);/*输入字符和权值 */void mai n()HTNode HT;Huffma nCode HC,*hc;Huffma nTree ht;huf *HUF,huf2;int n;sw w40;char ch, in char500,outchar1000;char *abc;char *p=in char;in put(&n, w);HUF=Huffma nCodi ng(&HT,&HC,w, n,&huf2);printf(input chars to translate:);