bitree.cpp

一个多项式运算程序 实现多项式的加 减 乘除 乘方 积分 微分 混合运算 一个二叉树运算程序 实现二叉树的创建 复制 深度计算 和树形显示 一个哈夫曼算法的演示程序 实现对电文的编码 编码的输出

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<process.h>
#include<string.h>
#include<math.h>
#include<stdio.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAXSIZE 50
char f[80]={'\0'};


typedef struct BiTnode{
	char *data;
    struct BiTnode *lchild,*rchild;
	int layer;//给树加上layer属性方便输出的格式控制
}BiTnode,*BiTree;

typedef struct stack{
	BiTree data;
	struct stack *next;
} stack,* linkstack;	

typedef struct stack1{
	float data;
	struct stack1 *next;
} stack1,* linkstack1;	

typedef struct {
    BiTree *elem;
	int front;
	int rear;
	int queuesize;
}Queue;
/**************************************************************/
void push(linkstack &S,BiTnode *e)
{   linkstack p;
	p=new stack;
	p->data=e;
	p->next=S;
	S=p;
}
/**************************************************************/
void push1(linkstack1 &S,float e)
{   linkstack1 p;
	p=new stack1;
	p->data=e;
	p->next=S;
	S=p;
}
/**************************************************************/
bool pop(linkstack &S,BiTnode* &e)
{
	linkstack p;
	if(S)
	{
		p=S;
		S=S->next;
		e=p->data;
		delete p;
		return TRUE;
	}
	else return ERROR;
}
/**************************************************************/
bool pop1(linkstack1 &S,float &e)
{
	linkstack1 p;
	if(S)
	{
		p=S;
		S=S->next;
		e=p->data;
		delete p;
		return TRUE;
	}
	else return ERROR;
}
/*		********************************************************************			*/
bool ISOP(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')
		return TRUE;
	else return ERROR;
}
/*		********************************************************************			*/
bool IsNumber(char c)
{
	if(c>='0'&&c<='9')
		return TRUE;
		else return ERROR;
}
/*		********************************************************************			*/
char* GetNum(char* &p)
{
	char *floatnum=new char [20];
	int i=0;
    //floatnum[i]=*p;
	//i++;
	while(IsNumber(*(p+1))||*(p+1)=='.')
	{
		floatnum[i]=*p;
		p++;
		i++;
	}
	floatnum[i]=*p;
	floatnum[i+1]='\0';
	return floatnum;
}

/*		********************************************************************			*/
void ChartoNum(char *a,float &f1)
{// 将a数组中的字符型数变成浮点数f1
	f1=0;
	int flag=0,count=0;
	while(*a!='\0')
	{
		    if(*a=='.') flag=1;
			else 
			{
		      f1=f1*10+(*a)-'0';
			  if(flag==1) count++;//count 统计小数位 出现flag==1表明出现小数位
		      
			}
			a++;
	}

    f1=f1/(float)pow(10,count);




}
/*		********************************************************************			*/
int checktable(char b,char a)//b 是栈顶元素， a是新遇到的运算符，比较a b的优先级
{ 
	char table1[7]={'+','-','*','/','(',')','#'};
	int b1=0,a1=0;
	
	while(table1[b1]!=b)b1++;
	while(table1[a1]!=a)a1++;
	
	int table[7][7]={ 0,0,1,1,0,0,0,
                      0,0,1,1,0,0,0,
				   	  0,0,0,0,0,0,0,
					  0,0,0,0,0,0,0,
					  1,1,1,1,0,2,0,
					  1,1,1,1,2,0,0,
					  1,1,1,1,1,1,3}; //优先级s>=p就返回0，优先级s<p就返回1，左右括号相遇时就返回2,#和#相遇就返回3
	
	return (table[b1][a1]);
}

/*		********************************************************************			*/
void InitQueue(Queue &Q,int maxsize=MAXSIZE)
{
	Q.elem=new BiTree[maxsize];
	Q.queuesize=maxsize;
	Q.front=Q.rear=0;
}
/*		********************************************************************			*/
bool DeQueue(Queue &Q,BiTree &e)
{
	if(Q.front==Q.rear) return FALSE;
	e=Q.elem[Q.front];
	Q.front=(Q.front+1)%Q.queuesize;
	return TRUE;
}

/*		********************************************************************			*/
bool EnQueue(Queue &Q,BiTree e)
{  
	if((Q.rear+1)%Q.queuesize==Q.front)  return FALSE;
    Q.elem[Q.rear]=e;
	Q.rear=(Q.rear+1)%Q.queuesize;
    return TRUE;
}
    
/*		********************************************************************			*/
bool QueueEmpty(Queue Q)
{
	if(Q.front==Q.rear) return TRUE;
	else return FALSE;
}
/*		********************************************************************			*/
void printspace(int depth)
{   int i=depth;
	for(;i>0;i--)
	{
		cout<<" ";
	}
}
/*		********************************************************************			*/

