一元多项式相乘链表的实现

刺骨的言语ヽ痛彻心扉 2022-06-01 12:52 204阅读 0赞

**一、题目**

将两个一元多项式相乘，最后将相乘的结果输出。

一元多项式指数默认递增。输入时依次输入每项系数和指数。

比如：

多项式A：1+2\*x-4\*x^4

多项式B：2-2\*x+5^x^4

输入：

0 1 2 1 -4 4 0 0

2 0 -2 1 5 4 0 0

输出：

2+2\*x+13\*x^5+20\*x^8

**二、题目分析**

首先得会一元多项式的相加：[点击打开链接][Link 1]

注意：如果单纯的使用多个一元多项式相加，由于不知道链表的长度，不能建立与链表长度数相同的多项式个数。则需重新建立新链表在其上累加，且保证要相加两链表的不变。

一种写法是利用递归函数。还有一种是利用循环。

建立链表可以用单链表，由于多次用到所指元素的前一个节点，也可以用双向链表。

下面是利用单链表及循环实现目标。

#include<stdio.h>
    #include<stdlib.h>
    typedef struct Node
    {
    	int coef;//coefficient:系数
    	int index;//index:指数
    	struct Node *next; 
    }node;
    
    node *creat()
    {
    	int coef,index;
    	node *head,*p;
    	head=(node *)malloc(sizeof(node));
    	p=head;
    	while(1)//系数和指数都为0，作为结束标识 
    	{
    		scanf("%d",&coef);
    		scanf("%d",&index);
    		if(coef==0&&index==0)
    			break;
    		p->next=(node *)malloc(sizeof(node));
    		p=p->next;
    		p->coef=coef;
    		p->index=index;
    	}
    	p->next=NULL;
    	return head;
    } 
    
    node *ridepolylist(node *la,node *lb)//ride：乘
    {
    	int temp1,temp2;
    	node *p;
    	node *lc;
    	node *pa,*pb,*pc;
    	node *pc1,*pc2; 
    	pa=la->next;
    	pb=lb->next;
    	//复制la指数到lc中 
    	lc=(node *)malloc(sizeof(node));
    	lc=pc;
    	while(pa)
    	{
    		pc->next=(node *)malloc(sizeof(node));
    		pc=pc->next;
    		pc->coef=0;//lc初始化系数为0 
    		pc->index=pa->index;
    		pa=pa->next;
    	} 
    	pc->next=NULL; 
    	//复制完成
    	//逐项相乘 
    	pa=la->next;
    	while(pa)
    	{
    		pb=lb->next;
    		while(pb)
    		{
    			pc1=lc;
    			pc2=pc1->next;
    			temp1=(pa->coef)*(pb->coef);
    			temp2=(pa->index)+(pb->index);
    			while(pc2)//寻找在lc中位置 
    			{
    				if(pc2->index<temp2)
    				{
    					pc1=pc2;
    					pc2=pc1->next;
    				}
    				else if(pc2->index==temp2)
    				{
    					pc2->coef=pc2->coef+temp1;//如果是0进行最后处理 
    					break;
    				}
    				else
    				{
    					//这里要插在前方，用单项链表不好写，建立时应该用双向链表 
    					p=(node *)malloc(sizeof(node));
    					p->coef=temp1;
    					p->index=temp2;
    					pc1->next=p;
    					p->next=pc2;
    					break;
    				}	
    			}
    			if(!pc2)//插在最后位置
    			{
    				p=(node *)malloc(sizeof(node));
    				p->coef=temp1;
    				p->index=temp2;
    				pc1->next=p;
    				p->next=NULL; 
    			}
    			pb=pb->next; 
    		}
    		pa=pa->next;
    	}
    	return lc;	
    } 
    
    
    node *delay0elem(node *lc)//删除 
    {
    	node *p,*q;
    	p=lc;
    	q=p->next;
    	while(q)
    	{
    		if(q->coef==0)
    		{
    			p->next=q->next;
    		}
    		p=q;
    		q=p->next;
    	}
    	return lc;
    }
    
    void pri(node *head)
    {
    	node *p;
    	p=head->next;
    	while(p)
    	{
    		printf("+%d*x^%d ",p->coef,p->index);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    
    void main()
    {
    	node *creat();
    	node *ridepolylist(node *la,node *lb);
    	node *delay0elem(node *lc);
    	void pri(node *head);
    	
    	node *la,*lb,*lc;
    	
    	printf("输入多项式la,以0 0作为结束标识："); 
    	la=creat();
    	pri(la);
    	
    	printf("输入多项式lb,以0 0作为结束标识：");
    	lb=creat();
    	pri(lb);
    	
    	printf("输出两多项式乘机lc：");
    	lc=ridepolylist(la,lb); 
    	lc=delay0elem(lc);
    	pri(lc);
    }

**四、代码分析**  
lc链表初始化时，复制了la.这步可以省略。它可以包含在创立新节点的情况里。

![Image 1][]

**![Image 1][]**

[Link 1]: http://blog.csdn.net/sinat_38816924/article/details/79199399
[Image 1]: