复件 哈夫曼编码.cpp

c++写的HuffmanTree。 有建立HuffmanTree并编码功能

#include <iostream>
#include "math.h"
#include "queue.h"
using namespace std;
typedef struct {                                           //存储节点定义
	unsigned int weight;               
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
void Select (HuffmanTree &ht, int n, int &s1, int &s2) 
{ 
	int i; 
	int k;  
	for(i = 1, k = 1; i <= n; i++)                      //从1循环到n
		{ 
			if(ht[i].parent != 0){k++; continue;}       //有双亲直接跳过
			if(i == k) s1 = i;                          //初始化 s1
			else 
				{ 
					if(ht[i].weight < ht[s1].weight)s1 = i;//比较权值，记录小的那个
				} 
		} 

	for(i = 1, k = 1; i <= n; i++) 
		{ 
			if(ht[i].parent != 0 || i == s1){k++;continue;}
			if(i == k)s2 = i;                           //初始化 s2 
			else 
				{if(ht[i].weight < ht[s2].weight)s2 = i;} 
		}
}
void Code(HuffmanTree HT, LinkQueue bcode[],int n,char a[])
{                                         
	for(int i=1;i<=n;i++)
	{
		int k=i ;                                          //记录第几个元素
		cout<<a[i-1]<<"    ";
		InitQueue (bcode[i-1]);                            //初始化列队
		while(HT[k].parent!=0)
		{
			int p;
			p=HT[k].parent;                                //找到双亲     
			if(HT[p].lchild==k)                            //进0
			{	EnQueue(bcode[i-1],0);cout<<"0";}
			else if(HT[p].rchild==k){ EnQueue(bcode[i-1],1);cout<<"1"; }  //进1
			else ;
			k=p;                                           //往上走 到最后一个
		}//while
		cout<<endl;
	}//for
}
int main()
{
	HuffmanTree HT;
    HuffmanTree p;                                         //辅助指针
	int n=0;                                               //统计字符个数
	int m=0;                                               //总的节点个数
	int w[10];                                             //存放权值
	char a[10];                                            //存放字符
	cout<<"输入字符以及它们的权值，#结束输入"<<endl;
	char b;int k;
	cin>>b;a[0]=b; 
	cin>>k; w[0]=k;   n=1;                                 //输入第一个字符与权值   
	for(int i=0;a[i]!='#';i++,n++)
	{
		cin>>b;if(b=='#')break;
		a[i+1]=b;
		cin>>k;if(k<=0)break;
		w[i+1]=k;
	}                                                      //存入了字符与权值，n记录了个数
	m=2*n-1;                                               //计算总节点                
	HT=new HTNode[m+1];                                    //开辟相应的空间
	p=HT+1;
	for(i=1;i<=n;++i)
	{
		p->weight=w[i-1];
		p->lchild=0;
		p->rchild=0;
		p->parent=0;
		p++;
	}                   
	for( ;i<=m;++i,++p)                                    //++p不能少
	{
		p->weight=0;
		p->lchild=0;
		p->rchild=0;
		p->parent=0;
	}
	for(i=n+1;i<=m;++i)                                    //建立HuffmanTree
	{  
		int s1=1,s2=1;
		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<<"HuffmanTree如下"<<endl<<endl;
	cout<<"     "<<"number"<<"     ";              
	for(int d=0;d<n;d++)                                 //显示字母
	{cout<<a[d]<<"   ";}
	cout<<endl<<"     "<<"weight"<<"     ";              
	for(d=1;d<m+1;d++)                                 //显示权值
	{cout<<HT[d].weight<<"   ";}
	cout<<endl<<"     "<<"parent"<<"     ";
	for(d=1;d<m+1;d++)                                     //显示双亲
	{cout<<HT[d].parent<<"   ";}
	cout<<endl<<"     "<<"lchild"<<"     ";
	for(d=1;d<m+1;d++)                                     //显示左孩子
	{cout<<HT[d].lchild<<"   ";}
	cout<<endl<<"     "<<"rchild"<<"     ";
	for(d=1;d<m+1;d++)                                     //显示右孩子
	{cout<<HT[d].rchild<<"   ";}
	cout<<endl<<endl<<endl;
	cout<<"编码"<<endl;
	LinkQueue bcode[10];                                   //列队存放编码
       Code(HT,bcode,n,a);
	cout<<endl<<endl<<endl;

	return 0;	
}