c - 尝试递归地计算循环双向链表中的节点时出错

Question

这是我的计数实现:

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 Value\n");
    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 node\n");
    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 found\n");
} 

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;
}