游客 注册 | 登录
中文 | En

2606 - 多项式相加

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

一条单链表可以表示一个一元多项式，每个节点包含三个域：指数、系数和后继节点（指针或引用）。

表示多项式3X4-6X2+5X-10的单链表如图所示。给定两个多项式，实现两个多项式相加算法。

题目输入

第一行输入包含两个整数m,n

后续为m行和n行数据

m，n分别代表两个多项式的项数

后续每一行代表多项式的项，包含a,b两个数据，表示该项的系数和指数。

题目输出

从较高指数到较低指数，依次输出求得的和。

每行一项，格式与输入相同，但无需输出项数，系数为0的项也不输出。

输入/输出样例

输入格式

2 3
1 2
1 1
2 2
1 1
2 0

输出格式

3 2
2 1
2 0

C++解答

#include <stdio.h>
#include <malloc.h>

typedef struct LNode {
	int data; //系数
	int index; //指数
	struct LNode *next;
} LNode;

void init(LNode *&L, int data, int index) {
	LNode *s, *p, *q;
	s = L;
	p = L -> next;
	q = (LNode *) malloc(sizeof(LNode));
	q -> next = NULL;
	q -> data = data;
	q -> index = index;

	if (p) {
		int subIndex;

		while (p) {
			subIndex = q -> index - p -> index;

			if (subIndex > 0) {
				q -> next = p;
				s -> next = q;
				break;
			}
			
			if (subIndex == 0) {
				p -> data += q -> data; //系数相加,指数不变
				free(q);
				break;
			}

			s = p;
			p = p -> next;
		}

		if (p == NULL) {
			q -> next = p;
			s -> next = q;
		}
		
	} else {
		q -> next = p;
		s -> next = q;
	}
}

void output(LNode *L) {
	LNode *p;
	p = L -> next;
	while (p) {
		if (p -> data != 0) {
			printf("%d %d\n", p -> data, p -> index);
		}
		p = p -> next;
	}
}

int main() {
	int i;
	int m, n;
	int data, index;
	LNode *L;
	L = (LNode *) malloc(sizeof(LNode));
	L -> next = NULL;

	scanf("%d %d", &m, &n);

	for (i = 1; i <= m+n; ++i) {
		fflush(stdin);
		scanf("%d %d", &data, &index);
		
		if (data != 0) { //系数不为0时，才插入链表
			init(L, data, index);
		}
	}

	output(L);

	return 0;
}
请先登陆