数据结构赫夫曼树2.doc

一、 实验目的
1. 进一步掌握二叉树的存储结构和相应算法
2. 掌握霍夫曼树树的创建和霍夫曼编码
二、 实验环境
1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows
2. 软件：DOS或Windows操作系统+TurboC;
三、 实验要求
1. 要求采用二叉链表作为存贮结构，完成霍夫曼树的创建
2. 输出对应数据的霍夫曼编码，并求出平均编码长度
四、 实验内容
1. 现在某电报公司假设有10字符进行编码，这10个字符的使用频率如下表所示，请创建霍夫曼树。
A
B
C
D
E
F
G
H
I
J
19
18
16
14
12
8
6
4
2
1
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号单元未使用*/
printf("输入字符及权重:\n");
for(i=1;i<=n;i++)
{/*1-n号放叶子结点，初始化*/
fflush(stdin);
scanf("%c %d",&c,&w);
(*ht)[i].data = c;
(*ht)[i].weight = w;
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
}
for(i=n+1;i<=m;i++)
{
(*ht)[i].weight = 0;
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
} /*非叶子结点初始化*/
/*创建非叶子结点,建哈夫曼树*/
for(i=n+1;i<=m;i++)
{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/
select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
}
}
//中序输出哈夫曼树叶子节点//
void outputHuffman(HuffmanTree HT, int m)
{

if(m!=0)
{
outputHuffman(HT,HT[m].LChild);
if(!HT[m].LChild&&!HT[m].RChild)printf("%c\t", HT[m].data);
outputHuffman(HT,HT[m].RChild);
}
}
/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i;
unsigned int c;
int start;
int p;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/
cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/
cd[n-1]='\0'; /*从右向左逐位存放编码，首先存放编码结束符*/
for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/
{
start=n-1; /*初始化编码起始指针*/
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/
if( (*ht)[p].LChild == c)
cd[--start]='0'; /*左分支标0*/
else
cd[--start]='1'; /*右分支标1*/
hc[i]=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1;i<=n;i++)
printf("%c编码为%s\n",(*ht)[i].data,hc[i]);
}

// 主函数//
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int n;
int m;
printf("输入叶子节点的个数:" );
scanf("%d",&n);
CrtHuffmanTree(&HT,n);
m = 2*n-1;printf("中序输出哈夫曼树叶子节点：\n");
outputHuffman(HT,m);
printf("\n");
CrtHuffmanCode(&HT,&HC,n);

}

五、实验结果