用链表表示多项式，并实现多项式的加法运算

输入格式:

输入在第一行给出第一个多项式POLYA的系数和指数，并以0,0 结束第一个多项式的输入；在第二行出第一个多项式POLYB的系数和指数，并以0,0 结束第一个多项式的输入。

输出格式:

对每一组输入，在一行中输出POLYA+POLYB和多项式的系数和指数。

输入样例:

5,0 2,1 1,6 8,15 0,0
-2,1 3,6 4,8 0,0

输出样例:

5,0 4,6 4,8 8,15 

本题主要思路；

1.建立两个头指针分别为head1和head2链表，链表每一个节点分别记录每一个多项式的系数coef和指数exp.

2.preA遍历链表head1,preB遍历链表head2.

3.建立一个只有一个头节点的链表head,逐步遍历链表head1和head2.分别有如下三种情况

①preA->expexp,将节点preA利用尾插法插入链表head。

②preB->expexp,将节点preB利用尾插法插入链表head.

③preB->exp=preA->exp,这种情况分为两种

当preA->coef+preB->coef=0时：

释放节点preA和preB.

当preA->coef+preB->coef≠0时：

将多项式系数相同的项的指数相加，记录在preA,并利用尾插法将preA节点插如链表head.

相加的代码如下

 文章来源地址https://www.toymoban.com/news/detail-733744.html

void Add_Poly(PNode pa,PNode pb)
{
	PNode p = pa->next;    //链表1，和多项式的结果放在链表1中 
	PNode q = pb->next;
	PNode pre = pa;
	PNode u;
	float x;        //临时变量 
	while(p != NULL && q != NULL)
	{
		if(p->exp < q->exp)
		{
			//比较链表1和链表2当前节点的指数大小，链表1也是存放结果的地方
			pre = p;
			p = p->next;
			//p指向要比较的下一个节点，pre指向结果链表的最后一个节点 
		}
		else if(p->exp == q->exp)
		{
			//假如链表1和链表2的指数相等，则要系数相加
			x = p->coef + q->coef;
			if(x != 0)
			{
				//相加后的系数不是0，保留上一个节点就好了
				p->coef = x;
				pre = p; 
			 } 
			 else
			 {
			 	//相加后系数为0，不需要保留任何一个节点，删除链表1的节点
				 pre->next = p->next;
				 free(p); 
			 }
			 p=pre->next;     //p指向下一个节点
			 
			 //下面是进行链表2的删除工作
			 u = q;
			 q = q->next;
			 free(u); 
		}
		else
		{
			//如果链表2当前节点指数小，把链表2的当前节点加入到链表1中
			u = q->next;
			q->next = p;
			pre->next = q;
			pre = q;
			q = u; 
		}
	}
	if(q)
	{
		//如果链表2比链表1长，那么需要把链表2多余的部分加入到结果链表中
		//如果链表1比链表2长，则不需要任何操作
		pre->next = q; 
	}
	free(pb);
}	

完整代码如下：

#include<stdio.h>
#include<stdlib.h>

struct tagNode
{
	float coef;     //系数 
	int exp;        //指数
	struct tagNode *next;  //指针域 
};

typedef struct tagNode Node;
typedef struct tagNode *PNode;

void insertList(PNode head,PNode pnode)
{
	PNode pPre = head;
	while(pPre->next != NULL)
	{
		if(pPre->next->exp>pnode->exp)
		{
			pnode->next = pPre->next;
			pPre->next = pnode;
			break;
		}
		else
		{
			pPre = pPre->next;
		}
	}
	if(pPre->next == NULL)
	{
		pPre->next = pnode;
	}
}

void CreateList(PNode head)
{
	int exp;
	float coef;
	PNode pTemp = NULL;
	head->next = NULL;
	scanf("%f,%d",&coef,&exp);
	while(coef != 0 || exp != 0)
	{
		pTemp = (PNode)malloc(sizeof(struct tagNode));
		pTemp->coef = coef;
		pTemp->exp = exp;
		pTemp->next = NULL;
		insertList(head,pTemp);
		scanf("%f,%d",&coef,&exp);
	}
}

void printLinkedList(PNode head)
{
	PNode temp = head->next;
	while(temp != NULL)
	{
		printf("%0.0f,",temp->coef);
		printf("%d ",temp->exp);
		temp = temp->next;
	}
	printf("\n");
}

void Add_Poly(PNode pa,PNode pb)
{
	PNode p = pa->next;    //链表1，和多项式的结果放在链表1中 
	PNode q = pb->next;
	PNode pre = pa;
	PNode u;
	float x;        //临时变量 
	while(p != NULL && q != NULL)
	{
		if(p->exp < q->exp)
		{
			//比较链表1和链表2当前节点的指数大小，链表1也是存放结果的地方
			pre = p;
			p = p->next;
			//p指向要比较的下一个节点，pre指向结果链表的最后一个节点 
		}
		else if(p->exp == q->exp)
		{
			//假如链表1和链表2的指数相等，则要系数相加
			x = p->coef + q->coef;
			if(x != 0)
			{
				//相加后的系数不是0，保留上一个节点就好了
				p->coef = x;
				pre = p; 
			 } 
			 else
			 {
			 	//相加后系数为0，不需要保留任何一个节点，删除链表1的节点
				 pre->next = p->next;
				 free(p); 
			 }
			 p=pre->next;     //p指向下一个节点
			 
			 //下面是进行链表2的删除工作
			 u = q;
			 q = q->next;
			 free(u); 
		}
		else
		{
			//如果链表2当前节点指数小，把链表2的当前节点加入到链表1中
			u = q->next;
			q->next = p;
			pre->next = q;
			pre = q;
			q = u; 
		}
	}
	if(q)
	{
		//如果链表2比链表1长，那么需要把链表2多余的部分加入到结果链表中
		//如果链表1比链表2长，则不需要任何操作
		pre->next = q; 
	}
	free(pb);
}	
	
int main()
{
	PNode head1 = (PNode)malloc(sizeof(struct tagNode));
	PNode head2 = (PNode)malloc(sizeof(struct tagNode));
	CreateList(head1);
	CreateList(head2);
	Add_Poly(head1,head2);
	printLinkedList(head1);
	return 0;
	
}	
	

测试结果如下：

 

到了这里，关于用链表表示多项式，并实现多项式的加法运算的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！