Forgetting to Set a Pointer to NULL
Suppose we would like to reverse the order of some integers being entered
by the user. We can do this easily using a stack and a queue. As the user
enters each integer, we'll create a node, fill its data portion with that
integer and Push() it onto a stack. When the user is finished entering values,
we'll Pop() the stack and Enqueue() the value. We'll continue to Pop() and
Enqueue() until the stack is empty. The queue will now contain the values
that the user entered, but they will be in reverse order.
Since both the stack and the queue are being implemented as linked lists,
the nodes are the same. If we modify Pop() so that it returns a pointer to
the node being popped, rather than free()ing the node and returning only the
data portion, then we won't have to create a new node to store the data in
before we can Enqueue() it. This is a great idea and saves lots of time, but
you must be very careful. This code shows a very common mistake :
<![CDATA[
/******************
* Pop takes a pointer to a NODEPTR as its
* only argument. It will hold the address
* of top. This function removes an item from
* the stack and returns a pointer to the node
* it's in. This function alters the value
* of top unless the stack is empty.
******************/
NODEPTR Pop (NODEPTR *topPtr)
{
NODEPTR temp;
temp = *topPtr;
if (IsEmpty (*topPtr))
{
printf ("Can't pop an empty stack\n");
}
else
{
*topPtr = (*topPtr) -> next;
}
return temp;
}
]]>
What address is temp -> next holding ?
It's pointing to the node that is on top of the stack. It really should
have been set to NULL before returning temp.
Here is a program that Push()es 4 items onto a stack, then Pop()s 1 item
and Enqueue()s that item. I've used the buggy code for the Pop() function
shown above.
<![CDATA[
The stack is empty
Enter the value of data : 1
Pushing the value, 1
Enter the value of data : 2
Pushing the value, 2
Enter the value of data : 3
Pushing the value, 3
Enter the value of data : 4
Pushing the value, 4
The stack contains :
4 3 2 1
The queue is empty
4 was Popped
Enqueueing : 4
After Enqueueing only one item
The queue contains :
4 3 2 1
and
The stack contains :
3 2 1
]]>
Oops !