Linked List help!

krisopotamus · #1 06-Dec-2005, 04:25

Hopefully I can get a response so I can get this done, as I am tired...anyways I'll post my code up first

Here is my header file:

CPP / C++ / C Code:

// polynomial.h
//

#ifndef __POLYNOMIAL_H__
#define __POLYNOMIAL_H__

struct Term {
  int coef;       // coefficient (never zero)
  unsigned exp;   // exponent
  Term *next;
};

class Polynomial {
 public:

  Polynomial();
  Polynomial(const Polynomial& P);
  Polynomial& operator=(const Polynomial& P);
  ~Polynomial();

  bool zero() const;
  unsigned degree() const;
  Polynomial& multiply_term(int c, unsigned k);
  Polynomial& add_term(int c, unsigned k);
  void print() const;

 private:

  Term *terms;

};

#endif

And here is my .cpp file

just SCROLL PAST THIS for now (just in case you guys say to post all my code...ill tell the problem after this paste)

CPP / C++ / C Code:

// polynomial.cpp
//

#include "polynomial.h"
#include <cassert>
#include <iostream>

using namespace std;

static void deleteList(Term *P) 
{
  Term *current = NULL;
  Term *next = P;
  while (next != 0) 
  {
    current = next;
    next = current->next;
    delete current;
  }
}


static Term *duplicateList(Term *terms) 
{
  if (terms == NULL)
    return NULL;
  Term *H = new Term;
  Term *prev = H;
  H->exp = terms->exp;
  for (Term *P = terms->next; P != NULL; P = P->next) 
  {
    prev->next = new Term;
    prev->next->exp = P->exp;
    prev = prev->next;
  }
  prev->next = NULL;
  return H;
}


Polynomial::Polynomial() 
{
  terms = NULL;
}

Polynomial::Polynomial(const Polynomial& P) 
{
  terms = duplicateList(P.terms);
}


Polynomial& Polynomial::operator=(const Polynomial& P) 
{
  if (&P != this) 
  {
    Term *H = duplicateList(P.terms);
    deleteList(terms);
    terms = H;
  }
  return *this;
}


Polynomial::~Polynomial() 
{
  deleteList(terms);
}


bool Polynomial::zero() const
{
  if(terms->next == NULL)
    return true;		//meaning it is zero
  else
    return false;		//meaning it is not zero poly
}

unsigned Polynomial::degree() const
{
  int degree = 0;
  for(Term *P = terms; P != NULL; P = P->next)
    degree = P->exp;
  return degree;
}

static Term *find_term(Term *T, unsigned k)
{
  Term *prev = NULL;
  Term *curr = T;
  while(curr != NULL && curr->exp < k) 
  {
    prev = curr;
    curr = curr->next;
  }
  return prev;
}

Polynomial& Polynomial::multiply_term(int c, unsigned k)
{
  assert(c != 0);
  for (Term *P = terms; P != NULL; P = P->next) 
  {
    P->coef = P->coef * c;   // multiply coef
    P->exp = P->exp + k;    // add exponents
  }
  return *this;
}


Polynomial& Polynomial::add_term(int c, unsigned k)
{
  Term *T = new Term;
  T->coef = c;
  T->exp = k;

  Term *prev = find_term(terms, k);

  if(terms == NULL)
  {
    T->next = terms;
    terms = T;
    return *this;
  }
  if(prev == NULL)
  {
    if(terms->exp == k)
    {
      T->coef += c;
      T->next = terms;
      delete terms;
      terms = T;
      return *this;
    }

    else if(terms->exp != k)
    {

      T->next = terms;
      terms = T;
      return *this;
    }
  }

  T->next = terms;
  terms = T;
  return *this;
}


bool Polynomial::equal(const Polynomial& P) const
{
  //check first node
  if(terms->coef != P.terms->coef || terms->exp != P.terms->exp)
    return false;

  //check other nodes
  Term *node1 = terms->next;
  Term *node2 = P.terms->next;
  while(terms != NULL)
  {
    if(node1->coef != node2->coef || node1->exp != node2->exp)
      return false;
    node1 = node1->next;		//increment the nodes
    node2 = node2->next;
  }
  if(P.terms != NULL)	//if they don't end at the same node
    return false;

  return true;		//if it never fails, they are same
}


