C语言实现一元多项式加法运算

说到一元多项式相加，相信很多小伙伴都不会陌生，甚至 “合并同类项” 已经要脱口而出了（因为上节课本人就是这样的哈哈~）回到正题，一元多项式的加法运算，大概是这样的：知道怎么操作了之后就来看看如何储存一元多项式叭：很明显为了方便操作，而且每一项都含有系数（coefficient）、指数（index），为了避免S形一元多项式带来的空间浪费，我们采用链式结构储存一元多项式，本题中采用普通的单链表进行

山野下

11551人浏览 · 2020-10-08 23:12:11

山野下 · 2020-10-08 23:12:11 发布

说到一元多项式相加，相信很多小伙伴都不会陌生，甚至 “合并同类项” 已经要脱口而出了（因为上节课本人就是这样的哈哈~）
回到正题，一元多项式的加法运算，大概是这样的：

在这里插入图片描述
知道怎么操作了之后就来看看如何储存一元多项式叭：
很明显为了方便操作，而且每一项都含有系数（coefficient）、指数（index），为了避免S形一元多项式带来的空间浪费，我们采用链式结构储存一元多项式，本题中采用普通的单链表进行储存（不需要方便访问头尾结点时可以不用循环链表）

话不多说，先整两个一元多项式看看↓
老规矩，数据类型和结构体定义先给出来
PNode、LinkList分别表示结点和链表，Datatype即int，coe为系数，ind为指数

//重定义类型和声明函数
typedef struct Node* PNode;
typedef struct Node* LinkList;
typedef int Datatype;
struct Node
{
	Datatype      coe;
	Datatype      ind;
	struct Node* next;
};
PNode Add_POLYA(LinkList head1, LinkList head2);

构建一元多项式：
ps:当接收到的系数和指数同时为0时停止输入，即一个多项式的结束

LinkList setnulllist_link()
{
	LinkList head = (LinkList)malloc(sizeof(struct Node));
	if (head != NULL) head->next = NULL;
	else printf("alloc failure");
	return head;
}

void createlist_tail(struct Node* head)
{
	PNode p = NULL;
	PNode q = head;
	Datatype coe;
	Datatype ind;
	printf("please input coefficient and index:\n");
	scanf_s("%d,%d", &coe, &ind);
	while ((coe != 0) || (ind != 0))
	{
		p = (struct Node*)malloc(sizeof(struct Node));
		p->coe = coe;
		p->ind = ind;
		p->next = NULL;
		q->next = p;
		q = p;
		scanf_s("%d,%d", &coe, &ind);
	}
	return;
}

再来看多项式相加函数：
ps:两个多项式的和最后储存在第一个多项式head1中，不喜欢的小伙伴也可以自行调整嗷~

PNode Add_POLYA(LinkList head1, LinkList head2)
{
	PNode pre = NULL, p = NULL, qre = NULL, q = NULL;
	pre = head1;
	p = head1->next;
	qre = head2;
	q = head2->next;
	if (qre == NULL)
	{
		return head1;
	}
	while (p != NULL)
	{
		if (q == NULL)
		{
			return head1;
		}
		//两个项指数相等时
		if (p->ind == q->ind)
		{
			p->coe = q->coe + p->coe;
			//两项和为0时
			if (p->coe == 0)
			{
				pre->next = p->next;
				free(p);
				p = pre->next;
				qre->next = q->next;
				free(q);
				q = qre->next;
			}
			else {
				pre = p;
				p = p->next;
				qre->next = q->next;
				free(q);
				q = qre->next;
			}
		}
		//多项式1的项的指数大于多项式2的项时
		else if (p->ind > q->ind)
		{
			qre->next = q->next;
			q->next = p;
			pre->next = q;
			pre = q;
			q = qre->next;
		}
		//多项式2的项指数大小在多项式1的项与下一项中间时
		else if (q->ind > p->ind && q->ind < (p->next)->ind)
		{
			qre->next = q->next;
			pre = p;
			p = p->next;
			q->next = p;
			pre->next = q;
			pre = q;
			q = qre->next;
		}
		else if (q->ind > p->ind && q->ind >= (p->next)->ind)
		{
			pre = p;
			p = p->next;
		}
	}

	return head1;
}

