c++ - 动态内存和链表

Question

好吧，假设我们有一个用 C++ 实现的链表。此外，假设节点是一个类，列表本身也是一个类，它看起来像这样:

#include <iostream>

using namespace std;

class List;

class Node
{
private:
    Node(char, Node*);
    char data;
    Node* next;
    friend class List;
    friend ostream& operator<<(ostream&, const List&);
};

class List
{
public:
    List(int = 0);
    List(const List&);
    ~List();
    bool gotoBeginning();
    bool gotoEnd();
    bool gotoNext();
    bool gotoPrior();
    bool insert(char);
    bool remove(char&);
    bool empty() const;
    bool full() const;
    bool clear();
    List& operator=(const List&);
    friend ostream& operator<<(ostream&, const List&);

private:
    Node* head;
    Node* cursor;
};

#endif

假设列表是空的。此外，假设我们刚刚将一个新元素“z”插入到列表中，这意味着该列表当前有 1 个节点。

让我们看一下插入函数:

bool List::insert(char item)
{
    if(empty())
    {
        Node* newNode = new Node(item, NULL);
        head = cursor = newNode;
        return true;
    }
    else
    {
        // I dont need to show this part because the above code will suffice
    }
}

好吧，我们都知道，类型为节点指针的变量 newNode 被分配了包含已存储在堆上的节点的内存位置。

现在记住我们刚刚创建了一个新节点，让我们假设传递给插入函数的项目是“z”

    Memory AllocationStack             Heap    |               |    |               |   \|/             \|/  512               902            memory address| -----|   |--->|-----|-----||  902 |   |    |  'z'| NULL|                    |------|---|    |-----|-----|newNode        (no name/ newNode)   variable name

(no name): because memory allocated on the heap can not be directly accessed other than by a pointer.

The problem I'm having is this. Is the newNode pointer created on the stack and assiged some memory address like 512 as shown above?Or is the pointer never allocated on the stack (so just remove the 512 above) and only pointing to the memory (902) that was creted on the heap?

The reason I am asking is because the second line of code inside of the if statement inside of the insert function assigns newNode to both head and cursor

thats whats confusing me. Would head and cursor now contain address 512 or 902?

also if we were to continue and write the code inside of the else statement inside of the insert function then it would look like this:

bool List::insert(char item)
{
    if(empty())
    {
        Node* newNode = new Node(item, NULL);
        head = cursor = newNode;
        return true;
    }
    else
    {
        Node* newNode = new Node(item, NULL);
        cursor = cursor->next = newNode; // what is this line doing
        return true;
    }

    return false;
}

那么cursor->next是如何获取新节点的值的，cursor也是如何获取新节点的值的。

是的，上面的函数工作正常，我在这个项目上得了 A，所以所有的代码都是正确的，但我提到的概念让我很困扰

Answer 1

new 返回的指针需要存储在某个地方，它存储在堆栈变量newNode 中。 newNode 的值，即它的内容，是 new 返回的地址。

当您将一个指针分配给另一个指针时，复制的是指针的值、内容、指针指向的地址。

所以当你这样做时

head = newNode;

然后 head 将得到与 newNode 相同的值，并将指向由 new 表达式分配的内存。

---

让我们举个小例子:假设你有两个指针:

int* a;
int* b;

您分配一些内存并分配给a:

a = new int;

现在内存看起来像这样:

+---+     +------------------+| a | --> | allocated memory |+---+     +------------------+

Then you assign from a to b:

b = a;

然后内存看起来像这样:

+---+| a | -.+---+  |    +------------------+        >-> | allocated memory |+---+  |    +------------------+| b | -'+---+

变量 a 和 b 的确切存储位置并不重要，它们指向何处也不重要。