void Polynomial::print() const
{
  Term *T = terms;	//copy the polynomial so I can advance the node
  if(T == NULL)
    cout << 0;
  else
  {
    while(T != NULL)
    {
      // print the sign of the term
      if(T->coef < 0)
        cout << "- ";
      else if(T->coef > 0 && T->exp == 0)
        cout << " ";
      else if(T->coef > 0 && T->exp > 0)
        cout << "+ ";

      // print the term
      if(T->exp == 0)
        cout << abs(T->coef);
      else if(terms->exp == 1)
        cout << abs(T->coef) << " x ";
      else if(terms->exp > 1)
        cout << abs(T->coef) << " x^" << T->exp << " ";
      T = T->next;		//advance to next node
    }
  }
}

Now the problem lies within add_term

CPP / C++ / C Code:

Polynomial& Polynomial::add_term(int c, unsigned k)
{
  Term *T = new Term;
  T->coef = c;
  T->exp = k;

  Term *prev = find_term(terms, k);

  if(terms == NULL)
  {
    T->next = terms;
    terms = T;
    return *this;
  }
  if(prev == NULL)
  {
    if(terms->exp == k)
    {
      T->coef += c;
      T->next = terms;
      delete terms;
      terms = T;
      return *this;
    }

    else if(terms->exp != k)
    {

      T->next = terms;
      terms = T;
      return *this;
    }
  }

  T->next = terms;
  terms = T;
  return *this;
}

The problem is that, when I initialize a zero polynomial "poly1" and then go:
poly1.add_term(-4,0).add_term(2,1).print();

It will show 2x - 4 instead of -4 + 2x

Something in there is making it switch the order so when the new node is added to the linked list, it puts it before the existing one, rather than after...

I am super tired and my brain cannot comprehend anything, so PLEASE be descriptive with how I can fix this. i'm really in a rut here guys...

Thanks in advance,

Kris

EDIT: by the way, here is my test program:

CPP / C++ / C Code:

// test_polynomial.cpp
//

#include <iostream>
#include "polynomial.h"

using namespace std;

int main() 
{
  //zero polynomial
  Polynomial poly1;
  cout << "The zero polynomial is: " << endl;
  poly1.print();
  unsigned deg1 = poly1.degree();
  cout << endl << "The degree of the zero polynomial is: " << endl;
  cout << deg1 << endl;


  cout << "The constant polynomial -2 is: " << endl;
  poly1.add_term(-2, 0).print();
  deg1 = poly1.degree();
  cout << endl << "The degree of the -2 polynomial is: " << endl;
  cout << deg1 << endl;

  Polynomial poly2;
  cout << "The polynomial ( -3 + 4x ) is: " << endl;
  poly2.add_term(-3, 0).add_term(4,1).print();
  cout << endl << endl;
  

  return 0;
}

cable_guy_67 · #2 06-Dec-2005, 05:28

krisopotamus,

First off, very nicely presented request. One thing though. When I tried to compile I got the error:

Code:

ME@MYCPU ~/workarea/forum
$ g++ -Wall test_polynomial.cpp polynomial.cpp -s -o TestPoly
polynomial.cpp:151: error: no `bool Polynomial::equal(const Polynomial&) const' member function declared in class `Polynomial'

Easy enough to take care of but I wanted to be sure you posted your correct h file.

Mark

LuciWiz · #3 06-Dec-2005, 05:36

Quote:

Originally Posted by krisopotamus

The problem is that, when I initialize a zero polynomial "poly1" and then go:
poly1.add_term(-4,0).add_term(2,1).print();

It will show 2x - 4 instead of -4 + 2x

Something in there is making it switch the order so when the new node is added to the linked list, it puts it before the existing one, rather than after...

Yes. The "something" is you

CPP / C++ / C Code:

else if(terms->exp != k)
{
	T->next = terms;  // !!!make the rest of the list follow this new node!!!
	terms = T;          //  !!!the new node is the new first element          !!!
	return *this;       // return the new element
}

Right?
So you must think the other way around: instead of inserting the new element in front of the list, insert it at the end.
In case this wasn't descriptive enough (meaning you can't change it for yourself), I'll post the solution in a few hours.
But try it please

Kind regards,
Lucian

krisopotamus · #4 06-Dec-2005, 10:49

That's what I thought the problem was too, I spent some time trying to change it (before you posted), without any success.

I don't really know what I have to do to fix this

LuciWiz · #5 06-Dec-2005, 16:42

Quote:

Originally Posted by krisopotamus

That's what I thought the problem was too, I spent some time trying to change it (before you posted), without any success.

I don't really know what I have to do to fix this

Hi.

Sorry for replying so late. You can thank my ISP

I'll write some code now or in the morning. First, be careful with a few things.
First, your printing function isn't OK:

CPP / C++ / C Code:

      // print the term
      if(T->exp == 0)
        cout << abs(T->coef);
      else if(terms->exp == 1)
      // ... [snipped]

