一元多项式的加法和乘法运算(Java实现)——浙大数据结构(陈越)_用java编写一个程序实现两个一元多项式相乘。csdn-程序员宅基地

技术标签: 算法  多项式  java  数据结构  数据结构||浙江大学陈越课后题系列  

输入格式: 输入分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

其他:
  • 时间限制:200ms
  • 内存限制:64MB
  • 代码长度限制:16kB
  • 解题思路:

    按照多项式的乘法和加法规则来编写代码即可,只是在选用数据结构的时候看您要怎么选。

    可以用数组实现,因为输入里已经确定数组的大小了,但是因为是复习巩固链表知识,所以我采用了单链表来存储数据,单链表的工作方式和队列一样FIFO,所以代码中创建了一个Queue类。这个队列到底是什么样的,其实是仁者见仁,智者见智。我个人认为当你用到它们的时候可以方便您地这个数据结构就是好的,不一定要和教科书上的一模一样。

    当队列为空的时候,是这样子的:

    置顶        一元多项式的乘法与加法运算Java实现通过单项链表实现队列

    当插入元素的时候是这个样子的:

    置顶        一元多项式的乘法与加法运算Java实现通过单项链表实现队列

    头节点(front节点)的数据域始终是空的;尾节点(rear节点)的next域始终是空的,当队列为空时,数据域也是空的,但插入数据时从尾节点开始插入,所以队列不空,尾节点的数据域也不空。

    队列的操作可以按需来写。

    Jvav代码如下:

    package cn.eee.www;
    
    import java.util.Scanner;
    public class Test5 {
    	public static void main(String[] args) {
    		//读入多项式,以指数递降方式输入,非零项系数
    		Scanner sc=new Scanner(System.in);
    		Queue queueA=readNomal(sc);
    		Queue queueB=readNomal(sc);
    		
    		Queue MulResult=mulQ(queueA,queueB);//多项式乘法计算
    		MulResult.printQ();//输出计算后的多项式
    		
    		Queue AddResult=addQ(queueA,queueB);//多项式加法计算
    		AddResult.printQ();//输出计算后的多项式
    	}
    	//读入多项式的方法
    	public static Queue readNomal(Scanner sc){
    		int m=sc.nextInt();
    		Queue queue=new Queue();
    		for(int i=0;i<m;i++){
    			Node node=new Node(sc.nextInt(),sc.nextInt());
    			queue.enQueue(node);
    		}
    		return queue;
    	}
    	//多项式相乘的方法
    	public static Queue mulQ(Queue queueA,Queue queueB){
    		Queue queueMul=new Queue();
    		Node nodeACurrent=queueA.getFistNode();
    		Node nodeBCurrent=queueB.getFistNode();
    		while(nodeACurrent!=null){//第二个多项式的第一项和第一个多项式的所有项相乘,得到初始多项式
    			queueMul.enQueue(new Node(nodeACurrent.getCoe()*nodeBCurrent.getCoe(),nodeACurrent.getExp()+nodeBCurrent.getExp()));
    			nodeACurrent=nodeACurrent.next;
    		}
    		nodeBCurrent=nodeBCurrent.next;
    		while(nodeBCurrent!=null){//queueB中每一个元素和queueA相乘
    			nodeACurrent=queueA.getFistNode();
    			while(nodeACurrent!=null){//queueB中某一个元素和queueA中每一个元素相乘
    				Node nodeMul=new Node(nodeBCurrent.getCoe()*nodeACurrent.getCoe(),nodeBCurrent.getExp()+nodeACurrent.getExp());//待插入的节点
    				//在初始多项式中找插入的位置并且插入到多项式中
    				Node nodeMulCurrent=queueMul.getFistNode();
    				Node nodeMulPrev=queueMul.getFront();
    				while(nodeMulCurrent!=null){
    					if(nodeMul.getExp()<nodeMulCurrent.getExp()){
    						if(nodeMulCurrent==queueMul.getRear()){//指数比rear节点小,则插入到rear节点后面
    							nodeMulCurrent.next=nodeMul;
    							queueMul.setRear(nodeMul);
    							break;
    						}else{
    							nodeMulCurrent=nodeMulCurrent.next;
    							nodeMulPrev=nodeMulPrev.next;
    						}
    					}else if(nodeMul.getExp()==nodeMulCurrent.getExp()){//合并同类项,插入
    						if((nodeMul.getCoe()+nodeMulCurrent.getCoe())==0){//合并系数是零就要删除
    							
    							if(nodeMulCurrent==queueMul.getRear()){//要删除的这个节点是rear节点
    								
    								if(nodeMulPrev==queueMul.getFront()){//要删除的这个节点是多项式的rear节点,并且rear节点上唯一的数据节点,则把数据域赋值为零就行
    									nodeMulCurrent.setCoe(0);
    									nodeMulCurrent.setExp(0);
    								}else if(nodeMulPrev!=queueMul.getFront()){//要删除的这个rear节点前面还有数据节点,则rear节点指向前一个节点(直接删除该节点)
    									queueMul.setRear(nodeMulPrev);
    									nodeMulPrev.next=null;
    								}
    							}else{//要删除的这个节点不是rear节点,直接删除
    								nodeMulPrev.next=nodeMulCurrent.next;
    							}
    							
    						}else{//插入
    							nodeMulCurrent.setCoe(nodeMul.getCoe()+nodeMulCurrent.getCoe());
    						}
    						break;
    						
    					}else if(nodeMul.getExp()>nodeMulCurrent.getExp()){
    						//插入到该节点的前面
    						nodeMul.next=nodeMulCurrent;
    						nodeMulPrev.next=nodeMul;
    						break;
    					}
    				}
    				nodeACurrent=nodeACurrent.next;
    			}
    			nodeBCurrent=nodeBCurrent.next;
    		}
    		return queueMul;
    	}
    	
    	//多项式相加的方法
    	public static Queue addQ(Queue queueA,Queue queueB){
    		Queue queueAdd=new Queue();
    		while((!queueA.isEmpty())&&(!queueB.isEmpty())){
    			Node currentA=queueA.getFistNode();
    			Node currentB=queueB.getFistNode();
    			if(currentA.getExp()>currentB.getExp()){
    				Node temp=new Node(currentA.getCoe(),currentA.getExp());
    				queueAdd.enQueue(temp);queueA.deQueue();
    			}else 
    				if(currentA.getExp()<currentB.getExp()){
    				Node temp=new Node(currentB.getCoe(),currentB.getExp());
    				queueAdd.enQueue(temp);
    				queueB.deQueue();
    			}else
    			if(currentA.getExp()==currentB.getExp()){
    				Node temp=new Node(currentA.getCoe()+currentB.getCoe(),currentA.getExp());
    				if(temp.getCoe()!=0){
    					queueAdd.enQueue(temp);
    				}
    				queueA.deQueue();
    				queueB.deQueue();
    			}
    		}
    		while(!queueA.isEmpty()){
    			Node currentA=queueA.getFistNode();
    			Node temp=new Node(currentA.getCoe(),currentA.getExp());
    			queueAdd.enQueue(temp);
    			queueA.deQueue();
    		}
    		while(!queueB.isEmpty()){
    			Node currentB=queueB.getFistNode();
    			Node temp=new Node(currentB.getCoe(),currentB.getExp());
    			queueAdd.enQueue(temp);
    			queueB.deQueue();
    		}
    		return queueAdd;
    	}
    
    }
    class Node{//链表节点类
    	private int coe;//系数
    	private int exp;//指数
    	Node next;
    	public Node(int c,int e){
    		this.coe=c;
    		this.exp=e;
    		this.next=null;
    	}
    	public Node(){
    		this.coe=0;
    		this.exp=0;
    		this.next=null;
    	}
    	public int getCoe(){
    		return this.coe;
    	}
    	public int getExp(){
    		return this.exp;
    	}
    	public void setCoe(int c){
    		this.coe=c;
    	}
    	public void setExp(int e){
    		this.exp=e;
    	}
    }
    class Queue{//用单向链表实现的队列(头节点的数据域是空的)
    	private Node front;
    	private Node rear;
    	public Queue(){//创建一个头节点(元素为空)指向尾节点(元素为空)的空队列
    		this.front=new Node();
    		this.rear=new Node();
    		this.front.next=this.rear;
    	}
    	public boolean isEmpty(){
    		if(this.rear.getCoe()==0){
    			return true;
    		}else{
    			return false;
    		}
    	}
    	public void enQueue(Node node){//从队尾插入一个节点(入队)
    		if(this.isEmpty()){
    			this.front.next=node;
    			this.rear=node;
    		}else{
    			this.rear.next=node;
    			node.next=null;
    			this.rear=node;
    		}
    	}
    	public void deQueue(){//从队头删除节点(出队)
    		Node node=this.front;
    		if(this.isEmpty()){
    			System.out.println("空队列,不可删除节点");
    		}else if(this.getFistNode()==this.rear && this.rear.getCoe()!=0){
    			this.rear.setCoe(0);
    			this.rear.setExp(0);
    		}else{
    			node.next=this.getFistNode().next;
    		}
    	}
    	public Node getFistNode(){
    		return this.front.next;
    	}
    	public Node getFront(){
    		return this.front;
    	}
    	public Node getRear(){
    		return this.rear;
    	}
    	public void setFront(Node node){
    		this.front=node;
    	}
    	public void setRear(Node node){
    		this.rear=node;
    	}
    	public void printQ(){
    		Queue q=this;
    		if(q.isEmpty()){
    			System.out.print(0+" "+0);
    		}else{
    			Node node=q.getFistNode();
    			System.out.print(node.getCoe()+" "+node.getExp());
    			q.deQueue();
    			while(!q.isEmpty()){
    				node=q.getFistNode();
    				System.out.print(" "+node.getCoe()+" "+node.getExp());
    				q.deQueue();
    			}
    		}
    		System.out.println();
    	}
    }







    输入格式: 输入分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

    其他:
  • 时间限制:200ms
  • 内存限制:64MB
  • 代码长度限制:16kB
  • 解题思路:

    按照多项式的乘法和加法规则来编写代码即可,只是在选用数据结构的时候看您要怎么选。

    可以用数组实现,因为输入里已经确定数组的大小了,但是因为是复习巩固链表知识,所以我采用了单链表来存储数据,单链表的工作方式和队列一样FIFO,所以代码中创建了一个Queue类。这个队列到底是什么样的,其实是仁者见仁,智者见智。我个人认为当你用到它们的时候可以方便您地这个数据结构就是好的,不一定要和教科书上的一模一样。

    当队列为空的时候,是这样子的:

    置顶        一元多项式的乘法与加法运算Java实现通过单项链表实现队列

    当插入元素的时候是这个样子的:

    置顶        一元多项式的乘法与加法运算Java实现通过单项链表实现队列

    头节点(front节点)的数据域始终是空的;尾节点(rear节点)的next域始终是空的,当队列为空时,数据域也是空的,但插入数据时从尾节点开始插入,所以队列不空,尾节点的数据域也不空。

    队列的操作可以按需来写。

    JAVA代码如下
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zjkC050818/article/details/53610464

