哈夫曼编码

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
/**哈夫曼编码思想**/
typedef struct Node
{
	char typeChar;
	int rate;
	Node *leftChild;
	Node *rightChild;
}charNode;
//存放输入的字符种类
char *inputStr;
//存放字符节点的数组
Node nodes[200 + 199];
//总的节点数
int total;
//记录当前所处的深度
int depth;
//统计数量
int getNum(char *in, char c)
{
	int times = 0;
	for (int i = 0; i <= strlen(in); i++)
	{
		if (*(in + i) == c) times++;
	}
	return times;
}
//统计输入的字符种类(当时写的这方法不好，个人推荐使用hash存储的方式统计)
int getTypeChar(char *in)
{
	inputStr = (char *)malloc(sizeof(char)*200);
	memset(inputStr, '\0', sizeof(inputStr));
	int p = 0;
	bool isAdded;
	//cout<<strlen(in)<<endl;
	for (int i = 0; i<strlen(in); i++)
	{
		isAdded = false;
		if (p == 0)
		{
			*inputStr = *in;
			nodes[p].typeChar = *inputStr;
			nodes[p].rate = getNum(in, *in);
			nodes[p].leftChild = NULL;  //叶节点
			nodes[p].rightChild = NULL;  //叶节点
			p++;
			continue;
		}
		for (int j = 0; j<p; j++)
		{
			if (*(inputStr + j) == *(in + i))
			{
				isAdded = true;
				break;
			}
		}
		if (!isAdded)
		{
			inputStr[p] = *(in + i);
			nodes[p].typeChar = *(inputStr + p);
			nodes[p].rate = getNum(in, *(in + i));
			nodes[p].leftChild = NULL;  //叶节点
			nodes[p].rightChild = NULL;  //叶节点
			p++;
		}
	}
	return p;
}
//给排序函数使用的比较函数
bool compNode(const Node & node1, const Node & node2)
{
	if (node1.rate <= node2.rate)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//哈夫曼编码
void huf(int startIndex, int endIndex, int length)
{
	sort(nodes + startIndex, nodes + startIndex + length, compNode);
	nodes[endIndex + 1].rate = nodes[startIndex].rate + nodes[startIndex+1].rate;
	nodes[endIndex + 1].leftChild = &nodes[startIndex];
	nodes[endIndex + 1].rightChild = &nodes[startIndex+1];
	if (endIndex + 1 != total)
	{
		huf(startIndex + 2, endIndex + 1, length - 1);
	}
}
int depthFirst(charNode *);
//遍历哈夫曼树，计算出编编码长度
int getCodeLength(int lastIndex)
{
    charNode *root = &nodes[lastIndex];
	depth = -1;
	return depthFirst(root);
}
//递归遍历
int depthFirst(charNode *node)
{
    depth++;
	if (node->leftChild == NULL && node->rightChild == NULL)
	{
		return node->rate * depth;
	}
	else
	{
		int leftSize = depthFirst(node->leftChild);
		depth--;
		int rightSize = depthFirst(node->rightChild);
		depth--;
		return  leftSize + rightSize;
	}
}
int main()
{
	char *in;
	int num;  //不同字符的数量
	in = (char *)malloc(sizeof(char) * 1000);
	while(scanf("%s", in) != EOF)
    {
        num = getTypeChar(in);
        if(num == 1)
        {
            cout<<strlen(in)<<endl;
            continue;
        }
	    total = num * 2 - 1;
	    huf(0, num - 1, num);
	    cout<<getCodeLength(total-1)<<endl;
    }
	return 0;
}