void CreatBiT(BiTree &T)
{
    BiTnode *tempt[20]={NULL};//tempt中存放树的节点
	BiTree a,b,c;
	int i=0,flag;
	char *p=f;//p 是指向计算式的指针 ch 接受字符 a&b是操作数 c是运算符。
	linkstack S_number=NULL,S_op=NULL;
    
	/*while((ch=getchar())!='#')
	{
		f[i]=ch;
		i++;
	}
	f[i]='#';//输入算式*/

	tempt[0]=new BiTnode;
    tempt[0]->data=new char;//申请空间 并赋值
	tempt[0]->data[0]='#';
	push(S_op,tempt[0]);
	
    i=1;
	while(1)
	{


		if(IsNumber(*p)) 
		{
			tempt[i]=new BiTnode;
			tempt[i]->data=GetNum(p);
			tempt[i]->lchild=NULL;
			tempt[i]->rchild=NULL;
			push(S_number,tempt[i]);//若是 操作数入作操数栈
            i++;		
		}
	    else if(*p=='(') 
		{	tempt[i]=new BiTnode;
            tempt[i]->data=new char;
			tempt[i]->data[0]=*p;
			push(S_op,tempt[i]);
            i++;	     //左括号直接入栈
		}
		else if(ISOP(*p))
		{
			
			
			flag=checktable(S_op->data->data[0],*p);//判断优先级
			while(flag==0)
			{
				pop(S_number,a);
			    pop(S_number,b);
				pop(S_op,c);
				T=c;
			    c->rchild=a;
				c->lchild=b;//栈顶优先级高于未入栈的 则建立树
				push(S_number,c);

				flag=checktable(S_op->data->data[0],*p);
			}
			if(flag==1)
			{ 
				tempt[i]=new BiTnode;
				tempt[i]->data=new char;
			    tempt[i]->data[0]=*p;
			    push(S_op,tempt[i]);//栈顶优先级低于未入栈的 则入op栈
                i++;
			}		
			if(flag==2)
                pop(S_op,a);//括号相遇就消除之
            if(flag==3)
            return;



             
		}//else if
			   
		p++;
	}//while


	for(i=0;tempt[i]!=NULL;i++)
	{
		free (tempt[i]);//释放临时的辅助节点
	}
}
/*		********************************************************************			*/
void Operate(BiTree T,linkstack1 &Snum,float &result)
{//实现对二叉树表达式的求值
    float f1,f2,f;
    if(T)
	{
		Operate(T->lchild,Snum,result);
        Operate(T->rchild,Snum,result);
		
		if(ISOP(T->data[0]))
		{
			pop1(Snum,f1);
			pop1(Snum,f2);
			switch(T->data[0])
			{
			case '+':
				{
					result=f1+f2;break;
				}
			case'-':
				{
					result=f2-f1;break;
				}
			case '*':
				{
					result=f1*f2;break;
				}
			case '/':
				{
					result=f2/f1;break;
				}
			default:
				{
					cout<<"算式不合法!\n";
					return;
				}
			}
              push1(Snum,result);
		}//if
		else 
		{
				ChartoNum(T->data,f);
			    push1(Snum,f);
		}
	}//if
}//operate

/*		********************************************************************			*/    
float Operate1(BiTree T)
{//实现对二叉树表达式的求值
    float f1,f2,f;
	if(!T->lchild&&!T->rchild)
		{
				ChartoNum(T->data,f);
			    return f;
		}
    
	
	else{
		f1=Operate1(T->lchild);
        f2=Operate1(T->rchild);
		
		if(ISOP(T->data[0]))
		{
		
			switch(T->data[0])
			{
			case '+':
				{
					 return f1+f2;
				}
			case'-':
				{
					return f1-f2;
				}
			case '*':
				{
					return f1*f2;
				}
			case '/':
				{
					return f1/f2;
				}
			default:
				{
					cout<<"算式不合法!\n";
					return FALSE;
				}
			}
              
		}//if
	}//else
}//operate	
/*		********************************************************************			*/

void Operate2(BiTree T,float &result)
{//实现对二叉树表达式的求值
    float f1,f2;
    if(T)
	{
		Operate2(T->lchild,f2);
        Operate2(T->rchild,f1);
		
		if(ISOP(T->data[0]))
		{
		
			switch(T->data[0])
			{
			case '+':
				{
					result=f1+f2;break;
				}
			case'-':
				{
					result=f2-f1;break;
				}
			case '*':
				{
					result=f1*f2;break;
				}
			case '/':
				{
					result=f2/f1;break;
				}
			default:
				{
					cout<<"算式不合法!\n";
					return;
				}
			}
   
		}//if
		else 
		{
				ChartoNum(T->data,result);
		}
	}//if
}//operate2
/*		********************************************************************			*/

