C语言 尝试在循环双链表中递归计数节点时出错

Question

这是我对count的实现:

int count(node *start)
{
    static int l ;
    node *current;            /* Node for travelling the linked list*/
    current=start;
    if(current->next!=start)
    {
        l = 1 + count ( current->next ) ;
        return ( l ) ;
    }

    else
    {
        return(1);
    }
}

下面是main函数的一个片段，我在这里调用它:

void main()
{
    node *head;
printf ( "Length of linked list = %d", count ( head ) ) ;
}

结构如下:

struct cirdoublelinklist
{
    struct cirdoublelinklist *prev;  /** Stores address of previous node **/
    int value;                   /** stores value **/
    struct cirdoublelinklist *next;  /** stores address of next node **/
};
/** Redefining list as node **/
  typedef struct cirdoublelinklist node;

在运行并试图查看列表的长度时，由于内存超出限制而崩溃。请帮我解决这个问题，我已经为此工作了很长时间了。

添加第一个节点的方法:

void initialize(node *start)
{
    start->prev=start;
    printf("nEnter Valuen");
    scanf("%d",&start->value);
    start->next=start;
}

在指定位置之后添加后续节点的方法:

void insert_after(node *start)
{
    int num;                  /* value for inserting a node */
    int flag=0;
    node *newnode;            /* New inputed node*/
    node *current;            /* Node for travelling the linked list*/
    newnode=(node*)malloc(sizeof(node));
    printf("nEnter the value after which you want to insert a noden");
    scanf("%d",&num);
    init(newnode);
    current=start;
    while(current->next!=start)
    {
        if(current->value==num)
        {
            newnode->next=current->next;
            current->next->prev=newnode;
            current->next=newnode;
            newnode->prev=current;
            flag=1;
        }
        current=current->next;
    }
    if(flag==0 && current->next==start && current->value==num)
    {
        /***  Insertion checking for last node  ***/
        newnode->next=current->next;     /* Start is being copied */
        current->next->prev=newnode;
        current->next=newnode;
        newnode->prev=current;
        flag=1;
    }
    if(flag==0 && current->next==NULL)
        printf("nNo match foundn");
} 

Answer 1

每次调用count时，它都有一个新的start，因此current->next!=start总是将一个节点与其后继节点进行比较，只有当列表长度为1时才会结束。你最可能想做的是有两个函数:

int count(node *start)
{
    if(start == NULL)
        return 0;
    return count_helper(start, start);
}
int count_helper(node *start, node *current)
{
    static int l;
    if(current->next!=start)
    {
        l = 1 + count (start, current->next);
        return ( l ) ;
    }
    else
    {
        return(1);
    }
}

正如其他人提到的，静态变量不是必需的。我所说的count_helper的更好的写法是:

int count_helper(node *start, node *current)
{
    if(current->next!=start)
    {
        return 1 + count (start, current->next);
    }
    else
    {
        return 1;
    }
}

最后，一个更有效的实现是非递归的:

int count(node *start)
{
    if(start == NULL)
        return 0;
    node *current = start->next;
    int c = 1;
    while(current != start)
    {
        c++;
        current = current->next;
    }
    return c;
}

Answer 2

嗯，问题是你在一个NULL指针上调用main函数。事实上，node *head;是声明的，但从来没有赋值给什么。所以当你执行这一行时:

if(current->next!=start)

程序崩溃，因为它将检查NULL->next，显然，不存在。

Answer 3

在insert_after函数中需要传递一个指向起始指针的指针

void insert_after(node **start)

不是

void insert_after(node *start)

否则你将只是更新*start的本地副本。

initialize

类似

void initialize(node **start)

Answer 4

简单地说，递归调用不知道原始的开始节点。您需要添加第二个node*参数并通过它传递开始节点。

Answer 5

这是一个不使用静态或辅助变量的递归解决方案:

int count(Node* head) {
  // Base cases:
  // 0 nodes
  if (!head)
    return 0;
  // 1 node
  if (head->next == next)
    return 1;
  // Keep a pointer to the node to be removed
  Node* rest = head->next;
  // Remove the node
  head->next = head->next->next;
  // Get the length of the new list
  int result = 1 + count(head->next);
  // Reconnect the node
  head->next = rest;
  return result;
}