Discussion in 'Mac Programming' started by DesertFox, Mar 17, 2007.

1. ### DesertFox macrumors member

Joined:
Nov 25, 2004
#1
Hello,

I have 2 items in each node of my linked list. My goal is to perform polynomial addition and multiplication (assignment from my college prof). The first item in the node is the coefficient and the second is the exponent. Right now im only able to search and delete according to the first item in the list...

How do I check the second items in the node as well in the list as well?

And, also, does anyone know how addition and multiplication is suppose to work with linked lists?

Any help is much appreciated.

Here is the source code:

{
public static void main (String [] args )
{

// fill equations with coefficient and exponent
firstEq.insertFirst(4, 1);
firstEq.insertFirst(3, 1);
firstEq.insertFirst(2, 2);
firstEq.insertFirst(4, 2);
firstEq.insertLast(3, 3);

secondEq.insertFirst(2, 1);
secondEq.insertFirst(1, 1);
secondEq.insertFirst(4, 2);
secondEq.insertFirst(3, 2);

firstEq.displayList();
secondEq.displayList();

if( x != null)
System.out.println("Found link with key " + x.iData);
else

if( y != null )
System.out.println("Deleted link with key " + y.iData);
else

firstEq.displayList();

/*
while (!theList.isEmpty() ) // delete until list is empty
{
System.out.print("Deleted ");
System.out.println("");
}

theList.displayList();
*/
}

}

{

{
first = null;
last = null;
}

public boolean isEmpty() // true of list is empty
{
return (first==null);
}

// insert at start of list
public void insertFirst( int id, int dd)
{

if (isEmpty() )

}

public void insertLast(int id, int dd) // insert at end of list
{

if( isEmpty() ) // if empty list,
else

}

// find link with given key
{
Link current = first; // start at first
while(current.iData != key ) // while no match
{
if (current.next == null) // if end of list
return null; // didnt find it
else
current = current.next; // go to next link
}
return current; // found it
}

{
while(current.iData != key )
{
if ( current.next == null )
return null;
else
{
previous = current;
current = current.next;
}
}

if(current == first)
first = first.next;
else
previous.next = current.next;
return current;
}

// delete first item (assumes list is not empty)
{
first = first.next; // delete it: first --> old
return temp; // return deleted link
}

public void displayList()
{
System.out.print("Equation { coefficient, exponent }: ");
Link current = first; // start at beginning of list
while (current != null )
{
current = current.next;
}

System.out.println();
}
}

AND THE LIST FILE:

{
public int iData;
public int dData;

public Link (int id, int dd)
{
iData = id;
dData = dd;
}

{
System.out.print("{ " + iData + ", " + dData + " } ");
}

}

Joined:
Nov 3, 2005
Location:
UK
#2
I am totally puzzled, why in the linked list class do you not just use two arrays of doubles/ints?

3. ### lazydog macrumors 6502a

Joined:
Sep 3, 2005
Location:
Cramlington, UK
#3
Hi DessertFox

Looks to me as though your linked list stuff is searching on the coefficient rather than the exponent. I would have thought searching on the exponent would be much more useful since in a (canonical?) polynomial equation the exponents should be unique eg 4x^3 + 4x^2 + 4x.

If by addition and multiplication you mean symbolic addition and multiplication then for addition you would have something like this:-

equation1: 4x^3 + 3x^2 +2
equation2: 3x^2 + 5x

equation1 + equation2: 4x^3 + 6x^2 + 5x + 2

So addition would involve walking through the linked lists adding the coefficients of items with the same exponent to produce the result.

Mulitplication is a bit more difficult. This involves multiplying each item in the 1st equation by each item in the 2nd equation to produce the result. In multiplication you would multiply coefficients and add exponents. So in the above example:-

equation1 * equation2: 12x^5 + 20x^4 + 9x^4 + 15x^3 +6x^2 + 10x

If you look at the result you'll see you have 2 items that have an exponent of 4. So you would add these together to give

equation1 * equation2: 12x^5 + 29x^4 + 15x^3 + 6x^2 + 10x

hope this helps

b e n