Problem with linked list addition

This is a discussion on Problem with linked list addition within the C++ Programming forums, part of the General Programming Boards category; okay, I'm writing a function that takes two polynomials, adds them, then outputs the result. there are two things wrong ...

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    46

    Problem with linked list addition

    okay, I'm writing a function that takes two polynomials, adds them, then outputs the result. there are two things wrong with my program:

    1) when one of the terms in the polynomial has an exponent of 1 my input function always puts it at the beginning of the list for some reason
    2) when I add and output the result, only the coefficient of the first term is written. this is only with the first term, the rest is fine

    here's my code (important functions are in bold):
    Code:
    POLYNOMIAL.H
    ------------
    //this is the header file for class Polynomial and struct term
    
    using namespace std;
    
    struct node
    {
      int co;   //coefficient of the term
      int exp;  //exponent of the term
      node* link;
    };
    
    typedef node* nodeptr;
    
    class Polynomial
    {
      public:
        Polynomial (const Polynomial& p1);
        ~Polynomial();
        void operator = (Polynomial& p1);
        Polynomial() {head = NULL;}
        const nodeptr get_head() const {return head;}
        void set_head(nodeptr t1) {head = t1;}
        Polynomial operator + (Polynomial& p1);
        friend istream& operator >> (istream& ins, Polynomial& p1);
        friend ostream& operator << (ostream& outs, Polynomial& p1);
      private:
        nodeptr head;
    };
    
    POLYNOMIAL.cc
    -------------
    //definitions for = and + operators and output
    
    Polynomial Polynomial::operator + (Polynomial& p1)
    {
      Polynomial temp;
      nodeptr temp_ptr, current;
      nodeptr cursor1 = head;
      nodeptr cursor2 = p1.get_head();
      nodeptr result;
    
      if (cursor1->exp > cursor2->exp)
      {
        temp_ptr = new node;
        temp_ptr->co = cursor1->co;
        temp_ptr->exp = cursor1->exp;
        temp.set_head(temp_ptr);
        cursor1 = cursor1->link;
      }else if (cursor2->exp > cursor1->exp)
      {
        temp_ptr = new node;
        temp_ptr->co = cursor2->co;
        temp_ptr->exp = cursor2->exp;
        temp.set_head(temp_ptr);
        cursor2 = cursor2->link;
      }else if (cursor1->exp == cursor2->exp)
      {
        temp_ptr = new node;
        temp_ptr->co = cursor1->co + cursor2->co;
        temp_ptr->exp = cursor1->exp;
        temp.set_head(temp_ptr);
      }
      current = temp.get_head();
    
      while ((cursor1 != NULL) || cursor2 != NULL))
      {
        if (!cursor1)
        {
          current->link = new node;
          current = current->link;
          current->co = cursor2->co;
          current->exp = cursor2->exp;
          cursor2 = cursor2->link;
        }else if (!cursor2)
        {
          current->link = new node;
          current = current->link;
          current->co = cursor1->co;
          current->exp = cursor1->exp;
          cursor1 = cursor1->link;
        }else if (cursor1->exp == cursor2->exp)
        {
          current->link = new node;
          current = current->link;
          current->co = cursor1->co + cursor2->co;
          current->exp = cursor1->exp;
          cursor1 = cursor1->link;
          cursor2 = cursor2->link;
        }else if (cursor1->exp > cursor2->exp)
        {
          current->link = new term;
          current = current->link;
          current->co = cursor1->co;
          current->exp = cursor1->exp;
          cursor1 = cursor1->link;
        }else if (cursor1->exp < cursor2->exp)
        {
          current->link = new term;
          current = current->link;
          current->co = cursor2->co;
          current->exp = cursor2->exp;
          cursor2 = cursor2->link;
        }
      }
      current->link = NULL;
      return temp;
    }
    
    istream& operator >> (istream& ins, Polynomial& p1)
    {
      char x;
      nodeptr temp, current, prev;
      int co, exp;
    
      ins >> co;
      while (ins.peek() != '\n')
      {
        ins >> x >> exp;
        temp = new node;
        temp->link = NULL;
        temp->co = co;
        temp->exp = exp;
    
        if (p1.get_head() == NULL)
        {
          p1.set_head(temp)
        }else
        {
          current = p1.get_head();
          while (current != NULL && current->exp > exp)
          {
            prev = current;
            current = current->link;
          }
          if (current = p1.get_head())
          {
            temp->link = p1.get_head();
            p1.set_head(temp);
          }else
          {
            temp->link = current;
            prev->link = temp;
          }
        }
        ins >> co;
      }
      if (p1.get_head() != NULL)
      {
        current = p1.get_head();
        prev = current;
        if (current->link != NULL)
        {
          current = current->link;
          while (current->link != NULL)
          {
            current = current->link;
            prev = prev->link;
          }
          temp = new node;
          temp->co = co;
          temp->link = NULL;
          current->link = temp;
        }else if (current->link == NULL)
        {
          temp = new node;
          temp->co = co;
          temp->link = NULL;
          current->link = temp;
        }
      }
      return ins;
    }
    
    ostream& operator << (ostream& outs, Polynomial& p1)
    {
      for (nodeptr ptr = p1.get_head(); ptr != NULL; ptr = ptr->link)
      {
        if (ptr == p1.get_head())
        {
          if (ptr->exp == 0)
          {
            outs << ptr->co;
          }else if (ptr->exp == 1)
          {
            outs << ptr->co << "x";
          }else if (ptr->exp > 1)
          {
            outs << ptr->co << "x" << ptr->exp;
          }
        }else
        {
          if (ptr->exp == 0)
          {
            outs.setf(ios::showpos);
            outs << ptr->co;
            outs.unsetf(ios::showpos);
          }else if (ptr->exp == 1)
          {
            outs.setf(ios::showpos);
            outs << ptr->co << "x";
            outs.unsetf(ios::showpos);
          }else if (ptr->exp > 1)
          {
            outs.setf(ios::showpos);
            outs << ptr->co;
            outs.unsetf(ios::showpos);
            outs << "x" << ptr->exp;
          }
        }
      }
      return outs;
    }
    
    void Polynomial::operator = (Polynomial& p1)
    {
      nodeptr temp, temp1;
      temp = p1.get_head();
    
      if (temp == NULL)
        return;
    
      temp1 = new node;
      temp1->co = temp->co;
      temp1->exp = temp1->exp;
      head = temp1;
      temp = temp->link;
    
      for (nodeptr ptr = temp; ptr != NULL; ptr = ptr->link)
      {
        temp1->link = new term;
        temp1 = temp1->link;
        temp1->co = ptr->co;
        temp1->exp = ptr->exp;
      }
      temp1->link = NULL;
    }
      
    //copy constructor has the exact same code as the equal operator
    //I don't think you need the code for the destructor
    
    MAIN.cc
    -------
    //application file
    
    #include <iostream>
    #include "polynomial.h"
    
    using namespace std;
    
    int main()
    {
      Polynomial poly1, poly2, result;
    
      cout << "Please enter a polynomial: ";
      cin >> poly1;
      cout << endl;
      cout << "Please enter another one: ";
      cin >> poly1;
      cout << endl;
    
      result = poly1 + poly2;
      cout << "The addition of the polynomials is:\n";
      cout << "  " << poly1 << endl;
      cout << "+ " << poly2 << endl;
      cout << "-------------------------\n";
      cout << "  " << result << endl;
    
      return 0;
    }
    
    SAMPLE OUTPUT:
    --------------
    p1% g++ *.cc
    p1% a.out
    Please enter a polynomial: 2x3+4x5+6
    Please enter another one: 6x2+3x5+3
    The addition of the polynomials is:
    
      4x5+2x3+6
    + 3x5+6x2+3
    -------------
    7+2x3+6x2+9
    
    //I can't figure out why it only outputs the coefficient of the first term
    
    p1% a.out
    Please enter a polynomial: 3x3+4x4+2x1+3
    Please enter another one: 3x2+4x3+4
    The addition of the polynomials is:
    
      2x+4x4+3x3+3
    + 4x3+3x2+4
    ---------------
    4+3x2+2x+4x4+3x3+7
    
    //this one just has me stumped,I can't figure out why it sends the term with
    //an exponent of 1 to the head this is what always happens when there's a 
    //term with an exponent of 1'
    please help me, I need to get this done tonight

  2. #2
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    I haven't traced the program flow extensively, but the very first thing that jumped out at me is:
    Code:
    ins >> x >> exp;
    It looks to me like you're not checking to see if there is an exponent or not - so if the exponent is 1 (so you don't put an exponent after the x), then you'll have a problem with input (I'm surprised you don't just get an error flag set and the rest of the program whiz by without getting any more input). You can probably fix this particular problem by adding another peek() to see if the next character is a '+' or a digit, and only input exp if it's not '+'.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    46
    in the input there has to be a 1 after the x. I tried to make it more robust but my instructor told me not to bother lol

  4. #4
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    Alright, well I noticed this in your operator=:
    Code:
    temp1->exp = temp1->exp;
    Looks a little suspicious to me.

    Also:
    Code:
    temp1->link = new term;
    Not sure if this was a typo, but I don't see 'term' defined anywhere, so I don't see how this is compiling at all. It would seem to me that you want new node here instead? After all, isn't temp1->link defined to be a nodeptr or node*?

    See if that helps, if not then (*sigh*) we'll have to inspect the operator+ and other functions as well.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    311
    I don't see where this causes a problem but one thing to help untangle things is to give node a constructor.
    Code:
    struct node
    {
        int co;    //coefficient of the term
        int exp;  //exponent of the term
        node* next;
        node(int cco, int eexp, node *n=0) : co(cco), exp(eexp), next(n) 
    {}
        node(const node &o) : co(o.co), exp(o.exp), next(0) {} // shallow copy ctor
    };
    
    typedef node* nodeptr;
    // Grrrrrrrrrr
    
    if(head==0 || head->exp < exp ) head = new node(co,exp);
    else {
        node *p=head->next;
        while(p && exp < p->exp) p = p->next;
        p->next = new node(co,exp,p->next);
    }
    
    // we can even do this
    struct node
    {
        int co;    //coefficient of the term
        int exp;  //exponent of the term
        node* next;
        node(int cco, int eexp, node *n=0) : co(cco), exp(eexp), next(n) {}
        node(const node &o) : co(o.co), exp(o.exp), next(0) {} 
        node * add(int c, int e) {
            if(e > exp) return new node(c,e,this);
            if(e < exp) {
                node *p = this;
                while(p->next && e < p->exp) p = p->next;
                if(p->next && p->next->exp == e) {
                    p->next->co += c;
                } else {
                    p->next = new node(c,e,p->next);
                }
            } else co += c;
            return this;
        }
    };
    
    if(head) head = head->add(c,e); else head = new node(c,e);

    The main thing is that you have several places where you are creating and setting up nodes, the constructor gives you only one way to build a node, and while you can still muck around with the next pointers and screw things up you have less reason to do so.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  3. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21