一、实验目的
1.进一步掌握二叉树的存储结构和相应算法
2.掌握霍夫曼树树的创建和霍夫曼编码
二、实验环境
1.硬件:每个学生需配备计算机一台。操作系统:DOS 或 Windows
2.软件:DOS 或 Windows 操作系统+TurboC;
三、实验要求
1.要求采用二叉链表作为存贮结构,完成霍夫曼树的创建
2.输出对应数据的霍夫曼编码,并求出平均编码长度
四、实验内容
1.现在某电报公司假设有 10 字符进行编码,这 10 个字符的使用频率如下表所示,请创建霍
夫曼树。
2.编写函数求出 A~J 的霍夫曼编码。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* HuffmanCode;
typedef struct
{char data;
unsigned int weight ;
unsigned int parent, LChild,RChild ;
}HTNode, * HuffmanTree;
//选出权值最小的两个//
void select(HuffmanTree *ht,int n, int *s1, int *s2)
{int i;
int min1=0,min2=0;
(*ht)[min1].weight=(*ht)[min2].weight=101;
for(i=1;i<=n;i++)
{if((*ht)[i].weight < (*ht)[min1].weight&&(*ht)[i].parent == 0)
min1=i;}
for(i=1;i<=n;i++)
{if((*ht)[i].weight < (*ht)[min2].weight&&(*ht)[i].parent == 0&&min1!=i)
min2=i;}
*s1=min2;*s2=min1;
}
void CrtHuffmanTree(HuffmanTree *ht , int n)
{ /* w存放已知的n个权值,构造哈夫曼树ht */
int m,i,w;
int s1,s2;char c;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/