智能推荐

OpenCV之增强图像对比度与亮度_opencv.js 亮度-程序员宅基地

文章浏览阅读3.8k次。通过一个一元一次方程的参数控制增强亮度与对比度。#include &lt;iostream&gt;#include &lt;opencv2/opencv.hpp&gt;using namespace std;using namespace cv;int main(int argc, char* argv[]){ Mat src,dest; src = imread("D:/test/b.jpg")..._opencv.js 亮度

一年Android工作经验,阿里/百度/网易/美团/小米/快手面经_小米跳槽阿里-程序员宅基地

文章浏览阅读319次。转载自:http://blog.csdn.net/csdnsevenn/article/details/79386137前 言人生困难重重,在漫长而艰辛的前行路上,坚持不懈、脚踏实地的“低头拉车”固然重要。但认清形势、找准目标的“抬头看路”也很关键,甚至决定着你能否达到成功彼岸。只寻求远方的梦想,而不付出当下的努力,那是迷梦;只知道埋头苦干,而不认清方向,那是徒劳。先简单说说我最近的面试经历..._小米跳槽阿里

01-服务端测试做什么?_服务端测试是什么-程序员宅基地

文章浏览阅读6.9k次,点赞6次,收藏61次。服务端测试做什么?作者:钱蓓蕾 链接:https://www.zhihu.com/question/29164912/answer/110735124一般来说,服务端测试有两种:一种是直接对WEB或者APP的服务端进行测试;另一种是对更后端的数据库、缓存系统、中间件、文件系统等进行测试。 一、先来说第一种吧:直接对WEB或者APP的服务端进行测试。 一般来说,这种服务端的开发人员就是WEB/APP产品团队的开发人员,当然,测试人员跟WEB/APP的前端测试人员也是一个团队的。这种服务端就是为WEB/_服务端测试是什么

