我很难理解这个递归代码是如何工作的,我已经画了图并使用 gdb
运行了代码。
void RecursiveReverse(struct node** headRef)
{
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case
first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
if (rest == NULL) return; // empty rest base case
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
// after: rest = {3, 2}
first->next->next = first; // put the first element on the end of the list
first->next = NULL;
*headRef = rest; // fix the head pointer
}
我知道当递归调用栈被建立并且列表只包含{3}时,空的 rest 基本情况 if (rest == NULL)
第一次为真。
之后,递归调用栈开始破裂,并且在 {2, 3} 中第一次命中 first->next->next = first;
在执行此行前,在 gdb
中输出:
(gdb)p *first
{data = 2, next = 0x1003001f0}
(gdb) p *rest
{data = 3, next = 0x0}
执行这行代码后,
(gdb) p *rest
{data = 3, next = 0x1003000a0}
继续执行代码,第二次到达
first->next->next = first;
这一行:(gdb) p **head_ref
{data = 1, next = 0x1003000a0}
(gdb) p *rest
{data = 3, next = 0x1003000a0} // expected p *rest to be 2
在递归调用堆栈建立时,我期望本地指针rest
应该指向节点2,因为**headRef
指向节点1,在执行代码rest = first->next;
后,rest
指向节点2。
执行*headRef = rest;
后,headRef
不应该指向节点2吗?
为什么本地状态会丢失,rest
指向节点3?
1->2<-3
且2->next
包含null
时,为什么行*headRef = rest;
不会像它在列表只包含 {2, 3} 时那样将*headRef
指向节点 2,而是指向了节点 3?在此之后,rest
怎么总是等于{3,...}
呢? - Haslo Vardos*headRef = rest
才会实际修改 head 指向 restrest 等于 3
,之后这个赋值操作就变得无关紧要了,因为它做的是同样的事情? - Haslo Vardos