时间戳

首页 > 解决方案 > 析构函数数组堆栈tiwer hanoi c++双指针

c++ - 析构函数数组堆栈tiwer hanoi c++双指针

问题描述

我尝试将元素推入堆栈，但它表明存在空间量错误。如果长度大于容量，容量会升级。有人知道如何纠正这个错误吗？我认为这可能来自析构函数，但我对此不太确定。

ArrayStack.cpp

#include "ArrayStack.h"

ArrayStack::ArrayStack() 
{
   maxCapacity = DEFAULT_CAPACITY;
   this->tab = new int* [DEFAULT_CAPACITY];
   this->topElement = 0;
   this->length = 0;
}

ArrayStack::~ArrayStack()
{
    for (int i = 0; i < maxCapacity; i++)
    {
        delete tab[i];
    }
    delete[] tab;
}

void ArrayStack::push(int element)
{
    this->length++;
    while (this->maxCapacity <= this->length) {
        maxCapacity += DEFAULT_CAPACITY;

        int** temp = new int* [maxCapacity];
        for (int i = 0; i < maxCapacity; i++)
        {
            temp[i] = tab[i];
        }
        delete tab;
        this->tab = temp;
    }
   
    this->tab[this->length] = new int (element);
    this->topElement = element;
    
}

void ArrayStack::pop()
{
    if (isEmpty())
    {
        throw Empty_Stack();
    }
    delete tab[this->length];

    this->length--;
    if (isEmpty())
    {
        this->topElement = -1;
    }
    else 
    {
        this->topElement = *tab[this->length];
    }


}

int ArrayStack::top() const
{
    if (isEmpty())
    {
        throw Empty_Stack();
    }
    return this->topElement;

}

bool ArrayStack::isEmpty() const
{
    if (this->length == 0)
    {
        return true;
    }
    return false;
}

int ArrayStack::size() const
{
    return this->length;
}

ArrayStack.h

#pragma once
#include "Stack.h"
#include "NotImplementedException.h"
class ArrayStack : public Stack
{
public:
    static const int DEFAULT_CAPACITY = 10;

    // ATTENTION, pour chacune des méthodes, lorsque
    // vous créez sa définition dans le .cpp, vous devez
    // remplacer {} (et éventuellement son contenu) par un ;
    ArrayStack();
    ~ArrayStack();
    void push(int element) override;
    void pop() override;
    int top() const override; 
    bool isEmpty() const override;
    int size() const override;

private:
    int length;
    int** tab;
    int topElement;
    int maxCapacity;

};

标签： c++arraysstackdestructortowers-of-hanoi

解决方案

我发现此类管理其数组的方式存在许多问题：

  • 构造函数正在分配一个指针数组int*，但没有将它们中的任何一个设置为nullptr初始值。这会导致析构函数出现问题，因为它正在调用delete每个指针，无论它们是否已初始化。为了避免不得不delete使用未使用的指针，析构函数应该循环到length，而不是maxCapacity。

  • 同样，pop()没有将任何已释放的指针设置为nullptr，这也会导致析构函数在循环到maxCapacity而不是时出现问题length。它也是delete错误的数组元素，如果数组达到其最大容量，则会超出范围。

  • 当push()分配一个新数组时（仅供参考，外部while循环是不必要的），它从旧数组中复制了太多元素，这比新数组小。此外，它使用delete而不是delete[]释放旧数组。

  • 该类不遵循3/5/0 规则，因为它应该实现（或至少禁用）复制/移动构造函数和复制/移动赋值运算符。

尝试更多类似的东西：

ArrayStack.h

#pragma once
#include "Stack.h"
#include "NotImplementedException.h"

class ArrayStack : public Stack
{
public:
    static const int DEFAULT_CAPACITY = 10;

    // ATTENTION, pour chacune des méthodes, lorsque
    // vous créez sa définition dans le .cpp, vous devez
    // remplacer {} (et éventuellement son contenu) par un ;

    ArrayStack();
    ArrayStack(const ArrayStack &src);
    ArrayStack(ArrayStack &&src);
    ~ArrayStack();

    ArrayStack& operator=(ArrayStack rhs);

    void push(int element) override;
    void pop() override;
    int top() const override; 
    bool isEmpty() const override;
    int size() const override;

private:
    int length;
    int** tab;
    int topElement;
    int maxCapacity;
};

