数据结构作业—哈夫曼编码器

知识点复习

• priority_queue小于运算符定义， <代表的是优先级的小于
  方式一：

struct cmp
{
	bool operator()(int a, int b)
	{
		return a < b;
	}
};

方式二：

struct node
{
    int val;
    node(int aa = 0) : val(aa){}
    bool operator< (const node& b) const//该行定义<就代表着b是优先级高的，也就是b先出队，下面的语句代表什么情况下b优先级高，假设值越大优先级越高
    {
        b.val > val;//这里最好把b写在左边，更加直观
    }
};

• 构造函数不能直接取地址, 就像常量字符串不能直接取地址一样，他们都是右值
  -- 左右值的区别：

//左值：
int i = 1;   // i 是左值
int *p = &i; // i 的地址是可辨认的
i = 2; // i 在内存中的值可以改变

class A;
A a; // 用户自定义类实例化的对象也是左值

//右值
int i = 2; // 2 是右值
int x = i + 2; // (i + 2) 是右值
int *p = &(i + 2);//错误，不能对右值取地址
i + 2 = 4; // 错误，不能对右值赋值

class A;
A a = A(); // A() 是右值

int sum(int a, int b) {return a + b;}
int i = sum(1, 2) // sum(1, 2) 是右值

• new、堆与栈
  -- https://blog.csdn.net/qq_35451572/article/details/83302054

• 代码：

#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <queue>
#include <vector>
#include <map>
#define print(i) cout << "debug: " << i << endl
using namespace std;
const int maxn = 1e4;
struct node
{
	int ch;
	node* l, * r;
	node(int a)
	{
		ch = a, l = r = NULL;
	}
	node(int a, node* b = NULL, node* c = NULL) : ch(a), l(b), r(c){}
};
struct cmp
{
	bool operator()(node* a, node* b)
	{
		return b->ch < a->ch;
	}
};
set<char> s;
priority_queue<node*, vector<node*>, cmp> q;
map<char, string> m;
node* root;

node* build()
{
	while (q.size() >= 2)
	{
		node* left = q.top(); q.pop();
		node* right = q.top(); q.pop();
		q.push(new node(left->ch + right->ch, left, right));
	}
	return q.top();
}

void dfs(node* now, string code)
{
	if (!now->l && !now->r)
	{
		m[now->ch] = code;
		return;
	}
	if (now->l) dfs(now->l, code + "0");
	if (now->r) dfs(now->r, code + "1");
}

void makecode(string text)
{
	string code;
	for (int i = 0; i < text.length(); i++) code += m[text[i]];
	ofstream outfile("code.txt");
	cout << "编码: " << code << endl;
	outfile << code << endl;
	outfile.close();
}

void decode()
{
	string code, text;
	node* now = root;

	ifstream infile("code.txt");
	getline(infile, code);
	for (int i = 0; i < code.length(); i++)
	{
		if (code[i] == '0') now = now->l;
		else now = now->r;
		if (now->l == NULL && now->r == NULL) 
			text += char(now->ch), now = root;
	}
	ofstream outfile("text.txt");
	cout << "解码:" << text << endl;
	outfile << text << endl;
	outfile.close();
}

int main()
{
	string text;
	string tmp;

	cout << "请输入一行要编码的字符串:";
	getline(cin, text);
	for (int i = 0; i < text.length(); i++) s.insert(text[i]);
	for (auto it = s.begin(); it != s.end(); it++)
	{
		q.push(new node(int(*it), NULL, NULL));
	}
	root = build();	
	dfs(root, tmp);
	makecode(text);
	decode();
}