前言

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 

知其然 知其所以然！

设计一个哈夫曼编码器/译码器设计

【基本功能】

将哈夫曼编码应用于通讯系统时，在发送端对待发电文进行编码，在接收端对收到的电文进行译码。对于双工通讯，每端都需要一个编码器和译码器。请设计一个哈夫曼编码器/译码器。

【基本要求】

（1）初始化：键盘输入n个字符和n个权值，建立哈夫曼树；
（2）编码：利用已建立的huffman树生成huffman编码 ；
（3）译码：利用已建立的哈夫曼树对一段代码进行译码。

代码

#include<iostream>
#include <fstream>
#include<iomanip>
const int maxsize=1000;
using namespace std;
struct element
{
	double weight;
	int lchild,rchild,parent;
	int flag;
	char ch;
};
struct Code
{
	char bits[maxsize];
	char ch;
	int size;
 };
class Huff
{
	private:
		int n;
		element hufftree[maxsize];
		Code code[maxsize];
		char d[maxsize];
	public:
		void unit();
		void menu();
		void Huffmantree();
		void Select(int *i1,int *i2,int k);
		void Encode();
		void Decode(char *d);
		void Output();
};

void Huff::Output()
{
	cout<<setw(10)<<"字符"<<setw(15)<<"编码序列"<<endl; 
	for(int i=0;i<n;i++)
	{
		cout<<setw(10)<<hufftree[i].ch<<setw(15)<<code[i].bits<<endl;
	}
 } 
//查找权值最小的两个根结点
void Huff::Select(int *i1,int *i2,int k)
{
	double min1=99999998,min2=99999999;
	int i;
	for( i=0;i<k;i++)
	{
		if(hufftree[i].parent==-1)
		{
			if((hufftree[i].weight<min1)&&(hufftree[i].flag==0))
			{
				min1=hufftree[i].weight;
				*i1=i;
			}
		}
	}	
	hufftree[*i1].flag=1;
	for(i=0;i<k;i++)
	{
		if(hufftree[i].parent==-1)
		{
			if((hufftree[i].weight<min2)&&(hufftree[i].flag==0))
			{
				min2=hufftree[i].weight;
				*i2=i;
			}
		}
	}
	hufftree[*i2].flag=1;	
}

//构造哈夫曼树
void Huff::Huffmantree()
{
	int i,k;
	cout<<"                           ┏━━━━━━━━━━━━━━━━━━━━┓"<<endl; 
	cout<<"                           ┃     1.从键盘输入     ┃"<<endl;
	cout<<"                           ┃     2.从文件导入     ┃"<<endl;
	cout<<"                           ┗━━━━━━━━━━━━━━━━━━━━┛"<<endl;
	cout<<"\t\t\t\t请选择输入形式：";
A:	cin>>i;
	switch(i)
	{
		case 1:
			{
				cout<<"请输入编码字符个数：";
				cin>>n;
				for(i=0;i<n;i++)
				{
					cin.sync();
					cin.ignore();
					cout<<"请输入第"<<i+1<<"个字符：";
					hufftree[i].ch=cin.get();
					cout<<"请输入第"<<i+1<<"个字符的权值：";
					cin>>hufftree[i].weight;
				}
				break;
			}
		case 2:
			{
				fstream fi;
				fi.open("HuffTree.txt",ios::in);
				if(!fi)
				{
					cout<<"\t\t\t文件打开失败，请重新选择写入方式！";
					goto A;
				}
				else
				{ 
				    i=0;
					while(!fi.eof())
					{
						fi>>hufftree[i].ch>>hufftree[i].weight;
						i++;
					}
				}
				n=i;
				fi.close();
				break;
			}
		default:
		{
			cout<<"输入不合法！请重新输入！"<<endl;
			goto A;
		}	
	 } 
	 for(i=0;i<2*n-1;i++)
	{
		hufftree[i].parent=-1;
		hufftree[i].lchild=-1;
		hufftree[i].rchild=-1;
		hufftree[i].flag=0;
		hufftree[i].weight=0;
	}
	for(k=n;k<2*n-1;k++)
	{
		int i1,i2;
		Select(&i1,&i2,k);
		hufftree[i1].parent=k;
		hufftree[i2].parent=k;
		hufftree[k].weight=hufftree[i1].weight+hufftree[i2].weight;
		hufftree[k].lchild=i1;
		hufftree[k].rchild=i2;
	}
}

