huffmantree.cpp

数据结构课程设计源码以及报告 有3个程序：1）哈弗曼树及哈弗曼编码 2）排序—内部排序方法 3）Hanoi Tower

# include "HuffmanTree.h"

int r;		//设置全局变量，控制输出

HuffmanTree::HuffmanTree()
{
 Node=NULL;
 Info=NULL;
 LeafNum=0;
}

HuffmanTree::~HuffmanTree()
{
 delete[] Node;
 delete[] Info;
}

//------------初始化-------------
void HuffmanTree::Initialization(int WeightNum)
{
 int i, j, pos1, pos2, max1, max2;
 Node=new HuffmanNode[2*WeightNum-1];  //总共有2*WeightNum-1个结点
 Info=new char[2*WeightNum-1];
 for(i=0; i<WeightNum; i++)
 {
  cout<<"\t输入第"<<i+1<<"个字符值:";
  getchar();
  Info[i]=getchar();  //输入字符，放入字符数组中
  getchar();
  cout<<"\t输入该字符的权值:";
  cin>>Node[i].weight;
  Node[i].parent=-1;      //为根结点
  Node[i].lchild=-1;
  Node[i].rchild=-1;      //无左右孩子
 }// 输入字符与对应的权重，并把每个字符都设置成一个单独的根结点
 
 for(i=WeightNum;i<2*WeightNum-1;i++) //建立Hffman树
 {
  pos1=-1;
  pos2=-1;          //分别用来存放当前最小值和次小值的编号 
  max1=32767;
  max2=32767;       //分别用来存放当前找到的最小值和次小值  

  for(j=0;j<i;j++)
   if(Node[j].parent==-1)			//判断是否为根结点
    if(Node[j].weight<max1)			//判断是否比最小值要小
    {
     max2=max1;
     max1=Node[j].weight;
     pos2=pos1;            //修改次小值编号
     pos1=j;               //修改最小值编号
    }
    else
     if(Node[j].weight<max2)
     {
      max2=Node[j].weight;
      pos2=j;                  //修改次小值编号
     }

  Node[pos1].parent=i;       //修改parent结点的位置
  Node[pos2].parent=i;
  Node[i].lchild=pos1;       //修改child结点位置
  Node[i].rchild=pos2;
  Node[i].parent=-1;         //下一个结点为根结点
  Node[i].weight=Node[pos1].weight+Node[pos2].weight;//这个结点的权重设置为它的两个child的权重的和
 }

	LeafNum=WeightNum;
	ofstream fop;   //建立文件流
	fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
	if(fop.fail())
	cout<<"\t文件打开失败!";
	fop.write((char*)&WeightNum,sizeof(WeightNum));  //写入WeightNum
	for(i=0;i<WeightNum;i++)						//把所有字符信息写入文件
	{
		fop.write((char*)&Info[i],sizeof(Info[i]));
		flush(cout);				//？？
	}
	 for(i=0;i<2*WeightNum-1;i++)        //把个节点内容写入文件
	{
		 fop.write((char*)&Node[i],sizeof(Node[i]));
		 flush(cout);		//？....
	}
	 fop.close();
	 cout<<"\tHuffman树建立成功.";
		getchar();
}//Initialization
//---------------------------------------------------------------

void HuffmanTree::Encoder()
{	int len1, len2=0;
	char str[20];
	cout<<"\t输入要压缩的文件名:";
	cin>>str;
	ifstream fip;
	fip.open("hfmTree.dat",ios::binary|ios::in);//以二进制方式打开hfmTree.dat文件
	if(fip.fail())
	 {
	 cout<<"\n文件打开失败！\n";
	 return;
	}
	fip.read((char*)&LeafNum,sizeof(LeafNum));  //读取叶子数
	Info=new char[LeafNum];
	 Node=new HuffmanNode[2*LeafNum-1];
	for(int i=0;i<LeafNum;i++)              //读取字符信息
	 fip.read((char*)&Info[i],sizeof(Info[i]));
	for(i=0;i<2*LeafNum-1;i++)              //读取结点信息
	fip.read((char*)&Node[i],sizeof(Node[i]));
 
	char *Tree;          //数组tree用来存储要编码的内容
	ifstream fip1(str);
	if(fip1.fail())
	{
		cout<<"\t文件打开失败!\n";
		getchar();
		return;
	 }
	 char ch;
	 int k=0;
	 while(fip1.get(ch))
	 {
		 k++;                     //计算文件中代码长度..？
	 }
	 len1 = k;
	 fip1.close();
  Tree=new char[k+1];
  ifstream fip2(str);
  k=0;
  while(fip2.get(ch))
  {
   Tree[k]=ch;           //读取文件内容然后存到Tree中
   k++;
  }
  fip2.close();
  Tree[k]='\0';
  int n=k;
  cout<<"\t需编码内容为:";
  r=1;
  for(k=0; k<n; k++){
  cout<<Tree[k];
  if(r==50)
  { 
   cout<<endl<<"\t             ";
   r=0;
  }
  r++;
  }
  ofstream fop("CodeFile.dat",ios::trunc);      //存储编码后的代码,以覆盖原文件的形式储存
  i=0;
  k=0;
  char *code;
  code=new char[LeafNum];        //为所产生编码分配容量为LeafNum的最大存储空间
								 //因为编码中最长的编码不会超过要求编码的字符总数
 while(Tree[k]!='\0')            //对每一个字符编码
 {
  int j, s=0;
  for(i=0;i<LeafNum;i++)
   if(Info[i]==Tree[k])            //求出该文字所在单元的编号
    break;
    j=i;
  while(Node[j].parent!=-1)        //结点j非树根
	{
	 j=Node[j].parent;               //非结点j的双亲结点
	if(Node[j].lchild==i)           //是左子树，则生成代码0
	 code[s++]='0';
	else                            //是右子树，则生成代码1
	 code[s++]='1';
	 i=j;
	}
	code[s]='\0';               //设置串结束符

  for(i=0;i<s/2;i++)          //对二进制序列进行翻转
  {
   j=code[i];
   code[i]=code[s-i-1];
   code[s-i-1]=j;
  }
   i=0;
  while(code[i]!='\0')        //存储代码
  {
   fop<<code[i];
   i++;
  }
   k++;
   len2 = len2+i;
 }
 double V;
 V = ((double)(len1*8)-(double)len2)/(double)(len1*8);
 fop.close();
 cout<<"\n\t编码成功!";
 cout<<"\n\t压缩率为: "<<V*100<<"%";
 HuffmanTree::Print();
}  //Encode
//----------------------------------------------------------

