haffcode.cpp

课程设计： 1.求出在一个n×n的棋盘上

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fstream.h>
#include "Design.h"                    //开始页面
#include "Introduce.h"                 //开始介绍
#include "Direction.h"                 //菜单选项
static unsigned int NUM=0,M_num=0;

/*定义哈夫曼树类型*/
struct Tree    
{ 
	unsigned int ID;  //标号
	char C;           //字符名称
	unsigned int Weight;//权值（频度）
	unsigned int Parent,L_child,R_child;//根，左孩子，右孩子
	int flag; //标志
};
/*字符代码*/
struct C_Code 
{
	char STR;
	char* Code;
};
/*设定延迟时间*/
void sleep(clock_t wait)
{
	clock_t delay;
	delay=wait+clock();
	while(delay>clock());
}
/*获取要译码的代码*/
void getCode()
{
	int len;
	char* str=new char[50];//假定输入的‘1’‘0’代码不超过50
	cout<<"Please input the code you want to translate: ";
	cin>>str;
	len=strlen(str);//求出输入代码的长度
	fstream writeTo("code.txt",ios::trunc); //将输入要译码的代码放在code.txt中
	writeTo<<len<<' '<<str;
	writeTo.close();	
	delete[] str;//释放指针
}
/*判断是否与以前输入的字符相同*/
int find(Tree* sear,char C,int n)
{
	int Ctrl=-1;
	for(int i=0;i<n;i++)
	{
		if(sear[i].C==C)
		{
			Ctrl=1;
			break;
		}
	}
	return(Ctrl);
	
}
void Backup_Rule(int shift)
{
	if(shift==0)
	{
		int len=0;
		char* str;
		char C;
		int n;
		ifstream Back_From("Rule.txt",ios::nocreate);//打开Rule.txt，取内容
			if (!Back_From.fail())
			{
				Back_From>>len;//???????????????????????????
				if (len>0)
				{
					fstream Back_To("Rule_Backup.txt",ios::trunc);//放到Rule_Bcakup.txt中
					Back_To<<len<<endl;
					for (int i=0;i<len;i++)
					{
						Back_From>>C>>n;
						str=new char[n+1];
						Back_From>>str;
						Back_To<<C<<' '<<n<<' '<<str<<endl;
						delete[] str;//释放指针
					}
					Back_To.close();
				}
				Back_From.close();
				
			}
	}
	else
		{
		int len=0;
		char* str;
		char C;
		int n;
		ifstream Back_From("Rule_Backup.txt",ios::nocreate);
			if (!Back_From.fail())
			{
				Back_From>>len;
				if (len>0)
				{
					fstream Back_To("Rule.txt",ios::trunc);
					Back_To<<len<<endl;
					for (int i=0;i<len;i++)
					{
						Back_From>>C>>n;
						str=new char[n+1];
						Back_From>>str;
						Back_To<<C<<' '<<n<<' '<<str<<endl;
						delete[] str;
					}
					Back_To.close();
				}
				Back_From.close();
			}
	}
}
void Code_Show();

