C ++循环链表的递归基本案例 [英] Recursive base case for c++ circular linked list

问题描述

这都是假设的

我有这样的结构:

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

和只有头指针的循环链表，我如何为计算循环表节点的递归函数建立一个基本案例?我什至不知道从哪里开始，因为我脑力激荡的一切，我很快就意识到这是行不通的，因为列表中的最后一个节点直接指向头，而不是NULL.

and a circular linked list with only a head pointer, how would I set up a base case for a recursive function that counts the nodes of the circular list? I don't even know where to begin because everything I brainstorm, I quickly realize wouldn't work, because the last node in the list points right back to head instead of NULL.

示例功能:

int count(node *head)
{
   int listCount = 0;

   if(base case)
   {
     then return 0;
   }
   else
   {
     calculate listCount
     count(head->next);
   }

   return listCount
}

推荐答案

好吧，我们必须区分:

• 空列表，头为nullptr
• 我们在名单的首位
• 我们在列表中间
• 我们在列表的结尾，即e.我们再次到达头部

为了能够与众不同，您需要保持头脑清醒！在给定的情况下，通过简单的迭代来完成任务会更容易，所以让我们开始:

To be able to differentiate, you need to keep track of the head! In the given case, it is easier to do the task with simple iteration, so let's start with:

unsigned int count(node* head)
{
    if(head == nullptr)
        return 0;
    unsigned int n = 1;
    node* current = head->next; // start at next element!
    while(current != head)      // only way to detect end!
    {
       ++n;
       current = current->next;
    }
    return n;
}

现在，如果您坚持使用递归函数:由于我们需要跟踪头部，因此需要两个指针.没办法但是我们可以提供一个单独的入口函数，仅接受头，然后将两个指针都传递给实际的递归函数:

Now, if you insist on a recursive function: As we need to keep track of the head, we need two pointers. No way around. But we can provide a separate entry function accepting the head only and then passing both pointers to the actual recursive function:

unsigned int count(node* head)
{
    if(head == nullptr)
        return 0;
    return count(head, head->next);
}
unsigned count(node* head, node* current)
{
    if(current == head) // our end condition!
        return 1;
    return 1 + count(head, current->next);
}

这篇关于C ++循环链表的递归基本案例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！