我的数据结构课程设计源码

#include<iostream.h>
#include<string.h>
#include<stdio.h>
#define maxvalue 100000000

//哈夫曼树结点
typedef struct node{
	char  data;
	int   weight;
	int   left;
	int   right;
	int   parent;
}node,*nodeprt;

static char nodecode[50][50];//存放编码的数组
void bianli(int , int , const nodeprt ,int );//输出编码
nodeprt HTree(int );// 建立哈夫曼树，返回数组
void bianma(char *, nodeprt, int);//对字符串进行编码
void yima(char *, nodeprt, int);//对01码进行译码 

//主函数

void main()
{
	nodeprt HTreeN;
	int n;
	char a[200],key;
	cout<<"现在开始建立哈夫曼编码树："<<endl<<"请输入叶子结点个数：";
	cin>>n;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			nodecode[i][j]='\0';
		}	
	}
	HTreeN=HTree(n);    // 建立哈夫曼树，返回数组
	bianli(2*n-1,0,HTreeN,n);	//输出哈夫曼树编码

A:	cout<<"请输入您的操作(1:译码   2:编码   其他:退出)： ";
	cin>>key;
	switch(key)
	{
	case '1':
		{
			cout<<"请输入要编码的字符串："<<endl;
			gets(a);
		    	bianma(a,HTreeN,n);
			goto A;
		}
	case '2':
		{
			cout<<"请输入要译码的字符串："<<endl;
			gets(a);
			yima(a,HTreeN,n);
			goto A;
		}
	default:
		{
		break;
		}
	}
	delete HTreeN;
}

nodeprt HTree(int n)// 建立哈夫曼树，返回数组
{
	nodeprt HTreeN=new node[2*n];
	int i,j,max_min1,max_min2,x1,x2;
	for(i=1; i<2*n; i++)//第零号单元装头结点的下标
	{
		HTreeN[i].weight =0;
		HTreeN[i].data   ='`';
		HTreeN[i].parent =-1;
		HTreeN[i].left   =-1;
		HTreeN[i].right  =-1;
	}
	cout<<"请输入n个叶子接点的权值\n"
		<<"及字符（格式：字符，权值）"<<endl;
	for(i=1; i<=n; i++)
	{
		cin>>HTreeN[i].data>>HTreeN[i].weight;
	}	
	//构造哈夫曼树
	for(i=0; i<n-1; i++)
	{
		max_min1=max_min2=maxvalue;
		x1=x2=0;
		for(j=1; j<= n+i; j++)
		{
			if( HTreeN[j].parent==-1 && HTreeN[j].weight<max_min1 )
			{
				max_min2=max_min1;
				x2=x1;
				max_min1=HTreeN[j].weight;   //max_min1 用来记录一个weight最小的结点权值
				x1=j;                        //x1 用来记录一个weight最小的结点下标
			}
			else if( HTreeN[j].parent==-1 && HTreeN[j].weight<max_min2 )
			{
				max_min2=HTreeN[j].weight;   //max_min2 用来记录一个weight次最小的结点权值
				x2=j;                        //x2 用来记录一个weight次最小的结点下标
			}
		}
		//将两棵子树合成一棵子树
		HTreeN[x1].parent=n+i+1;
		HTreeN[x2].parent=n+i+1;
		HTreeN[n+i+1].weight=HTreeN[x2].weight+HTreeN[x1].weight;
		HTreeN[n+i+1].right=x1;
		HTreeN[n+i+1].left=x2;
	}
	return HTreeN;
}




//输出编码
void bianli(int xiabiao, int len, const nodeprt HTreeN,int n)
{
	static int a[100];
	if(xiabiao<2*n && xiabiao>0)
	{
		if(HTreeN[xiabiao].left==-1 && HTreeN[xiabiao].right==-1)
		{
			cout<<"结点权值"<<HTreeN[xiabiao].data<<"的编码:";
			for(int i=0;i<len;i++)
			{
				cout<<a[i]<<' ';						//静态数组保存对字母的编码,xiabiao
				nodecode[xiabiao][i]=(char)(a[i]+48);   //与哈夫曼树中字母的下标相同
			}
			cout<<"\t权值："<<nodecode[xiabiao]<<endl;
		}
		else
		{
			a[len]=0;bianli(HTreeN[xiabiao].left,len+1,HTreeN,n);

			a[len]=1;bianli(HTreeN[xiabiao].right,len+1,HTreeN,n);
		}
	}
}

////对字符串进行编码
void bianma(char *array, nodeprt HTreeN, int n)
{
	int i=0, seen=0;
	while(array[i]!='\0')
	{
		for(int j=0; j<n; j++)
		{
			if(array[i]==HTreeN[j+1].data)
			{
				cout<<nodecode[j+1]<<' ';
				seen=1;
			}
		}
		if(array[i]==' '){}
		else if(seen==0)
		{
			cout<<"无"<<array[i]<<"的编码"<<' ';
		}
		else 
		{
			seen=0;
		}
		i++;
	}
	cout<<endl;
}

//
void yima(char *array, nodeprt HTreeN, int n)
{
	static char a[50];
	int i=0, seen=0;
	while(array[i]!='\0')
	{
		for(int j=0 ; array[i]!=' ';i++,j++)
			a[j]=array[i];

		for(j=0; j<n; j++)
		{
			if(strcmp(a,nodecode[j+1])==0)
			{
				cout<<HTreeN[j+1].data;
				seen=1;
				break;
			}
		}
		if(seen==0)
			cout<<"无与"<<a<<"对应的字符"<<' ';
		for(j=0;j<50;j++)//将静态数组清空
			a[j]='\0';
		if(array[i]==' '){ cout<<' ';}//如果array[i]是空格不报错,输出空格
		if(seen!=0)
		{
			seen=0;
		}
		i++;
	}
	cout<<endl;
}