`

用线性表实现两个一元多项式相加

阅读更多

                                          用线性表实现两个一元多项式的相加

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.用顺序表实现

顺序表其实就是用数组的形式实现,同样需要一个Item类,这就不做叙述了。还要有一个List类来存储数据

List类:

 

public class List {
	private Item[] a = new Item[100];
	private int size = 0;
	private int current;

	public List() {
		int i = 0;
		size = 0;
		for (i = 0; i < 100; i++)
			a[i] = null;
	}

	public int getSize() {
		return this.size;
	}

	public void listAll() {
		for (int i = 0; i < size; i++) {
			System.out.print(" " + a[i].getCoef() + "x^" + a[i].getExp());
			System.out.println(i < size ? " + " : "  ");
		}
	}

	public void addAt(int index, Item data) {
		if (index < 0 || index > size) {
			System.out.println("the index error");
		} else {
			for (int i = size - 1; i >= index; i--) {
				a[i + 1] = a[i];
			}
			a[index] = data;
			this.size++;
		}
	}

	public Item getData(int i) {
		if (i >= 0 && i < size)
			return a[i];
		else
			return null;

	}

	public List mergeChain(List list1, List list2) {
		int index = 0;
		int i = 0;
		int j = 0;
		List list3 = new List();
		while (i < list1.getSize() && j < list2.getSize()) {
			if (list1.getData(i).getExp() > list2.getData(j).getExp()) {
				list3.addAt(index, list2.getData(j));
				j++;
				index++;
			} else if (list1.getData(i).getExp() < list2.getData(j).getExp()) {
				list3.addAt(index, list1.getData(i));
				i++;
				index++;
			} else {

				int coef = list1.getData(i).getCoef()
						+ list2.getData(j).getCoef();
				int exp = list1.a[i].getExp();
				Item item = new Item();
				item.setCoef(coef);
				item.setExp(exp);
				if (coef != 0) {
					list3.addAt(index, item);
					i++;
					j++;
					index++;
				}

			}
		}
		while (i < list1.getSize()) {

			list3.addAt(index++, list1.getData(i++));

		}
		while (j < list2.getSize()) {
			list3.addAt(index++, list2.getData(j++));
		}

		return list3;
	}

}

 



同样需要一个主函数类

 

Manager类:

 

public class Manager{
      public static void main(String[] args){
         //按降幂实例化三个顺序表
   List list1 = new List();
         List list2 = new List();
         List list3 = new List();
  
         list1.addAt(0, new Item(1, 5));
         list1.addAt(1, new Item(2, 3));
         list1.addAt(2, new Item(1, 1));
  
         list2.addAt(0, new Item(1, 5));
         list2.addAt(1, new Item(2, 4));
         list2.addAt(2, new Item(3, 3));
         list2.addAt(3, new Item(3, 0));  
  
         list3 = list3.mergeChain(list1, list2);
  
         System.out.println("一元多项式相加的过程: ");
         list1.listAll();
         System.out.println(" + ");
         list2.listAll();
         System.out.println(" = ");
         list3.listAll();
        }
}

 

这样就实现了用线性表完成两个多项式的相加。这算得上是线性表的经典应用了吧,通过这两个实验

 

我基本上算是了解了线性表。后来看了老师给的代码发现其实我的代码还是比较累赘的,而且比较死板,

 

多项式是直接定死了,不是从键盘输入的还有待改进。


 

 

分享到:
评论

相关推荐

    c语言 两个一元多项式相加。

    用线性表的存储形式实现两个一元多项式相加。

    数据结构课件:第2章 线性表2一元多项式的表示及相加.pptx

    数据结构课件:第2章 线性表2一元多项式的表示及相加.pptx

    数据结构+实验报告+线性表及其应用(多项式相加、相乘)等

    此次上机实验应用了线性表实现了一次实际操作,完成了一个一元多项式的简单计算器,不仅对此次编译程序的算法思想有了新的认识,还让我深刻的体会到了线性表的重要性以及其应用的方便,并且对指针加深了映象,应用了...

    一元多项式的表示及相加 严蔚敏

    本程序配合清华大学出版社 《数据结构(C语言版)》P39页 在WIT-TC下调试通过

    数据结构课程设计——用STL实现多项式的运算

    输入部分,要求用户能从屏幕上格式化输入两个一元多项式。如多项式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 问题描述:有两个指数递减的一元多项式,写一程序先求这两个多项式的和,再求它们的积。 基本要求:用带表头结点的单链表作为多项式的存储表示;要建立两个单链表;多项式相加就是要把一个单链表中的结点插入到...

    C/C++:一元多项式的表示及其运算.rar(含注释)

    符号多项式的操作,已经成为表处理的典型用例。在数学上,一个一元多项式Pn(x)可按升幂写 ...本题要求选用线性表的一种合适的存储结构来表示一个一元多项式,并在此结构上实现一元多 项式的加法,减法和乘法操作

    使用c或C++一元稀疏多项式的加法运算

    设计一个实现一元稀疏多项式相加运算的演示程序: (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. 将两个有序线性表...

Global site tag (gtag.js) - Google Analytics