0

My List 是通过这两个结构实现的。第一个包含列表中的项目，而第二个包含列表本身。

typedef Employee Item;

typedef struct ListNodeTag {
    Item item;
    struct ListNodeTag *next;
} ListNode;

typedef struct {
    int size;
    ListNode *first;
} List;

我正在尝试使用以下递归函数来反转列表的内容，但是，一旦列表中有多个项目，我就会遇到分段错误。

void Reverse(List *L){
  ListNode *q,*p;

  q = L->first;
  p = q->next;

  if(p == NULL)
    return;

  Reverse(L);

  q->next->next = q;
  q->next = NULL;}

我认为问题在于，我没有将列表的成员作为函数参数传递，而是传递了指向列表本身的指针。我将如何更改此代码以使其在不传递不同参数的情况下工作？

4

2 回答 2

0

当您将项目附加到列表时，您是否确保将所有 next 指针初始化为 NULL？

此外，当我阅读它时，该函数实际上不会递归，因为您总是传递 L。换句话说，在第一次调用之后，该函数如何知道在列表中再往下走？

于 2013-11-05T00:10:55.370 回答
0

您需要将另一个参数传递给函数以将递归函数推进到列表的末尾。这可以像这样完成-

void Reverse(ListNode *f, List *l){
    if(l->first == NULL)
        return;

    //Last node reached
    if(f->next==NULL){
        l->first->next = NULL;
        l->first = f;
        return;
    }
    ListNode *p,*q;
    p = f;
    q = f->next;

    Reverse(f->next,l);

    q->next = p;
}

虽然这个函数有效，但它需要大量内存，所以我推荐一种迭代方法，比如这个 -

void Reverse(List *l){
    ListNode *f = l->first;
    ListNode *fn,*fnn;

    if(f==NULL)
        return;
    fn = f->next;
    if(fn==NULL)
        return;
    fnn = fn->next;

    while(fnn!=NULL){
        fn->next = f;
        f = fn;
        fn = fnn;
        fnn = fnn->next;
    }
    fn->next = f;
    l->first->next = NULL;
    l->first = fn;
}
于 2013-11-05T08:56:43.553 回答