博客

我也是初识数据结构，本来这一个题目在本站上有许多的解决办法，但是似乎使用的方法就是链表居多，而且可能有点也有点难以理解。下面代码绝对适合像我这样的小白，但是有的问题还是没有解决，就是没怎么去考虑算法结构了，可能复杂度就有点不合人意，但是能跑起来不就是小白最大的心愿吗，代码如下：

#include<iostream>
#include<string>

using namespace std;

const int n = 26;		//定义编码字符个数
char ch[n];		//定义字符存储数组
int w[n];			//定义字符权重存储数组

//定义一个结构体，用作结点信息存储
struct ElemType {
	string code="";		//用来存储该字符的哈夫曼编码
	char data;		//用来存储叶子节点的字符
	int weight;		//假设权值为整数，用来存储叶子结点的权重
	int parent, lchild, rchild;		//用来存储父节点，以及左右孩子结点
	int index = -1;//用来存储原来结构体数组下标，以便于后面给i1，i2赋值
	int LR;	//用来唯一标记该结点是左孩子还是右孩子
};

void Select(ElemType huffTree[], int &i1, int &i2) {		//选择排序，以便于通过每个根节点的权重来获取两个权重最小的根节点下标志
	int count = 0;	//用来计数，方便后边给i1和i2赋值
	ElemType reserve[2 * n - 1];
	for (int i = 0; i < 2 * n - 1; i++) {		//将结构体数组的元素下标初始化
		huffTree[i].index = i;	//将结构体里面的index给初始化，防止排序过后顺序变化而导致获取的原来下标不是之前的数组小标
		reserve[i] = huffTree[i];//同时将reserve[i]用来暂时保存传入的哈夫曼数，以便于后边将这一个给赋值回来，
	}
	for (int i = 0; i < 2 * n - 1; i++) {		//使用冒泡排序对数组通过权重进行从小到大排序
		for (int j = 0; j < 2 * n - 1 - i; j++) {
			if (huffTree[j].weight > huffTree[j + 1].weight) {
				ElemType temp = huffTree[j + 1];
				huffTree[j + 1] = huffTree[j];
				huffTree[j] = temp;
			}
		}
	}
	for (int i = 0; i < 2 * n - 1; i++) {	//遍历huffTree数组，当排好了序的数组遍历到第一个结构体的parent=-1时候将其赋值给i1，之后小中断此循环，之后在进行相似操作，以获取i2
		if (count == 0 && huffTree[i].parent == -1) {		//定义count方便用来获取权重最小的和倒数第二小的结点
			i1 = huffTree[i].index;
			count = 1;
			continue;	//找到第一个之后暂时终止程序，以防两个最小的被赋值为同一个下标
		}
		if (count == 1 && huffTree[i].parent == -1) {
			i2 = huffTree[i].index;
			break;		//找到下标后就可以中断
		}
	}
	//排序过后将haffmanTree恢复原来顺序
	for (int i = 0; i < 2*n-1; i++) {
		huffTree[i] = reserve[i];
	}
}

void input(char ch[],int w[]) {
	cout << "请输入" << n << "个字符:" << endl;
	for (int i = 0; i < n; i++) {
		cin >> ch[i];
	}
	cout << "请输入每个字符对应的权重：" << endl;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}
	cout << endl;
}

void createHuffmanTree(ElemType huffTree[], int w[], char ch[]) {
	int i, k, i1, i2;//使用i1和i2用来存储权值权值最小的两个根节点
	cout << endl;
	for (i = 0; i < 2 * n - 1; i++) {	//刚开始所有结点设置为没有双亲和孩子，由于有n个叶子结点就有2*n-1个节点，所以创建创建2*n-1个结点用来存储
		huffTree[i].parent = -1;//指向-1表示没有指向任何一个结点
		huffTree[i].lchild = huffTree[i].rchild = -1;
		huffTree[i].weight = 0x7fffffff;	//权重赋初值为无穷大，以便于后边排序从而寻找i1和i2
		huffTree[i].data = '\0';//给所有的结构体的字符赋值为空字符
	}
	for (i = 0; i < n; i++) {	//储存叶子结点的权值和对应的字符
		huffTree[i].weight = w[i];
		huffTree[i].data = ch[i];
	}
	for (k = n; k < 2 * n - 1; k++) {		//进行n-1次合并,至于为什么是n-1次，这是由于每一次合并都会产生一个新的结点，而除了叶子结点外所有的结点（n-1个）全是合并而来，所以就要进行n-1次合并
		Select(huffTree, i1, i2);		//权值最小的根节点下标为i1和i2
		huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;	//新建立的结点权重就是两个子节点权重之和
		huffTree[i1].parent = huffTree[i2].parent = k;		//设置父索引是k
		huffTree[k].lchild = i1; huffTree[k].rchild = i2;	//设置左子索引是i1，右子索引是i2
		huffTree[i1].LR = 0; huffTree[i2].LR = 1;		//用来唯一的表示是左孩子还是右孩子
		cout << "第" << k - n + 1 << "次结点合并权值最小的两个根节点下标：";
		cout << i1 << "和" << i2 << endl;
	}
}

void huffTreeStruct(ElemType huffTree[]) {
	cout << "\n哈夫曼树结构：" << endl;
	cout << "下标   " << "权重   " << "父索引  " << "左子索引 " << "右子索引 " << "字符   " << endl;
	for (int i = 0; i < 2 * n - 1; i++) {
		cout << i << "\t" << huffTree[i].weight << "\t" << huffTree[i].parent << "\t" << huffTree[i].lchild << "\t" << huffTree[i].rchild << "\t  " << huffTree[i].data << endl;
	}
	cout << endl;
}

//根据权重来实现哈夫曼编码
void EnHuffmanCode(ElemType huffTree[]) {
	for (int i = 0; i < n; i++) {	//有n个叶子结点，就要进行n次编码，左子树编码为0，右子树编码为1的规则
		int j = i;		//利用j来存储i以便于后面不至于改变i的值
		while (huffTree[i].parent != -1) {		//循环至根节点停止
			if (huffTree[i].LR == 0) {	//如果该叶子结点的索引等于他父节点的左孩子的索引，也就是判断该结点是他父节点的左孩子，就给编码前面加上"0"
				huffTree[j].code = "0" + huffTree[j].code;		//如果是左孩子就在前面添加上"0"字符
				i = huffTree[i].parent;		//将i用父节点的下标代替
			}
			if (huffTree[i].LR == 1) {	//如果该叶子结点的索引等于他父节点的右孩子的索引，也就是判断该结点是他父节点的右孩子，就给编码前面加上"1"
				huffTree[j].code = "1" + huffTree[j].code;
				i = huffTree[i].parent;		//将i用父节点的下标代替
			}
		}
		i = j;	//将保存了i的j赋值给i
	}
}

void printCode(ElemType huffTree[]) {
	cout << "对输入字符的哈夫曼编码：" << endl;
	for (int i = 0; i < n; i++) {
		cout << huffTree[i].data<<"的编码是："<<huffTree[i].code << endl;
	}
}

int main() {
	input(ch,w);
	cout << "------------------结果------------------" << endl;
	ElemType huffTree[2 * n];
	createHuffmanTree(huffTree, w, ch);
	EnHuffmanCode(huffTree);
	huffTreeStruct(huffTree);
	printCode(huffTree);
	return 0;
}

问题在于，这一个不是一个可变的数组（只能通过改程序顶部那一个n的取值来解决了），还有就是这一个复杂度有点高，还有就是没有分文件写和有关类的定义.若有问题欢迎大佬指正