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

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

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();
        }
}

 

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

 

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

 

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