Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 2 of 2
Thread: Polynomial linked list

10202011, 06:27 AM #1
 Join Date
 Sep 2011
 Posts
 9
 Thanks
 2
 Thanked 0 Times in 0 Posts
Polynomial linked list
Unlike my last post, this one is homework. I really wish I could just take a beginners java class instead of trying to do this based on C++ programming classes a year ago. Unfortunately, I'm not allowed to take "extra" classes that don't count towards my degree and still keep my financial aid. Anyway, here's what I have:
Code:class Node { private int exponent, coefficient; private Node next; public Node() { exponent = 0; coefficient = 0; next = null; } public void setCoefficient (int coeff) { coefficient = coeff; } public int getCoefficient() { return coefficient; } public void setExponent(int exp) { exponent = exp; } public int getExponent() { return exponent; } public void setNext(Node poly) { next = poly; } public Node getNext() { return next; } } class Polynomial { private Node head = new Node(); public Polynomial() { head = null; } public void Insert(int coefficient, int exponent) { Node current = null, previous = null; boolean inserted = false; Node newNode = new Node(); newNode.setCoefficient(coefficient); newNode.setExponent(exponent); newNode.setNext(null); if (head == null) head = newNode; else if (exponent > head.getExponent() ) { newNode.setNext(head); head = newNode; } else { inserted = false; previous = head; current = head.getNext(); } while(inserted == false && current != null ) { if (exponent > current.getExponent() ) { previous.setNext(newNode); newNode.setNext(current); inserted = true; } else { current = current.getNext(); previous = previous.getNext(); } } if (current == null) previous.setNext(newNode); } }
Could anyone help me figure out what I'm doing wrong with the Polynomial class, and if I have anything wrong in the node class?
10202011, 04:33 PM
#2
 Join Date
 Sep 2002
 Location
 Saskatoon, Saskatchewan
 Posts
 16,987
 Thanks
 4
 Thanked 2,660 Times in 2,629 Posts
Something feels wrong about both classes.
LinkedLists like other collections tend to favour nonspecific datatypes. The Node class you have here is designed specifically for the polynomial.
The polynomial itself is simply a collection of Term. Since you have been given an insert method, that would indicate that this is to be developed from scratch instead of by using a builtin collection, which now means your Node should probably just be labeled as your Term. So you now have a Polynomial pseudocollection of type Term.
I don't see anything wrong with the insert method as defined specifically for the polynomial.
As for the Term class, I'm not sure what you need to do with it either. Given that this is a custom list, my perception of a polynomial is simply that it is a collection of Term (or more accurately, I'd call it a collection of ITerm since they can be either constant or variable). If you were to use a builtin collection, it would be tremendously easier (but I think the creation is the actual assignment :/)
How I perceive it:
Unfortunately with the Java PriorityQueue, the only time you are guaranteed the order specified is during the pq.poll(). I just ran a few tests and found that neither a print of it, nor an iteration of it provided the proper ordering. Checking the api confirmed that this is normal behaviour in a priority queue for java. You can however sort them by converting to an array instead (according to the API).PHP Code:
public interface ITerm
{
public final Comparator<ITerm> SORT_BY_EXP_DESC = new Comparator<ITerm>()
{
@Override
public int compare(ITerm t1, ITerm t2)
{
return t2.getExponent()  t1.getExponent();
}
};
public int getExponent();
}
public class Term implements ITerm
{
private int coefficient, exponent;
public Term()
{
this(0, 0);
}
public Term(int coefficient, int exponent)
{
this.coefficient = coefficient;
this.exponent = exponent;
}
public String toString()
{
return "Term[coefficient=" + this.coefficient + ", exponent=" + this.exponent + "]";
}
@Override
public int getExponent()
{
return this.exponent;
}
public static void main(String[] argv)
{
java.util.PriorityQueue<ITerm> pq = new java.util.PriorityQueue<ITerm>(10, ITerm.SORT_BY_EXP_DESC);
pq.add(new Term(5, 2));
pq.add(new Term(5, 7));
pq.add(new Term(5, 5));
ITerm tCurrent = pq.poll();
while (tCurrent != null)
{
System.out.println(tCurrent);
tCurrent = pq.poll();
}
}
}