ArrayStack.cpp

#include "ArrayStack.h"
#include <utility>

ArrayStack::ArrayStack() 
{
   maxCapacity = DEFAULT_CAPACITY;
   tab = new int* [DEFAULT_CAPACITY];
   for (int i = 0; i < DEFAULT_CAPACITY; ++i) {
      tab[i] = nullptr;
   }
   length = 0;
   topElement = -1;
}

ArrayStack::ArrayStack(const ArrayStack &src)
{
   maxCapacity = src.maxCapacity;
   tab = new int* [maxCapacity];
   for (int i = 0; i < src.length; ++i) {
      tab[i] = new int (*(src.tab[i]));
   }
   for (int i = src.length; i < maxCapacity; ++i) {
      tab[i] = nullptr;
   }
   length = src.length;
   topElement = src.topElement;
}

ArrayStack::ArrayStack(ArrayStack &&src)
{
   maxCapacity = src.maxCapacity; src.maxCapacity = 0;
   tab = src.tab; src.tab = nullptr;
   length = src.length; src.length = 0;
   topElement = src.topElement; src.topElement = -1;
}

ArrayStack& ArrayStack::operator=(ArrayStack rhs)
{
    std::swap(maxCapacity, rhs.maxCapacity);
    std::swap(tab, rhs.tab);
    std::swap(length, rhs.length);
    std::swap(topElement, rhs.topElement);
    return *this;
}

ArrayStack::~ArrayStack()
{
    for (int i = 0; i < length; ++i) {
        delete tab[i];
    }
    delete[] tab;
}

void ArrayStack::push(int element)
{
    if (maxCapacity <= length) {
        int newCapacity = maxCapacity + DEFAULT_CAPACITY;

        int** temp = new int* [newCapacity];
        for (int i = 0; i < length; ++i) {
            temp[i] = tab[i];
        }
        for (int i = length; i < newCapacity; ++i) {
            temp[i] = nullptr;
        }

        delete[] tab;
        tab = temp;
        maxCapacity = newCapacity;
    }
   
    tab[length] = new int (element);
    ++length;

    topElement = element;
}

void ArrayStack::pop()
{
    if (isEmpty()) {
        throw Empty_Stack();
    }

    --length;
    delete tab[length];
    tab[length] = nullptr;

    if (isEmpty()) {
        topElement = -1;
    }
    else {
        topElement = *tab[length-1];
    }
}

int ArrayStack::top() const
{
    if (isEmpty()) {
        throw Empty_Stack();
    }
    return topElement;
}

bool ArrayStack::isEmpty() const
{
    return (length == 0);
}

int ArrayStack::size() const
{
    return length;
}

在线演示

话虽如此，根本没有充分的理由使用int*指针数组。您应该改用一组int值。然后你将有一点点手动管理：

ArrayStack.h

#pragma once
#include "Stack.h"
#include "NotImplementedException.h"

class ArrayStack : public Stack
{
public:
    static const int DEFAULT_CAPACITY = 10;

    // ATTENTION, pour chacune des méthodes, lorsque
    // vous créez sa définition dans le .cpp, vous devez
    // remplacer {} (et éventuellement son contenu) par un ;

    ArrayStack();
    ArrayStack(const ArrayStack &src);
    ArrayStack(ArrayStack &&src);
    ~ArrayStack();

    ArrayStack& operator=(ArrayStack rhs);

    void push(int element) override;
    void pop() override;
    int top() const override; 
    bool isEmpty() const override;
    int size() const override;

private:
    int length;
    int* tab;
    int topElement;
    int maxCapacity;
};

ArrayStack.cpp

#include "ArrayStack.h"
#include <utility>

ArrayStack::ArrayStack() 
{
   maxCapacity = DEFAULT_CAPACITY;
   tab = new int [DEFAULT_CAPACITY];
   length = 0;
   topElement = -1;
}

ArrayStack::ArrayStack(const ArrayStack &src)
{
   maxCapacity = src.maxCapacity;
   tab = new int [maxCapacity];
   for (int i = 0; i < src.length; ++i) {
      tab[i] = src.tab[i];
   }
   length = src.length;
   topElement = src.topElement;
}

