は、ここで再帰

Question

を使用して二重リンクリストのノード数をカウントし、私はこれまで何をやったかである：

struct rep_list { 
    struct node *head; 
    struct node *tail; 
} 

typedef rep_list *list; 

int length(const list lst) { 
    if (lst->head == NULL) { 
     return 0; 
    } 
    else { 
     lst->head = lst->head->next; 
     return 1 + length(lst); 
    } 
} 

をこれは動作しますが、パラメータが変更されますと、リストの先頭は、関数が受け入れます。私はそれを修正する方法を知らない。

私は関数定義を変更することはできないので、常にリスト変数を受け入れる必要があります。

アイデア？

編集：コメントにTyler Sが示唆したことを試みましたが、別の問題が発生しました。最初にノード*変数を作成すると、lst-> headを指すはずです。しかし、関数を呼び出すたびにlst-> headに戻り、私は前進することができません。

Answer 1

ローカルノードは必要ありません。リストヘッドを変更しないでください。代わりに、次のポインタを再帰ヘッドとして渡します。私が見

int length(const list lst) { 
    if (lst->head == NULL) { 
     return 0; 
    } 
    else { 
     return 1 + length(lst->head-next); 
    } 
} 

---

。はい;これは選ばれた表現のためにちょっとしたものになってしまいます。残りのリストを含めるには一時変数が必要です。これは頭​​を変えることを含む。各再帰ステップで

int length(const list lst) { 
    if (lst->head == NULL) { 
     return 0; 
    } 
    else { 
     new_lst = new(list) 
     new_lst->head = lst->head->next; 
     var result = 1 + length(new_lst); 
     free(new_lst) 
     return result 
    } 
} 

、あなたは、新しいリストオブジェクトを作成して現在のリストの2番目の要素を指すように、そして継続します。これはあなたの仕事ですか？

Answer 2

この解決法は厄介であり、私はそれが嫌いですが、方法シグニチャを変更せずに求めていることを達成するための唯一の方法です。私たちはクラスのメンバーデータとして一時的なnode *を作成し、開始時に変更します。

struct rep_list { 
    struct node *head; 
    struct node *tail; 
} 

node *temp = NULL; 
bool didSetHead = false; 

typedef rep_list *list; 

int length(const list lst) { 
    if ((didSetHead) && (lst->head != temp)) { 
     temp = lst->head; 
     didSetHead = false; 
    } 
    if (temp == NULL) { 
     didSetHead = true; 
     return 0; 
    } 
    else { 
     temp = temp->next; 
     return 1 + length(temp); 
    } 
} 

私はこのコードをテストしていないとあなたが少しでプレイしているかもしれませんが、アイデアは動作しますのでご注意ください。