hufftree.h

数据结构的一个作业

#include<iostream>

/***************************************
*                  蔡敏
***************************************/

using namespace std;

HaffNode* hufftree(char_record* w,int n) {
	int i,j;
	HaffNode * ht = new HaffNode[2*n-1];
	unsigned long m1,m2;
	unsigned int  x1,x2;

	for(i=0;i<2*n-1;i++) {
		if(i<n) {
			ht[i].weight     = w[i].weight;
			ht[i].ascii_code = w[i].ascii_code;
		}
		else {
			ht[i].weight = 0;
		}
		ht[i].parent =  0;
		ht[i].lchild = -1;
		ht[i].rchild = -1;
	};

	for(i=0;i<n-1;i++) {
		// 两个最小权值
		m1 = 4294967295;
		m2 = 4294967295;
		// 两个最小的权值的索引
		x1 = 0;
		x2 = 0;
		// 找出两个权值最小的节点
		for(j=0;j<n+i;j++) {
			//
			if(ht[j].weight < m1 && ht[j].parent == 0) {
				m2 = m1;//最小保存到次小 
				x2 = x1;
				m1 = ht[j].weight;
				x1 = j;
			}
			else {
				if(ht[j].weight < m2 && ht[j].parent == 0) {
					m2 = ht[j].weight;
					x2 = j;
				}
			}
		}
		ht[x1].parent  = n + i;
		ht[x2].parent  = n + i;
		ht[n+i].weight = ht[x1].weight + ht[x2].weight;
		ht[n+i].lchild = x1;
		ht[n+i].rchild = x2;
	};
	return ht;
}