huffman.cpp

这是数据结构基础算发知识的VC实现 如二叉树遍历、拓扑排序、哈夫曼树等

#include <iostream.h>
typedef struct tree{
      int lchild;
	  int rchild;
}HuffMan;
int Partition(int data[],int low,int high)       //寻找轴记录
{   int pivotkey;
    data[0]=data[low];
	pivotkey=data[low];
	while(low<high)
	{    while(low<high && data[high]>=pivotkey) --high;
	     data[low]=data[high];
		 while(low<high && data[low]<=pivotkey) ++low;
		 data[high]=data[low];   }
	data[low]=data[0];
	return low;
}
void Qsort(int data[],int low,int high)       //快速排序函数
{   int pivoloc;
	if(low<high){
                 pivoloc=Partition(data,low,high);
				 Qsort(data,low,pivoloc-1);
				 Qsort(data,pivoloc+1,high);    }
}
void select_code(int data[],int sa,int n,int &min1,int &min2)
{   int i=0,sign;
    data[n]=sa;
	for(i=n+1;data[i]!=-1;i++)
		if(data[i-1]>data[i]){
	                       sign=data[i-1];
						   data[i-1]=data[i];
						   data[i]=sign;    }
	min1=data[n];
	min2=data[n+1];
}
void main()             //赫夫曼树的建立、层序遍历输出
{   int data[30],i,j,n,min1,min2;
    HuffMan huff[30];
    data[0]=data[1]=data[2]=0;
	cout<<"\n\n\n";
	cout<<"请你输入哈夫曼树结点，最多30个结点(用-1做为结束): ";
    cout<<"\n\n";
    for(i=1;;i++){
		          cin>>data[i];
				  if(data[i]==-1)break;   }
	if(i<3) return;
	i=i-1;
	Qsort(data,1,i);
	min1=data[1];
    min2=data[2];
	n=2;
	for(j=i-1;j>=0;j--)
	{   
		huff[j].lchild=min1;
		huff[j].rchild=min2;
		data[0]=min2+min1;
		if(j>0)select_code(data,data[0],n,min1,min2);
		n++;    }
    huff[0].rchild=data[0];
	cout<<"\n\n";
    cout<<"该哈夫曼树的层序遍历序列为:\n"<<huff[0].rchild<<' ';
	for(j=1;j<i;j++)
		cout<<huff[j].lchild<<' '<<huff[j].rchild<<' ';
	cout<<'\n'<<endl;
}