/*初始化哈夫曼树*/
Tree* INIT()
{
	Tree* Temp=NULL;//定义空树Temp
	char C;
	int Ctrl;//标志输入的字符是否重复
	unsigned int Wt,i;
	cout<<"Please input the number of the chars : ";//输入字符数目
	cin>>NUM;//叶子数目（输入字符数目）
	while(NUM<2)//输入字符数目应多于2
	{
		cout<<"The wrong number,please input the number of the chars again: ";
		cin>>NUM;
	}
	M_num=2*NUM-1;//总节点数目
	Tree* INit_Tree=new Tree[M_num+1];
	for(i=0;i<NUM;i++)
	{
		Temp=INit_Tree+i;
		cout<<"Please input the char  :  ";//输入字符
		cin>>C;
		Ctrl=find(INit_Tree,C, i);//判断输入字符是否重复，将值赋给Ctrl
		while(Ctrl==1)
		{
			cout<<"Please input the char again :  ";
			cin>>C;
			Ctrl=find(INit_Tree,C, i);
		}
		cout<<"Please input the weight:  ";//输入权值
		cin>>Wt;
		while(Wt<=0)
		{
			cout<<"The wrong number,please input the weight of this char again: ";
			cin>>NUM;
		}
		Temp->ID=i+1;
		Temp->C=C;
		Temp->Weight=Wt;
		Temp->Parent=0;
		Temp->L_child=0;
		Temp->R_child=0;
		Temp->flag=0;		
	}
	for(unsigned int j=NUM;j<M_num;j++)
	{
		Temp=INit_Tree+j;
		Temp->ID=j+1;
		Temp->C='-';//将非叶子节点赋为'-'		
		Temp->Weight=0;
		Temp->Parent=0;
		Temp->L_child=0;
		Temp->R_child=0;
		Temp->flag=0;
	}	
	return (INit_Tree);
}
Tree* HaffTree(Tree* Head)
{
	unsigned int i,j,Ctrl=0;
	Tree* Point_1;
	Tree* Point_2;
	Tree* temp;
	Tree* Temp;
	for(j=NUM;j<M_num;j++)//对非叶子节点进行处理
	{
		for(i=0;i<j;i++)
		{
			Temp=Head+i;
			if(Temp->flag==1)
				continue;	
			if(Ctrl==0)
			{
				Point_1=Temp;
				++Ctrl;
				continue;
			}
			else
			{
				if(Ctrl==1)
				{
					Point_2=Temp;
					++Ctrl;
					if(Point_1->Weight>Point_2->Weight)
					{
						temp=Point_1;
						Point_1=Point_2;
						Point_2=temp;
					}
					continue;
				}
			}				
				if(Temp->Weight<Point_1->Weight)
				{			
					Point_2=Point_1;
					Point_1=Temp;
					continue;
				}
				else
					if(Temp->Weight>=Point_1->Weight&&Temp->Weight<Point_2->Weight)
						Point_2=Temp;				
		}	
		Temp=Head+j; 		
		Temp->Weight=(Point_1->Weight+Point_2->Weight);
		Point_1->Parent=Temp->ID;
		Point_1->flag=1;
		Point_2->Parent=Temp->ID;
		Point_2->flag=1;
		Temp->L_child=Point_1->ID;
		Temp->R_child=Point_2->ID;	
		Ctrl=0;
	}
	fstream HaffTree("tree.txt",ios::trunc);//将构造的哈夫曼树存入tree.txt
	HaffTree<<NUM<<endl;
	for(i=0;i<M_num;i++)
	{
		HaffTree<<Head[i].ID<<' '<<Head[i].C<<' '<<Head[i].Weight<<' '<<Head[i].Parent<<' '<<Head[i].L_child<<' '<<Head[i].R_child<<endl;
	}
	HaffTree.close();
	return (Head);
}