void CreatBiT2(BiTree &T)
{
	char ch;


	cin>>ch;  //if here is getchar()  cannot opetate well why??
	if(ch=='#'){T=NULL;return;}
    
    else
	{
	T=new BiTnode;
	T->data=new char;
	T->data[0]=ch;
	cout<<"输入"<<T->data[0]<<"左孩子\n";
    CreatBiT2(T->lchild); 
    cout<<"输入"<<T->data[0]<<"右孩子\n";
    CreatBiT2(T->rchild); 
	}
}
/*		********************************************************************			*/
void BiTDepth(BiTree T,int &depth,int h)
{
	if(T==NULL) return;
	
	if(h>depth) depth=h;
    BiTDepth(T->lchild,depth,h+1);// must be ++h not h++!!
	BiTDepth(T->rchild,depth,h+1);
}
/*		********************************************************************			*/
void Show(BiTree T)
{
	Queue Q;
    BiTree e;
	int i=0;
	int depth=0,h=1,count=0,n=0;
	int prelayer=0;
	if(T==NULL) return;

	InitQueue(Q);
    EnQueue(Q,T);
	Q.elem[Q.front]->layer=1;//this is the first layer
    BiTDepth(T,depth,h);

	while(!QueueEmpty(Q))
	{

        DeQueue(Q,e);
		if(e->layer!=prelayer)  // if layer changed output space and return
		{
			cout<<"\n";
			printspace(depth--);
		}//print return
		prelayer=e->layer;

		if(e->lchild!=NULL)
		{
			EnQueue(Q,e->lchild);
            e->lchild->layer=e->layer+1;
		}
		if(e->rchild!=NULL)
		{
			EnQueue(Q,e->rchild);
			e->rchild->layer=e->layer+1;
		}
		i=0;
		while(e->data[i])
		{
			cout<<e->data[i];
		    i++;
		}
		cout<<" ";

	}
}
/*	 	********************************************************************			*/
void CopyTree(BiTree T,BiTree &T1)
{
	if(T==NULL) {T1=NULL;return;}

	T1=new BiTnode;
	T1->data=T->data;
    CopyTree(T->lchild,T1->lchild);
	CopyTree(T->rchild,T1->rchild);
}
/*		********************************************************************			*/
void DestoryTree(BiTree T)
{
	if(T){
		DestoryTree(T->lchild);
		DestoryTree(T->rchild);
		free(T);
	}
}//
/*		********************************************************************			*/
void Calcute(BiTree T,float &result)
{

	float f1,f2;
	if(T)
	{
		Calcute(T->lchild,f1);
       // if(T->lchild!=NULL)ChartoNum(T->lchild->data,f1);
        Calcute(T->rchild,f2);
	//	if(T->lchild!=NULL)ChartoNum(T->rchild->data,f2);
		
		if(T->lchild==NULL)
		{
		ChartoNum(T->data,result);
			ChartoNum(T->data,result);
		}

        else{


		  switch(T->data[0])
		  {
			
	     	case '+':{ result=f1+f2;break;}
	    	case '-':{result=f1-f2;break;}
	    	case '*':{result=f1*f2;break;}
            case '/':{result=f1/f2;break;}
		  }
		}

}
}
/*		********************************************************************			*/
void main()
{   int depth=0;
    int h=1,k;
	BiTree T=NULL,T1=NULL,TNUM=NULL;//T is tree T1 is its copy TNUM is tree for computing machine;
	float  result;
	linkstack1 Snum=NULL;

while(1)
{
	cout<<"-------------二叉树计算器-------------\n"
		<<"1 创建二叉树\n"
	    <<"2 复制二叉树\n"
		<<"3 销毁二叉树\n"
		<<"4 求树的深度\n"
		<<"5 树形显示二叉树\n"
		<<"6 二叉树实现的数值计算器，支持浮点数\n"
		<<"0 退出\n";

	
	cin>>k;
	switch(k)
	{
	case 1:
		{
		    cout<<"创建二叉树请输入根节点：\n";
			CreatBiT2(T);
			cout<<"创建二叉树成功\n";
			break;
		}
	case 2:
		{   
			CopyTree(T,T1);
			cout<<"复制二叉树成功\n";
			Show(T);Show(T1);
			break;
		}
	case 3:
		{
			DestoryTree(T);
			DestoryTree(T1);
			DestoryTree(TNUM);
            cout<<"销毁二叉树成功\n";
			break;
		}
	case 4:
		{
			BiTDepth(T,depth,h);
			cout<<"树的深度是"<<depth<<"\n";
			break;

		}
	case 5:
		{
			cout<<"树形显示二叉树如下:\n";
			Show(T);
			cout<<"\n";
			break;
		}

	 case 6:
		{
			  int i=0;
			  cout<<"请输入算式，以'#'字符结束输入：\n";
              cin>>f[i];
			  while(f[i]!='#')
			  {
				  i++;
		         cin>>f[i];
		         
			  }
	          //输入算式
			  
	          CreatBiT(TNUM);
			  Operate2(TNUM,result);
			  //result=Operate1(TNUM);
			  cout<<result;

			  //Calcute(TNUM,result);
	          //Operate(TNUM,Snum,result);
			  cout<<"\n";
			  cout<<"运算结果:"<<result<<"\n";
			  cout<<"树形显示如下:\n";
              Show(TNUM);
			  cout<<"\n";
			  break;
   
	          
		}
	 case 0:
		 {
			 return;
		 }
    }//switch
}//while
}//main