时间戳

首页 > 解决方案 > 如何将指针的值存储在递归函数中？

c++ - 如何将指针的值存储在递归函数中？

问题描述

现在假设我想编写一个函数，递归地搜索链表中的某个节点。当我成功到达目标节点时，该函数将通过引用返回它的 ID 和其他信息，其中它的 ID 将通过结构存储：

struct P{
     int ID;
     int some_info;
     P* next_node;
}

该功能将类似于

void search(int targeted_ID, P*& current_node){
     P* c = current_node;
     if(c->ID == targeted_ID){
           current_node = c;
     }
     if(c->next_node == nullptr){
           return;
     }
     else{
          search(ID, current_node->next_node);
     }
}

输出语句将类似于

cout << "The targeted node have ID= " << current_node->ID << "with" << current_node->some_info << endl;

但是，这个函数会自己递归调用，直到所有节点都到达并检查完，并且在current_node整个过程中指针的值会不断变化。

主要问题是如何在递归时保持它的值不变。

ps 存在以下限制：

  1. 无法添加任何全局变量
  2. 不能使用任何静态变量
  3. 不能在 void 函数中添加任何参数
  4. 无法使用数组
  5. 无法更改struct的内容
  6. 输出语句不能更改
  7. 不能用goto

标签： c++pointersrecursion

解决方案

正如@Ted Lyngmo 指出的那样，我只是编码了一点，你必须返回一个值，所以你不能使用 void 函数。

这是代码：

#include <iostream>

struct P {
    int ID;
    int some_info;
    P* next_node;
};


P* newNode(int ID, int some_info) {
    P* temp = new (std::nothrow) P;

    if (temp == nullptr){
        return nullptr;
    }
    else {
        temp->ID = ID;
        temp->some_info = some_info;
        temp->next_node = nullptr;
        return temp;
    }
}


P* search(int targeted_ID, P* current_node) {
    // check if current node is valid
    if (current_node == nullptr) {
        return nullptr;
    }
    // check for ID of current node
    else if (current_node->ID == targeted_ID) {
        return current_node;
    }
    // this node isn't the desired one --> go to nex node
    else {
        return search(targeted_ID, current_node->next_node);
    }
}



void freeMem(P* list) {
    P* tmp = nullptr;

    while (list != nullptr) {
        tmp = list->next_node;
        delete list;
        list = tmp;
    }
}


int main()
{
    P* list = nullptr;
    P* tmp = nullptr;
    P* lastNode = nullptr;

    // populate list
    for (int i = 0; i < 10; ++i) {
        tmp = newNode(i, i * 10);
    
        if (tmp == nullptr) {
            // error occured
            // free memory
            freeMem(list);
            list = nullptr;
            return -1;
        }

        if (list == nullptr) {
            // first node
            list = tmp;
            lastNode = list;
        }
        else {
            lastNode->next_node = tmp;
            lastNode = tmp;
        }
    }

    tmp = nullptr;
    lastNode = nullptr;

    int ID_to_find = 1;
    P* node = search(ID_to_find, list);

    if (node == nullptr) {
        // node not found ...
        std::cout << "node not found" << std::endl;
    }
    else {
        // node found
        std::cout << "node found at: " << node << std::endl;
    }


    freeMem(list);
    list = nullptr;

    return 0;
}

这段代码有效，但它不是真正的 C++，它更像 C。如果你想编写 C++ 代码，请使用 STL-Containers，不要编写自己的列表，因为它更具可读性并且有机会拥有一个错误要小得多。还要考虑使用异常而不是(std::nothrow).

推荐阅读