0

My List は、これら 2 つの構造体を介して実装されます。1 つ目はリスト内の項目を含み、2 つ目はリスト自体を含みます。

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

再帰関数をリストの最後に進めるには、関数に別のパラメーターを渡す必要があります。これはこのように行うことができます-

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 に答える