《数据结构》02-线性结构2 一元多项式的乘法与加法运算

题目

设计函数分别求两个一元多项式的乘积与和。

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

分析

链表一直是硬伤，所以这道题我选择了硬刚链表实现
实现加法：

指数相同，系数相加
指数不同，取指数大的结点

存在特殊情况：即系数和为 0 ，此时要不就跳过此结点，要不输出的时候控制不输出，我选择输出的时候控制不输出

实现乘法：系数相乘，指数相加
实现乘法其实就很迷了，因为加法加起来很自然的就能递减排列，但是乘法结果的指数难以控制，不过我们可以借助前面实现的加法，具体做法如下：循环两相乘链表，每次取两链表的某一结点，相乘得出结果，再将结果结点和之前排好序的链表进行加法计算，由于一端只有单一结点，会很自然地插入在之前排好序的链表中，这样就实现了乘法

#include<stdio.h>
#include<stdlib.h>
typedef struct Node *List;
struct Node{
	List Next;
	int z;   // 指数 
	int x;  // 系数 
};

// 读入链表 
List Read(){
	List L = (List)malloc(sizeof(struct Node));
	List head = L;
	int n;
	int i=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		int x;
		int z;
		List t = (List)malloc(sizeof(struct Node));
		scanf("%d %d",&x,&z);
		t->x = x;
		t->z = z;
		L->Next = t;
		L = L->Next;
	}
	L->Next = NULL;
	return head->Next;
}

// 实现加法运算 
List addition(List L1,List L2){
	List tmpL1 = L1;
	List tmpL2 = L2;
	List add=(List)malloc(sizeof(struct Node));
	add->Next = NULL;
	List head = add;
	List t;
	while(tmpL1 && tmpL2){
		t = (List)malloc(sizeof(struct Node));
		if(tmpL1->z == tmpL2->z){  //指数相等，系数相加 
			t->x = tmpL1->x + tmpL2->x;
			t->z = tmpL1->z;
			tmpL1 = tmpL1->Next;
			tmpL2 = tmpL2->Next;
		}else if(tmpL1->z < tmpL2->z){   // L2 结点指数更大，把 L2 结点加入链表 
			t->x = tmpL2->x;
			t->z = tmpL2->z;
			tmpL2 = tmpL2->Next;
		}else if(tmpL2->z < tmpL1->z){   // L1 结点指数更大，把 L1 结点加入链表 
			t->x = tmpL1->x;
			t->z = tmpL1->z;
			tmpL1 = tmpL1->Next;
		}
		add->Next = t;
		add = add->Next; 
	}
	if(tmpL1)   // 若 L1 不等于 NULL，将剩下结点加入其后 
		add->Next = tmpL1;
	else if(tmpL2)  // 同理 
		add->Next = tmpL2;
	return head->Next; // head 结点只有指针域存值 
}

// 实现乘法运算 
List multiplication(List L1,List L2){
	List tmpL1 = L1;
	List tmpL2 = L2;
	List mul=(List)malloc(sizeof(struct Node));
	mul->Next = NULL;
	List head = mul;
	List t;
	for(;tmpL1;tmpL1=tmpL1->Next)
		for(tmpL2 = L2;tmpL2;tmpL2=tmpL2->Next){
			t = (List)malloc(sizeof(struct Node));
			t->x = tmpL1->x * tmpL2->x;  // 系数相乘
			t->z = tmpL1->z + tmpL2->z;  // 指数相加
			t->Next = NULL;
			head = addition(t,mul);  // 将新增结点和之前已经排好序的结点排序 
			mul = head; // 重新确定开头 
		}
	return head;
}
void Print(List L){
	List t = L;
	int flag = 1;
	for(;t;t = t->Next){
		if(!flag && t->x)   //控制空格输出
			printf(" ");
		if(t->x){   // 如果系数为 0，不输出 
			printf("%d %d",t->x,t->z);
			flag =0;		
		}
	}
	if(flag)
		printf("0 0");
	printf("\n");
}
int main(){
	List L1,L2,add,mul;
	L1 = Read();
	L2 = Read();
	add = addition(L1,L2);
	mul = multiplication(L1,L2);
	Print(mul);
	Print(add);
	return 0;
}