c++ - 具有返回类型 node* 的函数与 C++ 中的 OOP 结合使用

Question

我需要编写一个程序，它采用线性链表的实例并删除列表中除最后两项之外的所有项目。我正在使用类在 C++ 中执行此操作，因此我将有 3 个文件:main.cpp、list.h 和 list.cpp。不能有循环:我可以使用多个函数，但遍历部分必须是递归的。

我考虑了一下，得出的结论是:我必须有一个可以从 main 中调用的不带参数的公共(public)函数，称为 void lastTwo()。我将有另一个名为 node* lastTwo(node *& current, node *& tail) 的私有(private)函数，它将由 lastTwo() 调用，它将递归遍历列表并删除它接触的节点，直到它到达第二个列表中的最后一个节点，然后它将返回该节点的地址。

然后，当它返回列表中倒数第二个节点的地址时，公共(public)函数 lastTwo() 将捕获该地址并将 head 设置为等于它。

我遇到的问题是我需要在 vi 中执行此操作并从命令行编译和运行，即使我画了一个指针图也找不到问题我的代码。

我在我大学的学生服务器上做这个，除了这两个函数之外的所有数据结构的实现都是我的导师写的，所以它们都很可靠。此外，每次运行 a.out 文件时，他们都会将其编写为生成一个新的、随机的、非空的链表，至少包含 5 个节点。

我认为问题与返回类型为“node*”的函数有关，因为我也尝试在 visual studio 中这样做，但它不会让我拥有类型为 node* 的函数。但是，我知道当您不使用类而只是将所有内容放在一个文件中时，节点* 类型的函数就可以工作。

这是我的 list.h:

#include<iostream>

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

class list
{
public:
    // these functions were already written by the school and included in the .o file
    list();
    ~list();
    void build();
    void display();

    // my functions
    void lastTwo();

private:
    node* head;
    node* tail;
    node* lastTwo(node *& current, node *& tail);
}

和list.cpp:

void list::lastTwo(){
    node* current = head;
    node * newHead = lastTwo(current, tail);
    head = newHead;
    delete newHead;
    head->next = tail;
}

node* lastTwo(node *& current, node *& tail){
    if(current->next == tail){
        return current;
    }
    else if(current->next != tail){
        node* temp = current;
        current = current->next;
        temp->next = NULL;
        delete temp;
        lastTwo(current, tail);
    }
    return NULL;
}

任何关于可能是什么问题的想法，以及正确的方法是什么，将不胜感激!谢谢

Answer 1

您的问题发生在您的递归展开时。对 lastTwo 的大部分调用发生在 else if 中。该基本情况是返回当前的 if，但是当 else if结束。

想象一下，当达到基本情况时，这是您的堆栈:

 lastTwo // Base case, returns current, but the call below this doesn't do anything with it.
 lastTwo // returns null
 ...
 lastTwo // returns null

那个 NULL 被另一个 lastTwo 使用，你得到了你的段错误。