当先锋百科网

首页 1 2 3 4 5 6 7

数据结构：哈夫曼树及哈夫曼编码

问题描述：

用哈夫曼编码进行通信时，可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对要传输的数据预先编码。试为这样的信息发送端写一个哈夫曼编码程序。

1.初始化：从终端输入字符集大小 n ，以及 n 个字符和 n 个权值，试构造一棵哈夫曼树，要求左子树的权值小于右子树的权值。

2.编码。若输入的权值分别是报文中不同字符出现的频率，利用已建好的哈夫曼树，对n个字符进行哈夫曼编码，每个编码的指针存放在一个一维数组中，并将编码输出。

设计要求：

首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。

主控菜单设计要求：

程序运行后，给出5个菜单项的内容和输入提示：

  1. 输入字符集大小
  2. 输入带编码字符及其权值
  3. 建立哈夫曼树HT
  4. 完成哈夫曼编码HC，并显示编码
  5. 退出

请选择菜单1--5：

功能要求：

完成各菜单的功能，并能正确显示编码内容

1.初始化：从终端输入字符集大小 n ，以及 n 个字符和 n 个权值，试构造一棵哈夫曼树，要求左子树的权值小于右子树的权值。

2.编码。若输入的权值分别是报文中不同字符出现的频率，利用已建好的哈夫曼树，对n个字符进行哈夫曼编码，每个编码的指针存放在一个一维数组中，并将编码输出。

实现要求：

  1. 哈夫曼树建立后，从叶子到根逆向求每一个字符的哈夫曼编码
  2.  设在通信中只可能出现的10种字符，其对应的概率如下表所示：试设计哈夫曼编码。

a

b

e

f

i

k

s

t

y

z

0.12

0.05

0.07

0.08

0.14

0.23

0.03

0.15

0.02

0.11

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[100];

//哈夫曼树的存储表示
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

HuffmanTree HT;
HuffmanCode HC;

//Select函数
void Select(HuffmanTree HT,int m,int *s1,int *s2)
{
	int i;
	int min1=1000;
	int min2=1000;
	for(i=1;i<=m;i++){
		if(HT[i].parent==0&&min1>HT[i].weight){
			min1=HT[i].weight;
			*s1=i;
		}
	}
	for(i=1;i<=m;i++){
		if(i!=(*s1)&&HT[i].parent==0){
			if(HT[i].weight<min2){
				min2=HT[i].weight;
				*s2=i;
			}
		}
	}
}
	


//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int n)
{
	int s1,s2;
	if(n<=1)
		return ;
	int m=2*n-1;
	HT=new HTNode[m+1];
	for(int i=1;i<=m;i++)
	{
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	printf("输入前n个单元中叶子结点的权值:\n");
	for(i=1;i<=n;i++)
	{
		scanf("%d",&HT[i].weight);
	}
	for(i=n+1;i<=m;i++)
	{
		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;
	}
}


//完成哈夫曼编码HC，并显示编码
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{
	char *cd;
	HC=new char*[n+1];
	cd=new char[n];
	cd[n-1]='\0';
	for(int i=1;i<=n;++i)
	{
		int start=n-1;
		int c=i;
		int f=HT[i].parent;
		while(f!=0)
		{
			--start;
			if(HT[f].lchild==c)
				cd[start]='0';
			else
				cd[start]='1';
			c=f;
			f=HT[f].parent;
		}
		HC[i]=new char[n-start];
		strcpy(HC[i],&cd[start]);
	}
	printf("输出叶子结点及其哈夫曼编码为:\n");
	for(i=1;i<=n;i++){
		printf("%c:",a[i]);
		printf("%s\n",HC[i]);
	}
	delete cd;
}


//主函数
int main()
{
	int n,m,i;
	int choice;
	printf("**********哈夫曼树及哈夫曼编码**********\n");
	printf("1.输入字符集大小\n");
	printf("2.输入带编码字符及其权值\n");
	printf("3.建立哈夫曼树HT\n");
	printf("4.完成哈夫曼编码HC，并显示编码\n");
	printf("5.退出\n");
	while(choice)
	{
		printf("请选择菜单1--5:\n");
		scanf("%d",&choice);
		if(choice>5||choice<=0)
		{
			printf("您输入的数据有误!\n");
			return 0;
		}
		while(choice<=5)
		{
			if(choice==1)
			{
				printf("请输入字符集大小:\n");
				scanf("%d",&n);
				break;
			}
			if(choice==2)
			{
				printf("输入带编码字符及其权值\n");
				printf("请输入%d个字符:\n",n);
				for(i=0;i<=n;i++){
					scanf("%c",&a[i]);
				}
				getchar();
				break;
			}
			if(choice==3)
			{
				printf("建立哈夫曼树HT:\n");
				CreateHuffmanTree(HT,n);
				break;
			}
			if(choice==4)
			{
				printf("完成哈夫曼编码HC，并显示编码:\n");
				getchar();
				CreateHuffmanCode(HT,HC,n);
				break;
			}
			if(choice==5)
			{
				printf("退出!\n");
				return 0;
			}
		}
	}
}

 

实验结果：eba8f27951c147f89d888ec5150a72c6.png