main.cpp

各类Huffman编码

#include <stdlib.h>
#include <time.h>
#include <search.h>

#include <iostream>
#include <exception>
using namespace std;

#include "huffman_base.h"
#include "huffman_a.h"
#include "huffman_b.h"
#include "huffman_c.h"
#include "huffman_d.h"
#include "huffman_e.h"
#include "huffman_f.h"
#include "huffman_g.h"
#include "huffman_h.h"

class tester
{
public:
	tester(int num) 
	{
		this->num = num;
		weights = new unsigned long[num];
		weights_sorted = new unsigned long[num];
		srand( (unsigned)time( NULL ) * (unsigned)clock() );

		// 随机产生权值序列。这里要对65536取模的原因是，Linux下rand()
		// 产生的随机数可能非常大，而这里的所有huffman算法都是在unsigned long
		// 类型中做权值的累加计算的。一旦累加出界，就会得到不可预料的效果。
		for(int i = 0; i < num; i++)
			weights[i] = weights_sorted[i] = rand() % 65536;

		// 强制加几个权值为0的元素，以测试算法对0权值处理的正确性
		// 目前的规则是，0权值元素均不参加编码，其码长为0
		if (num > 5) 
			weights[0] = weights[2] = weights_sorted[0] = weights_sorted[2] = 0;

		qsort(weights_sorted, num, sizeof(weights_sorted[0]), weight_compare);
	}

	virtual ~tester()
	{
		delete[] weights;
		delete[] weights_sorted;
	}

	void run(huffman_base* p_huffman, bool dump)
	{
		try
		{
			clock_t t1, t2;
			if (p_huffman->if_need_sorted())
			{				
				t1 = clock();
				p_huffman->generate_codes(num, weights_sorted);
				t2 = clock();
			}
			else
			{
				t1 = clock();
				p_huffman->generate_codes(num, weights);
				t2 = clock();
			}
			
			cout << endl << typeid(*p_huffman).name() << " 耗时: " 
				 << double(t2 - t1) / CLOCKS_PER_SEC << "秒" << endl;

			if (!p_huffman->verify())
			{
				cout << endl << typeid(*p_huffman).name() 
					<< " 生成的Huffman树不正确，算法可能存在缺陷" << endl;
				return;
			}

			if (dump)
			{
				cout << "------------------------------------------------------" << endl;
				cout << "序号\t权值\t码长\t编码" << endl;
				cout << "------------------------------------------------------" << endl;
				vector<int> code_lens = p_huffman->get_all_code_lens();
				vector<string> codes = p_huffman->get_all_code_strs();
				for(int i = 0; i < (int)codes.size(); i++)
				{
					cout << i+1 << "\t";
					if (p_huffman->if_need_sorted())
						cout << weights_sorted[i];
					else
						cout << weights[i];
					cout  << "\t" << code_lens[i] << "\t" << codes[i] << endl;
				}
			}
		}
		catch(exception* e)
		{
			cout << endl << typeid(*p_huffman).name() << " 执行时错误: " << e->what() << endl;
			delete e;
		}
	}
private:
	int num;
	unsigned long* weights;
	unsigned long* weights_sorted;
	
	static int weight_compare(const void* a, const void* b)
	{
		if (*((unsigned long*)a) > *((unsigned long*)b))
			return 1;
		else if (*((unsigned long*)a) < *((unsigned long*)b))
			return -1;
		else
			return 0;
	}
};

int main()
{	
	int n = 0; 
	while (n < 2) 
	{
		cout << "请输入Huffman算法测试使用的元素数目: "; 
		cin >> n;
	}
	bool dump = (n <= 10); tester t(n);

	huffman_a ha; huffman_b hb; huffman_c hc; 
	huffman_d hd; huffman_e he; huffman_f hf;
	huffman_g hg; huffman_h hh(15);
	
	t.run(&ha, dump); t.run(&hb, dump); t.run(&hc, dump); 
	t.run(&hd, dump); t.run(&he, dump); t.run(&hf, dump);
	t.run(&hg, dump); t.run(&hh, dump);

	return 0;
}