哈夫曼编码器（C）

2024-01-20 10:03:10

哈夫曼编码器

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言

利用哈夫曼树编制哈夫曼编码在数据通讯中有广泛的应用。利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。

一、项目设计

1.结构体构建

哈夫曼树的表示：
设计哈夫曼树的结构体(HTNode)，其中包含权重、左右孩子、父母和要编码的字符。用这结构体(HTNode)定义个哈夫曼数组(HuffmanTree[])。
typedefstruct{
int weight; //存放各个点的权值
intparent,LChild,RChild;//指向双亲，孩子结点的指针
char key;
}HTNode;
typedefHTNodeHuffmanTree[MAXLEN];

2、项目流程

哈夫曼编码器（C）

二、主要算法

1.对输入电文进行加密

代码如下（示例）：

void encoding(HuffmanTreeht,int n) {
	char r[1000];//用来存储输入的字符串
	int i, j;
	printf("\n\n请输入要编码的字符:");
	gets(r);
	printf("编译结果为:");
	for(j=0;r[j]!='\0';j++){
		for(i=1;i<=n;i++){
			if(r[j]==ht[i].key)
			CrtHuffmanCode( ht, i, j);
		}	
	} 
	printf("\n");
}

2.对输入的密码进行译码

代码如下（示例）：

void decoding(HuffmanTreeht,int n) {
	char r[100];
	inti,j,len;
	j=2*n-1; //初始节点从根节点开始
	printf("请输入要译码的字符串：");
	gets(r);
	len=strlen(r);
	printf("译码的结果是：");
	for(i=0;i<len;i++){
		if(r[i]=='0'){
			j=ht[j].LChild;
			if(ht[j].LChild==0){
				printf("%c",ht[j].key);
				j=2*n-1;
			}
		}
		else if(r[i]=='1'){
				j=ht[j].RChild;
				if(ht[j].RChild==0){
					printf("%c",ht[j].key);
					j=2*n-1;
			}
		}	
	} 
	printf("\n");
}

3、主要函数

