Huffman编码与译码

博主水平有限有问题请在评论区指出o(^▽^)┛

听前奏猜一猜歌名<(￣︶￣)↗头给你打破还来偷看

Huffman编码与译码

• 统计某电文中字符出现的频率（假设电文中只含有大小写英文字母，以及逗号和点号）；
• 把字符出现的频率作为权值建立哈夫曼树，进行哈夫曼编码，并输出每个字符的编码结果；
• 对电文进行哈夫曼编码。
• 把电文的哈夫曼编码进行译码，输出对应电文的内容。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <time.h>
#include <windows.h>
#include <conio.h>

using namespace std;

//哈夫曼树结构体定义 
typedef struct
{
    unsigned int weight; //结点的权值
    unsigned int parent; //结点的父节点下标
    unsigned int lchild; //左孩子结点下标
    unsigned int rchild; //右孩子结点下标
}HTNode, HuffmanTree[10000];

typedef pair<char, unsigned int> PCI; //单个字符及其对应的权值 
vector<PCI> v; //整个电文中各个字符及其权值
string inputString; //需要进行编码的电文 
string inputYima; //需要破译的二进制编码 
set<char> s; //辅助完成字符出现频率的算法 
map<char, string> m;//每个字符对应的编码
map<string, char> m2; //每个编码对应的字符串 

//函数声明 
void Select(HuffmanTree ht, int n, int* s1, int* s2);
void CountWeight(string u);
void CrtHuffmanTree(HuffmanTree ht, vector<PCI> w, int n);
void CrtHuffmanCode(HuffmanTree ht, int n, vector<PCI> v);
string bM(string u);
void huffdecode(HuffmanTree ht,string yima,int len,int n);
void menu();

//主函数 
int main()
{
	menu();
    return 0; 
}

/*在ht[1]至ht[n]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给s1，s2*/
void Select(HuffmanTree ht, int n, int* s1, int* s2) {
	int i, min1 = 0x3fff, min2 = 0x3fff;
	*s1 = 0;
	*s2 = 0;
	for (i = 1; i <= n; i++) {
		if (ht[i].parent == 0) {
			if (ht[i].weight < min1) {
				min2 = min1;
				*s2 = *s1;
				min1 = ht[i].weight;
				*s1 = i;
			}
			else if (ht[i].weight < min2) {
				min2 = ht[i].weight;
				*s2 = i;
			}
		}
	}
}

/*计算输入电文中各字符出现的次数*/
void CountWeight(string u) 
{
    int k = 1;
    for(int i = 0; i< u.length(); i ++)
    {
        if(!s.count(u[i]))
        {
            v.push_back({u[i], 1});
            s.insert(u[i]);
        }
        else
        {
            for(int j = 0; j < v.size(); j++)
                if(v[j].first == u[i]) v[j].second ++;
        }
    }
}

/*创建哈夫曼树算法*/
void CrtHuffmanTree(HuffmanTree ht, vector<PCI> w, int n) {

	for (int i = 1; i <= n; i++) 
    {		//1至n号单元存放叶子结点，初始化
		ht[i].weight = w[i-1].second;
		ht[i].parent = 0;
		ht[i].lchild = 0;
		ht[i].rchild = 0;
	}

	int m = 2 * n - 1;//所有结点总数

	for (int i = n + 1; i <= m; i++) {	//n+1至m号单元存放非叶结点，初始化
		ht[i].weight = 0;
		ht[i].parent = 0;
		ht[i].lchild = 0;
		ht[i].rchild = 0;
	}

	/*初始化完毕，开始创建非叶结点*/
	int s1, s2;
	for (int i = n + 1; i <= m; i++) {	//创建非叶结点，建哈夫曼树
		Select(ht, i - 1, &s1, &s2);//在ht[1]至ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给s1，s2
		ht[i].weight = ht[s1].weight + ht[s2].weight;
		ht[s1].parent = i;
		ht[s2].parent = i;
		ht[i].lchild = s1;
		ht[i].rchild = s2;
	}
}


/*从叶子结点到根，逆向求每个叶子结点(共n个)对应的哈夫曼编码*/
void CrtHuffmanCode(HuffmanTree ht, int n, vector<PCI> v) 
{
	char* cd;
	cd = (char*)malloc(n * sizeof(char));	//分配当前编码的工作空间
	for (int i = 1; i <= n; i++) {
        string coad;			//求n个叶子结点对应的哈夫曼编码
		int start = n - 1, c = i, p = ht[i].parent;
		while (p != 0) {
			--start;
			if (ht[p].lchild == c)			//左分支标0
				cd[start] = '0';
			else
				cd[start] = '1';			//右分支标1
			c = p;							//向上倒堆
			p = ht[p].parent;
		}
		for (int j = 0; j < n; j++) {
			if (cd[j] == '0' || cd[j] == '1') {
                coad += cd[j];
			}
		}
        m.insert({v[i-1].first, coad});
		m2.insert({coad, v[i-1].first});
		memset(cd, -1, n);
	}
}

