c++ - 打印双向链表

Question

我目前正在学习如何使用链表，特别是双向链表，当我尝试向后打印程序时遇到了问题。

这是我需要帮助的代码部分:

#include <iostream>

using namespace std;

struct node
{
    int data; //int to store data in the list
    node *next; //pointer to next value in list
    node *prev; //pointer to previous value in list
};

node *appendList(node *current, int newData) //Function to create new nodes in the list
{
    node *newNode; //create a new node
    newNode = new node;
    newNode->data = newData; //Assign data to it
    newNode->next = NULL; //At end of list so it points to NULL
    newNode->prev = current; //Link new node to the previous value
    current->next = newNode; //Link current to the new node
    return newNode; //return the new node
}

node *createList(int maxLoop, node *begin, node *current, node *end) //Function to create list
{
    //Allocate the starting node
    current = new node;
    current -> data = 1; //First data value is 1
    current -> next = NULL; //next value is NULL
    current -> prev = NULL; //previous value is NULL
    begin = current; //This is the beginning of the list

    for (int count = 2; count <= maxLoop; count++) //Loop to fill the list
    {
        current = appendList(current, count*count); //Create new nodes and fill with square numbers
    }
    end = current; //Now we are at the end of the list
    return begin; //Return begin, this is the problem; I can't return end as well
}

void printForward (node *p) //Function to print the list forwards
{
    node *curr = p; //current is the beginning value of the list
    while (curr != NULL) //Continue while current is not at the end of the list
    {
        cout << curr->data << " "; //Print out the data of current
        curr = curr->next; //Move one value along in the list
    }
}

void printBackward (node *p) //Function to print the list backwards
{
    node *curr = p; //current is the end value of the list
    while (curr != NULL) //Continue while current is not at the beginning of the list
    {
        cout << curr->data << " "; //Print out the data of current
        curr = curr->prev; //Move one value back in the list
    }
}

int main()
{
    //Initialize current, begin, and end
    node *current = NULL; 
    node *begin = NULL;
    node *end = NULL;
    int maxLoop = 10; //The number of items in the list

    cout << "The list has now been created." << endl;
    begin = createList(maxLoop, begin, current, end); //function to create the list
    cout << "Printed forwards, this list is: ";
    printForward(begin); //Function to print the list forwards
    cout << endl;
    cout << "Printed backwards, this list is: ";
    printBackward(end); //Function to print the list backwards
    cout << endl;
    return 0;
}

这个程序的目的是创建一个列表，向前打印，向后打印，插入一个元素，删除一个元素，然后销毁这个列表。我已将其简化为创建、向前打印和向后打印功能。

我遇到的问题是，在 createList 函数中，我同时修改了 begin 和 end，但我只能返回一个或另一个。这意味着无论我不返回哪个在 main 函数中仍然是 NULL，因此不指向任何东西。我已经尝试将开始/当前/结束设置为不等于 NULL，但如果我这样做，createList 将不起作用。

有没有人对我如何修改两者有任何想法？明确一点，列表必须在函数中创建，只需在主函数中初始化它就非常容易。

谢谢，特里斯坦

Answer 1

你的问题是你正在复制指针，当你应该通过引用传递它们时，即使用指针到指针或引用到指针而不是仅仅复制 main 中指针的值 原来是指向的。对于你正在做的事情，你无法修改在 main 中声明的原始指针变量......通过引用将允许你这样做，同时还保持所有列表设置您的函数中的代码。

例如，改变

node* createList(int maxLoop, node *begin, node *current, node *end)

到

void createList(int maxLoop, node** begin, node** current, node** end)

然后确保在函数体中考虑额外的取消引用

最后，您可以这样调用它:

createList(maxLoop, &begin, &current, &end);

并在 createList 的函数体内而不是在 main 中对 begin 进行最终赋值。