m元多项式.c

M元多项式的表示以及一些运算

#include<stdio.h>
#include<math.h>
#include<string.h>
typedef enum { ATOM,LIST,HEAD } ElemTag  ;

typedef union {
	int mark;
	struct _Node *subList;
} VNode ;

typedef union {
	int mark ;
	int exp ;
    double coef ;
} EXP ;

typedef struct _Node {
	ElemTag Tag;
	VNode Data;
	EXP exp ;
	struct _Node *next;
}Node;

Node* CreatNode(int mark ,int exp )
{
	Node *p;
	p = (Node*)malloc( sizeof(Node) );
	p->Tag = ATOM ;
	p->Data.mark = mark ;
	p->exp.exp = exp ;
	p->next = NULL ;
	return p ;
}
void merge(Node * );
void CreatList(Node *  ,char * );
void DisplayList(Node * ) ;
void InitList(Node *L) ;
void order(Node *L) ;
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////	
void CreatList(Node * L,char *s)
{
	int i=0 , exp , mark , j , sign = 0 , coe = 1,tt;
	int a[5] ;
	double t=1;
	Node *current = NULL , *temp ;
	L->Tag = HEAD ;
	L->Data.subList = L->next = NULL ;
	if( s[i] == '-' )
	{
		coe = -1 ;
		i++;
	}
    
	for( ; s[i] != '\0' ; i++ )
	{
		if( s[i] == '+' ) 
		{
			temp = (Node*)malloc( sizeof(Node) );
			temp->Tag = HEAD ;
			temp->next = NULL ;	
			coe = 1 ;
			L = L->next = temp;
			current = NULL ;
			for( j = 1 ; s[i+j] != 'x' ; j++ )      ;
			if( j == 1)      L->exp.coef = 1 ;
			else             L->exp.coef = coe * atof(  strncpy( a , s+i+1 , j-1 )  ) ;
			i = i + j-1;
			continue ;
		}

		if( s[i] == '-' ) 
		{
			temp = (Node*)malloc( sizeof(Node) );
			temp->Tag = HEAD ;
			temp->next = NULL ;	
			coe = -1 ;
			L = L->next = temp ;
            current = NULL ;
			for( j = 1 ; s[i+j] != 'x' ; j++ )      ;
			if( j == 1)      L->exp.coef = 1 ;
			else             L->exp.coef = coe * atof(  strcpy( a , s+i+1 , j-1 )  ) ;
			i = i + j-1;
			continue ;
		}
        
		if( s[i] == 'x' ) 
		{
			for( j = 1 ; s[i+j] != '^' && s[i+j] != '+' && s[i+j] != '-' && s[i+j] != '\0' && s[i+j] != 'x' ; j++) ;

		    if( s[i+j] == '^')
			{
				for(tt=0;tt<=4;tt++) a[tt]='\0';
				mark = atoi(  strncpy( a , s+i+1, j-1 )  ); printf("\n%d\n",mark);
			}
			else
			{
				exp = 1 ;
				for(tt=0;tt<=4;tt++) a[tt]='\0';
				mark = atoi(  strncpy( a , s+i+1, j-1 )  );
				if( current != NULL ) 
				current = current->next = CreatNode( mark , exp );
				else  
				{
					current = L->Data.subList = CreatNode( mark , exp );
					L->exp.coef = coe * t ;
				}
			}
			i = i + j -1;
            continue ;
		}
   
		if( s[i] == '^' )
		{
			for( j = 1 ; s[i+j] != 'x' && s[i+j] != '+' && s[i+j] != '-' && s[i+j] != '\0' ; j++ )   ;
		    for(tt=0;tt<=4;tt++) a[tt]='\0';
			exp = atoi( strncpy( a , s+i+1, j-1 ) ); 					      				
			if( current != NULL ) 
				current = current->next = CreatNode( mark , exp );
            else  
			{
				current = L->Data.subList = CreatNode( mark , exp );
				L->exp.coef = coe * t ;
			}
			i = i + j -1 ;	
			continue ;
		}

		for( j =1 ; s[i+j] != 'x' ; j++ ) ;
		t = atof(  strncpy( a , s+i , j )  );
        i = i + j - 1 ;
	}
}
//-----------------------------------------------------------------------------------------
void DisplayList(Node *L)
{
	Node *current;
	printf("%g",L->exp.coef);
	if(L!=NULL)
	{
		for( current = L->Data.subList ; current != NULL ; current = current->next )
			printf("X%d^%d",current->Data.mark,current->exp.exp);
		
	}
     
	for( L = L->next ; L != NULL ; L = L->next )
	{
		printf("%+g",L->exp.coef);
		for( current = L->Data.subList ; current != NULL ; current = current->next )
			printf("X%d^%d",current->Data.mark,current->exp.exp);	
	}
	printf("\n");
}
//--------------------------------------------------------------------------------
void InitList(Node *L)
{
	L->Tag = HEAD ;
	L->exp.coef = 1 ;
	L->next = L->Data.subList = NULL ;
}
//--------------------------------------------------------------------------
void order(Node *L)
{
	Node *head,*p1,*p2,*temp;
	for( ; L != NULL ; L = L->next )
		for( head = L->Data.subList ; head != NULL ; head = head->next )
		{
			p1 = head ;
			p2 = head->next ;
			while( p2 != NULL )
			{
				if( p2->Data.mark == head->Data.mark )
				{
					head->exp.exp += p2->exp.exp ;
					p1->next = p2->next ;
					free( p2 );
					p2 = p1->next ;
					continue ;
				}
				if( p2->Data.mark < head->Data.mark )
				{
					p1->next = p2->next ;
					p2->next = head ;
					head = p2 ;
					p2 = p1->next ;
					L->Data.subList = head ;
					continue ;
				}
				p1 = p2;
				p2 = p2->next ;
			}
		}
}
//-----------------------------------------------------------------------
void merge(Node *L)
{  
	Node *p1 , *p2 , *sub1 , *sub2 ;
	for( ; L != NULL ; L = L->next )
	{
		p1 = L ;
		p2 = L->next ;
        while( p2 != NULL )
		{
			
			for( sub1=L->Data.subList,sub2 =p2->Data.subList ; sub1!=NULL&&sub2!=NULL;sub1=sub1->next,sub2=sub2->next)	
			{	
				if(sub1->Data.mark!=sub2->Data.mark || sub1->exp.exp!=sub2->exp.exp) 
				{
					p1=p2;
					p2=p2->next;
					break;}
			}
			
			if( sub1==NULL && sub2==NULL )
			{
				L->exp.coef+=p2->exp.coef;
				p1->next=p2->next;
				free(p2);
				p2=p1->next;
				continue ;
			}
    
			p1=p2;
			p2=p2->next;	
		}
	}
}

void add(Node *L1 ,Node *L2)
{
	for(;L1->next!=NULL;L1=L1->next );
	L1->next = L2;
}

int main()
{
	Node *head,*h;
	char array[100];
	head=(Node*)malloc(sizeof(Node));
	h=(Node*)malloc(sizeof(Node));
	InitList(head);
    
	scanf("%s",array);
	CreatList(head,array);
	CreatList(h,array);

	


    add(head,h);

	DisplayList(head);
//	printf("\n***********\n");
    merge(head);
 
	
	//DisplayList(&head);

}