LinkBack URL
About LinkBacks
Please help about data structures.
Please help me, I got stuck on this one from yesterday til now. Long story short : I have to build an java apps for doing polynomial : addition, subtraction, derivative .... The data structure chosen is linked list. There are five classes
Term class : hold the exponent and coefficient for each term of the polynomial
Node class : each node have a term in it and a link to the next Node
Orderedsequences class: contains the head of the ordered sequence, the term must be arranged from high exponent to low exponent. orderedsequence also contains a cursor to show the current term, and a count to show how many term in there.
Polynomial class : contains method to manipulate polynomial : add term, subtract two polynomials, derivative...
Test class: to test the method.
Previously, when I use array as the data structure to hold the term, everything is fine, when I change to linked list lost of thing happen. I think I have a trouble with the insert method (insert new terms into orderedsequence) and isCurrent method in the Orderedsequence class. Please help.
Here is the code for the five classes.
public class Node { private Term data; private Node link; //constructor public Node(Term t,Node l) { data=t; link=l; } //add Node after this Node public void addNodeafter(Term item) { link =new Node (item,link); } //Accessor public Term getTerm () { return data; } public Node getLink(){ return link; } //remove Node after this Node public void removeNodeAfter() { link=link.link; } //Set the term for this Node public void setTerm (Term x) { data=x; } //Set the Link for this Node public void setLink(Node x) { link=x; } //List copy public static Node listCopy(Node source) { Node ans=null; if(source != null) { ans=new Node (source.data,null); Node cursor=source.link; Node tail= ans; while(cursor != null) { tail.link = new Node (cursor.data,null); cursor = cursor.link; tail = tail.link; } } return ans; } }
[CODE]public class Term implements Comparable<Term> { private double coeff; private int exp; //constructor public Term (double x,int y) { coeff=x; exp=y; } // Return the value of the coefficient of this term public double getCoeff() { return coeff; } //Return the value of the power of this term public int getExp() { return exp; } //modify the coefficient of a term public void setCoeff(double d) { coeff = d; } //modify the coefficient of a term public void setExp(int i) { exp = i; } //this term and term a has the same power //Return a term that is a sum of this term and a public Term add(Term a) { return new Term(coeff+a.coeff,exp); } //this term and term a has the same power //Return a term that is a substraction of term a from this term public Term subtr(Term a) { return new Term(coeff-a.coeff,exp); } //Return the differnce of the two terms which has same power public Term subtract(Term t){ return new Term(coeff-t.coeff,exp); } //Return a term that is a multiplication of this term and term a public Term mult(Term a) { return new Term(coeff*a.coeff,exp+a.exp); } //Return a term that is the derivative of this term public Term derivative() { return new Term (coeff*exp,exp-1); } //Return a term that is the integral of this term public Term integral() { return new Term(coeff/(exp+1),exp+1); } //Return the value of the definite integral from a to b of this term public double defintegral(double a,double b){ return (integral().eval(b)-integral().eval(a));} //Compare the exponent of the two terms, return 0 if equals, -1 < , 1 > public int compareTo(Term t){ int ans =0; if(exp>t.exp) ans = 1; else if (exp<t.exp) ans=-1; return ans; } public boolean equals(Object obj) { boolean ans = false; if(obj instanceof Term && compareTo((Term)obj)==0&&coeff==((Term)obj).coeff) ans=true; return ans; } //Return value of this term at a particulate value public double eval(double x) { double ans=coeff*Math.pow(x,exp); return ans; } //Return a string that describes this term. public String toString() { String ans=""; if(exp>1&&coeff!=0) ans=ans+coeff+"x^"+exp+" "; else if(exp==1&&coeff>1) ans=ans+coeff+"x"; else if (exp==0&&coeff!=0) ans=ans+coeff; else if(exp==1&&coeff==1) ans=ans+"x"; return ans; } }
public class OrderedSequence implements Cloneable { private Node head; private int count; private Node cursor ; //Constructor with any length public OrderedSequence() { head=null; count=0;cursor=head; } //insert a term in the ordered sequence. Ordered from high exponent to low exponent.When the new term has same exponen //with an existing term, add the two together, if the result exponent is zero, remove the term. public void insert(Term t) { if(head==null) { head=new Node(t,null); } else { if(t.getExp()>head.getTerm().getExp()) { head=new Node (t,head); count++; } else { start(); while (cursor != null&&t.getExp()!=cursor.getTerm().getExp()) { advance(); } if(cursor!=null)//the power of t is the same as one of the exp in the os { cursor.setTerm(new Term(t.getCoeff()+cursor.getTerm().getCoeff(),t.getExp())); count++; if(cursor.getTerm().getCoeff()==0) { removeCurrent(); count--; } } else //cursor is null, there is no term in os has the same power as t { cursor.addNodeafter(t);count++; } } } } //restart the cursor to the beginning position public void start() { cursor = head; } // return the number of terms in the array public int getCount(){ return count; } //return the current position in the sequence public Term getCurrent() { return cursor.getTerm(); } //check if cursor is in the current positions in this ordered sequence public boolean isCurrent() { boolean answer = false; if(cursor.getTerm()!=null) answer = true; return answer; } //move the cursor to the next term public void advance() { if(isCurrent() == true) cursor=cursor.getLink(); } //remove the term at current public boolean removeCurrent() { boolean ans=false; if(isCurrent() == true) { cursor.setTerm(cursor.getLink().getTerm()); cursor.setLink(cursor.getLink().getLink()); ans=true; } return ans; } //merge two ordered sequence together public OrderedSequence merge(OrderedSequence os){ OrderedSequence ans=clone();start(); while(cursor!=null) { ans.insert(os.getCurrent()); advance(); } return ans; } public OrderedSequence clone() { OrderedSequence ans= new OrderedSequence(); start(); while(cursor!=null) { ans.insert(getCurrent()); advance(); } return ans; } /* public OrderedSequence clone(){ OrderedSequence ans ; try { ans=(OrderedSequence)super.clone(); } catch (CloneNotSupportedException e) { throw new RuntimeException("This class does not implement Cloneable"); } ans.head = head.clone(); return ans;} */ }
public class Polynomial implements Cloneable { private OrderedSequence os; //Constructor public Polynomial() { os=new OrderedSequence(); } public Polynomial (OrderedSequence ost) { os=ost; } //insert term with specified coefficient and exponent public void insert(double a,int b) { os.insert(new Term(a,b)); } //get the degree of this polynomial public int getDegree() { os.start(); return os.getCurrent().getExp(); } public int numberOfTerms(){ return os.getCount(); } //Evaluate the value of a polynomial public double evaluate(double x) { double ans=0;os.start(); while(os.isCurrent()==true) { ans=ans+os.getCurrent().eval(x); os.advance(); } return ans; } //return the sum of this polynimial and polynomial t public Polynomial add(Polynomial t) { return new Polynomial(os.merge(t.os)); } //return the difference between this polynomial and polynomial a public Polynomial sub(Polynomial a) { Polynomial ans=clone(); a.os.start(); while(a.os.isCurrent()==true) { ans.insert(-1*(a.os.getCurrent().getCoeff()),a.os.getCurrent().getExp()); a.os.advance(); } return ans; } // Take derivative public Polynomial derivative() { Polynomial ans=new Polynomial(); os.start(); while(os.isCurrent()==true) { ans.insert(os.getCurrent().derivative());os.advance(); } return ans; } //Integrate polylinomial public Polynomial integrate() { Polynomial ans=new Polynomial(); os.start(); while(os.isCurrent()==true) { ans.insert(os.getCurrent().integral());os.advance(); } return ans; } //Definite integral from a to b public double definiteIntegral(double a,double b) { Polynomial inte=integrate(); return (inte.evaluate(b)-inte.evaluate(a)); } //Multiplication of this polynomial and polinomial a public Polynomial multiply(Polynomial a) { Polynomial ans =new Polynomial(); os.start(); while(os.isCurrent()==true) { a.os.start(); while(a.os.isCurrent()==true) { ans.insert(os.getCurrent().mult(a.os.getCurrent())); a.os.advance(); } os.advance(); } return ans; } //Clone method for polynomial public Polynomial clone(){ Polynomial ans=new Polynomial(os.clone()) ; return ans;} //Compares the whole term of this polynomial and polynomial a public boolean equals(Object obj) { boolean ans = false; if(obj instanceof Polynomial&&os.getCount() == ((Polynomial)obj).os.getCount()) { os.start();((Polynomial)obj).os.start(); while(os.isCurrent()==true&&os.getCurrent().equals(((Polynomial)obj).os.getCurrent())==true) { os.advance();((Polynomial)obj).os.advance(); } if(os.isCurrent()==false) ans=true; } return ans; } //Insert a term into this polynomial public void insert (Term a) { os.insert(a); } //display the polynomial public String toString() { os.start(); String ans=""; while(os.isCurrent()==true) { ans=ans+os.getCurrent().toString(); os.advance(); if(os.isCurrent()==true&&os.getCurrent().getCoeff()!=0) ans=ans+" + "; } return ans; } }
public class TestLab2x{ public static void main (String arg[]){ //Make a new term 3.5x^4 Term t1=new Term(2,4); Term tt=new Term(2,4); Term t2=new Term(2.5,4); Term t3=t1.add(t2); Term t4=new Term(1,1);Term t5=new Term(2,2);Term t6=new Term(3,3);Term t7=new Term(5,5);Term t8=new Term(10,0); System.out.println("This is the term t1 "+t1); //Compare term t1 and tt System.out.println("Compare t1 and tt "+t1.equals(tt)); System.out.println("Compare t1 and t2 "+t1.equals(t2)); System.out.println("Compare t1 and 1000 "+t1.equals(1000)); //Extract the coefficient of t1 System.out.println("The coefficient of t1 is "+t1.getCoeff()); //Extract the exponent of t1 System.out.println("The exponent of t1 is "+t1.getExp()); System.out.println("This is the term t3 "+t3); //Extract the coefficient of t1 System.out.println("The coefficient of t3 is "+t3.getCoeff()); //Extract the exponent of t1 System.out.println("The exponent of t3 is "+t3.getExp()); //Derivative of a term Term t9=t1.derivative();System.out.println("Display t9 "+t9.toString()); Term t10=t8.derivative();System.out.println("Display t10 "+t10.toString()); //Evaluate t1 at x=2 System.out.println("Value of t1 at x=2 is " + t1.eval(2)); System.out.println("Display t8 "+t8.toString()+"\n"); Polynomial p1=new Polynomial(); p1.insert(t1);p1.insert(t5); System.out.println("Polynomial p1 is : " +p1.toString()); }}
Reply With Quote
Related threads:
