哈夫曼树实验报告

1、精选文档试验报告试验名称 Huffman编码 专业班级 计科三班 姓名 学号 指导老师 日期 2014.12.20 一、试验目的 娴熟把握二叉树应用（Huffman编码）的基本算法实现。二、试验内容l 1对输入的一串电文字符实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。实现功能如下：¨ Huffman树的建立¨ Huffman编码的生成编码文件的译码三、试验要求l 设计思路：数据结构：#define n 100/叶子结点数#define m 2*n-1/ Huffman树中结点总数typedef struct int weight;/权

2、值 int lchild , rchild , parent; /左右孩子及双亲指针HTNode; /树中结点类型typedef HTNode HuffmanTreem+1;/0号单元不用主要实现函数：n 统计字符串中字符的种类以及各类字符的个数的函数n 构造Huffman树的函数n Huffman编码的函数n 建立正文的编码文件的函数n 代码文件的译码函数n 主函数四、试验概要设计1)功能框图Huffman树的建立从叶子到根逆向求编码退出Huffman编码程序Huffman编码的生成编码文件的译码五. 使用说明1.运行环境：VC+ 6.0 2.首先选择主控菜单中的操作，即建表，然后进行其它操

3、作六试验截图七 试验体会1、构建哈夫曼树的关键在于找最小树；在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。2、由于学习的不足没有实现编码文件的译码，今后会加以改进 (）3、在逆向求编码的for循环里犯了一个规律错误导致求出来的3、4位编码串行，尝试了多钟数据输入才找到缘由所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。附源程序：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.

4、h>typedef struct char data; /结点字符 int weight; /结点权值 int parent,lchild,rchild; /父子结点 HTNode,* HuffmanTree;typedef char * *HuffmanCode;void Select(HuffmanTree HT, int m, int& s1, int& s2) int i; s1 = s2 = 1; for(i=1; i<=m; i+) if (HTi.parent=0) s1=i; break; for(i=i+1; i<=m; i+) if (HT

5、i.parent=0 && HTs1.weight>HTi.weight) s1=i; for(i=1; i<=m; i+) if(HTi.parent=0&&i!=s1) s2=i; break; for(i=i+1; i<=m; i+) if(HTi.parent=0 && HTi.weight<HTs2.weight && i!=s1) s2=i; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) /w存放

6、n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼树编码HCint f; int m,i,s1,s2;int c;HuffmanTree p;char *cd;if (n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i<=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;for( ;i<=m;+i,+p) (*p).parent=0;for(i=n+1;i<=m;

7、+i) /建立赫夫曼树 /在HT1.i-1选择parent为0且weight最小的两个节点，其序号分别为s1,s2.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*);/安排n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char); /安排求编码的工作区间cdn-1=&

8、#39;0' /编码结束符for(i=1;i<=n;+i) /逐个字符求赫夫曼树编码 int start; start=n-1; /编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'else cd-start='1'HCi=(char *)malloc(n-start)*sizeof(char); /为第i个字符编码安排空间strcpy(HCi,&cdstart); /从cd复制编码（串）到HCfree(cd); /释放空间void main()HuffmanTree HT;HuffmanCode HC;int *w,n,i; printf("请输入权值的个数(): ");scanf ("%d",&n);w=(int *)malloc(n*sizeof(int);printf("请依次输入%d个权值(整型):n"