C++链接列表递归问题

Question

我在理解下面的代码块时遇到了一些麻烦:

void InsertSorted(Entry * & list, Entry * newOne) {
    if (list == NULL || newOne->name < list->name) {
        newOne->next = list;
        list = newOne;
    } else {
        InsertSorted(list->next, newOne);
    }
}

我尝试了遍历代码但只能设法达到第一个if语句的地步.一旦我到达执行第一个if语句的位置,我就不明白先前对InsertSorted的调用如何管理将列表的前部连接到新创建的列表.

谢谢

Answer 1

要理解这个功能,只需绘制每次调用所获得的数据.

假设你有一个像这样的列表(假设名字是一个int):

1 -> 4 -> 6 -> 7 -> 10 -> NULL

你想插入5.

在第一次调用时,list指的是1通过原始调用者指针.也就是说,如果你这样做:

InsertSorted(myList, someNode);

的list在函数内部是指myList 外部的功能,并改变它的内部改变它外面.现在,if条件没有传递,因为list不是NULL和newOne->name不是< list->name.因此,函数调用自身,用list的next指针和newOne.这就是我们现在所处的位置:

1 -> 4 -> 6 -> 7 -> 10 -> NULL
^ list refers to this one

5
^ this is newOne, floating off somewhere by itself

在下一个调用中,list指的是list->next最后一次调用,这意味着它指的是4.再次if不满意所以我们继续else:再次调用函数list->next(记住list现在指的是4,这使得list->next参考6此调用).这就是我们现在所处的位置:

1 -> 4 -> 6 -> 7 -> 10 -> NULL
     ^ list refers to this one through 1's next pointer

5
^ this is newOne, floating off somewhere by itself

在下一个调用中,list指的是next指针4,表示6.这是列表的样子:

1 -> 4 -> 6 -> 7 -> 10 -> NULL
          ^ list refers to this one through 4's next pointer

5
^ this is newOne, floating off somewhere by itself

此时,if 被满足(因为5 <6),所以我们

1. 请newOne->next点list.这使得新节点表示5指向6它的next节点.

2. 设置list为newNode.这可能令人困惑,但请记住,这list是一个参考,这意味着更改它会改变原始.原来是list->next当list提到的4,所以它的相同设置,指向所述节点4的next指针,以指向newOne.

这意味着列表现在看起来像这样:

1 -> 4 -> 5 -> 6 -> 7 -> 10 -> NULL
          ^ here's newOne

并且该函数不进行任何调用,因此函数终止,并且控制返回到首先调用它的函数.

而且你刚刚按排序顺序插入了新元素.

您需要考虑三个角落案例:

1. 该列表为空(list == NULL立即)
2. 您插入的元素小于所有现有元素
3. 您插入的元素比所有现有元素都大

让我们假设您总是尝试插入5这些测试的新元素.

所以对于第一个,什么时候list是NULL - 也就是说,你的列表看起来像

NULL

该if声明将立即生效,并设置newOne->next为list(表示newOne->next是NULL),并设置list为newOne.该函数退出,您的列表如下所示:

5 -> NULL

到现在为止还挺好.

如果要插入的元素小于所有其他元素,请说如下:

7 -> 9 -> NULL

5
^ newOne

然后if立即触发.您设置newOne->next为list,使其指向7,并设置list为newOne.

5 -> 7 -> 9 -> NULL

这是照顾.

最后一个角落的情况是新元素大于所有现有元素.说你有

3 -> NULL

作为你的清单.在第一次传球时,list将指向3并且if不会被触发.所以你要调用list->next指向的函数NULL.将if被触发(因为list == NULL)并设置newOne->next到list(这是NULL),然后设置list到newOne,这让3->next点newOne,因为在第一次调用,你通过它的next引用指针,这意味着改变list改变它.现在你有:

3 -> 5 -> NULL

这一切都很好.因此,此函数似乎可以为任何列表生成所需的结果.

作为旁注,这个函数是尾递归的,但是可以通过迭代而不是递归来使其更快.这是一个很好的学习练习.

另请注意,这不是插入排序,因为您没有采用未排序的列表并对其进行排序,您只是以类似于插入排序的方式在现有列表中插入新数据.