需要注意的就是两个项的指数大小问题（注意看上方的注释嗷~）
最后来看整体代码与运行结果：

//链式存储实现多项式加法
#include<stdio.h>
#include<stdlib.h> 

//重定义类型和声明函数
typedef struct Node* PNode;
typedef struct Node* LinkList;
typedef int Datatype;
struct Node
{
	Datatype      coe;
	Datatype      ind;
	struct Node* next;
};
PNode Add_POLYA(LinkList head1, LinkList head2);

LinkList setnulllist_link()
{
	LinkList head = (LinkList)malloc(sizeof(struct Node));
	if (head != NULL) head->next = NULL;
	else printf("alloc failure");
	return head;
}

void createlist_tail(struct Node* head)
{
	PNode p = NULL;
	PNode q = head;
	Datatype coe;
	Datatype ind;
	printf("please input coefficient and index:\n");
	scanf_s("%d,%d", &coe, &ind);
	while ((coe != 0) || (ind != 0))
	{
		p = (struct Node*)malloc(sizeof(struct Node));
		p->coe = coe;
		p->ind = ind;
		p->next = NULL;
		q->next = p;
		q = p;
		scanf_s("%d,%d", &coe, &ind);
	}
	return;
}

void print(LinkList head)
{
	PNode  p = head->next;
	while (p != NULL)
	{
		if (p->next != NULL) {
			printf("%d,%d ", p->coe, p->ind);
		}
		else {
			printf("%d,%d ", p->coe, p->ind);
		}
		p = p->next;
	}
	return;
}

void destorylist_link(LinkList head)
{
	PNode  pre = head;
	PNode p = pre->next;
	while (p)
	{
		free(pre);
		pre = p;
		p = pre->next;
	}
	free(pre);
	return;
}

int main()
{
	LinkList head1 = NULL, head2 = NULL;
	head1 = setnulllist_link();
	head2 = setnulllist_link();
	createlist_tail(head1);
	createlist_tail(head2);
	Add_POLYA(head1, head2);
	print(head1);
	destorylist_link(head1);
	system("pause");
	return 0;
}

PNode Add_POLYA(LinkList head1, LinkList head2)
{
	PNode pre = NULL, p = NULL, qre = NULL, q = NULL;
	pre = head1;
	p = head1->next;
	qre = head2;
	q = head2->next;
	if (qre == NULL)
	{
		return head1;
	}
	while (p != NULL)
	{
		if (q == NULL)
		{
			return head1;
		}
		//两项和为0时
		if (p->ind == q->ind)
		{
			p->coe = q->coe + p->coe;
			if (p->coe == 0)
			{
				pre->next = p->next;
				free(p);
				p = pre->next;
				qre->next = q->next;
				free(q);
				q = qre->next;
			}
			else {
				pre = p;
				p = p->next;
				qre->next = q->next;
				free(q);
				q = qre->next;
			}
		}
		//多项式1的项的指数大于多项式2的项时
		else if (p->ind > q->ind)
		{
			qre->next = q->next;
			q->next = p;
			pre->next = q;
			pre = q;
			q = qre->next;
		}
		//多项式2的项指数大小在多项式1的项与下一项中间时
		else if (q->ind > p->ind && q->ind < (p->next)->ind)
		{
			qre->next = q->next;
			pre = p;
			p = p->next;
			q->next = p;
			pre->next = q;
			pre = q;
			q = qre->next;
		}
		else if (q->ind > p->ind && q->ind >= (p->next)->ind)
		{
			pre = p;
			p = p->next;
		}
	}

	return head1;
}