文档介绍:华北水利水电学院数据结构实验报告
2010~2011学年第二学期 08 级通信专业
实验三树的应用
实验目的:
,递归特点和动态性。
。
。
实验内容:
从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出每个字符及对应的哈夫曼编码。
实验要求:
C/ C++完成算法设计和程序设计并上机调试通过。
撰写实验报告,提供实验结果和数据。
写出算法设计小结和心得。
程序源代码:
#include<>
#include<>
#include<>
#include<>
#include<>
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 50
typedef struct node /*结点类型定义*/
{
char letter;
int weight;
int parent;
int lchild;
int rchild;
}HNodeType;
typedef struct /*编码类型定义*/
{
char letter;
int bit[MAXBIT];
int start;
}HCodeType;
typedef struct /*输入符号的类型*/
{
char s;
int num;
}lable;
void HuffmanTree(HNodeType HuffNode[],int n,lable a[])
{
int i,j,m1,m2,x1,x2,temp1;
char temp2;
for (i=0;i<2*n-1;i++) /*结点初始化*/
{
HuffNode[i].letter=0;
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for (i=0;i<n-1;i++)
for (j=i+1;j<n-1;j++)
if (a[j].num>a[i].num)
{
temp1=a[i].num;
a[i].num=a[j].num;
a[j].num=temp1;
temp2=a[i].s;
a[i].s=a[j].s;
a[j].s=temp2;
}
for (i=0;i<n;i++)
{
HuffNode[i].weight=a[i].num;
HuffNode[i].letter=a[i].s;
}
for (i=0;i<n-1;i++) /*构造huffman树*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for (j=0;j<n+i;j++)
{