欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

计算一元多项式的相加

程序员文章站 2022-08-29 12:51:58
一元多项式的表达和相加​ 使用单链表表示一元多项式,由于使用java语言自己编写实现,没有使用LinkedList集合实现。所以需要创建单链表的类,类中包含指数,系数和后继元素的地址。类的设计如下:public class SingleList {public double coef;//系数public int expn;//指数public SingleList next;//后继//构造函数public SingleList(double coef, int...

一元多项式的表达和相加

​ 使用单链表表示一元多项式,由于使用java语言自己编写实现,没有使用LinkedList集合实现。所以需要创建单链表的类,类中包含指数,系数和后继元素的地址。类的设计如下:

public class SingleList {
	public double coef;//系数
	public int expn;//指数
	public SingleList next;//后继
	
	//构造函数
	public SingleList(double coef, int expn) {
		this.coef = coef;
		this.expn = expn;
	}
}

​ 下面来讲解一下如何用单链表表示和运算。

/*
 * 
 * 1.一元多项式的表示:
 * 	采用单链表的形式表示,只存储非0系数项
 * 	链表中的每一个项封装成一个对象:coef--系数 expn--指数 next--后继元素
 * 
 * 2.一元多项式的相加:
 * 	2.1定义两个指针qa和qb分别指向两个链表的当前元素
 *  2.2如果两个指针都不为空的时候执行while循环
 *  2.3循环语句中包含三种情况:
 *  	2.3.1 qa的指数小于qb的指数:qa的指针后移,qb不动,结束本次循环
 *  	2.3.2 qa的指数等于qb的指数:
 *  			计算系数和sum
 *  				1.如果系数和为0,将qa指向的元素删除,qa指针同时后移一位
 *  				2.如果系数和不为0,将qa指向的元素的系数修改为sum,qa指针后移一位
 *  				3.无论系数是不是为0,,删除qb指向的元素,qb指针后移
 *  	2.2.2 qa的指数大于qb的指数:qb的指针后移,qa不动,结束本次循环
 *  2.4如果第二个链表不为空,将剩余元素插入到第一个链表的最后
 *  2.5清空并释放链表2
 */

**1.**在类中首先定义两个头结点,用于指向链表中的第一个元素,不表示具体的元素项。

import java.util.Scanner;
public class PolynomialOfOne {

	//两个 链表的头结点
	public static SingleList head1 = new SingleList(0,0);
	public static SingleList head2 = new SingleList(0,0);
}

**2.**初始化链表方法

	/*
	 * 多项式链表初始化
	 */
	public static void init(SingleList head) {
		head.next = null;
	}

**3.**增加元素项

/*
	 * 多项式链表增加元素项
	 */
	public static void put(SingleList head,SingleList m){
		//1.如果链表为空,直接放到头结点后
		if(head.next == null) {
			head.next = m;
			return;
		}
		//2.如果链表不空,找到链表的最后一个元素,插入
		SingleList p = head.next;
		while(p.next != null) {
			p = p.next;
		}
		p.next = m;
	}

**4.**遍历输出多项式

    /*
	 * 遍历输出
	 */
	public static void traverse(SingleList head) {
		SingleList p = head.next;
		int k = 0;//记录位置
		
		while(p != null) {
			k++;
			if(k == 1 || p.coef < 0) {//第一项或者系数为负数时,不需要另加运算符
				System.out.print(p.coef+"x^"+p.expn);
			}
			else {//不是第一项的正数项,需要加“+”运算符
				System.out.print("+"+p.coef+"x^"+p.expn);
			}
			p = p.next;
		}
		System.out.println();
	}

**5.**两个多项式相加

/*
	 * 两个多项式相加
	 */
	public static void addition() {
		//多项式加法:head1+head2,利用两个多项式的节点构成“和多项式”
		//pa和pb分别指向head1和head2中的当前结点
		SingleList qa = head1.next;
		SingleList qb = head2.next;
		//当pa和pb均为非空时
		while(qa !=null && qb !=null) {
			if(qa.expn < qb.expn) {//多项式ha中的当前结点指数值小
				qa = qa.next;
			}//if
			else if(qa.expn == qb.expn) {//多项式ha和hb中的当前结点指数值相等
				double sum = qa.coef + qb.coef;//系数和
				if(sum != 0.0) {//如果系数值不为0就修改当前ha中当前结点的值
					qa.coef = sum;
					qa = qa.next;
				}//else if
				else {//删除多项式ha中的当前结点,并将qa指向下一个结点
					qa = freeElement(head1, qa);
				}
				//无论系数和为不为0,都要将当前的qb的元素删除
				qb = freeElement(head2, qb);
			}
			else {//多项式hb中的当前结点指数值小
				qb = qb.next;
			}//else
		}//while
		//如果链表2不为空,将元素加入到链表1的后边
		if(!isEmpty(head2)) {
			appEnd(head1, head2);
		}
		//释放链表2
		clear(head2);
	}

**6.**删除多项式中的项

/*
	 * 删除链表中的某个元素并返回所删元素的下一个元素
	 */
	public static SingleList freeElement(SingleList head,SingleList l) {
		SingleList p = head.next;//当前位置的元素
		SingleList q = head;//q为p的前驱
		while(p!=null) {
			//如果找到该元素,删除后跳出循环
			if(p == l) {
				q.next = p.next;
				p = null;
				break;
			}
			//否则元素后移,前驱也跟着后移
			else {
				p = p.next;
				q = q.next;
			}
		}
		return q.next;
	}

**7.**判断链表是否为空

/*
	 * 判断链表是否为空
	 */
	public static boolean isEmpty(SingleList head) {
		if(head.next == null) {
			return true;
		}
		else {
			return false;
		}
	}

**8.**清空链表

/*
	 * 清空链表
	 * 如果head的后继为空,直接return即可
	 * 否则定义一个指针,依次后移将元素置空,最后将head的后继置空
	 */
	public static void clear(SingleList head) {
		if(head.next==null) {
			return;
		}
		SingleList p = head.next;
		while(p.next!=null) {
			head.next = p.next;//记录p的后继
			p = null;
			p = head.next;//p后移
		}
		head.next = null;//表置空
	}

**9.**将一个链表的元素插入到另一个链表的最后

/*
	 * 将一个链表h2的元素插入到另一个链表h1的最后
	 */
	public static void appEnd(SingleList h1,SingleList h2) {
		SingleList p = h1.next;//指针
		while(p!=null) {
			//当p.next等于空时,找到了h1的最后元素
			if(p.next==null) {
				//h1的最后元素指向h2的第一个元素完成连接
				p.next = h2.next;
				break;
			}
			p = p.next;
		}
	}

**10.**测试主函数

public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		//初始化链表
		System.out.println("请输入你的选择:\n输入-1停止添加:");
		init(head1);
		init(head2);
		while(true) {
			//选择操作
			System.out.println("请输入你的选择:\n1.给多项式1添加新项\n2.给多项式2添加新项\n输入-1结束");
			int select = reader.nextInt();//输入的选择
			//输入-1结束添加
			if(select == -1) {
				break;
			}
			else {
				//输入系数和指数
				System.out.println("请输入系数:");
				double coef = reader.nextDouble();
				System.out.println("请输入指数:");
				int expn = reader.nextInt();
				//封装成对象
				SingleList L = new SingleList(coef, expn);
				//如果输入的为1给多项式1添加 否则给多项式2添加
				if(select == 1) {
					put(head1, L);
				}
				else {
					put(head2, L);
				}
			}
		}
		//添加结束,打印输出
		System.out.println("多项式1如下:");
		traverse(head1);
		System.out.println("多项式2如下:");
		traverse(head2);
		System.out.println("*****************************");
		addition();
		traverse(head1);
	}

**11.**运行实例

多项式1如下:
3.0x^1+5.0x^2+9.0x^6
多项式2如下:
6.0x^1-5.0x^2+7.0x^3+8.0x^4+11.0x^5+7.0x^7
*****************************
9.0x^1+9.0x^6+7.0x^3+8.0x^4+11.0x^5+7.0x^7

计算一元多项式的相加

本文地址:https://blog.csdn.net/weixin_47666481/article/details/110245019