Member Avatar for sarahnade17

The program I'm trying to write uses a linkedList templated class to manipulate and add polynomials in the form ax^b + cx^d + ex^f etc. The polynomials are stored as linked lists.
My problem occurs when I try to add them together. I've added some cout lines to try to trace what the program is doing. It seems like the getNext function is successfully advancing the current pointer, but when the program leaves getNext the current pointer goes back to the beginning. I can't understand why it's starting itself over.
I think it's either a problem with getNext (in the implementation file) or add (in the application file).

HERE'S MY LINKEDLIST CLASS:

template <class T>
class linkedList
{public:

  //sets the head to null
  linkedList() {head = NULL;}

  //Copy constructor does a deep copy
  linkedList(const linkedList &list);

  //Assignment operator does a deep copy
  linkedList& operator=(const linkedList &list);

  //returns true if the list is empty, false otherwise
  bool empty() const;

  //inserts the value in the list to maintain ascending order
   //insert fails if the value is already in the list
  bool insert(T value);

  //find looks for the value in the list.  If found, it copies
  // the list component into the parameter.  This is in case
  // the component is not a simple type.
  //Return: true if found, falser otherwise
  bool find(T &value);

  //for traversing
  //moves to the beginning of the list
  void start();

  //returns the next value in the list and advances along
  //getNext fails if it is at the end of the list
  bool getNext(T &value);

 private:

  class node
  {
    public:
      node() {next = NULL;}
      node(T value) {data = value; next = NULL;}
      T data;
      node *next;
  };

  //attributes
  node *head;            //points to the beginning of the list
  node *current;         //keeps track of where the traversal is
};

MY GETNEXT FUNCTION IS DEFINED IN THE IMPLEMENTATION FILE:

bool linkedList<T>::getNext(T &value)
      { start();
        value = current->data;
        cout << value << endl;
        if(current->next != NULL)
          { current = current->next;
            return true;
          }
        else
          return false;
      }

MY ADD FUNCTION IS DEFINED IN THE APPLICATION FILE:

linkedList<term> add(linkedList<term> &Apoly1, linkedList<term> &Apoly2)
  { linkedList<term> answer;
    term t1, t2, t3;
    bool oneOK, twoOK;
    Apoly1.start();
    Apoly2.start();
    oneOK = Apoly1.getNext(t1);
    twoOK = Apoly2.getNext(t2);
    while(oneOK && twoOK)
      { if(t1==t2)
          {t3 = t1 + t2;
            answer.insert(t3);
            oneOK = Apoly1.getNext(t1);
            twoOK = Apoly2.getNext(t2);
          }
        else if (t1 < t2)
          {answer.insert(t1);
            oneOK = Apoly1.getNext(t1);
            }
        else
          { answer.insert(t2);
            twoOK = Apoly2.getNext(t2);
          }
      }
    while(oneOK)
      { answer.insert(t1);
         oneOK = Apoly1.getNext(t1);
      }
    while(twoOK)
     { answer.insert(t2);
        twoOK = Apoly2.getNext(t2);
      }
  }

When I tried to run the program, I used poly1= 2x^2 + 3x^3 and poly2= 4x^2 + 6x^3. I added some cout lines in getNext to see where current was.

Basically, when getNext was first called, the current pointer in poly1was pointing to 2x^2, and the current pointer in poly2 was pointing to 4x^2.
GetNext correctly set t1 = 2x^2 and t2 = 4x^2.
GetNext moved the current pointer in poly1 was to point to to 3x^3 and the current pointer in poly2 to point to 6x^3.
Add inserted 6x^2 into the sum.
BUT when it called on getNext a second time (and every time after that), the current pointer in poly1 was pointing to 2x^2 again! And the current pointer in poly2 was pointing to 4x^2 again!
So even though getNext is changing the current pointer, the change isn't lasting- the pointer starts over at the beginning after we leave getNext.

  • 2 Contributors
  • 2 Replies
  • 128 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by sarahnade17

Dani AI

Generated

Short diagnosis: nailed the root cause — getNext should not call start(). That resets current to the head every time, so traversal can never advance. Also, getNext as written returns false when it hands back the last node (because it returns false when current->next == NULL), which is the wrong semantic: it should return true whenever it successfully returns a value and only return false when there is nothing to return.

Minimal, safe traversal semantics to adopt (replace the buggy versions):

void linkedList<T>::start() { current = head; }

bool linkedList<T>::getNext(T &value) {
  if (current == NULL) return false;   // nothing left
  value = current->data;               // give caller the current item
  current = current->next;             // advance for the next call
  return true;                         // we returned a value
}

Other issues to check while fixing this:

  • Initialize current in the constructor (e.g., set it to NULL or head) so getNext and start behave predictably.
  • The add function in the posted code builds answer but never returns it. Add return answer; at the end and compile with warnings enabled (-Wall -Wextra) to catch this.
  • Traversal via start()/getNext() mutates current. If callers expect the original list to remain usable afterwards, either traverse on a copy or provide a const iterator/const traversal API.
  • Verify term has consistent operator==, operator<, and operator+ semantics (compare exponents as intended for polynomials).
  • Ensure your copy constructor / assignment operator perform deep copies to avoid lifetime/double-free problems when returning answer.

Quick debugging tips: print pointer values (cast to void*) to watch current change, use a debugger to step through calls, and run under Valgrind to catch invalid memory access.

Recommended Answers

All 2 Replies

Member Avatar for nucleon

Is it because you're calling start() at the beginning of getNext() ? According to your comment for start() it moves the pointer to the beginning of the list.

Member Avatar for sarahnade17

oh my god I can't believe I didn't notice that. I think that might be it, I'll try that.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.