C++数据结构实验4.2 哈夫曼树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++数据结构实验4.2 哈夫曼树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1732字，纯文字阅读大概需要3分钟。

内容图文

提交评测的代码几乎无注释，原注释的花花绿绿的代码不见了 ，枯了+_+

/**2018数据结构实验4.2 哈夫曼**/
#include<iostream>
#include<string>
using namespace std;
struct Node
{
	char val;
	int weg;
	int d;
	Node *lc;
	Node *rc;
};

class haTree
{
private:
	Node * HList[10001];
	int sum;

public:
	haTree(int num);
	void sort(int num);
	Node* rebuild(Node *root, int num);
	void find(Node *root, char e, int &depth);
	int totalD();
};

int haTree::totalD()
{
	return sum;
}

haTree::haTree(int num)
{
	sum = 0;
	char value;
	int weight;

	for (int i = 0; i < num; i++)
	{
		cin >> value >> weight;
		HList[i] = new Node;
		HList[i]->d = 0;
		HList[i]->val = value;
		HList[i]->weg = weight;
		HList[i]->lc = NULL;
		HList[i]->rc = NULL;
	}
}

void haTree::sort(int num)
{
	if (num == 1)return;
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < num - i - 1; j++)
		{
			if (HList[j]->weg > HList[j + 1]->weg)
			{
				Node *temp = new Node;
				temp = HList[j];
				HList[j] = HList[j + 1];
				HList[j + 1] = temp;
			}
		}
	}
}

Node* haTree::rebuild(Node *root, int num)
{
one:
	if (num == 1)
	{
		return root;
	}
	else
	{
		sort(num);
		root = new Node;
		root->val = '#';
		root->weg = HList[0]->weg + HList[1]->weg;
		root->lc = HList[0];
		root->rc = HList[1];
		HList[0] = root;
		HList[1] = HList[num - 1];
		num--;
		goto one;
	}
}

void haTree::find(Node* root, char e, int &depth)
{
	if (root == NULL)
	{
		depth--;
		return;
	}
	else if (root->val == e)
	{
		root->d = depth;
		sum += depth;
		return;
	}
	find(root->lc, e, ++depth);
	find(root->rc, e, ++depth);
	depth--;
}

int main()
{
	int times;
	cin >> times;
	while (times--)
	{
		int num;
		cin >> num;
		haTree h(num);
		Node* r = new Node;
		r = h.rebuild(r, num);
		string Who;
		cin >> Who;
		for (int i = 0; i < int(Who.length()); i++)
		{
			int hh = 0;
			h.find(r, Who[i], hh);
		}
		cout << h.totalD() << endl;
	}
	return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的C++数据结构实验4.2 哈夫曼树全部内容，希望文章能够帮你解决C++数据结构实验4.2 哈夫曼树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端