/*打印哈夫曼表*/
void Print(Tree* head)
{
	ofstream Code("code.txt");
	unsigned int i=0;
	Tree* Temp=NULL;
	cout<<"┏━━┳━━━━┳━━━━┳━━━━┳━━━━━┳━━━━━┳━━━┓"<<endl;
	cout<<"┃"<<setw(3)<<"ID"<<setw(3)<<"┃"<<setw(7)<<"string"<<setw(3)<<"┃"
		<<setw(7)<<"Weight"<<setw(3)<<"┃"<<setw(7)<<"Parent"<<setw(3)<<"┃"
		<<setw(8)<<"L_child"<<setw(4)<<"┃"<<setw(8)<<"R_child"<<setw(4)<<"┃"
		<<setw(5)<<"flag"<<setw(3)<<"┃"<<endl;
	
	for(;i<M_num;i++)
	{
		Temp=head+i;
		cout<<"┣━━╋━━━━╋━━━━╋━━━━╋━━━━━╋━━━━━╋━━━┫"<<endl;
		cout<<"┃"<<setw(3)<<Temp->ID<<setw(3)<<"┃"<<setw(5)<<Temp->C<<setw(5)<<"┃"
			<<setw(5)<<Temp->Weight<<setw(5)<<"┃"<<setw(5)<<Temp->Parent<<setw(5)<<"┃"
			<<setw(6)<<Temp->L_child<<setw(6)<<"┃"<<setw(6)<<Temp->R_child<<setw(6)<<"┃"
			<<setw(4)<<Temp->flag<<setw(4)<<"┃"<<endl;		
	}
	cout<<"┗━━┻━━━━┻━━━━┻━━━━┻━━━━━┻━━━━━┻━━━┛"<<endl;
} 
char** TranstoCode(Tree* Head)//进行编码
{
	char** Save_Code=new char* [NUM];	
	Tree* Temp_Son;
	Tree* Temp_Father;
	int K;
	unsigned int i=0;
	for(;i<NUM;i++)
	{
		Temp_Son=Head+i;
		char* temp=new char[NUM];     //Code should use the temp array
		int Pos=NUM-1;
		temp[Pos]='\0';
		while(Temp_Son->Parent!=0)
		{
			K=(Temp_Son->Parent)-1;
			Temp_Father=Head+K;
			if(Temp_Son->ID==Temp_Father->L_child)
				temp[--Pos]='0';		
			else	
				temp[--Pos]='1';		
			Temp_Son=Temp_Father;
		}
		Save_Code[i]=new char[NUM-Pos];
		strcpy(Save_Code[i],&temp[Pos]);
		delete[] temp;
	}	
	return(Save_Code);
}
C_Code* Build_Code(char** Head_Code,Tree* Head) //建立编码规则编码
{
	unsigned int i;
	char* Str;	
	Tree* Temp;
	C_Code* C_Head=new C_Code[NUM];
	C_Code* C_Temp;
	for(i=0;i<NUM;i++)
	{	
		Temp=Head+i;
		Str=Head_Code[i];
		C_Temp=C_Head+i;
		C_Temp->STR=Temp->C;
		C_Temp->Code=new char[strlen(Str)+1];
		strcpy(C_Temp->Code,Str);
	}
	ofstream Str_Code("Rule.txt");
	Str_Code<<NUM<<endl;
	for(i=0;i<NUM;i++)
		Str_Code<<C_Head[i].STR<<" "<<strlen(C_Head[i].Code)<<" "<<C_Head[i].Code<<endl;
	return ( C_Head );
}
void Print_Code(C_Code* Head)
{
	unsigned int i;
	C_Code* Temp;
	cout<<"┏━━━━┳━━━━━━━━┓"<<endl;
	cout<<"┃"<<setw(7)<<"String"<<setw(3)<<"┃"<<setw(11)<<"Code"<<setw(7)<<"┃"<<endl;
	
	for(i=0;i<NUM;i++)
	{
		Temp=Head+i;
		cout<<"┣━━━━╋━━━━━━━━┫"<<endl;
		cout<<"┃"<<setw(5)<<Temp->STR<<setw(5)<<"┃"<<setw(13)<<Temp->Code<<setw(5)<<"┃"<<endl;		
	}
	cout<<"┗━━━━┻━━━━━━━━┛"<<endl;
}
/*调取文件或直接输入要编码的字符*/
char* Input()   
{	
	int len=0;
	char* InStr;
	char Str;
	cout<<"You can Press F key to read the file or press I key to input once more !"<<endl;
	cin>>Str;
	if(Str=='i'||Str=='I')//直接输入编码字符
	{
		cout<<"Please input the strings:  ";
		InStr=new char[50];
		cin>>InStr;
		len=strlen(InStr);
		while(len<2)//两个以下字符无法编码
		{
			cout<<"The strings are too short,please input again: ";
			InStr=new char[50];
			cin>>InStr;
			len=strlen(InStr);
		}
		ofstream Text_In("TEXT.txt");//将刚输入要编码的字符存入TEXT.txt
		Text_In<<len<<' '<<InStr; 
		Text_In.close();
		return (InStr);
	}
	ifstream Text_Read;
	Text_Read.open("TEXT.txt",ios::nocreate);//直接从文件TEXT.txt调取字符
	if(!Text_Read.fail()&&!Text_Read.eof())
	{	
		Text_Read>>len;
		InStr=new char[len+1];
		Text_Read>>InStr;
		Text_Read.close();
	}
	if(len==0)
	{
		if(Text_Read.fail())
			cout<<"The file isn't exit ,please input the strings:  ";//文件不存在	
		else
			cout<<"The file is empty,please input the strings:  ";	//文件为空
		InStr=new char[50];
		cin>>InStr;
		len=strlen(InStr);
		while(len<2)
		{
			cout<<"The strings are too short,please input again: ";
			InStr=new char[50];
			cin>>InStr;
			len=strlen(InStr);
		}
		ofstream Text_In("TEXT.txt",ios::trunc);
		Text_In<<len<<' '<<InStr;
		Text_In.close();
	}
	return(InStr);
}
void StrtoCode()
{
	int n,i;
	int R_len;
	C_Code* C_Head=NULL;
	ifstream Text_Rule("Rule.txt",ios::nocreate);
	if(Text_Rule)
	{
		Text_Rule>>R_len;
		NUM=R_len;
		C_Head=new C_Code[R_len];
		for(i=0;i<R_len;i++)
		{
			Text_Rule>>C_Head[i].STR>>n;
			C_Head[i].Code=new char[n+1];
			Text_Rule>>C_Head[i].Code;
		}
		Text_Rule.close();
	}	
	ifstream Text_Read("TEXT.txt",ios::nocreate);	
	Text_Read>>n;
	char* IN_Head=new char[n+1];
	Text_Read>>IN_Head;
	Text_Read.close();	
	char** temp=new char* [n];
	unsigned int j;
	char P1;
	int len=0;
	C_Code* P2;
	for(i=0;i<n;i++)
	{
		P1=*(IN_Head+i);
		for(j=0;j<NUM;j++)
		{
			P2=C_Head+j;
			if(P1==P2->STR)
				break;
		}
		if(j==NUM)
		{
			cout<<P1<<" isn't to be translate to code!"<<endl;
			break;
		}
		else
			temp[i]=new char [strlen(P2->Code)+1];
		len+=strlen(P2->Code);
		temp[i]=P2->Code;
	}
	if(j!=NUM)
	{
		ofstream Text_Code("CODE.txt");
		Text_Code<<len<<endl;
		cout<<"The code is: "<<endl;
		for(i=0;i<n;i++)
		{
			Text_Code<<temp[i];
		}
		Text_Code.close();
		Code_Show();
		cout<<endl;