链接列表递归...为什么我需要return语句？

问题描述：

void add(llist *list, lnode *newNode){ 
    list->size++; 
    addRecursion(&list->head, newNode); 
} 

lnode* addRecursion(lnode **node, lnode *newNode){ 
    if(*node == NULL){ 
     *node = newNode; 
    } 
    else{ 
     lnode *nextNode = (*node)->next; 
     (*node)->next = addRecursion(&nextNode, newNode); 

    } 
    return *node; 
}

此代码正常工作..我在网上查看了代码并做了一些更改。但我仍然不明白为什么addRecursion函数必须具有返回类型。我改变了功能类似链接列表递归...为什么我需要return语句？

void addRecursion(lnode **node, lnode *newNode){ 
     if(*node == NULL){ 
      *node = newNode; 
     } 
     else{ 
      lnode *nextNode = (*node)->next; 
      addRecursion(&nextNode, newNode); 

     } 
    }

然后它没有工作..

如果你检查返回的是什么，以及在良好函数结束时保存了什么lnode – Ryan 2011-03-24 23:42:46

答

它总是返回它存储在* node中的值，并且在修改后的代码中它会丢失该值，因为递归调用会传递一个本地temp，而不是实际需要放置该值的地方，然后执行store它返回。一个非常奇怪的构造。您可以addRecursion空穴（和简单），如果你只是摆脱局部变量的：

void addRecursion(lnode **node, lnode *newNode){ 
    if(*node == NULL){ 
     *node = newNode; 
    }else{ 
     addRecursion(&(*node)->next, newNode); 
    } 
}

答

要分配的东西(*node)->next。这指向列表中的下一个节点，我想。因此，如果没有分配，列表不会进入最后一个节点，新节点将被添加到该节点。递归可以用迭代代替。

答

因为函数返回算法中需要的下一个节点的地址来设置最终节点。

答

随着递归的进行，可能会帮助将调用堆栈的增长/收缩可视化。假定以下列表：

node1 -> node2 -> node3 -> null

addRecursion然后展开如下（伪码）：

addRecursion(&node1, newNode) 
    node1.next = addRecursion(&node2, newNode); 
     node2.next = addRecursion(&node3, newNode); 
      node3.next = addRecursion(null, newNode); // returns &newNode 
      node3.next = &newNode; 
     node2.next = &node3; 
    node1.next = &node2; 
// return value ignored

新节点被添加到结束，并在链中的每个链接被保留。

答

还应该工作，如果你做这个调整你的代码，你重新分配的nextNode值回(*node)->next因为你通过引用传递该值递归函数调用（因此它是在后来的递归调用修改）：

void addRecursion(lnode **node, lnode *newNode) 
{ 
    if(*node == NULL) 
    { 
     *node = newNode; 
     return; 
    } 

    lnode *nextNode = (*node)->next; 
    addRecursion(&nextNode, newNode); 
    (*node)->next = nextNode; //Add this line to re-connect the link 
}

上述克里斯的版本是有点清洁，虽然因为轴了两次任务，这样做由于没有本地指针var所需的存储空间，所以也节省了一些空间有效的nextNode。

链接列表递归...为什么我需要return语句？

相关推荐