void InitHuffmanTree(HuffmanTreeht,int n);//对结构体进行初始化 
void InputWeight(HuffmanTreeht,int n);//输入函数
void Select(HuffmanTreeht, int n, int *s1, int *s2;//选择两个parent为0，且weight最小的结点为s1,s2
void CrtHuffmanTree(HuffmanTreeht, int n);//构造哈夫曼树ht
void CrtHuffmanCode(HuffmanTreeht,inti,int j);  //递归求每个叶子节点对应的哈夫曼编码 
void PrintHuffmanCode(HuffmanTreeht,int n);//输出哈夫曼编码
void encoding(HuffmanTreeht,int n);//对用户输入的电文进行加密
void decoding(HuffmanTreeht,int n);//对输入的密码进行译码

三、运行与测试

1、主菜单

哈夫曼编码器（C）在主菜单输入设定字符个数之后，进行编码字符及权重的输入，如下图所示：
哈夫曼编码器（C）结果如下：
哈夫曼编码器（C）

2、测试

哈夫曼编码器（C）
哈夫曼编码器（C）

四、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXLEN 100
typedef struct{
	int weight; //存放各个点的权值
	int parent,LChild,RChild;//指向双亲，孩子结点的指针 
	char key;  
}HTNode;
typedef HTNode HuffmanTree[MAXLEN];

void InitHuffmanTree(HuffmanTree ht,int n)//对结构体进行初始化 
{
	int i;
	for(i=1;i<=2*n-1;i++)
	{
		ht[i].weight=0;
		ht[i].parent=0;
		ht[i].RChild=0;
		ht[i].LChild=0;
	}
	printf("\n");
}

void InputWeight(HuffmanTree ht,int n)//输入函数
{
	int w,i;//w表示权值
	char k;//k表示获取的字符 
	for(i=1;i<=n;i++){
		printf("请输入第%d个字符：",i);
		scanf("%c",&k);
		getchar();
		ht[i].key=k;
		printf("请输入第%d个字符的权值：",i);
		scanf("%d",&w);
		getchar();
		ht[i].weight=w;
		printf("\n");
	}
} 

//选择两个parent为0，且weight最小的结点为s1,s2
void Select(HuffmanTree ht, int n, int *s1, int *s2)
{
	int i,min;
	for(i=1;i<=n;i++){
		if(ht[i].parent==0){
			min=i;
			break;
		}
	} 
	for(i=1;i<=n;i++){
		if(ht[i].parent==0) {
			if(ht[i].weight<ht[min].weight){
				min=i;
			}
		} 
	} 
	*s1=min;
	for(i=1;i<=n;i++){
		if(ht[i].parent==0&&i!=(*s1)){
			min=i;
			break;
		}
	}
	for(i=1;i<=n;i++){
		if(ht[i].parent==0&&i!=(*s1)){
			if(ht[i].weight<ht[min].weight){
				min=i;
			}
		}
	}
	*s2=min;
} 

//构造哈夫曼树ht
void CrtHuffmanTree(HuffmanTree ht, int n)
{
	int m,i,s1,s2;
	m=2*n-1;
	InitHuffmanTree(ht,n);
	InputWeight(ht,n);
	printf("\n            -----------------------------------------------------\n");
	printf("            *************** 哈 夫 曼 树 结 构 为 ****************\n");
	printf("            -----------------------------------------------------\n");
	printf("            \t\t权重\t左孩子权值\t右孩子权值\t\n");
	for(i=n+1;i<=m;i++) //创建非叶子节点，建哈夫曼树 
	{//在ht[0]——ht[i]内选择两个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;
	 	printf("            \t\t%d\t    %d\t\t%d\t\n",ht[i].weight,ht[s1].weight,ht[s2].weight);
	}
	printf("            -----------------------------------------------------\n\n");
} 

//求每个叶子节点对应的哈夫曼编码 
void CrtHuffmanCode(HuffmanTree ht,int i,int j) {
	int a,b;
	a=i;
	b=j=ht[i].parent;
	if(ht[j].parent!=0){
		i=j;
		CrtHuffmanCode(ht, i, j);
	}
	if(ht[b].LChild==a){
		printf("0");
	}
	else{
		printf("1");
	}
}

void PrintHuffmanCode(HuffmanTree ht,int n)
{
	int i,j,a;
	printf("\n            -----------------------------------------------------\n");
	printf("            **************** 哈 夫 曼 编 码 为 ******************\n");
	printf("            -----------------------------------------------------\n");
	for(i=1;i<=n;i++){
		j=0;
		printf("\n    \t\t %c \t\t\t",ht[i].key);
		CrtHuffmanCode(ht,i, j);
		printf("\n");
	}
	printf("            -----------------------------------------------------\n\n");
 } 

void encoding(HuffmanTree ht,int n)//对用户输入的电文进行编码 
{
	char r[1000];//用来存储输入的字符串
	int i, j;
	printf("\n\n请输入要编码的字符:");
	gets(r);
	printf("编译结果为:");
	for(j=0;r[j]!='\0';j++)
	{
		for(i=1;i<=n;i++)
		{
			if(r[j]==ht[i].key)
			CrtHuffmanCode( ht, i, j);
		}	
	} 
	printf("\n");
} 

void  decoding(HuffmanTree ht,int n)//对输入的密码进行译码 
{
	char r[100];
	int i,j,len;
	j=2*n-1; //初始节点从根节点开始
	printf("请输入要译码的字符串：");
	gets(r);
	len=strlen(r);
	printf("译码的结果是：");
	for(i=0;i<len;i++)
	{
		if(r[i]=='0'){
			j=ht[j].LChild;
			if(ht[j].LChild==0){
				printf("%c",ht[j].key);
				j=2*n-1;
			}
		}
		else if(r[i]=='1'){
				j=ht[j].RChild;
				if(ht[j].RChild==0){
					printf("%c",ht[j].key);
					j=2*n-1;
			}
		}	
	} 
	printf("\n");
}

int main()
{
	HuffmanTree HT;
	int i,n;
	char flag;
	system("color 06");
	printf("\n            *****************************************************\n");
	printf("\n            *****************************************************\n");
	printf("\n            |---------------------------------------------------|\n");	
	printf("\n            *************** 哈 夫 曼 编 码 课 程 设 计 **********\n");
	printf("\n            *****************************************************\n\n");
	printf("\n            -----------------------------------------------------\n");	
	printf("            ******************* 创 建 哈 夫 曼 树 ***************\n");
    printf("            -----------------------------------------------------\n");
	printf("\n请输入字符个数n=：");
	scanf("%d",&n);
	getchar();
	CrtHuffmanTree (HT,n);
	PrintHuffmanCode(HT,n);
	printf("\n            -----------------------------------------------------\n");
	printf("\n            ****************** 编码 译码 退出 *******************\n");
	printf("\n            ******************    1  编码     *******************\n");
	printf("\n            ******************    2  译码     *******************\n");
	printf("\n            ******************    0  退出     *******************\n");
	printf("\n            -----------------------------------------------------\n\n");
	printf("请您输入选择：");
	flag=getchar();
	getchar();
	while(flag!='0'){
		if(flag=='1'){
			encoding(HT,n);
		}
		else if(flag=='2'){
			decoding(HT,n);
		}
		else{
			printf("您输入有误，请重新输入。\n ");
		}
		printf("\n            -----------------------------------------------------\n");
		printf("\n            ****************** 编码 译码 退出 *******************\n");
		printf("\n            ******************    1  编码     *******************\n");
		printf("\n            ******************    2  译码     *******************\n");
		printf("\n            ******************    0  退出     *******************\n");
		printf("\n            -----------------------------------------------------\n");
		printf("请您输入选择：");
		flag=getchar();
		getchar();
	}
	system("pause");
	return 0;
}

五、主要参考文献

[1]算法精解C语言描述
[2]数据结构（第2版）清华大学出版社严蔚敏编著 2007
[3]数据结构C语言版[M]清华大学出版社严蔚敏2007
[4] 数据结构课程设计 哈夫曼编码-豆丁建筑网
[5] C语言-哈夫曼编码实验报告-道客巴巴

上一篇：数字孪生绿色工业之盾构机三维可视化


下一篇：杜均「点火」