数据结构学习（三）多项式加法链式实现

た入场券 2022-08-09 14:56 194阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    typedef struct Node *ListNode;
    struct Node 
    {
    	int coeff;
    	int expo;
    	ListNode next;
    
    };
    
    ListNode initList(ListNode poly);
    void insert(ListNode poly, int coeff, int expo);
    void addPoly(ListNode polya, ListNode polyb);
    
    int main(){
    	ListNode polya, polyb;
    	int a, b;
        initList(polya);
        initList(polyb);
    
    	printf("输入第一个多项式：\n");
        while (a!='\0')
        {
        	scanf("%d",&a);
        	scanf("%d",&b);
            insert(polya, a, b);
        }
        printf("输入第二个多项式：\n");
        while (a!="\0")
        {
        	scanf("%d",&a);
        	scanf("%d",&b);
            insert(polyb, a, b);
        }
        addPoly(polya, polyb);
        return 0;    
    }
    ListNode initList(ListNode poly)
    {
    	poly=(ListNode)malloc(sizeof(struct Node));
    	poly->next=NULL;
    	return poly;
    }
    void insert(ListNode poly, int coeff, int expo)
    {
    	ListNode pre=poly, new;
    	new=(ListNode)malloc(sizeof(struct Node));
    	for(pre=poly;pre->next;pre=pre->next);
    	
        new->coeff=coeff;
        new->expo=expo;
        new->next=NULL;
        pre->next=new;
    }
    void addPoly(ListNode polya, ListNode polyb)
    {   
    	ListNode polyadd;
    	initList(polyadd);
    	ListNode ptra=polya, ptrb, ptradd;
    	for(ptrb=polyb; ptra&&ptrb; )
    	{
    		if(ptra->expo > ptrb->expo)
    		{
    			insert(polyadd, ptra->coeff, ptra->expo);
    			ptra=ptra->next;
    		}else 
    		if (ptra->expo < ptrb->expo)
    		{
    			insert(polyadd, ptrb->coeff, ptrb->expo);
    			ptrb=ptrb->next;
    		}else
    		{
    			if(ptra->coeff+ptrb->coeff!=0)
    			{
    				insert(polyadd, ptra->coeff+ptrb->coeff, ptra->expo);
    			}
    			ptra=ptra->next; ptrb=ptrb->next;
    		}
    	}
    	if(ptra)
    	{
    		for(;ptra;ptra=ptra->next)
    		{
    			insert(polyadd, ptra->coeff, ptra->expo);
    		} 
    	}else
    	if(ptrb)
    	{
    		for(;ptrb;ptrb=ptrb->next)
    		{
    			insert(polyadd, ptrb->coeff, ptrb->expo);
    		}
    	}
    	for(ptradd=polyadd;ptradd;ptradd=ptradd->next)
    	{   
    		if(ptradd->next)
    			printf("%d x^%d +", ptradd->coeff, ptradd->expo);
    	    else 
    	    	printf("%d x^%d ", ptradd->coeff, ptradd->expo);
    	}
    }