用线性表实现两个一元多项式相加
????????????????????????????????????????? 用线性表实现两个一元多项式的相加
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();
??????? }
?
?
?
?
?
?
?
?
?
?
?
}
?
?
?
这样就实现了用线性表完成两个多项是的相加。这算得上是线性表的经典应用了吧，同过这两个实验
?
我基本上算是了解了线性表。后来看了老师给的代码发现其实我的代码还是比较累赘的，而且比较死板，
?
多项式是直接定死了，不是从键盘输入的还有待改进。
?
?