頭部ポインタのみが与えられた循環リンクリストのノード数を再帰的に計算する

Question

私は宿題の一部としてこの関数を書いています。テールポインタが含まれていて、コードの大部分がインストラクターによって提供され、オブジェクトファイルに含まれていた場合、その実装は含まれていません。とにかく、なんらかの理由で、私の関数の基底関数に決して達しません。誰もがなぜこのループを維持するのか教えてもらえますか？

#include "clist.h" 
#include <iostream> 

using namespace std; 

struct node 
{ 
    int  data; 
    node* next; 
}; 

//Iteratively compute and return the number of nodes in the circular linked list 
int count(node* head) 
{ 
    int nodeTotal = 1; 
    node* temp = head; 
    while(temp->next != head) 
    { 
     nodeTotal++; 
     temp = temp->next; 
    } 
    return nodeTotal; 
} 


//Recursively compute and return the number of nodes in the circular linked list 
int countR(node* head) 
{ 
    node* temp = head; 
    if(temp->next == head) 
     return 0; 
    else 
     return 1 + countR(temp->next); 
} 


//Iteratively compute and return the sum of the ints contained in the circular linked list 
int sum(node* head) 
{ 
    int valuesTotal = 2; 
    node* temp = head; 
    while(temp->next != head) 
    { 
     valuesTotal += temp->data; 
     temp = temp->next; 
    } 
    return valuesTotal; 
} 

int main() 
{ 
    node* head{nullptr}; 

    /* Builds a circular linked list with a random number of nodes 
    *containing randomly-chosen numbers. 
    */ 
    build(head); 

    display(head); 

    // PUT YOUR CODE HERE to call the functions assigned, 
    // and print out the results. For example, 
    // 
    // cout << "iterative sum: " << sum(head) << endl; 
    // 
    // The code for your functions should be in clist.cpp. 
    cout << "\nIterative node count: " << count(head) << endl; 
    cout << "Iterative sum: " << sum(head) << endl; 
    cout << "Recursive node count: " << countR(head) << endl; 

    // When called the 2nd time, this also prints the total 
    // of the numbers in the nodes. 
    display(head); 




    int  nNodesFreed{0}; 
    node* n{head}; 
    node* temp; 

    while(n != head || ! nNodesFreed) { 
     temp = n->next; 
     delete n; 
     n = temp; 
     nNodesFreed++; 

     } 
    cout << "# nodes freed: " << nNodesFreed << endl; 

    //destroy(head); 

    return 0; 
} 

Answer 1

あなたは再帰呼び出しを行うたびに、あなたは新しいheadポインターで始まるので、あなたの停止条件が機能していません。それでは、あなたがこのようなリンクリストで始めましょう：あなたは（Aのほか、アドレス）Aを渡し、最初の呼び出しで

、それは== Bのそれがないかどうかをチェックします、この呼び出しでは、B == Cかどうかをチェックします。失敗すると、Cを渡す再帰呼び出しが実行されます.C == Dかどうかを確認します。失敗したので、D = = E。失敗すると、E == Aかどうかを確認します。失敗すると、A == Bかどうかを確認します。それでも失敗するので、続行します...

ラウンドラウンドします。それが止まるところで、誰も知らない！