polynomial.cpp

该源代码实现一元稀疏多项式的加法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
typedef struct PolyNode
{    
	int coef;    
	int expn;    
	struct PolyNode *next;
}PolyNode, *PolyType;

void FreePoly(PolyType *poly)
{    
	PolyNode *p = *poly, *q;    
	
	while (p != NULL)    
	{        
		q = p->next;        
		free(p);        
		p = q;			 
	}    
	    *poly = NULL;
}

void DispPoly(PolyType poly)
{   
	PolyNode *p = poly->next;     
	if (p == NULL)     
	{        
		printf("0\n");        
		return;      
	}    
	while (p != NULL)     
	{       
		if (p->expn > 0)            
			printf("%+dx^%d", p->coef, p->expn);       
		else            
			printf("%+d", p->coef);        
		p = p->next;    
	}   
	printf("\n");
}


void AddPoly(PolyType *res, PolyType left, PolyType right)
{   
	PolyNode *t, *p = left->next, *q = right->next;    
	*res = (PolyNode *)malloc(sizeof(PolyNode));    
	(*res)->expn = (*res)->coef = 0;    
	(*res)->next = NULL;  
	t = *res;   
	while (p!=NULL || q!=NULL)    
	{       
		if (p!=NULL && q!=NULL && p->expn==q->expn)        
		{           
			if (p->coef+q->coef != 0)            
			{              
				t->next = (PolyNode *)malloc(sizeof(PolyNode));               
				t = t->next;               
				t->expn = p->expn;               
				t->coef = p->coef+q->coef;               
				t->next = NULL;                
				(*res)->expn++;            
			}            
			p = p->next;            
			q = q->next;        
		}          
		else if (q==NULL || (p!=NULL && q!=NULL && p->expn>q->expn))          
		{      
			t->next = (PolyNode *)malloc(sizeof(PolyNode));        
			t = t->next;           
			t->expn = p->expn;          
			t->coef = p->coef;          
			t->next = NULL;          
			(*res)->expn++;           
			p = p->next;            
		}        
		else          
		{            
			t->next = (PolyNode *)malloc(sizeof(PolyNode));            
			t = t->next;           
			t->expn = q->expn;            
			t->coef = q->coef;           
			t->next = NULL;            
			(*res)->expn++;           
			q = q->next;           
		}     
	}
}




void SubPoly(PolyType *res, PolyType left, PolyType right)
{   
	PolyNode *t, *p = left->next, *q = right->next;    
	*res = (PolyNode *)malloc(sizeof(PolyNode));   
	(*res)->expn = (*res)->coef = 0;    
	(*res)->next = NULL;  
	t = *res;   
	while (p!=NULL || q!=NULL)   
	{     
		if (p!=NULL && q!=NULL && p->expn==q->expn)       
		{       
			if (p->coef-q->coef != 0)           
			{              
				t->next = (PolyNode *)malloc(sizeof(PolyNode));            
				t = t->next;            
				t->expn = p->expn;              
				t->coef = p->coef-q->coef;                
				t->next = NULL;               
				(*res)->expn++;           
			}         
			p = p->next;          
			q = q->next;       
		}
        
		else if (q==NULL || (p!=NULL && q!=NULL && p->expn>q->expn))          
		{    
			t->next = (PolyNode *)malloc(sizeof(PolyNode));        
			t = t->next;         
			t->expn = p->expn;      
			t->coef = p->coef;         
			t->next = NULL;          
			(*res)->expn++;           
			p = p->next;           
		}         
		else          
		{            
			t->next = (PolyNode *)malloc(sizeof(PolyNode));         
			t = t->next;         
			t->expn = q->expn;      
			t->coef = -q->coef;         
			t->next = NULL;         
			(*res)->expn++;       
			q = q->next;          
		}     
	}
}