void HuffmanTree::Decoder()
{
 int i=0,k=0;
 int j=LeafNum*2-1-1;				 //从根结点开始
 char* BitStr;
 ifstream fip1("CodeFile.dat");          //与文件CodeFile建立流
 if(fip1.fail())
 {
  cout<<"\t请先编码！";
  getchar();
  return;
 }
 cout<<"\t原内容为:";
 char ch;
 while(fip1.get(ch))            
 {
  k++;                     //计算CodeFile中代码长度
 }
 fip1.close();
 BitStr=new char[k+1];
 ifstream fip2("CodeFile.dat");
 k=0;
 while(fip2.get(ch))
 {
  BitStr[k]=ch;          //读取文件内容
  k++;
 }
 fip2.close();
 BitStr[k]='\0';
 if(Node==NULL)         //未建Huffman树
 {
  cout<<"\n\t请先建立权值表!";
  getchar();
  return;
 }
 r=0;
 ofstream fop("Text.txt");         //将字符形式的编码文件写入文件CodePrin中
 while(BitStr[i]!='\0')
 {  
  if(BitStr[i]=='1')
   j=Node[j].rchild;				//往右
  else
   j=Node[j].lchild;				 //往左
  if(Node[j].rchild==-1)       //到了叶子结点
  {
	if(r==50)					//控制输出格式
	{cout<<endl<<"\t         "; 
	r=0; }
   cout<<Info[j];             //输出叶子结点对应的字符 
   fop<<Info[j];
   j=LeafNum*2-1-1;             //表示重新从根结点开始往下搜索
   r++;  
  }
  i++; 
 }
  fop.close();
  cout<<"\n\t译码完成得到文件Text.txt.\n";
  getchar();
}//Decoder
//----------------------------------------------------------------

void HuffmanTree::Print()
{
 char ch;
 ifstream fip("CodeFile.dat");           //读取文件
 ofstream fop("CodePrin.dat");           //存储文件
 if(fip.fail())
 {
  cout<<"\t没有文件，请先编码！\n";
	getchar();
  return;
 }
   cout<<"\n\t得到Huffman编码:";
   r=1;
 while(fip.get(ch))
 {
  cout<<ch;             //读取文件内容
  fop<<ch;              //存到文件中
  if(r==50)             //每行输出50个字符
  { 
   cout<<endl<<"\t                ";
   r=0;
  }
  r++;
 }
 cout<<endl;
 fip.close();          //关闭CodeFile.dat文件
 fop.close();            //关闭CodePrin.dat文件
   getchar();
}
//-------------end of print----------------

void menue(){
		cout<<endl<<endl;
		cout<<"		Huffman编码程序"<<endl;
		cout<<"	      *****************"<<endl<<endl;
		cout<<"		  1.建立权值表."<<endl;
		cout<<"		  2.压缩文件."<<endl;
		cout<<"		  3.解压文件."<<endl;
		cout<<"		  4.退出 ...."<<endl<<endl;
		cout<<"	      *****************";
		cout<<endl;
}
//----------------end of menue----------------

int main()
{	char c;
	HuffmanTree huftree;         //定义哈夫曼树对象
	int weight;
	while(1)
	{ menue();
		cout<<"\t请选择操作:";
		cin>>c;
		switch(c)
		 {
			case '1':
				cout<<"\t输入表的长度(字符个数)：";
		    cin>>weight;
				huftree.Initialization(weight);  //初始化哈夫曼树
				 getchar();
				 system("cls");
				 break;
			case '2':
			 huftree.Encoder(); //  huftree.Print();
			      getchar();
				 system("cls");
			     break;
			 case '3':
				huftree.Decoder();
				getchar();
				system("cls");
				break;				  
			case '4':
			cout<<"		Quit...."<<endl;
			exit(0);                    //退出程序
					 return 0;
			 }
 }
}