polycalculator.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 MAXINT 3000

typedef struct polynode
{
	float coef;
	int   expn;
	struct polynode * next;
}polynode,* linkpoly;



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

polynode* P[21]={NULL};
/* ********************************************************     */
void test()
{

	P[3]=new polynode;
	P[3]->expn=3000;
    P[3]->next=new polynode;
	P[3]->next->coef=1;
    P[3]->next->expn=1;
	P[3]->next->next=NULL;

	P[1]=new polynode;
	P[1]->expn=3000;
    P[1]->next=new polynode;
	P[1]->next->coef=1;
    P[1]->next->expn=1;
	P[1]->next->next=NULL;

	P[2]=new polynode;
	P[2]->expn=3000;
    P[2]->next=new polynode;
	P[2]->next->coef=1;
    P[2]->next->expn=1;
	P[2]->next->next=NULL;
}
	

/* ********************************************************     */
void push(linkstack &S,char e)
{   linkstack p;
	p=new stack;
	p->data=e;
	p->next=S;
	S=p;
}
/**************************************************************/
bool pop(linkstack &S,char &e)
{
	linkstack p;
	if(S)
	{
		p=S;
		S=S->next;
		e=p->data;
		delete p;
		return TRUE;
	}
	else return ERROR;
}
/*				***************************************			*/

void OrderInsert(linkpoly P, polynode *s){
	polynode *p,*q;
	p=P;
	while(p->next && p->next->expn>s->expn)p=p->next;
	
	if(p->next&&p->next->expn==s->expn){
		p->next->coef+=s->coef;
    
        if(p->next->coef==0){
			q=p->next;
			p->next=q->next;
			free(q);
		}
		free(s);
	}
	else{
		s->next=p->next;
		p->next=s;
	}
}

/*    ******************************************************************     */
void copypoly(polynode *rear,polynode *p)
{
     while(p!=NULL)
		 {
			 rear->next=new polynode;
			 rear=rear->next;
             rear->coef=p->coef;
			 rear->expn=p->expn;
			 p=p->next;
		 }//while

		 rear->next=NULL;
}
/*			*****************************************************************		*/
void clean(linkpoly &Q)
{
	polynode *p;
	while(Q->next)
	{
		p=Q->next;
		Q->next=p->next;
		delete p;
	}
	delete Q;
}
/*	   ***********************************************************   */ 
bool Polyempty(linkpoly P)
{
	if(P==NULL) return TRUE;
	else return FALSE;
}
	
/*	   ***********************************************************   */ 

void creatpoly(linkpoly &P)
{
	P=new polynode;
	P->expn=3000;
	P->next=NULL;
	linkpoly pre,p,q;
	pre=p=P;

	printf("请输入系数和指数，连续输入两个0结束创建。\n");

	
	while(1)
    {
		q=new polynode;
        cin>>q->coef>>q->expn; 
		if(q->coef==0&&q->expn==0) break;
		while(p->expn>q->expn)
            {
			
				pre=p; 
				p=p->next;
				if(p==NULL) break;
            }
            
			if(p==NULL)
			{
				pre->next=q;
				q->next=NULL;
			}
			else if(p->expn<q->expn)
			{
			    pre->next=q;
			    q->next=p;
			}
		    else
			{
				p->coef+=q->coef;
			}
			

			p=pre=P;           // 复位
		
	}//while
   //return P;
}//creatpoly

/*	**************************************************************        */
void showpoly(linkpoly P)
{
    if(P==NULL)  {cout<<"空值\n"; return;}
	linkpoly p=P->next;
	while(p!=NULL)
	{
		
		if(p==P->next)  cout<<p->coef<<"x^"<<p->expn ;  //对第一个节点作特殊的处理

		else if(p->coef>0) cout<<"+"<<p->coef<<"x^"<<p->expn;

		else cout<<p->coef<<"x^"<<p->expn;

		p=p->next;
	}
	cout<<"\n";
}//showpoly

/*　****************************************************************     */  
float calculate(linkpoly P,float x)
{//计算x取给定值时的多项式值
	polynode *p=P->next;
    float result=0,node;
	int i;
	while(p)
	{ 
		node=1;//resetnode node is the value of the node 
		for(i=p->expn;i>0;i--)
		{
			node=node*x;
		}
		node=node*p->coef;
		result+=node;
		p=p->next;
	}//while

	return result;
}

 
/*　****************************************************************     */
void addpoly(linkpoly P1,linkpoly P2,linkpoly &P3)
{
     linkpoly p1=P1->next;
	 linkpoly p2=P2->next;
     linkpoly p3 ,rear;
	 
	 P3=new polynode;
	 P3->expn=MAXINT;
	 P3->next=NULL;
	 rear=P3;           // initialize P3
     
	 while(p1!=NULL&&p2!=NULL)
	 {
		 p3=new polynode;
		 if(p1->expn>p2->expn)
		 {
			 p3->coef=p1->coef;
			 p3->expn=p1->expn;

			 rear->next=p3;
		     rear=rear->next;
		     rear->next=NULL;

			 p1=p1->next;
		 }
		 else if(p1->expn<p2->expn)
		 {
			 p3->coef=p2->coef;
			 p3->expn=p2->expn;
			 
			 rear->next=p3;
		     rear=rear->next;
		     rear->next=NULL;

             p2=p2->next;
		 }
		 else
		 {
			 p3->coef=p1->coef+p2->coef;
			 p3->expn=p1->expn;
			 
			 if(p3->coef==0)delete p3;
			 
			 else
			 {
			     rear->next=p3;
			     rear=rear->next;
			     rear->next=NULL;
			 }
			
			 p1=p1->next;
			 p2=p2->next;
		 }

	
	 }//while

	 if(p1==NULL)  copypoly(rear,p2);
	 else copypoly(rear,p1);

}//addpoly

