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

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

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

	}
}