第四次数据结构作业.docx

07092030 刘言明数据结构作业之 -Huffman二叉树的使用班 级: 070921姓 名: 刘言明学 号: 07092030报告名称: Huffman二叉树的使用上机时间: 2010/10/22报告时间: 2010/10/24摘要实验目的: 加深理解树及二叉树的逻辑结构、存储结构 掌握树及二叉树上基本运算的实现 学会使用Huffman编码对数据进行无损压缩的原理 理解Huffman二叉树的概念 一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题实验方法： 利用哈夫曼二叉树用关知识，和最优二叉树解法，综合考虑各种因素，定义结构体变量，和其它函数的综合运用来实现对输入的数字考虑权值用二叉树方法表示，并利用哈夫曼编码的知识，将其转化成为最优二叉树，求出编码表示数，输入字符将其转化为编码，并进行译码，并用函数输入最后结果。实验结果：1. 读入输入字符的总数2. 分别读入每个结点的值和权值3. 构造最优二叉树，输出哈夫曼编码4. 读入一串字符，将字符转化成编码形式5. 再通过编码进行译码，得到翻译后的字符并比对内容问题重述 读入个一个ASCII文件 统计文档中字符出现的频度，并根据频度对每个字符生成Huffman编码 打印原始数据、每个字符对应的Huffman编码以及原文档的Huffman编码 按Huffman树对编码后的数据进行解码 验证解码的结果 输出一些统计数据：总编码长度、编码效率等算法描述 首先，定义结构体变量，实现对哈夫曼二叉树的构造。 其次，构造其他函数，分别实现输入，输出，排序，转化等方法。 最后，通过函数和结构体的综合调用，实现题目的要求。函数说明一、 结构体定义说明1.动态分配数组储存哈夫曼树typedef struct int weight; char ch; int parent,lchild,rchild;HTNode,*HuffmanTree;2.哈夫曼编码结构体typedef structchar ch;char *chs;HuffmanCode;3.哈夫曼结构体typedef structchar ch;int weight;sw;typedef structHuffmanTree HT;HuffmanCode *HC;huf;二、 其它函数说明void select(HTNode * HT,int n,int *n1,int *n2)函数：选择在给定权值的两个结点中选择最小的权值的结点，其中*n1和*n2分别用来储存两个结点huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)函数：主要进行哈夫曼编码，其中w存放n个字符的权值（均0）,构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC。void transcode(HuffmanTree ht,char *chars2,char*chars3)函数：进行译码的工作，将输入的字符根据哈夫曼编码进行译码执行结果input the mount of char:6input the 1th char and weight:e 45input the 2th char and weight:f 34input the 3th char and weight:a 58input the 4th char and weight:c 32input the 5th char and weight:s 51input the 6th char and weight:k 18e -001f -101a -01c -000s -11k -100input chars to translate:efacskkscafe#the chars translate are:00110101000111001001100001101001the chars are: efacskkscafe问题&解决在对于哈夫曼二叉树的讨论中，最难的问题应该在于建立最优二叉树的和将输入的数和其权值转化并输出。问题的解决方法当然是来源于网络，网络确实给了我很多的帮助，让我可以在困扰之中突然看到了光明，顿感网络的力量。其中二叉树的建立还好，从书上看到了不少例子，而对于转化的问题，在网上搜寻，并寻问其他会的人，其他的人最后得到方法，并得以完成报告。附录程序:#include#include#include#include/*节点定义*/typedef structint weight; char ch; int parent,lchild,rchild;HTNode,*HuffmanTree; /*动态分配数组存贮哈夫曼树*/typedef structchar ch;char *chs;HuffmanCode;typedef structchar ch;int weight;sw;typedef struct /*哈夫曼树结构体*/HuffmanTree HT;HuffmanCode *HC;huf;/*从HTi-1选择parent为零且weight最小的两个节点，分别编号为n1,n2.*/void select(HTNode * HT,int n,int *n1,int *n2) int i=1; int n3; while(HTi.parent!=0) i+; *n1=i; i+; while(HTi.parent!=0) i+;*n2=i; if(HT*n1.weightHT*n2.weight) n3=*n1;*n1=*n2;*n2=n3; for(i+;i=n;i+) if(HTi.parent=0) if(HTi.weightHT*n1.weight)*n1=i;else if(HTi.weight0）,构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC.*/int m,i,s1,s2,start,c,f; HuffmanTree p; char *cd; if(n=1) return 0;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;iweight=w-weight;p-ch=w-ch;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-ch=;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;i+) /*建立哈夫曼树*/select(HT,i-1,&s1,&s2); HTs1.parent=i;HTs2.parent=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;return HUF;char *convert(char *chars,char *chars1,HuffmanCode *hc,int n) char *p=chars; int i; while(*p) i=1; while(hci.ch!=*p&i=n) i+; strcat(chars1,hci.chs); p+; printf(the chars translate are:%sn,chars1); return chars1;/*译码*/void transcode(HuffmanTree ht,char *chars2,char*chars3) int i=1,p; char *q=chars2; char *r=chars3; while(hti.parent!=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 input(int *n,sw *w)int i;printf(input the mount of char:); /*输入要编码的字符数量*/scanf(%d,n);for(i=1;ich,&w-weight); /*输入字符和权值*/ void main()HTNode HT;HuffmanCode HC,*hc;HuffmanTree ht;huf *HUF,huf2;int n;sw w40;char ch,inchar500,outchar1000; char *abc; char *p=inchar;input(&n,w);HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);printf(input chars to translate:);