0

我现在开始为我的课程跳入 C++，我们在 Scheme 中介绍了入队和出队。但是，我们现在是用 C++ 做的，我们需要使用指针，我很难理解。我了解指针是什么，何时使用它们等。但是，我正在努力弄清楚如何在这个实验室中实现它们。我目前有这个代码：

#include <stdlib.h>
#include <iostream>
#include <assert.h>
using namespace std;

struct node {
    int item;
    node* next;
};

typedef node* nodePtr;   

typedef nodePtr* queue;  

queue makeQueue() {
    queue q = new nodePtr[2];
    q[0] = NULL;         
    q[1] = NULL;
    return q;
}

nodePtr start(queue q) {
    return q[0];
}

nodePtr tail(queue q) {
    return q[1];
}

void setStart(queue q, nodePtr newNode) {
    q[0] = newNode;
}

void setTail(queue q, nodePtr newNode) {
    q[1] = newNode;
}

bool emptyQueue(queue q) {
    return q[0] == NULL;
}

int head(queue q) {
    if (emptyQueue(q)) {
        cout << "Attempt to take head of an empty queue.\n";
        exit(1);
    }
    return start(q)->item;
}

void enqueue(queue q, int newItem) {
    // Answer goes here.
}

void dequeue(queue q) {
    // Answer goes here.
}

对于这段代码，我知道我需要做什么：Enqueue 会将 newItem 推送到队列的 cdr（或尾部），而 Dequeue 将删除队列开头的节点，并相应地更新适当的位置。但真正让我困惑的只是指针，我不知道该怎么办。

我将如何深入使用指针编写入队和出队？我将空白地假设入队和出队不应该是一行又一行的代码。

太感谢了！

4

1 回答 1

0

在处理基于指针的动态结构（如堆栈、链表和队列）时，一切都与重新排列指针有关。正如评论中所建议的那样，将指针表示为纸上指向节点的箭头将有助于可视化在入队/出队时需要如何重新分配指针。

我还想指出，您不应该像以前那样混合使用 C 和 C++ 标头。C++ 库包含与以相同头文件结构组织的 C 语言库相同的定义。每个头文件与 C 语言版本具有相同的名称，但带有“c”前缀且没有扩展名。例如，C 语言头文件的 C++ 等效项<stdlib.h>是<cstdlib>，类似地，<assert.h>是<cassert>. 此外，在 C++ 中，NULL 指针是nullptr; 混合NULL，并且在使用指针参数nullptr重载函数时可能会导致问题。int

现在到手头的问题。每个node都有一个 member next，这是一个指向node队列中下一个的箭头。看起来，q[0]并且q[1]是指向第一个和最后一个元素的相应箭头。

如果您只想从有效负载数据中加入一个新元素（而不是完整的node），那么您必须首先动态创建node对象。然后它的next指针必须指向所q[0]->next指向的内容，而q[0]->next必须重新分配以指向您刚刚创建的新节点：

前：

q[0]->next ---> somenode

后：

q[0]->next -.    -XXX->    somenode
            |                  ^
            |                  |
            '-> newnode->next -'

或在 C++ 中（未经验证）：

void enqueue(queue q, int newItem) {
    nodePtr newnode = new node;
    newnode->item = newItem;
    newnode->next = q[0]->next;
    q[0]->next = newnode;
}

出队相应地进行，只需看看您需要如何重新排列指针。不要忘记delete删除节点并提供删除创建的queue功能makeQueue。

于 2019-11-29T18:59:40.817 回答