//为哈夫曼树编码
void Huff::Encode() 
{
	char CD[10000];
	int k,j;
	for(int i=0;i<n;i++)
	{
		j=i;
		k=0;
		while(hufftree[j].parent!=-1)
		{
			if(hufftree[hufftree[j].parent].lchild==j)
			CD[k]='0';
			else
			CD[k]='1';
			 k++;
			 j=hufftree[j].parent;
		}
		code[i].bits[k]='\0';
		k--;
		int m=k;
		code[i].size=m;
		for(int l=0;l<m+1;l++)
		{
			code[i].bits[l]=CD[k];
			k--;
		}
		code[i].ch=hufftree[i].ch;
	}
	Output();
	system("pause");
}

//为哈夫曼树译码
void Huff::Decode(char *d)
{ 
	int flag=0;
	char s[maxsize];
	cin.sync();
	cin.ignore();
	cin.getline(s,maxsize);
	char *r1=d;
	char *r2=s;
	while(*r2!='\0')
	{
	   int parent=2*n-1-1;
		while(hufftree[parent].lchild!=-1)
		{
			if(*r2=='\0')
			{
			 	flag=1;
				break;
			}
			else 
			{	
				if(*r2=='0')
				parent=hufftree[parent].lchild;
				else
				parent=hufftree[parent].rchild;
			}	
			r2++;
		}
		if(flag!=1)
		{
			*d=hufftree[parent].ch;
			d++;
		}
	}
	cout<<"翻译后的代码为："<<endl;
	while(r1!=d)
	{
		cout<<*r1;
		r1++;
	}	
	system("pause");
}
void Huff::menu()
{
    cout<<"\t\t\t\t";
	while(1)
	{
		system("cls");
		cout<<"〓〓〓〓〓〓〓〓〓〓  ☆     哈 夫 曼 编/译 码 器       ☆  〓〓〓〓〓〓〓〓〓〓"<<endl;
		cout<<"〓〓〓〓〓〓〓★★★★★★★★★★★★★★★★★★★★★★★★★★〓〓〓〓〓〓〓"<<endl;
		cout<<"〓〓〓〓〓〓〓〓〓★  ☆          1.编码                ☆  ★〓〓〓〓〓〓〓〓〓"<<endl;
		cout<<"〓〓〓〓〓〓〓〓〓★  ☆          2.译码                ☆  ★〓〓〓〓〓〓〓〓〓"<<endl;
		cout<<"〓〓〓〓〓〓〓〓〓★  ☆          3.打印编码            ☆  ★〓〓〓〓〓〓〓〓〓"<<endl;
		cout<<"〓〓〓〓〓〓〓〓〓★  ☆          4.打印哈夫曼树        ☆  ★〓〓〓〓〓〓〓〓〓"<<endl;
		cout<<"〓〓〓〓〓〓〓〓〓★  ☆          5.退出                ☆  ★〓〓〓〓〓〓〓〓〓"<<endl;
		cout<<"\t\t\t\t请输入您的选择：";
		int k;
		cin>>k; 
		switch(k)
		{
		    case 1:
				{
					Huffmantree();
					Encode();
					break;
				 } 
			 case 2:
			 	{
					 Decode(d);
					 break;	
				 }
			 case 3:
			 	{
			 		Output();
					break;
				 }
			 case 6:
			 	{
			 		exit(0);
			 		break;
				 }
				 	
			default:
				cout<<"输入有误，请输入1~3选择功能"<<endl;
				break;
		}
		cout<<"\t\t\t\t";
	}
}

int main()
{
	Huff myHuff;
	myHuff.menu();
	return 0;
}

HuffTree.text

E	1.25
T	9.41
A	8.19
O	7.26
I	7.10
N	7.06
R	6.85
S	6.36
H	4.57
D	3.91
C	3.83
L	3.77
M	3.34
P	2.89
U	2.58
F	2.26
G	1.71
W	1.59
Y	1.8
B	1.47
K	0.41
J	0.14
V	1.09
X	0.1
Q	0.09 
Z	0.08

实验结果

菜单

编码

• 键盘输入
• 文件导入

译码

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/125306578