What's wrong here?

Also, there is absolutely no need to make a static pointer! Hm, maybe a situation could rise when this would be needed, since it is possible!? Very unlikely. You dynamically allocate the memory, so it will be there. I think you misunderstood the use of static (or pointers maybe?). More about this some other time...

The idea in adding values in a list at the end is to also store the last element of the list, not only the first (this also comes in handy when you wish to run through the list in both directions). I guess there are other ways to implement this solution too, but this seems the most straight forward.

Best regards,
Lucian

krisopotamus · #6 06-Dec-2005, 16:44

I got it working. The reason why I used static was because the header file (with function prototypes) was already given to me, and i had to make my program corresponding to them. I got it to add it in the right spot.

Thanks for the help tho, but yay I'm done

LuciWiz · #7 06-Dec-2005, 17:21

OK, from what I understood, you want to add the coefficients of the elements with the same exponent, right (logical). So, there shouldn't always be created a new T element. In order to make it resemble your original program, I left this part as it was (for now). You also delete the variable terms at some point - why? What was your reasoning there? (I really want to know)

I understand that you use terms as the pointer to the first element, right? I recommend you change the name to something more suggestive. Like I named the new member variable I added pLastTerm_ - p for Pointer, then a Camel notation for the words inside, and the last underscore to know it is a member variable (you can choose whatever convention you like). I also left the old name unchanged, so you can understand it easier.
I will now present you the code I produced; it's not complete, in the sense I miss some logic in it - I didn't quite get what you were trying to do. I'll just let you read the comments, and we can talk tomorrow, I'm really sleepy

So, add the new member variable:

CPP / C++ / C Code:

private:

	Term * terms;
	Term * pLastTerm_;

Initialize it:

CPP / C++ / C Code:

Polynomial::Polynomial() 
{
	terms = pLastTerm_ = NULL;
}

The code for add_term (with comments):

CPP / C++ / C Code:

Polynomial& Polynomial::add_term(int c, unsigned k)
{
	Term * T = new Term();
	T->coef = c;
	T->exp = k;

	Term * succ = find_next_term(terms, k);

	if (terms == NULL)				// empty list
	{
		T->next = NULL;				// the next element after the last should be NULL
		pLastTerm_ = T;				// the new added element should be the last
		terms = T;					// and also the first
		//return *this;				// no need for multiple return branches - messy!
	}
	else							// non-empty list
		if (succ != NULL)				//if found or greater (find_next_term returns NULL if not found)
		{
			if ( succ->exp == k )		// if it has the same exponent
			{			
				succ->coef += c;		// increment the coefficient
				//return *this;			// no need for multiple return branches - messy!
			}	
			else						//if (succ->exp != k)	
			{
				pLastTerm_->next = T;	// because it will be next after the former last
				pLastTerm_ = T;			// the new last element is the new added one
				//return *this;			// no need for multiple return branches - messy!
			}
		}
		else							// not found
		{
			pLastTerm_->next = T;	// because it will be next after the former last
			pLastTerm_ = T;			// the new last element is the new added one
			//return *this;			// no need for multiple return branches - messy!
		}

	// now return
	return *this;

}

The new find_next_term :

CPP / C++ / C Code:

Term * find_next_term(Term *T, unsigned k)
{
	Term * next = NULL;
	Term * curr = T;
	while(curr != NULL && curr->exp < k) 
	{
		//prev = curr;
		curr = curr->next;
		next = curr;
	}
	return next;
}

Also, while you are at it, please take a look at your degree member function; I really don't understand what (or why) are you trying to do - why would you cycle through the list, only to return the last element (because you didn't have a last maybe?

- still, there was no need to assign each element in the list...).

[edit]
I see you got it working; great news! Maybe you could post your code, there were some parts I didn't get

[/edit]

HTH,
Lucian

LuciWiz · #8 06-Dec-2005, 17:26

Quote:

Originally Posted by krisopotamus

The reason why I used static was because the header file (with function prototypes) was already given to me, and i had to make my program corresponding to them.

You mean you couldn't add member functions, right? Yes, I thought that was the reason - but static isn't he solution. Your functions will work the same without static. I'll try to explain better tomorrow.

Good night

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 14:13
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 01:34
adding to linked list from external file	cghv	C Programming Language	3	09-Mar-2005 13:36

Linked List help!

Re: Linked List help!

Re: Linked List help!

Re: Linked List help!

Re: Linked List help!

Re: Linked List help!

Re: Linked List help!

Re: Linked List help!