哈夫曼编码和译玛源程序

#include<iostream.h>
#include<string.h>
#include<iomanip.h>
struct huffnode
{
    char data;
	signed long weight;
	signed long parent;
	signed long lchild;
	signed long rchild;
};
huffnode*ht,*p;

signed int s1,s2,t;
char**hc;
char *ch;
static int n;
void selete(huffnode*hc,int k,int*s1,int*s2); //选择两个最小权值
void welcome(void)              //欢迎界面
{
cout<<"    ***********哈夫曼编码/译码系统***********  "<<endl<<endl;
cout<<"                  设计者---- 逐风"  <<endl<<endl;
}
char menu()                    //菜单
{
	cout<<"********************************************************************"<<endl;
	cout<<"** a: 初始化 b: 编码 c: 译码 d: 印代码文件  e: 印哈夫曼树 f: 退出 **"<<endl;
	cout<<"********************************************************************"<<endl;
	
	cout<<endl<<"请选择一个代码字母：  ";
	return 0;
}


void Init()                             //初始化函数
{
	int m=0;
	int*w;
    char*a;
	cout<<"请输入数据个数: ";
	cin>>n;                            //输入数据个数
	w=new int[n+1];                      //存放权值
	a=new char[n+1];                    //存放字符
	for(int i=1;i<=n;i++)          //建立哈夫曼数
	{
		cout<<"请输入第"<<i<<"个字符: ";
		cin>>a[i];
        cout<<"请输入 "<<a[i]<<" 的权值: ";
		cin>>w[i];
	}
	m=2*n-1;                          
	if((ht=new huffnode[m+1])==NULL)
	{
		cout<<"内存分配失败，停止运行.\n";
	}
	for(i=1,p=ht,++p;i<=n;++i,++p)
	{
		p->data=a[i];
	    p->weight=w[i];
		p->parent=0;
		p->lchild=0;
	    p->rchild=0;
	}
	for(i=n;i<=m;++i,++p)
	{
		p->data=NULL;
		p->weight=0;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}
	for(i=n+1;i<=m;++i)
	{
		selete(ht,i-1,&s1,&s2);    //选择weight最小的两个结点
		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;
	}	char*cd;
	if((hc=new char*[n+1])==NULL)
	{
		cout<<"内存分配失败，停止运行.\n";	}
	if((cd=new char[n])==NULL)
	{
		cout<<"内存分配失败，停止运行.\n";
	}
	cd[n-1]='\0';     //编码结束符
	for(i=1;i<=n;++i)   //逐个字符求哈夫曼编码
	{
		int start=n-1;     //编码结束符位置    
		for(long c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //cong 从叶子到根逆向求编码
		{
			if(ht[f].lchild==c)
				cd[--start]='0';
			else cd[--start]='1';
		}
		if((hc[i]=new char[n-start])==NULL)
	{
		cout<<"内存分配失败，停止运行.\n";
	}
		
	    strcpy(hc[i],&cd[start]);    //从cd复制编码串到hc
	}
	delete[]cd;
	cout<<endl;
	cout<<"初始化完毕!"<<endl<<endl;
}
void  print()                       //打印文件代码
{

	int i;
	if(ht==NULL){
		cout<<"没有初始化!!!"<<endl<<endl;
	}
	else{
		cout<<"编码文件\n"<<endl;
	for(i=1;i<=n;++i)
	{
		cout<<setw(30)<<i<<setw(10)<<ht[i].data<<setw(10)<<hc[i]<<endl<<endl<<endl;
	}
	return;
}
}

void selete(huffnode*hc,int k,int*s1,int*s2)     //寻找两个小权值
{
	    signed long m1=1000,m2=1000;
		for(int j=1;j<=k;j++)
		{
			if(hc[j].weight<m1&&hc[j].parent==0)
			{
				m2=m1;
				*s2=*s1;
				m1=hc[j].weight;
				*s1=j;
			}
			else if(hc[j].weight<m2&&hc[j].parent==0)
			{
				m2=hc[j].weight;
				*s2=j;
			}
		}
}

void Encode()                        //编码
{
	if(ht==NULL)                      //如果没有初始化则，返回
	{
	cout<<endl;
	cout<<setw(46)<<"没有初始化!!!!"<<endl<<endl;
		return;
	}
	else{

		int i=1,j=0;	
          char  ch[128];                //定义字符长度
	
			  
          cout<<"请输入字符: ";
		  
		  cin>>ch;
		  cout<<endl;
		  cout<<setw(36)<<"字符串 "<<ch<<" 的编码"<<endl<<endl;
		  
		  do{
			  for(i=1;ch[j]!=ht[i].data;i++);//寻找相同的字符
			  cout<<hc[i]<<" ";
		  j++;
		  }while(ch[j]!='\0');            //输入的字符串没有结束
	
        cout<<endl<<endl;
	}
}

void Decode() 
{
	if(ht==NULL)cout<<setw(43)<<"没有初始化!!!\n\n";
	else{
	int m=0;
	char de[200];
	cout<<"输入编码串:";
	cin>>de;
      cout<<"编码串"<<de<<" 的字符\n\n";
	do{
		int i=2*n-1;        //回到头结点
		for(;ht[i].lchild!=0 ;m++)  //孩子的值不为零时，继续往下找
		{
			if(de[m]=='0')         //当输入的值为'0'时，往左边找，否则往右
			{ i=ht[i].lchild;}
			else  {i=ht[i].rchild;}
		}
		cout<<ht[i].data<<"  ";
	
	}while(de[m]!='\0');      //字符的结束
	

	cout<<endl<<endl;

	}
}
	

     


void Printtree()    //打印树的结构图
{ 
	if(ht==NULL)cout<<setw(43)<<"没有初始化!!!\n\n";
	else{
	int i,m,k,j;
	cout<<"哈夫曼树结构图\n\n";   //哈夫曼的结构图
	cout<<"number"<<setw(12)<<"data"<<setw(13)<<"weight"<<setw(12)<<"parent"<<setw(12)<<"lchilde"<<setw(12)<<"rchlide"<<endl;
	for(i=1;i<=2*n-1;i++)    //打印孩子的个数
	{
	cout<<i<<setw(16)<<ht[i].data<<setw(10)<<ht[i].weight<<setw(12)<<ht[i].parent<<setw(12)<<ht[i].lchild<<setw(12)<<ht[i].rchild<<endl<<endl;
	}
	cout<<endl<<endl;
   cout<<"哈夫曼图形\n\n";   //用凹凸法画哈夫曼图
            i=1;
        for(m=1;m<=n;m++)    //打印数据的个数
		{        
			j=0;            //j为记录孩子到根结点的层数
       for(;ht[i].parent!=0;j++)   //从叶子结点找根结点
	   { 
      i=ht[i].parent;           
	   } 
         i=m+1;                  //指示叶子结点的地址
     cout<<ht[m].data<<"  ";  //打印孩子结点
       for(k=1;k<30-3*j;k++)            //打印孩子的长度
       cout<<"*";
      cout<<endl<<endl;
		}
       cout<<endl<<endl;
	}

	
}
     
 void  main(){                         //主函数
	  welcome();                       //界面
       char select='0';
loop1:                                //运行完函数后，跳回
      select=menu();             
loop2:
      cin>>select;                  //选择操作符
switch(select){               
    case'a':
	
		{
			cout<<"初始化:"<<endl;
		Init();
		goto loop1;                 //初始化后，跳回loop1
		}
    case'b':
	
		{
			Encode();
		goto loop1;
		}
	case'c':
	
		{
			Decode();
		   goto loop1;
			}
	case'd':
 
		{
			print(); 
			goto  loop1;
		}
	case'e':
	
		{
		Printtree();
			goto  loop1;
		}
	case'f':
                               
		{
			cout<<endl;
			cout<<"谢谢你使用本系统!"<<endl<<endl;
		    break;
		}
	default:                        // 错误的选择
		{
			cout<<"error!"<<endl;  
			cout<<"请再选择一个代码: "; 
			goto  loop2;
		}
	}
}