目录

一、多项式的初始化

二、多项式的创建

三、多项式的加法

四、多项式的输出

五、清除链表

六、主函数



用链表实现多项式时,每个链表节点存储多项式中的一个非零项,包括系数(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;  // 将头节点的指针域置为空
}

二、多项式的创建

多项式链表是一个有序表 (P_n, P_{n-1}, ..., P_1, P_0) ​,每项的位置都要经过比较才能确定。

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
     

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

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