一元多项式的加法和乘法 c语言

男娘i 2022-04-24 03:30 210阅读 0赞

### 一元多项式的加法和乘法（C语言链表实现） ###

**题目**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70][]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 1]  
**总体结构：**

main函数

ReadPoly

Attach

Add

Mult

compare

PrintPoly

**各函数解释：**

<table> 
 <thead> 
  <tr> 
   <th>函数名</th> 
   <th>负责功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ReadPoly</td> 
   <td>读入数据</td> 
  </tr> 
  <tr> 
   <td>Attach</td> 
   <td>将数据构建成链表</td> 
  </tr> 
  <tr> 
   <td>Add</td> 
   <td>多项式相加</td> 
  </tr> 
  <tr> 
   <td>Mult</td> 
   <td>多项式相乘</td> 
  </tr> 
  <tr> 
   <td>compare</td> 
   <td>比较</td> 
  </tr> 
  <tr> 
   <td>PrintPoly</td> 
   <td>打印结果</td> 
  </tr> 
 </tbody> 
</table>

**代码**

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct PolyNode *Polynomial;
    struct PolyNode{ 
    	int coef;//系数
    	int expon;//指数 
    	Polynomial link;//链表指针域指向下一地址 
    };
    
    Polynomial ReadPoly();//读入多项式
    void Attach(int c,int e,Polynomial *pRear);//将每次读入的多项式连接 
    Polynomial Add(Polynomial P1,Polynomial P2);//多项式相加 
    Polynomial Mult(Polynomial P1,Polynomial P2);//多项式相乘 
    int Compare(int a,int b);//比较 
    void PrintPoly(Polynomial P);//输出多项式 
    
    
    int main(void)
    { 
    	Polynomial P1,P2,PS,PP;
    	
    	P1=ReadPoly();//读入数据
    	P2=ReadPoly();
    	
    	PP=Mult(P1,P2);//多项式相乘 
    	PrintPoly(PP);
    	
    	printf("\n");
    	
    	PS=Add(P1,P2);//多项式相加 
    	PrintPoly(PS);
    	
    	return 0;
    }
    
    
    Polynomial ReadPoly()//读入数据 
    { 
    	Polynomial P,Rear,t;
    	int c,e,N; 
    	scanf("%d",&N);
    	P=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头
    	P->link =NULL;
    	Rear=P;//Rear始终指向链表的尾部
    	while(N--)
    	{ 
    		
            scanf("%d %d",&c,&e);
            if(c!=0)//对系数为零的项进行判断 
    		Attach(c,e,&Rear);
    	}
    	t=P;//释放表头为空的节点 
    	P=P->link ;
    	free(t);
    	return P;
    }
    
    
    void Attach(int c,int e,Polynomial *pRear)//将数据连接成链表 
    { 
    	Polynomial P;
    	P=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头
    	P->coef=c;
    	P->expon=e;
    	P->link =NULL;
    	(*pRear)->link=P;//将P指向的新节点插入到当前结果表达式尾项的后面
    	*pRear=P;//最后一项指向P
    }
    
    int Compare(int a,int b)//比较 ，a>b return 1，a<b return -1, a==b return 0 
    { 
    	if(a>b)
    	return 1;
    	else if(a==b)
    	return 0;
    	else
    	return -1;
    }
    
    Polynomial Add(Polynomial P1,Polynomial P2)//多项式相加 
    { 
    	Polynomial front,rear,temp;//front为头，Rear为尾
    	int sum;
    	rear=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头
    	front=rear;
    	while(P1&&P2)
    		switch(Compare(P1->expon ,P2->expon))
    		{ 
    			case 1://如果P1->expon>P2->expon
    				Attach(P1->coef,P1->expon,&rear);
    				P1=P1->link ;
    				break;
    			case -1://如果P1->expon<P2->expon
    				Attach(P2->coef,P2->expon,&rear);
    				P2=P2->link ;
    				break;
    			case 0://如果P1->expon=P2->expon
    				sum=P1->coef +P2->coef;
    				if(sum)//如果指数相等，先判断系数和是否为0 
    				Attach(sum,P1->expon,&rear);
    				P1=P1->link;
    				P2=P2->link ;
    				break;
    		}
    		//将未处理完的多项式中所有节点复制到结果多项式中
    		while(P1)
    		{ 
    			Attach(P1->coef,P1->expon,&rear);
    			P1=P1->link;
    		}
    		while(P2)
    		{ 
    			Attach(P2->coef,P2->expon,&rear);
    			P2=P2->link;
    		}
    
    		rear->link=NULL;//释放头为空的节点 
    		temp=front;
    		front=front->link ;
    		free(temp);
    		return front;
    }
    
    void PrintPoly(Polynomial P)//打印 
    { 
    	int flag=0;
    	if(!P)
    	{ 
    		printf("0 0");
    		return ;
    	}
    	
    	while(P)
    	{ 
    		if(!flag)
    			flag=1;
    		else
    			printf(" ");
    		printf("%d %d",P->coef ,P->expon );
    		P=P->link ;
    	}
    }
    
    Polynomial Mult(Polynomial P1, Polynomial P2)//多项式相乘 
    { 
        Polynomial P, Rear;
        Polynomial t1, t2, t;
        if (!P1 ||!P2)//判断两个链表是否为空
        { 
            return NULL;
    
        }
        t1 = P1;
        t2 = P2;
        P = (Polynomial)malloc(sizeof(struct PolyNode));
        Rear = P;
        while (t2)//先让t1的第一项和t2的每一项相乘，构建出一个新链表，用于后来数据的插入
        { 
            Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
            t2 = t2->link;
        }
        t1 = t1->link;
    
        while (t1)
        { 
            t2 = P2;
            Rear = P;//Rear每次都从所构建的链表头开始，以便于寻找插入位置 
            while (t2) 
            { 
                int c = t1->coef*t2->coef;
                int e = t1->expon + t2->expon;
                while (Rear->link&&Rear->link->expon > e)//Rear每次都从所构建的链表头开始，以便于寻找插入位置 
                { 
                    Rear = Rear->link;
                }
                if (Rear->link&&Rear->link->expon == e)//相等就不需要申请一个新的节点，只要把系数相加。
                { 
                    if (Rear->link->coef + c)//系数和不为0，
                    { 
                        Rear->link->coef += c;
                    }
                    else//系数和为0，删除节点
                    { 
                        t = Rear->link;
                        Rear->link = t->link;
                        free(t);
                    }
                }
                else//如果指数不相等，申请空间将将此项插入
                { 
                    t = (Polynomial)malloc(sizeof(struct PolyNode));
                    t->link = NULL;
                    t->coef = c;
                    t->expon = e;
                    t->link = Rear->link;
                    Rear->link = t;
    
                    Rear = Rear->link;
                }
                t2 = t2->link;
            }
            t1 = t1->link;
        }
        t2 = P;//释放空节点 
        P = P->link;
        free(t2);
    
        return P;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190414154244905.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019041415454137.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3,size_16,color_FFFFFF,t_70