void DifPoly(PolyType *res, PolyType poly)
{   
	PolyNode *p = poly->next, *t;   
	*res = (PolyNode *)malloc(sizeof(PolyNode));  
	(*res)->expn = (*res)->coef = 0;   
	(*res)->next = NULL;   
	t = *res;  
	while (p != NULL)    
	{        
		if (p->expn > 0)        
		{       
			t->next = (PolyNode *)malloc(sizeof(PolyNode));         
			t = t->next;       
			t->coef = p->coef*p->expn;      
			t->expn = p->expn-1;         
			t->next = NULL;           
			(*res)->expn++;          
		}      
		p = p->next;     
	}
}


long CalcPoly(PolyType poly, int x)
{   
	long res = 0;   
	PolyNode *p = poly->next; 
	while (p != NULL)    
	{    
		res += p->coef*(long)pow(x, p->expn);      
		p = p->next;     
	}   
	return res;
}

void ReadPoly(PolyType *poly)
{    
	PolyNode *p, *q;   
	int coef, expn;    
	*poly = (PolyNode *)malloc(sizeof(PolyNode));  
	(*poly)->expn = (*poly)->coef = 0;   
	(*poly)->next = NULL;   
	printf("input coef: ");  
	scanf("%d", &coef);  
	printf("input exp: ");   
	scanf("%d", &expn);
	
	while (!(expn==0 && coef==0))   
	{    
		p = *poly;     
		q = (*poly)->next;   
		while (q!=NULL && q->expn>expn)    	
		{         
			p = p->next;         
			q = q->next;          }         
		if (q!=NULL && q->expn==expn)          
		{            
			if (q->coef+coef == 0)                 
			{           
				p->next = q->next;         
				((*poly)->expn)--;                 
				free(q);                
			}              
			else                
				q->coef += coef;        
		}       
		else if (coef != 0)        
		{           
			p->next = (PolyNode *)malloc(sizeof(PolyNode));       
			p = p->next;          
			p->expn = expn;           
			p->coef = coef;          
			p->next = q;          
			((*poly)->expn)++;          
		}   
		printf("input coef: ");      
		scanf("%d", &coef);      
		printf("input exp: ");        
		scanf("%d", &expn);     
									
	} 
												
}


void DispUsage()
{   
	printf("\n1:add\n");   
	printf("2:sub\n");   
	printf("3:mul (NOT SUPPORTED)\n"); 
	printf("4:qiu_dao\n");  
	printf("5:data in x\n");  
	printf("6:exit\n\n");
}


int main(){   
	PolyType left, right, res;   
	int op, x;   
	long val;       
	DispUsage();    
	scanf("%d", &op);   
	while (op != 6)     
	{    
		switch (op)         
		{       
		    case 1: printf("input the first\n");
					ReadPoly(&left);                   
					printf("input the second\n"); ReadPoly(&right);AddPoly(&res, left, right);             
					printf("the first: "); DispPoly(left);        
					printf("the second: "); DispPoly(right);             
					printf("sum(+) is: "); DispPoly(res);               
					FreePoly(&left); FreePoly(&right); FreePoly(&res);                      
					break;               
		    case 2: printf("input the first\n"); ReadPoly(&left);               
					printf("input the second\n"); ReadPoly(&right);                
					SubPoly(&res, left, right);              
					printf("the first: "); DispPoly(left);              
					printf("the second: "); DispPoly(right);                
					printf("sum(-) is: "); DispPoly(res);              
					FreePoly(&left); FreePoly(&right); FreePoly(&res);            
					break;           
			case 4: ReadPoly(&left);              
					DifPoly(&res, left);               
					printf("before qiuda "); DispPoly(left);             
					printf("after qiuda "); DispPoly(res);            
					FreePoly(&left); FreePoly(&res);              
					break;            
		    case 5: ReadPoly(&left);              
					printf("input x: ");               
					scanf("%d", &x);               
					val = CalcPoly(left, x);            
					DispPoly(left);               
					printf("x = %d\n", x);              
					printf("sum(x) is: %ld\n", val);           
					FreePoly(&left);               
					break;               
		            default:DispUsage();           
		}       
		            scanf("%d", &op);      
	}         
	return 0;
}