c++ - 数组式链表实现C++

Question

我的任务是模拟链表结构，但使用节点数组而不是实际链表。当我调用我的附加函数时，我想检查我现有的数组是否已满，如果是，我想将数组大小加倍，并将我的节点附加到“列表”(数组)的末尾。

我无法将数组大小加倍。

为了给你上下文，这是我的一些 .h 文件:

...
const int NULL_INDEX = -1;

struct Node {
    char info;
    int next;
};

class LList1 {

private:
    Node free [4];

    // When more memory is called for, the array will double in size
    // returns true if reallocation of memory was successful
    bool doubleSize();
    .
    .
    .
}

这是我的 .cpp 文件中试图将数组大小加倍的部分:

bool LList1::doubleSize() {
    Node* newArray = new Node[this->length()*2];
    memcpy(newArray, free, this->length()*2);
    free = newArray;
    return true;
}

我也尝试过使用 realloc 和其他函数。我一直有同样的问题。 线路

"free = newArray" 

在 XCode 中一直给我这个错误:“Array type 'Node[4]' is not assignable”

请给我一些关于更好的方法的见解。所有在线解决方案似乎都适用于整数数组，但不适用于我的节点数组。

非常感谢。

Answer 1

您的代码中有几处不正确:

1. 您的free 属性是一个静态数组。在您的情况下，您需要一个动态的，具有适当的构造函数。
2. memcpy 命令采用字节大小，因此您需要乘以 sizeof(Node)。
3. 也许这是有意为之，但 doubleSize() 方法是私有(private)的。

这是编译和运行代码的更正版本:

...
const int NULL_INDEX = -1;

struct Node {
    char info;
    int next;
};

class LList1 {
public:
    LList1();
    ~LList1();
    int getLength();
    bool doubleSize();

private:
    int length;
    Node* free;

    // When more memory is called for, the array will double in size
    // returns true if reallocation of memory was successful
};

int LList1::getLength() {
    return this->length;
}

LList1::LList1() {
    this->free = new Node[4]; // Default size
    this->length = 4;
}

LList1::~LList1() {
    delete []this->free;
}

bool LList1::doubleSize() {
    Node* newArray = new Node[this->length*2];
    memcpy(newArray, free, this->length * sizeof(Node));
    free = newArray;
    this->length *= 2;
    return true;
}


int main(int, char **) {
    LList1 l;
    std::cout << "Original length: " << l.getLength() << std::endl;
    l.doubleSize();
    std::cout << "After doubling length: " << l.getLength() << std::endl;
    return 0;
}