贪婪算法huffman编码.cpp

算法设计分析的一些例子程序....凑字数..凑字数

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

typedef struct TNode
{
	int weight;
	int parent,lchild,rchild;
}TNode,*Huffmantree;

void swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}

class HuffmanTree
{
public:
	HuffmanTree(){}
	void select(int n,int &s1,int &s2)
	{
		if (n<2) return ;
	
		int i;
		s1=-1;s2=-1;
		int minA=INT_MAX-1;int minB=INT_MAX;
		for (i=1;i<=n;i++)
		{
			if (node[i].parent!=-1) continue;
			if (node[i].weight<minB) 
			{
				minB=node[i].weight;
				s2=i;
			}
			if (minA>minB) 
			{
				swap(minA,minB);
				int temp=s1;
				s1=s2;
				s2=temp;
			}
		}
	}


	void create(int *w,int n)
	{
		int i;	
		size=n;
		node=new TNode[2*n];
		for (i=1;i<=n;i++)
		{
			node[i].weight=w[i];
			node[i].parent=-1;
			node[i].lchild=-1;
			node[i].rchild=-1;
		}
		
		int s1,s2;
		for (i=n+1;i<=2*n-1;i++)
		{
			select(i-1,s1,s2);
			node[i].lchild=s1;//生成新节点
			node[i].rchild=s2;
			node[i].parent=-1;
			node[i].weight=node[s1].weight+node[s2].weight;
			node[s1].parent=i;//修改父节点指针
			node[s2].parent=i;
		}
		getCode();
	}

	void getCode()
	{
		int i;
		code=new string[size+1];
		for (i=1;i<=size;i++)
		{
			int t=i;

			while (node[t].parent!=-1)
			{
				int parent;
				parent=node[t].parent;
				if (node[parent].lchild==t) code[i]="0"+code[i];
				if (node[parent].rchild==t) code[i]="1"+code[i];
				t=parent;
			}
		}
	}
void display()
	{
		int i;
		for (i=1;i<=size;i++)
		{
			cout<<code[i]<<" ";
		}
	}
	int size;
	string *code;
	Huffmantree node;
};

int main()
{
	int w[]={0,45,13,12,16,9,5};
	HuffmanTree tree;
	tree.create(w,6);
	tree.display();
	return 0;
}