安卓刷机刷错导致无限闪屏_刷机后一直闪屏应用报错-程序员宅基地

文章浏览阅读354次。安卓努比亚z17s刷机不小心刷成了z17的包,重刷回官方包之后出现无限闪屏,该怎么办啊?求大佬们的救机方法,重启双清都搞过了,都没用求教程!最开始开机之后底图还有奇兔的recovery的背景图,现在不知道为什么没有这个底图了,但是还会无限闪屏,想自己学学搞机,求大佬赐教!!..._刷机后一直闪屏应用报错

Qt中mouseMoveEvent在MainWindow中使用_qt mousemoveevent只能在鼠标按下时才反应-程序员宅基地

文章浏览阅读2k次。最近用Qt软件界面,需要用到mouseMoveEvent,研究了下,发现些问题,分享一下。在Qt中要捕捉鼠标移动事件需要重写MouseMoveEvent,但是MouseMoveEvent为了不太耗资源在默认状态下是要鼠标按下才能捕捉到。要想鼠标不按下时的移动也能捕捉到,需要setMouseTracking(true)。boolmouseTracking这个属性..._qt mousemoveevent只能在鼠标按下时才反应

QML MouseArea元素_qml 矩形边框鼠标-程序员宅基地

文章浏览阅读159次。QML MouseArea元素_qml 矩形边框鼠标

