C++

Forum

 
Polynomial Addition in Array-based Linked List

TheJJJunk (181)
I've made a polynomial class using an array-based linked list, but my addition function isn't working. It seems to work if the 2nd polynomial only has one term, but not if it has more than one. I'm not sure if it is a problem with my add function or my insertTerm function.

The class uses a ListNode array.
1
2
3
4
5
6
7
8
9
10
11
12
 
struct ListNode
    {
        /** A data item on the list. */
        Polynomial_coefficient_type coefficient;
        Polynomial_exponent_type exponent;

       int next;
    }; // end ListNode

ListNode array[50];
int head; // first used index
int free;


free is the first unused index in the array.
The last used index in the list has a next item of '-1'.

This is a case in my switch statement in my main function, which creates the second polynomial and then adds it to the original one:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
case 6:
            cout << "\nEnter a term to create second polynomial.";
            do
            {
                cout << "\nEnter the new term's coefficient: ";
                cin  >> a;
                cout << "Enter the new term's exponent: ";
                cin  >> b;
                p2.insertTerm(a, b);
                cout << "Enter another term? (y/n): ";
                cin  >> cont;
            } while (cont == 'y');

             p1.add(p2);
            break;


My add function inserts terms from the second polynomial into the original polynomial. The polynomial is then simplified, which isn't shown:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void Polynomial::add(Polynomial b)
{
    //if b is empty, original polynomial is itself

    if (!b.isEmpty())
    {
        int bTemp = b.head;

        while (bTemp != -1) // '-1' is the 'next' item in the listnode of the last item in the list
        {
            insertTerm(b.array[bTemp].coefficient,
                       b.array[bTemp].exponent);
            bTemp = b.array[bTemp].next;
        }
    }
}


insertTerm:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
void Polynomial::insertTerm(Polynomial_coefficient_type& newCo,
                            Polynomial_exponent_type& newExpo)
{
    if (newCo != 0)
    {
        array[free].coefficient = newCo;
        array[free].exponent = newExpo;

        if (free == head) // if list is empty
        {
            array[head].next = -1;
            ++free;
        }

        else // if list isn't empty
        {
            int prev = head;
            int cur  = head;

            while (array[cur].next != -1 &&
               array[cur].exponent > newExpo)
            {
               prev = cur;
               cur  = array[cur].next;
            }

            if (cur == head && // 2nd item, at beginning
                array[cur].exponent < newExpo)
            {
               array[free].next = head;
               head = free;
               for (int i=0; i < 50; i++)
                  if (array[i].next == -2)
                   free = i;

            }

            else if (array[cur].next == -1) // insert at end
            {
                array[cur].next  = free;
                array[free].next = -1;
                for (int i=0; i < 50; i++)
                {
                  if (array[i].next == -2)
                  {
                      free = i;
                      break;
                  }
                }
            }

            else // insert in middle
            {
                array[free].next = cur;
                array[prev].next = free;
                for (int i=0; i < 50; i++)
                {
                  if (array[i].next == -2)
                  {
                      free = i;
                      break;
                  }
                }
            }
        }

        int newLength = getLength() + 1;
        size = newLength;

        simplify();
    }

    else
    {
        cout << "The coefficient is 0! "
             << "The term will not be added.\n";
    }
} // end insert


Thanks for the help.
Last edited on
helios (17574)
This is really a "linked list" in name only. Inserting a node takes O(n) time, and you're limited to 50 nodes. Why not allocate the nodes in the heap?
TheJJJunk (181)
I've already created a working pointer-based polynomial linked list, now I'm working on this one. And there is a doubling function which copies the array to a new array that is double the size of the original array, if it gets full.
Last edited on
Topic archived. No new replies allowed.