-1

So for some reason my program stops running after the 2nd enqueue. It compiles and gives no error messages, it just suddenly quits. Not even an aborted message or anything. I've had 2 other people in higher CS classes than me take a look and they can't see anything wrong either...

main is as follows:

using namespace std;
#include <iostream>
#include "Queue.h"
#include "LinkedList.h"

int main()
{
  try
    {
        int type = 0;

        cout<<"What data type do you want to work with? 1 = int, 2 = char"<<endl;
        cin>>type;

        if(type == 1)
        {
            Queue<int> q;

            q.enqueue(1);
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.enqueue(5);
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.enqueue(3);
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.enqueue(5);
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.dequeue();
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.dequeue();
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.dequeue();
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
        }

        if (type == 2)
        {
            Queue<char> q;

            q.enqueue('a');
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.enqueue('b');
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.enqueue('c');
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.dequeue();
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.dequeue();
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;

            q.dequeue();
            cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
        }

        return 1;
    }
    catch (int e)
    {
        if (e == 2)
        {
            cout<<"Call to dequeue() generated an exception, because the queue is empty."<<endl;
        }
        else if (e == 3)
        {
            cout<<"Call to front() generated an exception, because the queue is empty."<<endl;
        }
    }
}

Then the first template:

using namespace std; 
#include <iostream>
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <class T>
struct Node 
{
    T val; 
    Node<T> *next; 
};

template <class T>
class LinkedList
{
    public:
        LinkedList();
        ~LinkedList();
        void insertAtBack(T valueToInsert);
        bool removeFromBack();
        void print();
        bool isEmpty();
        int size();
        void clear();

        void insertAtFront(T valueToInsert);
        bool removeFromFront();

        T& firstNum();

    private:
        Node<T> *first; 
        Node<T> *last; 
};

/**************CPP FILE*****************/

template <class T>
LinkedList<T>::LinkedList()
{
    first = NULL;
    last = NULL;
}

template <class T>
LinkedList<T>::~LinkedList()
{
    Node<T>* temp = first;
    while(temp != NULL)
    {
        temp = temp->next;
        delete(first); 
        first = temp;
    }
}

template <class T>
void LinkedList<T>::insertAtBack(T valueToInsert)
{
    Node<T>* newNode;
    newNode->val = valueToInsert;
    newNode->next = NULL;

    Node<T>* temp = first;

    if (temp != NULL) 
    {
        while (temp->next != NULL) 
        {
            temp = temp->next;
        }

        temp->next = newNode;
    }
    else 
    {
        first = newNode;
    }
}

template <class T>
bool LinkedList<T>::removeFromBack()
{   
    if (first == NULL && last == NULL) {return false;}

    if (first == last)
    {
        cout<<"First is equal to Last."<<endl;
        delete(first);
        first = last = NULL;
        return true;
    }

    else
    {
        Node<T>* temp = first;
        int nodeCount = 0;

        while (temp != NULL)
        {
            nodeCount = nodeCount + 1;
            temp = temp->next;
        }

        Node<T>* temp2 = first;

        for(int i = 1; i < (nodeCount - 1); i++)
        {
            temp2 = temp2->next;
        }

        cout << temp2->val<<endl;
        delete(temp2->next);

        last = temp2;
        last->next = NULL;

        return true;
    }
}

template <class T>
void LinkedList<T>::print()
{
    Node<T>* temp = first;

    if (temp == NULL) 
    {
        cout<<"";
    }

    if (temp->next == NULL) 
    {
        cout<<temp->val;
    }
    else 
    {
        while (temp != NULL)
        {
            cout<< temp->val;
            temp = temp->next;
            cout<< ",";
        }
    }
}

template <class T>
bool LinkedList<T>::isEmpty()
{
    if (first == NULL && last == NULL) {return true;}
    else {return false;}
}

template <class T>
int LinkedList<T>::size()
{   
    if (first == NULL && last == NULL) {return 0;}

    Node<T>* temp = first;
    int nodeCounter = 0;

    while (temp != NULL)
    {
        nodeCounter = nodeCounter + 1;
        temp = temp->next;
    }
    return nodeCounter;
}

template <class T>
void LinkedList<T>::clear()
{
    Node<T>* temp = first;
    while(temp != NULL)
    {
        temp = temp->next;
        first = temp;
        delete(temp);
    }
}

template <class T>
void LinkedList<T>::insertAtFront(T valueToInsert)
{
    Node<T>* newNode;

    newNode->val = valueToInsert;

     if(first == NULL)
    {
        first = newNode;
    }
    else
    {
        newNode->next = first;
        first = newNode;
    }
}

template <class T>
bool LinkedList<T>::removeFromFront()
{
    if (first == NULL && last == NULL) {return false;}

    else
    {
        Node<T>* temp;

        temp = first;
        first = first->next;

        delete(temp);

        return true;
    }
}

template <class T>
T& LinkedList<T>::firstNum()
{
    return first->val;
}

#endif

And the second template:

#include <iostream>
#include "LinkedList.h"
#ifndef QUEUE_H
#define QUEUE_H

template <class T>
class Queue: public LinkedList<T>
{
  public:
        Queue();
        ~Queue();

        void enqueue(T value);
        T dequeue();
        T& front();
};

/**************CPP FILE*****************/

template <class T>
Queue<T>::Queue(){}

template <class T>      
Queue<T>::~Queue(){}

template <class T>      
void Queue<T>::enqueue(T value)
{
    LinkedList<T>::insertAtBack(value);
}

template <class T>  
T Queue<T>::dequeue()
{
    if(LinkedList<T>::isEmpty())
    {
        throw 2;
    }
    else
    {
        T firstElmnt = LinkedList<T>::firstNum();
        LinkedList<T>::removeFromFront();

        return firstElmnt;
    }
}

template <class T>  
T& Queue<T>::front()
{
    if(LinkedList<T>::isEmpty())
    {
        throw 3;
    }
    else
    {
        return LinkedList<T>::firstNum();
    }
}

#endif
4

1 回答 1

0

让我们看看发生了什么，LinkedList<T>::insertAtBack并在代码中添加一些注释：

template <class T>
void LinkedList<T>::insertAtBack(T valueToInsert)
{
    // Let's declare a pointer that is uninitialized and points to who 
    // knows where.
    Node<T>* newNode;

    // Now let's dereference this pointer. Remember, it points somewhere
    // random. Maybe this will crash, maybe this won't. It's undefined
    // behavior.
    newNode->val = valueToInsert;

    // We are well inside undefined behavior land now. I hope you brought
    // your passport and a fresh pair of pants.
    newNode->next = NULL;

    Node<T>* temp = first;

    if (temp != NULL) 
    {
        while (temp->next != NULL) 
        {
            temp = temp->next;
        }

        temp->next = newNode;
    }
    else 
    {
        // If we get here, first will be changed and end up pointing to
        // some random location in memory. And that's bad, mmkay?
        first = newNode;
    }
}

这个故事的寓意是取消引用未初始化的指针是不好的。

于 2013-05-03T22:09:13.447 回答