huffman.cpp

哈夫曼树又称最优二叉树

//coding by Zhoulin, all rights reserved//
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#include "Huffman.h"
#include "ExHuffman.h"


bool CMP2(struct ExOrder a, struct ExOrder b)
{
	if(a.dPoss > b.dPoss)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool CMP(struct Huffman_Code a, struct Huffman_Code b)
{
	if(a.iIdentify < b.iIdentify)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main()
{
	int iInstruct_Num, iNode_Num;
	int i;
	double dHuffman_Aver_Len, dExHuffman_Aver_Len, dIdeal_Length;

	printf("请输入指令条数：\n");
	scanf("%d", &iInstruct_Num);

	printf("请依次输入指令的使用频率：\n");
	iNode_Num = iInstruct_Num * 2; //2n - 1

	Alloc(iNode_Num);
	Init(iNode_Num);              //clear the array
	dIdeal_Length = 0;

	for(i = 1; i <= iInstruct_Num; i++)
	{
		scanf("%lf", &pHead[i].dFrequency);         //input section
		ExRank[i].dPoss = pHead[i].dFrequency;
		ExRank[i].iIdentify = i;
		pHead[i].iIdentify = i;
		dIdeal_Length += (pHead[i].dFrequency * (log(pHead[i].dFrequency) / log(2)));
	}

	dIdeal_Length = -dIdeal_Length;                       //ideal length
	Create_Huffman_Tree(iInstruct_Num, iNode_Num);     //get the huffman code
	Create_Huffman_Code(iInstruct_Num);
	sort(&ExRank[1], &ExRank[iInstruct_Num] + 1, CMP2);
	ExRank[0].dPoss = 0;
	for(i = 1; i <= iInstruct_Num; i++)
	{
		ExRank[i].dPoss += ExRank[i - 1].dPoss;       
	}
/************************************************************************/
	printf("以下为所输入的指令对应的哈夫曼编码:\n");
	for(i = 1; i <= iInstruct_Num; i++)
	{
		puts(Code[i].szCode);
	}

	dHuffman_Aver_Len = Caculate_HuffmanLen(iInstruct_Num);
	printf("\n");
	printf("哈夫曼编码的平均编码长度为：%.2lf\n理想编码长度为: %.2lf\n其信息冗余量为: %.2lf%%\n"
	, dHuffman_Aver_Len, dIdeal_Length, (dHuffman_Aver_Len - dIdeal_Length) / dHuffman_Aver_Len * 100);

	printf("\n请输入扩展哈夫曼的指令长度种类数：\n");
	Get_ExHuffman_Code(iInstruct_Num);

	
	Trans_ExCode(iInstruct_Num);

	sort(&Ex_Code[1], &Ex_Code[iInstruct_Num] + 1, CMP);
	printf("以下为所输入的指令对应的扩展哈夫曼编码:\n");
	
	for(i = 1; i <= iInstruct_Num; i++)
	{
		puts(Ex_Code[i].szCode);
	}
	printf("\n");

	dExHuffman_Aver_Len = Caculate_ExHuffmanLen(iInstruct_Num);
	printf("扩展哈夫曼编码的平均编码长度为：%.2lf\n理想编码长度为: %.2lf\n其信息冗余量为: %.2lf%%\n"
	, dExHuffman_Aver_Len, dIdeal_Length, (dExHuffman_Aver_Len - dIdeal_Length) / dExHuffman_Aver_Len * 100);

	return 0;
}