我理解递归，所以我试着写一个反向链表程序。我已经写了下面的函数，但它说分割错误(核心转储)。
void reverse(){
if (head -> next == NULL){
return;
}
reverse (head -> next);
struct node *q = (struct node*) malloc (sizeof(struct node));
q = head -> next;
q -> next = head;
head -> next = NULL;
}
有人能给我指路吗?谢谢你。
reverse不应该接受参数吗?请注意，你不能改变一个函数中的指针，并让它成为一个持久的改变。也就是说，在C函数中，唯一持久的更改是那些使用*var =什么的更改。
递归是一种通过实践获得的思维方式。所以恭喜你的尝试。这是不正确的，但不要气馁。
这里有两种处理这个问题的方法。您的目标是将其细分为自身的较小版本加上一个(希望容易和快速计算)增量步骤，从较小版本的解决方案到完整的解决方案。这就是递归思维的精髓。
第一次尝试:将列表想象为头部元素加上"列表的其余部分"。例如,
L = empty or
= h . R
，其中h是头元素，R是列表的其余部分，点.是将一个新元素加入列表。反转这个列表包括反转R，然后在末尾附加h:
rev(L) = empty if L is empty
= rev(R) . h otherwise
这是一个递归的解决方案，因为我们可以递归地调用反向函数来解决稍微小一点的问题，即反转R，然后在h后面添加一点工作，这样我们就得到了完整的解决方案。
这个公式的问题是附加h比您想要的更昂贵。由于我们有一个只有头指针的单链表，遍历整个链表非常耗时。但它会工作得很好。在C语言中应该是:
NODE *rev(NODE *head) {
return head ? append(head, rev(head->next)) : NULL;
}
NODE *append(NODE *node, NODE *lst) {
node->next = NULL;
if (lst) {
NODE *p;
for (p = lst; p->next; p = p->next) /* skip */ ;
p->next = node;
return lst;
}
return node;
}
那么如何摆脱糟糕的表现呢?通常情况下，一个问题的不同递归公式具有不同的效率。所以经常会有一些尝试和错误。
下一个尝试:考虑将列表分成两个子列表的计算:L = ht，因此rev(L) = rev(T) + rev(H)。这里加上+是列表连接。关键是，如果我知道rev(H)并想要在其头部添加一个新元素，要添加的元素是T中的第一个元素。如果这看起来很模糊，则设H = [a, b, c]并且T = [d, e]。然后，如果我已经知道rev(H) = [c, b, a]并且想要在头部加上下一个元素，我想要d，它是t的第一个元素，在我们的小符号中，你可以这样写:
rev(H + (d . T)) = rev(T) + ( d . rev(H) )
这看起来很好。在这两种情况下(获取T的头部并将其移动到rev(H)的头部)，我只对列表的头部感兴趣，这是非常有效的访问。
当然，如果T为空，那么rev(H) = rev(L)。这就是答案!
将此写入递归过程。
NODE *rev(NODE *t, NODE *rev_h) {
if (t) { // if t has some elements
NODE *tail = t->next; // save the tail of T
t->next = rev_h; // prepend the head to rev(H)
return rev(tail, t); // recur to solve the rest of the problem
}
return rev_h; // otherwise T is empty, so the answer is rev(H)
}
开始时，我们对rev(H)一无所知，因此T是整个列表:
NODE *reversed_list = rev(list, NULL);
下一个要注意的是这个函数是尾部递归的:递归调用在函数返回之前执行。这很好!这意味着我们可以很容易地将其重写为循环:
NODE *rev(NODE *t, NODE *rev_h) {
recur:
if (t) { // if t has some elements
NODE *tail = t->next; // save the tail of T
t->next = rev_h; // prepend the head to rev(H)
rev_h = t; // "simulate" the recursive call
t = tail; // by setting both args
goto recur; // and going back to the start
}
return rev_h; // otherwise T is empty, so the answer is rev(H)
}
你总是可以用尾部递归调用来做这个转换。你应该好好想想为什么这是可行的。
现在，goto很容易被重写为while循环，我们可以将rev_h初始化为NULL的局部变量，因为这就是初始调用所做的:
NODE *rev(NODE *t) {
NODE *rev_h = NULL;
while (t) { // while t has some elements
NODE *tail = t->next; // save the tail of T
t->next = rev_h; // prepend the head to rev(H)
rev_h = t; // "simulate" the recursive call
t = tail; // by setting both args
}
return rev_h; // otherwise T is empty, so the answer is rev(H)
}
一个只需要少量常量空间的就地链表反转器!
,看!我们从不需要画有趣的方框和箭头图，也不需要考虑指针。通过仔细地推理如何将问题细分为更小的实例，这就是递归的本质，它"恰好发生了"。这也是一个很好的方式来理解循环只是一种特殊的递归。很酷,不是吗?
我假设您在.c文件
中预定义了以下内容typedef struct node node_t;
struct node {
int some_data;
node_t *next;
};
/* Your linked list here */
typedef struct {
node_t *head;
node_t *foot; /* to keep track of the last element */
} list_t;
你的函数中有几个错误
- 不提供任何输入参数
- 访问头->下一个当程序不知道在哪里找到头
于是，导致了C语言中最令人沮丧的错误——分段错误!
相反，您应该尝试以下操作:
void reverse(list_t *mylinkedlist){
if (mylinkedlist->head->next == NULL) {
return;
}
/* do something */
}