Помилка при спробі розрахувати вузли в круговому подвійно пов'язаному списку рекурсивно

Ось моя реалізація графа:

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

Ось фрагмент основної функції, де я його називаю:

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");
} 
0
Чому ви зробили статтю l ? Це просто перешкоджає повній реалізації функції, яка, як правило, є необхідною для правильної рекурсії.
додано Автор Ignacio Vazquez-Abrams, джерело

4 Відповіді

Ну, проблема полягає в тому, що ви викликаєте функцію в основному на вказівнику NULL. Infact node * head; оголошується, але ніколи не призначається щось. Отже, коли ви виконуєте цю лінію:

if(current->next!=start)

the program crashes because it will check for NULL->next that, obviously, doesn't exist.

1
додано
@ user1017072 Ну, у такому випадку ви повинні показати нам функцію, яка додає дані. Крім того, видаліть лінію статичного int l; тому що це марно та змінити, якщо тільки повернути 1 + рахунок (поточний-> наступний); що є належним способом мати рекурсивну функцію.
додано Автор Aurelio De Rosa, джерело
У мене також є метод, який в основному вставляє значення даних у вузол. Але, здається, він збій навіть після того, як я створив нові вузли. Для першого вузла він дає правильну довжину 1 (тобто вона йде в інший блок), але для другого він збігає, коли він досягне if (current-> next! = Start), я повинен робити деяка ініціалізація в функції, де я створюю вузли? Дякую за твою допомогу
додано Автор user1017072, джерело
Привіт, я відредагував питання методами, щоб вставити початковий вузол, а потім наступні вузли. Я спробував видалити статичний, як вказано вами, але воно все одно виходить з тієї ж проблеми з пам'яттю. Ще більше пропозицій? Дякую за ваш час та підтримку
додано Автор user1017072, джерело

Every time you call count, it has a new start, so current->next!=start is always comparing a node to its successor, which will only ever end if the list has length 1. What you most likely want to do is have two functions:

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;
}
1
додано
@ user1017072 Будь ласка, зверніть увагу на редагування нерекурсивної версії, щоб спіймати довжину = 0. Крім того, було б корисно, якщо б ви прийняли відповідь, яка, на вашу думку, найкраще відповідає на ваше запитання.
додано Автор Aaron Dufour, джерело
@CVega Добре ловити. Я не пам'ятаю цю відповідь (2 роки!), Але на основі моєї ініціалізації c до 1 , я вважаю, що мій намір був для current почати з start-> next . Чи має це сенс?
додано Автор Aaron Dufour, джерело
@ Аарон Дюфур Я думаю, що нерекурсивна версія неправильна. Перед циклом в той час як поточний та початок рівні, так що вони не збираються входити в цикл, це повинно бути циклом do-while.
додано Автор Carlos Vega, джерело
Так, тепер це виправлено;)
додано Автор Carlos Vega, джерело
Велике спасибі Аарону, це було дуже корисно. Тепер я очищую свої концепції
додано Автор user1017072, джерело

Вам потрібно передати покажчик, щоб запустити покажчик у функції insert_after

void insert_after(node **start)

замість

void insert_after(node *start)

Інакше ви будете просто оновлювати локальну копію початком *.

Аналогічно для ініціалізації

void initialize(node **start)
1
додано

Простіше кажучи, рекурсивні виклики не знають вихідного вузла початку. Вам потрібно буде додати другий аргумент node * і передавати його за допомогою початкового вузла.

0
додано
У функції прототипу. У виклику функції
додано Автор Ignacio Vazquez-Abrams, джерело
Привіт Ігнасіо, де я повинен додати другий вузол і як я передаю початковий вузол. Мені шкода, що це звучить як нуб, але чи могли б ви показати мені, як це виправити, я не можу зрозуміти. Велике спасибі за вашу допомогу
додано Автор user1017072, джерело