随便推点

HTML5+CSS3小实例:鼠标悬停发光按钮_html5中鼠标悬停的标签-程序员宅基地

文章浏览阅读936次。HTML5+CSS3做一组鼠标悬停发光的按钮,鼠标悬停,按钮边框延展开来,首尾相连时填充按钮,过程伴随发光、倒影效果,并通过hue-rotate实现每个按钮不同颜色。效果:源码:<!DOCTYPE html><html><head> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name="viewport" co_html5中鼠标悬停的标签

在Jmeter的Beanshell使用Pattern/matcher进行正则匹配_beanshell字符串截取-程序员宅基地

文章浏览阅读612次。Pattern matcher Jmeter Beanshell_beanshell字符串截取

PE结构_pe 設为只讀-程序员宅基地

文章浏览阅读109次。硬盘与内存对齐方式1、分节节约硬盘空间2、内存中多开,可以节约内存空间,只读数据只开一份,可读可写多开。DOS 头e_magic 标志位e_lfanew :PE文件开始的地方如下图从文件开始的地方算,第E8个字节就是PE文件开始的地方*号重要标准PE头*号重要可选PE头*号重要..._pe 設为只讀

StackLabel 堆叠标签引入后无法使用_com.kongzue.stacklabelview.stacklabel-程序员宅基地

文章浏览阅读304次。一个功能很强大的堆叠标签implementation 'com.kongzue.stacklabel:stacklabelview:1.1.6'引入后发现不能使用,各种报错manifest,apt版本之类的,后来发现是作者在layout_label布局文件中的LinearLayout中使用了两个不存在的属性android:paddingHorizontal="12dp" androi..._com.kongzue.stacklabelview.stacklabel

es6中文手册_javascript 中文手册 es6 chm-程序员宅基地

文章浏览阅读2w次,点赞6次,收藏30次。这是一个 ES2015(ES6) 的Cheatsheet,其中包括提示、小技巧、最佳实践和一些代码片段,帮助你 完成日复一日的开发工作。Table of Contentsvar 与 let / const 声明代码执行块替换立即执行函数箭头函数字符串解构模块参数类SymbolsMapsWeakMapsPromisesGeneratorsAsync Await mor_javascript 中文手册 es6 chm

Hive 开窗函数_窗口函数取到分组后的第二条-程序员宅基地

文章浏览阅读318次。开窗函数普通的聚合函数聚合的行集是组,开窗函数聚合的行集是窗口。因此,普通的聚合函数每组(Group by)只返回一个值,而开窗函数则可为窗口中的每行都返回一个值。简单理解,就是对查询的结果多出一列,这一列可以是聚合值,也可以是排序值。开窗函数一般分为两类,聚合开窗函数和排序开窗函数。12测试数据– 建表create table student_scores(id int,studentId int,language int,math int,english int,classId_窗口函数取到分组后的第二条