用线性表实现两个一元多项式的相加
1.用链表实现:
因为是用链表来实现,所以要有一个节点(Node)类,又节点是用类存放数据(一个含有系数和指数的项),所以还要定义一个Item类(当然这个类也可以不写,直接把数据的特征放到节点类中)。
Item 类:
public class Item { private int coef; private int exp; public Item() { this.coef = 0; this.exp = 0; } public Item(int coef, int exp) { this.coef = coef; this.exp = exp; } public int getCoef() { return this.coef; } public void setCoef(int coef) { this.coef = coef; } public int getExp() { return this.exp; } public void setExp(int exp) { this.exp = exp; } }
Node类:
public class Node { private Item data; private Node next; public Node() { data = null; next = null; } public Node(Item data, Node next) { this.data = data; this.next = next; } public Item getData() { return this.data; } public void setData(Item data) { this.data = data; } public Node getNext() { return this.next; } public void setNext(Node next) { this.next = next; } }
再根据分析可知要有一个Chain类来将所有的节点串联起来
Chain类:
public class Chain { private Node head = null; private int size = 0; public Chain() { head = new Node(); size = 0; } public Node getHead() { return this.head; } public void setHead(Node head) { this.head = head; } public int getSize() { return this.size; } public void chainAll() { for (Node curr = head.getNext(); curr != null; curr = curr.getNext()) { System.out.print(" " + curr.getData().getCoef() + "x^" + curr.getData().getExp()); System.out.print(curr.getNext() == null ? " " : "+"); } } public boolean addAt(int i, Item elem) { if (i < 0 || i > size) { System.out.println("输入的数据不合法,请重新输入"); return false; } Node pre, curr; for (pre = head; i > 0 && pre.getNext() != null; i--) { pre = pre.getNext(); } curr = new Node(elem, pre.getNext()); pre.setNext(curr); size++; return true; } public Chain mergeChain(Chain chain1, Chain chain2) { int i = 0; Item item = new Item(); Node curr1, curr2; Chain chain3 = new Chain(); curr1 = chain1.getHead().getNext(); curr2 = chain2.getHead().getNext(); while (curr1 != null && curr2 != null) { if (curr1.getData().getExp() > curr2.getData().getExp()) { item = curr1.getData(); chain3.addAt(i, item); curr1 = curr1.getNext(); i++; } else if (curr1.getData().getExp() < curr2.getData().getExp()) { item = curr2.getData(); chain3.addAt(i, item); curr2 = curr2.getNext(); i++; } else { item = new Item(curr1.getData().getCoef() + curr2.getData().getCoef(), curr1.getData().getExp()); if (item.getCoef() != 0) { chain3.addAt(i, item); i++; } curr1 = curr1.getNext(); curr2 = curr2.getNext(); } } while (curr1 != null) { item = curr1.getData(); chain3.addAt(i++, item); curr1 = curr1.getNext(); } while (curr2 != null) { item = curr2.getData(); chain3.addAt(i++, item); curr2 = curr2.getNext(); } return chain3; } }
最后用一个主函数实现功能:
Test类:
public class Test { public static void main(String[] args) { Chain chain1 = new Chain(); Chain chain2 = new Chain(); Chain chain3 = new Chain(); // 按降幂实例化链表 chain1.addAt(0, new Item(1, 5)); chain1.addAt(1, new Item(2, 3)); chain1.addAt(2, new Item(1, 1)); chain2.addAt(0, new Item(1, 5)); chain2.addAt(1, new Item(2, 4)); chain2.addAt(2, new Item(3, 3)); chain2.addAt(3, new Item(3, 0)); chain3 = chain3.mergeChain(chain1, chain2); System.out.println("一元多项式的相加过程: "); chain1.chainAll(); System.out.println(" + "); chain2.chainAll(); System.out.println(" = "); chain3.chainAll(); } }
相关推荐
用线性表的存储形式实现两个一元多项式相加。
数据结构课件:第2章 线性表2一元多项式的表示及相加.pptx
此次上机实验应用了线性表实现了一次实际操作,完成了一个一元多项式的简单计算器,不仅对此次编译程序的算法思想有了新的认识,还让我深刻的体会到了线性表的重要性以及其应用的方便,并且对指针加深了映象,应用了...
本程序配合清华大学出版社 《数据结构(C语言版)》P39页 在WIT-TC下调试通过
输入部分,要求用户能从屏幕上格式化输入两个一元多项式。如多项式A为:x^3+2x^2-x+4;多项式B为:-x^3+3x^2-x+45。 程序通过语句得到这两个字符串,进行解析,分解出系数和指数,存储在不同的线性表LA,LB中。 然后...
利用实现的线性表,存储一元n次多项式,完成多项式的输入、显示;实现多项式的加法操作
学习实现一元n次多项式的加法是符号多项式的操作,是表处理的典型用例,需要注意的是:顺序存储结构指的是用数组方法,使用数组方法实现时,在插入和删除的方面,数组不如链表灵活,方法复杂,删除其中一个需要将其...
实验二 线性表的链式存储结构 题目:设计并实现以下算法:给出用单链表存储多项式的结构,利用后接法生成多项式的单链表结构,实现两个多项式相加的运算,并就地逆置相加后的多项式链式。1. 用户可以根据自己的需求...
一元多项式计算器 所设计系统的具体功能要求:a.输入并建立多项式a和b;b.输出多项式a和b;c.多项式a和b相加,建立并输出多项式a+b;d.多项式a和b相减,建立并输出多项式a-b;e.输入多项式中的未知数,计算多项式的...
题1 问题描述:有两个指数递减的一元多项式,写一程序先求这两个多项式的和,再求它们的积。 基本要求:用带表头结点的单链表作为多项式的存储表示;要建立两个单链表;多项式相加就是要把一个单链表中的结点插入到...
符号多项式的操作,已经成为表处理的典型用例。在数学上,一个一元多项式Pn(x)可按升幂写 ...本题要求选用线性表的一种合适的存储结构来表示一个一元多项式,并在此结构上实现一元多 项式的加法,减法和乘法操作
设计一个实现一元稀疏多项式相加运算的演示程序: (1)输入并建立两个多项式; (2)多项式a与b相加,建立和多项式c; (3)输出多项式a,b,c。输出格式:比如多项式a为:A(x)=c1xe1+ c2xe2+…+ cmxem,其中,ci和...
实验一:线性表的应用算法:构造一个递增有序的正整数链表,实现链表分解为一个奇数表和一个偶数表,之后再将两个链表合并一个递减...实验二:线性表的应用算法:构造两个按指数递增的有序链表,实现两个一元多项式相加
数据结构实用教程之线性表的应用,里面有线性表的定义以及应用,线性表的应用包含 两个有序表的合并、集合运算、一元多项式的表示和相加
1. 设计一个实现一元多项式简单运算的程序。要求其完成如下操作:1)多项式的建立,2)多项式的输出,3)多项式的相加运算,4)多项式的乘积运算。 2. 实现原理: 将两多项式存入链表pa、pb,用p扫描pa,q扫描pb,...
一、【题目】 利用链表的完整类C++类描述,用链表表示一元稀疏多项式,进而设计主程序算法,完成两个多项式相加,并将结果进行输出。 1、 目的: 熟练掌握线性表的基本操作在链表存储结构上的实现。 ...
一元多项式可以表示成数据由两个数据项组成的一个线性表,如果只存储系数让指数隐含在系数序号中,则会浪费存储空间。只对多项式的值无需修改系数和指数值的情况下,采用顺序表结构较好。
一元多项式的表示和相加(链表、建立、相加、输出) 2. 表达式括号匹配检验(压栈、出栈) 3. 数制的转换(十进制到二进制转换) 4. 约瑟夫环(循环单链表) 二、应用题 5. 表达式求解 6. 将两个有序线性表...