ArrayStack::ArrayStack(ArrayStack &&src)
{
   maxCapacity = src.maxCapacity; src.maxCapacity = 0;
   tab = src.tab; src.tab = nullptr;
   length = src.length; src.length = 0;
   topElement = src.topElement; src.topElement = -1;
}

ArrayStack& ArrayStack::operator=(ArrayStack rhs)
{
    std::swap(maxCapacity, rhs.maxCapacity);
    std::swap(tab, rhs.tab);
    std::swap(length, rhs.length);
    std::swap(topElement, rhs.topElement);
    return *this;
}

ArrayStack::~ArrayStack()
{
    delete[] tab;
}

void ArrayStack::push(int element)
{
    if (maxCapacity <= length) {
        int newCapacity = maxCapacity + DEFAULT_CAPACITY;

        int* temp = new int [newCapacity];
        for (int i = 0; i < length; ++i) {
            temp[i] = tab[i];
        }

        delete[] tab;
        tab = temp;
        maxCapacity = newCapacity;
    }
   
    tab[length] = element;
    ++length;

    topElement = element;
}

void ArrayStack::pop()
{
    if (isEmpty()) {
        throw Empty_Stack();
    }

    --length;

    if (isEmpty()) {
        topElement = -1;
    }
    else {
        topElement = tab[length-1];
    }
}

int ArrayStack::top() const
{
    if (isEmpty()) {
        throw Empty_Stack();
    }
    return topElement;
}

bool ArrayStack::isEmpty() const
{
    return (length == 0);
}

int ArrayStack::size() const
{
    return length;
}

在线演示

在这种情况下，更好的选择是替换手动数组，std::vector并让它为您完成所有繁重的工作：

ArrayStack.h

#pragma once
#include "Stack.h"
#include "NotImplementedException.h"
#include <vector>

class ArrayStack : public Stack
{
public:
    static const int DEFAULT_CAPACITY = 10;

    // ATTENTION, pour chacune des méthodes, lorsque
    // vous créez sa définition dans le .cpp, vous devez
    // remplacer {} (et éventuellement son contenu) par un ;

    ArrayStack();

    void push(int element) override;
    void pop() override;
    int top() const override; 
    bool isEmpty() const override;
    int size() const override;

private:
    std::vector<int> tab;
    int topElement;
};

ArrayStack.cpp

#include "ArrayStack.h"

ArrayStack::ArrayStack() 
{
   tab.reserve(DEFAULT_CAPACITY);
   topElement = -1;
}

void ArrayStack::push(int element)
{
    tab.push_back(element);
    topElement = element;
}

void ArrayStack::pop()
{
    if (isEmpty()) {
        throw Empty_Stack();
    }

    tab.pop_back();

    if (tab.empty()) {
        topElement = -1;
    }
    else {
        topElement = tab.back();
    }
}

int ArrayStack::top() const
{
    if (isEmpty()) {
        throw Empty_Stack();
    }
    return topElement;
}

bool ArrayStack::isEmpty() const
{
    return tab.empty();
}

int ArrayStack::size() const
{
    return tab.size();
}

在线演示

然后，最后，std::stack改用：

ArrayStack.h

#pragma once
#include "Stack.h"
#include "NotImplementedException.h"
#include <stack>

class ArrayStack : public Stack
{
public:
    // ATTENTION, pour chacune des méthodes, lorsque
    // vous créez sa définition dans le .cpp, vous devez
    // remplacer {} (et éventuellement son contenu) par un ;

    void push(int element) override;
    void pop() override;
    int top() const override; 
    bool isEmpty() const override;
    int size() const override;

private:
    std::stack<int> tab;
};

ArrayStack.cpp

#include "ArrayStack.h"

void ArrayStack::push(int element)
{
    tab.push(element);
}

void ArrayStack::pop()
{
    if (isEmpty()) {
        throw Empty_Stack();
    }

    tab.pop();
}

int ArrayStack::top() const
{
    if (isEmpty()) {
        throw Empty_Stack();
    }
    return tab.top();
}

bool ArrayStack::isEmpty() const
{
    return tab.empty();
}

int ArrayStack::size() const
{
    return tab.size();
}

在线演示

看看清洁度有多高？:-)

推荐阅读