/*　****************************************************************     */
void subpoly(linkpoly P1,linkpoly P2,linkpoly &P3)
{
     linkpoly p1=P1->next;
	 linkpoly p2=P2->next;
     linkpoly p3 ,rear;
	 
	 P3=new polynode;
	 P3->expn=MAXINT;
	 P3->next=NULL;
	 rear=P3;           // initialize P3
     
	 while(p1!=NULL&&p2!=NULL)
	 {
		 p3=new polynode;
		 if(p1->expn>p2->expn)
		 {
			 p3->coef=p1->coef;
			 p3->expn=p1->expn;
			 
			 rear->next=p3;
		     rear=rear->next;
		     rear->next=NULL;

             p1=p1->next;
		 }
		 else if(p1->expn<p2->expn)
		 {
			 p3->coef=-p2->coef;
			 p3->expn=p2->expn;
			 
			 rear->next=p3;
		     rear=rear->next;
		     rear->next=NULL;

			 p2=p2->next;

		 }
		 else
		 {
			 p3->coef=p1->coef-p2->coef;
			 p3->expn=p1->expn;
			 if(p3->coef==0) delete p3;
			 else
			 {   rear->next=p3;
			     rear=rear->next;
				 rear->next=NULL;
			 }

				 p1=p1->next;
		         p2=p2->next;
		 }

		     

	 }//while

	 if(p1==NULL)
	 {
		 while(p2!=NULL)
		 {
			 rear->next=new polynode;
			 rear=rear->next;
             rear->coef=-p2->coef;
			 rear->expn=p2->expn;

			 p2=p2->next;
		 }//while

		 rear->next=NULL;
	 }//if



	 else if(p2==NULL)
	 {
		 while(p1!=NULL)
		 {
			 rear->next=new polynode;
			 rear=rear->next;
             rear->coef=p1->coef;
			 rear->expn=p1->expn;

			 p1=p1->next;
		 }//while

		 rear->next=NULL;
	 }//else if
	 if(P3==rear)
	 {
		 rear->next=new polynode;
		 rear=rear->next;
		 rear->coef=0;
		 rear->expn=1;
		 rear->next=NULL;
	 }

}//subpoly

/*		******************************************************************		*/
void multipoly(linkpoly P1,linkpoly P2,linkpoly &P3)
{ 
      linkpoly p1=P1->next;
	  linkpoly p2=P2->next;
      linkpoly p3,rear;
	 
	  P3=new polynode;
	  P3->expn=MAXINT;
	  P3->next=NULL;
	  rear=P3;           // initialize P3
      
	  while(p1)
	  {
		  while(p2)
		  {
			  p3=new polynode;
			  p3->coef=p1->coef*p2->coef;
			  p3->expn=p1->expn+p2->expn;
              OrderInsert(P3, p3);
			  p2=p2->next;
		  }
		  p1=p1->next;
		  p2=P2->next;  // p2 reset
	  }
}
/*			*****************************************************************			*/
void divpoly(linkpoly P1,linkpoly P2,linkpoly &P3,linkpoly &P4)
{
      linkpoly p1=P1->next;
	  linkpoly p2=P2->next;
      linkpoly p3=new polynode,p4=new polynode;//as a head  p3 must be a poly if it wants to mutipoly
	  linkpoly tempt,r,rear,p3rear=p3;//
      
	  r=new polynode;
	  r->expn=MAXINT;
	  r->next=NULL;
	  rear=r;
	  copypoly(rear,p1);
	  p1=P1->next;

	 
	  P3=new polynode;
	  P3->expn=MAXINT;
	  P3->next=NULL;
	  rear=P3;           // initialize P3

      while(r->next->coef!=0&&r->next->expn>=p2->expn)
	  {    
		  p3rear->next=new polynode;
		  p3rear=p3rear->next;
         

		  p4->coef=p3rear->coef=r->next->coef/p2->coef;
		  p4->expn=p3rear->expn=r->next->expn-p2->expn;
		  p3rear->next=NULL;

          
		  OrderInsert(P3, p4);

		  multipoly(p3,P2,tempt);
		  clean(r);
		  subpoly(P1,tempt,r);
		  clean(tempt);

		  p3rear=p3;
		  p3rear->next=NULL;//reset p3rear
	  }//while
	  P4=r;
}
/*		********************************************************************			*/
bool ISOP(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')
		return TRUE;
	else return ERROR;
}

/*		********************************************************************			*/
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,