目录

一、多项式的初始化

二、多项式的创建

三、多项式的加法

四、多项式的输出

五、清除链表

六、主函数

---

---

用链表实现多项式时，每个链表节点存储多项式中的一个非零项，包括系数（coef）和指数（exp）两个数据域以及一个指针域（next）。对应的数据结构定义为：

typedef struct Node
{
    int coef;  // 系数
    int exp;  // 指数
    struct Node* next;
}Node, *Link;

一个多项式可以表示成由这些节点链接起来的单链表。

一、多项式的初始化

单向非循环链表可以分为以下两种：

1. 不设头结点的单向非循环链表

   

2. 设头结点的单向非循环链表

   

本次程序采用第二种。

void InitPoyln(Link* phead)
{
    assert(phead);  // phead 是指向头指针的指针，是一个二级指针
    *phead = (Node*)malloc(sizeof(Node));  // 生成新节点作为头节点
    if (NULL == *phead)
    {
        perror("initialization failed!");
        exit(-1);
    }
    (*phead)->next = NULL;  // 将头节点的指针域置为空
}

二、多项式的创建

多项式链表是一个有序表  ​，每项的位置都要经过比较才能确定。

void CreatePoyln(Link head, int n)
{
	assert(head);  // 头指针指向头节点
	for (int i = 0; i < n; ++i)
	{
		// 生成新节点
		Node* newnode = (Node*)malloc(sizeof(Node));  
		assert(newnode);
		scanf("%d %d", &newnode->coef, &newnode->exp);
		if (newnode->coef == 0)  // 只保存系数不为 0 的项
		{
			free(newnode);
			continue;
		}
		newnode->next = NULL;
		// 插入
		Node* prev = head;
		Node* cur = head->next;
		while (cur != NULL)
		{
			if (cur->exp == newnode->exp)
			{
				// 合并 cur 和 newnode
				int sum = cur->coef + newnode->coef;
				if (sum != 0)
				{
					cur->coef = sum;
					free(newnode);
				}
				else
				{
					prev = cur->next;
					Node* tmp = cur;
					cur = cur->next;
					free(tmp);
					free(newnode);
				}
				break;
			}
			else if (cur->exp > newnode->exp)
			{
				prev = cur;
				cur = cur->next;
			}
			else  // cur->exp < newnode->exp
			{
				// 将 newnode 插入到 prev 和 cur 之间
				prev->next = newnode;
				newnode->next = cur;
				break;
			}
		}
		if (cur == NULL)
		{
			prev->next = newnode;
		}
	}
}

三、多项式的加法

void AddPolyn(Link headA, Link headB)
{
	assert(headA != NULL && headB != NULL);
	Node* tail = headA;
	Node* curA = headA->next;
	Node* curB = headB->next;
	while (curA && curB)
	{
		if (curA->exp == curB->exp)
		{
			int sum = curA->coef + curB->coef;
			if (sum != 0)
			{
				curA->coef = sum;
				tail->next = curA;
				tail = curA;
				curA = curA->next;
                
				Node* tmp = curB;
				curB = curB->next;
				free(tmp);
			}
			else
			{
				Node* tmp = curA;
				curA = curA->next;
				free(tmp);
				tmp = curB;
				curB = curB->next;
				free(tmp);
			}
		}
		else if (curA->exp > curB->exp)
		{
			tail->next = curA;
			tail = curA;
			curA = curA->next;
		}
		else  // curA->exp < curB->exp
		{
			tail->next = curB;
			tail = curB;
			curB = curB->next;
		}
	}
	tail->next = curA ? curA : curB;
	free(headB);  // 释放 headB 指向的头节点
}

四、多项式的输出

void PrintPolyn(Link head)
{
	assert(head);
	Node* cur = head->next;
	int first = 1;
	while (cur != NULL)
	{
		// 输出正负号
		if (first)
		{
			if (cur->coef < 0)
				printf("%c", '-');
			first = 0;
		}
		else
		{
			if (cur->coef < 0)
				printf("%c", '-');
			else
				printf("%c", '+');
		}

		// 输出系数的绝对值
		if ((cur->exp > 0 && cur->coef != 1) || cur->exp == 0)
			printf("%d", abs(cur->coef));

		// 输出自变量 x
		if (cur->exp > 0)
			printf("%c", 'x');

		// 输出 ^exp
		if (cur->exp > 1)
			printf("%c%d", '^', cur->exp);

		cur = cur->next;  // 指向多项式的下一项
	}
	printf("\n");
}

五、清除链表

void ClearLink(Link head)
{
	assert(head);
	Node* cur = head->next;
	while (cur != NULL)
	{
		Node* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	free(head);
}

六、主函数

#include "Polyn.h"

int main()
{
	Link headA;
	Link headB;
	InitPoyln(&headA);
	InitPoyln(&headB);

	int nA = 0;
	int nB = 0;
	scanf("%d", &nA);
	CreatePoyln(headA, nA);
	printf("第一个多项式为：");
	PrintPolyn(headA);

	scanf("%d", &nB);
	CreatePoyln(headB, nB);
	printf("第二个多项式为：");
	PrintPolyn(headB);

	AddPolyn(headA, headB);
	printf("两个多项式的和为：");
	PrintPolyn(headA);

	ClearLink(headA);
	return 0;
}

1. 样例输入 1：

   4
   3 2
   4 5
   1 1
   2 3
   3
   -3 2
   -4 5
   2 4

   样例输出 1：

   第一个多项式为：4x^5+2x^3+3x^2+x
   第二个多项式为：-4x^5+2x^4-3x^2
   两个多项式的和为：2x^4+2x^3+x

2. 样例输入 2：

   2
   0 1
   2 3
   3
   2 6
   3 9
   4 3

   样例输出 2：

   第一个多项式为：2x^3
   第二个多项式为：3x^9+2x^6+4x^3
   两个多项式的和为：3x^9+2x^6+6x^3

3. 样例输入 3：

   3
   4 2
   -2 2
   -1 2
   2
   0 2
   6 2

   样例输出 3：

   第一个多项式为：x^2
   第二个多项式为：6x^2
   两个多项式的和为：7x^2
    

创作不易，可以点点赞，如果能关注一下博主就更好了~