/*对输入编码*/
string bM(string u) 
{
    string res;
    for(int i = 0; i < u.size(); i ++)
    {
        res += m[u[i]];
    }
    return res;
}

/*
哈夫曼树译码 
	ht:哈夫曼树
	len:要破译的二进制编码的长度 
	yima:要破译的编码
	n:叶子结点个数
*/
 void huffdecode(HuffmanTree ht,string yima,int len,int n)
{
	string ym; //破译出的电文 
	int x= 2 * n - 1;
	for(int i=0;i<len;i++)
	{
		if(yima[i]=='0') 
		{
			ym += '0';
			x=ht[x].lchild;
		}
		else if(yima[i]=='1') 
		{
			ym += '1';
			x=ht[x].rchild;
		}
	    if(ht[x].lchild==0)
		{
			cout << m2[ym];
			ym = "";
			x=2*n-1;
		}
	}
	cout << endl;
}

/*主菜单*/
void menu()
{
    while(1) {
        system("date/t");
        system("time/t");
        cout<<"            =============================================================================\n";
        cout<<"           ||                ★★★★★★★哈夫曼编码与译码★★★★★★★                ||\n";
        cout<<"           ||============================================================================||\n";
        cout<<"           ||============================================================================||\n";
        cout<<"           ||                    | 【1】--- 生成哈夫曼编码表   |                         ||\n";
        cout<<"           ||                    -------------------------------                         ||\n";
        cout<<"           ||                    | 【2】--- 生成电文哈夫曼编码 |                         ||\n";
        cout<<"           ||                    -------------------------------                         ||\n";
        cout<<"           ||                    | 【3】--- 进行哈夫曼译码     |                         ||\n";
        cout<<"           ||                    -------------------------------                         ||\n";
        cout<<"           ||                    | 【4】---    退出程序        |                         ||\n";
        cout<<"           ==============================================================================\n";
        cout<<"          请输入数字来选择对应的功能：";
        int num, idx = 0;
        if(!(cin>>num)) {
            system("CLS");
            cout<<"输入格式错误！请重新输入："<<endl;
               cin.clear();
               cin.sync();
               cin.ignore();
        } else {
            switch(num) {
                case 1:
                    system("CLS");
                    cout<<"请输入字符待译码的电文";
                    cin >> inputString; 
                    CountWeight(inputString);
                    HuffmanTree ht ;
    				CrtHuffmanTree(ht, v, v.size());
    				CrtHuffmanCode(ht, v.size(), v);
                    cout<<"生成哈夫曼编码表成功！下面是该编码表的输出："<<endl;
                    cout<<endl;
                    cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"编码"<<endl;
                    idx = 0;
                    for(auto e: v)
                    {
                    	cout << ++ idx << "\t" << e.first << "\t" << e.second << "\t"
						<< m[e.first] << endl; 
					}
                    getch();
                    system("CLS");
                    break;
                case 2:
                    system("CLS");
                    cout << "您输入的电文经编码后为:" << endl;
                    cout << bM(inputString) << endl;
                    getch();
                    system("CLS");
                    break;
                case 3:
                    system("CLS");
					cout << "请输入要破译的电文:" << endl;
					cin >> inputYima;
					huffdecode(ht, inputYima, inputYima.size(), m.size());
					idx = 0;
					cout << "-------------编码集--------------------" << endl;
					cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"编码"<<endl;
                    for(auto e: v)
                    {
                    	cout << ++ idx << "\t" << e.first << "\t" << e.second << "\t"
						<< m[e.first] << endl; 
					}
                    getch();
                    break;
                case 4:
                    cout<<"\n\n\n\n\n";
                    cout<<"\t\t*************************************************"<<endl;
                    cout<<"\t\t******                                     ******"<<endl;
                    cout<<"\t\t******     谢谢使用哈夫曼编码与译码程序    ******"<<endl;
                    cout<<"\t\t******                                     ******"<<endl;
                    cout<<"\t\t*************************************************"<<endl;
                    exit(0);
                default:
                    system("CLS");
                    cout<<"输入错误！没有此功能！请重新输入！"<<endl;
                    cout<<endl;
            }    
        }
    }
}
}