反转列表导致Seg错误

我想要递归地反转链接列表。我有这些结构：反转列表导致Seg错误

typedef Test test; 

typedef struct Node { 
    test t; 
    struct Node *nxt; 
} LNode; 

typedef struct { 
    int size; 
    LNode *first; 
} L;

其中Test是一个包含学生名称和等级（测试成绩）的结构。

void recursiveReverse(L * r) { 
     LNode * first; 
     first = r->first; //first node in list 

     reverseList(first); 
} 

void reverseList(LNode * first) { 
    LNode * rest; 
    rest = first->nxt; 

    reverseList(r,rest); 

    first->nxt->nxt = first; 
    first->nxt = NULL; 

    first = rest; 
}

但是，我似乎在尝试这个时候得到一个段错误。我不允许更改函数recursiveReverse的参数参数，我被告知必须调用另一个函数，并将其用作递归调用函数（我有）。任何帮助将非常感激。

来源

2015-11-05 user3739406

如何进行递归结束了吗？ –

从找到导致问题的最短列表（其中2或3个项目）开始。然后用调试器遍历代码，看看发生了什么问题。 – user3386109

它不完全清楚为什么你的reverseList需要'r'参数。目前还不清楚你是如何试图遵循链接的算法。您目前的计划与此不相似。 –

编写递归函数最重要的规则是它们必须终止。简而言之，必须有一个条件，在该条件下，递归函数不是自己调用。这就是所谓的“基本案例”。

对于您的列表反转函数，基本情况是当您必须反转的列表部分恰好包含一个节点时，因为单节点列表本身是一个微不足道的反转。因此，需要在这里你说的是里面reverseList的情况是这样的：

if (first->nxt == NULL) { 
    // Do not go into recursive invocation 
    return; // This is not complete yet 
}

是从你的代码中缺少另一件事是，反向名单将有一个新的头，这是用来节点成为尾巴。你的reverseList应该返回它。

一个有用的技巧来编写递归函数的其余部分是想象的功能已经写好给你，并与知识它做什么称呼它，遗忘了的一时间，如何做它。在列表反转的情况下，递归步骤相对容易：获取反转列表的头部，然后将当前节点的下一个更改为指向当前节点。

LNode* reverseList(LNode* list) { 
    if (list->nxt == null) { 
     return list; 
    } 
    // Reverse the tail 
    LNode *head = reverseList(list->nxt); 
    // Invert this node 
    list->nxt->nxt = list; 
    // Return the result of tail reversal 
    return head; 
}

在这一点上唯一缺少的是设置了新的尾部的nxt到NULL。你应该做你recursiveReverse函数中：

void recursiveReverse(L * r) { 
    LNode *first = r->first; 
    LNode *newHead = reverseList(first); 
    first->nxt = NULL; 
    r->first = newHead; 
}

Demo.

来源

2015-11-05 18:50:01 dasblinkenlight

嗯，不应该头调用反向列表，而不是反向？ – user3739406

另外我似乎仍然错误与此实施 – user3739406

@ user3739406是的，它需要是'reverseList'，而不是'reverse'。我修正了这一点。奇怪的是，你看到了这个实现的段错误。您是否能够在演示中遵循实施？还要确保你正在构建你的列表。 – dasblinkenlight

反转列表导致Seg错误

回答

相关问题