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"


class tester
{
public:

	tester(int num) 
	{
		this->num = num;
		if( num==8)
		{
			weights = new unsigned long[num];
		weights_sorted = new unsigned long[num];
		weights[0] = weights_sorted[0] = 0*1000;
		weights[1] = weights_sorted[1] = 0.3*1000;
		weights[2] = weights_sorted[2] = 0*1000;
		weights[3] = weights_sorted[3] = 0.06*1000;
		weights[4] = weights_sorted[4] = 0.04*1000;
		weights[5] = weights_sorted[5] = 0*1000;
		weights[6] = weights_sorted[6] =0.2 *1000;
		weights[7] = weights_sorted[7] =0.4 *1000;

		/* weights = new float[num];
		weights_sorted = new float[num];
		weights[0] = weights_sorted[0] = 0;
		weights[1] = weights_sorted[1] = 0.3;
		weights[2] = weights_sorted[2] = 0;
		weights[3] = weights_sorted[3] = 0.06;
		weights[4] = weights_sorted[4] = 0.04;
		weights[5] = weights_sorted[5] = 0;
		weights[6] = weights_sorted[6] =0.2;
		weights[7] = weights_sorted[7] =0.4;
		*/

		}
		else
		{
	
		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() % 10000;
	
		}


		// 强制加几个权值为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 < (double)codes.size(); i++)
				{
					cout << i+1 << "\t";
					if (p_huffman->if_need_sorted())
						cout <<(double) weights_sorted[i];
					else
						cout << (int)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()

{	char sam;
	int n = 0; 
	 //clock_t t1,t2;
	//double duration;

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


tester t(n);

/*	t1=clock();
t2=clock();
duration = (double)(t2- t1) / CLOCKS_PER_SEC;
	//cout<<t.weights_out()<<"/t"<<t.weights_sorted_out()<<endl;
cout<<t1<<"\t"<<t2<<"\t"<<duration<<endl;

*/

huffman_a ha;

t.run(&ha, dump);

cin>>sam;

	cout<<flush;
	return 0;
}