These are some of the most frequent mistakes students made in the lab when I worked as a tutor for ICS 46, Data Structure Implementation and Analysis. Anyone who is taking the class could benefit by reviewing these examples and trying to figure out what is wrong with each of them. I will explain what kind of errors each method contains and how to fix them at the bottom of this post.
Example 1.
template<class T>
int LinkedQueue<T>::enqueue(const T& element)
{
rear->next = new LN(element);
rear = rear->next;
return 1;
}
Example 2.
template<class T>
LinkedQueue<T>::LinkedQueue(const LinkedQueue<T>& to_copy)
{
used = to_copy.used;
front = to_copy.front;
rear = to_copy.rear;
mod_count = to_copy.mod_count;
}
Example 3.
template<class T>
T& HeapPriorityQueue<T>::peek() const
{
return pq[0];
}
Example 4.
template<class T>
void HeapPriorityQueue<T>::percolate_down(int i)
{
while (gt(pq[left_child(i)],pq[i]) || gt(pq[right_child(i)],pq[i])){
int greater_child = gt(pq[left_child(i)], pq[right_child(i)]) ? left_child(i) : right_child(i);
std::swap(pq[i], pq[greater_child]);
i = greater_child;
}
}
The examples above might seem to be working most of the times but would definitely cause errors or undesired behaviors somewhere in your program.
1) Example 1 will raise a segmentation fault when rear is nullptr. You can’t access rear->next when rear is not a node. This happens when you’re enqueuing to an empty queue. To avoid this kind of error, you should always consider edge cases; your code should always work from when you insert the first item until you delete the last item, and sometimes you need to make appropriate changes to your code. In this case, you should detect if the queue is empty and if it is then you should create a new node which will be both the front and the rear.
2) If you construct an object using the constructor in Example 2, then your queue would work as if you succeeded in copying another queue. Enqueuing and dequeuing on one queue might not seem to have any effect on the other. However, it does not change the fact that the code above merely makes the new queue refer to the original queue. If you implemented dequeue() method correctly and actually used delete statements, then you would see dequeuing or clearing from one queue affects the other queue and raises runtime errors when accessing items that have already been deleted.
3) The code in example 3 would work most of the times. However, when the queue is empty then it would show unexpected behavior. If you empty a queue and call a peek() method on it, it would behave as if the queue still has the last item you dequeued in its front. You should check if your queue is empty and show appropriate error message.
4) The method in example 4 might access data that has already been removed in the heap because of the same reason as example 3. Or it would access initialized variables (such as 0 or an empty string) and treat them as if they are part of the heap. You should check if the heap is using the indices of the children before accessing them and terminate the loop if both of them are not in the heap.
