《数据结构》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

分析

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

  1. 指数相同,系数相加
  2. 指数不同,取指数大的结点

存在特殊情况:即系数和为 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;
} 
全部评论

相关推荐

人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务