huffman.cpp

图的算法程序.最小生成树,最短路径等问题

// huffman.cpp : Defines the entry point for the console application.
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
typedef struct {
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;



//-------------------------------------------------------------------------------
void Select (HuffmanTree HT,int i,int &s1,int &s2)
{//s1,s2为HT[i..i-1]中parent==0且weight最小的两个结点
	int count;
	int unsigned min1=MAX;
	for(count=1;count<=i;count++)
	{
		if(HT[count].weight<min1&&HT[count].parent==0)
		{
			min1=HT[count].weight;
		    s1=count;
		}
	}
	min1=MAX;
	for(count=1;count<=i;count++)
	{
		if(HT[count].weight<min1&&HT[count].parent==0&&count!=s1)
		{
			min1=HT[count].weight;
			s2=count;
		}
	}

}

//----------------------------------------------------------------------------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
	if(n<=1)    return;
	int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元不用
	int i;
    for(i=1;i<=n;++i)
	{
		HT[i].weight=w[i-1];
		HT[i].lchild=0;
		HT[i].parent=0;
	    HT[i].rchild=0;                       //初始化 
	}
	for(;i<=m;++i)
	{
	    HT[i].lchild=0;
		HT[i].parent=0;
		HT[i].rchild=0;
		HT[i].weight=0;
	}
    cout<<"Initlize"<<endl;
	cout<<"weight"<<'\t'<<"parent"<<'\t'<<"lchild"<<'\t'<<"rchild"<<endl;
    for(i=1;i<=m;i++)
		cout<<HT[i].weight<<'\t'<<HT[i].parent<<'\t'<<HT[i].lchild<<'\t'<<HT[i].rchild<<endl;
	cout<<endl;



//----------------------------建huffmantree---------------------------------------

    int s1=1,s2=2;
    for(i=n+1;i<=m;++i)
	{
		Select(HT,i-1,s1,s2);
	   
		HT[s1].parent=i;HT[s2].parent=i;
		HT[i].lchild=s1;HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	cout<<endl;
    for(i=1;i<=m;i++)
		cout<<HT[i].weight<<'\t'<<HT[i].parent<<'\t'<<HT[i].lchild<<'\t'<<HT[i].rchild<<endl;


	//--------------------------求huffmancode----------------从叶子到根-----------

	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	int fag=0;
    int start=1;
	for(i=1;i<=n;++i)
	{
		 
		unsigned int c;
		int f;
			HC[i]=(char *)malloc((n+1)*sizeof(char));
		for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		{
		
	
			if(HT[f].lchild==c)
			   HC[i][start++]='0';
			else
				HC[i][start++]='1';
			fag++;
			
	
		}
		HC[i][0]=fag;
	}
}

//--------------------------------------------------------------------
void print(HuffmanCode HC,int n)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=HC[i][0];j>=1;j--)
		{
			if(HC[i][j]=='0'||HC[i][j]=='1')
				cout<<HC[i][j];
		}
		cout<<endl;
	}
}


//-----------------------------------------------------------
void arrange(int *w,int n)
{
	int i,k,j,t;
	for(i=0;i<n;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
			if(w[j]<w[k]) k=j;
			t=w[k];w[k]=w[i];w[i]=t;
	}
}


//Display-----------------------------------------------------------
void Display(HTNode p,HuffmanTree HT,int &t)
{  
	cout<<p.weight<<endl;
	int i=p.lchild;
	int j=p.rchild;
	int k=t;
	if(i)
	{
		while(t)
		{
			cout<<'\t';
			t--;
		}
		t=k+1;
		Display(HT[i],HT,t);
	}
	t=k;
	if(j)
	{
		while(t)
		{
			cout<<'\t';
			t--;
		}
		t=k+1;
		Display(HT[j],HT,t);
	}
}



void main(void)
{
	
	int n;
	cout<<"intput n:n is the number of weights"<<endl;
	cin>>n;
	int *w=(int *)malloc(n*sizeof(int));

	cout<<"input the weight"<<endl;
	for(int i=0;i<n;i++)
		cin>>w[i];
	cout<<endl;
	HuffmanTree HT;
	HuffmanCode HC;
	HuffmanCoding(HT,HC,w,n);
	cout<<"Huffmancode"<<endl;
	print(HC,n);
	cout<<endl<<endl;
	
    HTNode p=HT[2*n-1];
	int t=1;
	cout<<"HuffmanTree"<<endl;
	Display(p,HT,t);
}