Стек на основе массива - ошибка в деструкторе - PullRequest
Новая
       10

Стек на основе массива - ошибка в деструкторе

0 голосов
/ 01 сентября 2010

Это моя первая жалкая попытка C ++. Я сделал стек на основе массива в C ++, и деструктор выбрасывает некоторый дамп памяти. Я не могу понять, что пошло не так. 



#include <stdio.h>
#include <iostream>
#include <exception>

using namespace std;

class FullStackException : public exception {
    virtual const char* what() const throw() {
        return "Stack is full.";
    }
} fsex;

class EmptyStackException : public exception {
    virtual const char* what() const throw() {
        return "Stack is empty.";
    }
} esex;

template <class D>
class ArrayBasedStack {
private:
    int t; //t represents top
    D *S;
    int arrSize;
public:
    ArrayBasedStack(int arraySize = 10);
    ~ArrayBasedStack();
    int size(); /*returns the number of elements stored*/
    void push(D&); /*inserts an element*/
    D pop(); /*removes and returns the last inserted element*/
    D top(); /*returns the last inserted element without removing it*/
    int isEmpty(); /*indicates whether no elements are stored*/
};

template <class D>
ArrayBasedStack<D>::ArrayBasedStack(int arraySize) {
    /* Elements are added from left to right */
    S = new D[arraySize];
    arrSize = arraySize;
    /* t keeps track of the index of the top element */
    t = -1;
}

template <class D>
ArrayBasedStack<D>::~ArrayBasedStack() {
    if(S != NULL) {
        int i = 0;
        for(i = 0; i < size(); i++) {
            S[i] = NULL;
        }
        cout << "about to delete S" << endl;
        delete[] S;
    }
}

template <class D>
int ArrayBasedStack<D>::size() {
    return t;
}

template <class D>
void ArrayBasedStack<D>::push(D& data) {
    if(t == arrSize) {
        throw fsex;
    } else {
        S[t] = data;
        t++;
    }
}

template <class D>
D ArrayBasedStack<D>::pop() {
    if(isEmpty()) {
        throw esex;
    }
    D element = S[t];
    S[t--] = NULL;
    return element;
}

/*
 * returns true if the stack is empty, false otherwise
 */
template <class D>
int ArrayBasedStack<D>::isEmpty() {
    return (t < 0);
}

int main(int argc, char *argv[]) {

    char inputs[][10] = {
        "str1"
    };

    char *i = NULL;

    ArrayBasedStack<char *> stack;
    i = inputs[0];
    stack.push(i);
    try {
        stack.pop();
    }
    catch(exception& ex) {
        cout << "ERR:" << ex.what() << endl;
    }
    return 0;
}

Ответы [ 2 ]

2 голосов
/ 01 сентября 2010

Строка проблемы: 

    t = -1;

Должна быть 

    t = 0;

, потому что при добавлении первого элемента следующий код исполняется 

    } else {
       S[t] = data;    // t == -1
       t++;
    }
0 голосов
/ 01 сентября 2010

Следующее является виновником. 

template <class D> 
void ArrayBasedStack<D>::push(D& data) { 
    if(t == arrSize) { 
        throw fsex; 
    } else { 
        S[t] = data;       // Should be S[++t] = data;
        t++;               // Comment out this line
    } 
}

Эта реализация предполагает, что 't' указывает на самый верхний элемент в стеке, а не на следующее доступное место для push

Обратите внимание, что operator [] и operator ++ имеют одинаковый приоритет. Поскольку они ассоциируются слева направо, [] оценивается перед оператором ++.

В вашей реализации здесь проблема. При инициализации t в -1 вы переписываете за пределы индекса массива, который находится в S [-1], что приводит к undefined behavior.

По крайней мере, в моей системе проблема возникает при попытке освободить память в деструкторе класса стека. Это классический пример того, что синдром был виден после того, как произошла глупость

Также предложит push принять параметры как D const &

...