哈夫曼编码实验

一、实验目的

通过哈夫曼编码算法的实现，巩固二叉树及哈夫曼树相关知识的理解掌握，训练学生运用所学知识，解决实际问题的能力。

二.实验内容

已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。
基本要求：
（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树；
（2）打印每一个字符对应的哈夫曼编码。
（3）对从终端读入的字符串进行编码，并显示编码结果。

三、实验方案设计

（对基本数据类型定义要有注释说明,解决问题的算法思想描述要完整，算法结构和程序功能模块之间的逻辑调用关系要清晰，关键算法要有相应的流程图，对算法的时间复杂度要进行分析）

1.算法思想：

（1）构造一个结构体存储节点的字符。

typedef struct
{int weight;int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT,int len,int &s1,int &s2)
{int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值for(i=1;i<=len;i++){if(HT[i].weight<min1&&HT[i].parent==0){min1=HT[i].weight;s1=i;}	}int temp=HT[s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择HT[s1].weight=0x3f3f3f3f;for(i=1;i<=len;i++){if(HT[i].weight<min2&&HT[i].parent==0){min2=HT[i].weight;s2=i;}}HT[s1].weight=temp;//恢复原来的值
}

（2）读取前n个节点的字符及权值，构造哈夫曼数

void CreatHuffmanTree(HuffmanTree &HT,int n)
{//构造哈夫曼树HTint m,s1,s2,i;if(n<=1) return;m=2*n-1;HT=new HTNode[m+1];  		//0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点   for(i=1;i<=m;++i)        	//将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0   { HT[i].parent=0;  HT[i].lchild=0;  HT[i].rchi

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！