Need help with problem in my linked list class

freddy92 (274)
Hi, so I'm making a singly linked list class that is supposed to hold Term objects that make up a polynomial. I want the terms to be sorted from highest exponent to lowest exponent, but I'm having some trouble. For some reason that I cannot find, my insert function inserts them in the reverse order. If it should store something like 5x^7 + 3x^4 + 9x^2 + 10, it will store it as 10 + 9x^2 + 3x^4 + 5x^7. I'm sure that I have some simple little error somewhere in my functions that is causing this, but I just can't pin it down. Here are the related functions: 

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
 
template<typename T>
void List<T>::insert(int exp, const T& newItem)
{
	int newLength = getLength() + 1;

	if ( (exp < 0) || (exp > degree) )
		cout << "Exponent " << exp << " is out of range" << endl;

	else
	{
		ListNode *newPtr = new ListNode();
		newPtr->item = newItem;

		if (size == 0) // If the list is currently empty
		{
			newPtr->next = head;
			head = newPtr;
		}
		else
		{

			ListNode *prev = find(exp,newPtr->next);
			if (newPtr->next->item == exp) // If the value to be placed is already in the list
			{
				cout << "Insert failed.  Exponent " << exp << " already in list" << endl;
				return;
			}
			else if (prev == NULL) // If the value to be placed is to be first in the list
			{
				newPtr->next = head;
				head = newPtr;
			}
			else
			{
				prev->next = newPtr;
			}
		}
		size = newLength;
	}
}

// Intended to find the position in the list where the new node should be added.
// Should return the node previous to where the new node should be placed
// And pass the node after it back by reference
template<typename T>
typename List<T>::ListNode *List<T>::find(int exp, typename List<T>::ListNode * &current) const 
{
	if ( (exp < 0) || (exp > degree) )
	{
		cout << "Invalid exponent" << endl;
		current = NULL;
		return NULL;
	}
	else
	{
		ListNode *cur = head;
		ListNode *prev = NULL;
		for (int i = 0; i < size; i++)
		{
			if ( cur->item == exp || cur->item > exp)
				break;
			else
			{
				prev = cur;
				cur = cur->next;
			}
		}
		current = cur;
		return prev;
	}
}


From what I can tell, the function works fine except that it puts the items in the reverse order. I'm going to keep trying to track down the error here, but I figured that I might as well post it here to see if anyone else can help me out. If you can, that'd be great.
Mathhead200 (1016)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
//Line 60
if ( cur->item == exp || cur->item > exp)
	break;
/*
 * Your problem is right here in your "find" method.
 * You are looking for the appropriate place in ascending order;
 * i.e. insert the term in the first place such that it is greater (in order)
 * then all the elements before it, but not the ones that come after it.
 * You need to flip that; i.e. you want it in the first available space such that it is greater
 * (in order) then all the terms that will come after it, but not before it.
 */

//Try this:
if( cur->item <= exp )
	break;


Hope this works for you...
Note the combined comparison operations:
1
2
3
 
a >= b    same as    a > b || a == b
a <= b    same as    a < b || a == b
// ;)
Topic archived. No new replies allowed.