Памылка пры спробе злічыць вузлы ў кругавым двусвязном спісе рэкурсіўна

Вось мая рэалізацыя графа:

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
Чаму вы л статычны? Гэта проста прадухіляе функцыю ад поўнага зваротнай, які, як правіла, з'яўляецца абавязковым патрабаваннем для правільнай рэкурсіі.
дададзена аўтар Ignacio Vazquez-Abrams, крыніца

4 адказы

Ну, праблема ў тым, што вы выклікаеце гэтую функцыю ў асноўным на паказальнік NULL. Infact вузел * галава; аб'яўлена, але ніколі не прызначаецца да нечага. Таму, калі вы выконваеце гэты радок:

if(current->next!=start)

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

1
дададзена
@ User1017072 Ну, у гэтым выпадку вы павінны паказаць нам функцыю, дадаць дадзеныя. Акрамя таго, выдаліце ​​радкі статычнага Int л; так як гэта бескарысна і змяніць, калі ў проста вяртае 1 + колькасць (current-> наступная); які з'яўляецца належным чынам мець рэкурсіўная функцыю.
дададзена аўтар Aurelio De Rosa, крыніца
У мяне таксама ёсць метад, які ў асноўным ўстаўляе значэнне дадзеных да вузла. Але гэта, здаецца, не ў стане нават пасля таго, як я стварыў новыя вузлы. Для першага вузла, ён дае правільную даўжыню 1 (г.зн. пераходзіць да блоку яшчэ), але для другога, ён выходзіць з ладу, калі ён дасягне, калі (current-> наступнага! = Старт), я павінен зрабіць некаторыя ініцыялізацыі ў функцыі, дзе я ствараю вузлы? Дзякуй за дапамогу
дададзена аўтар 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-х гадоў!), Але на аснове маёй ініцыялізацыі з у 1 , я мяркую, што мая мэта была для бягучы пачаць у Пуск-> Далей . Ці значыць гэта мае сэнс?
дададзена аўтар Aaron Dufour, крыніца
@ Аарон-Dufour Я думаю, што нерекурсивна версія няправільная. Перад тым, <б>, а пятля <я> току і <я> старт роўныя, так што не збіраецца патрапіць у пятлю, ён павінен быць рабіць-то час цыклу.
дададзена аўтар Carlos Vega, крыніца
Так, цяпер гэта нерухомае;)
дададзена аўтар Carlos Vega, крыніца
Вялікі дзякуй Аарона, што было вельмі карысна. Цяпер я мае паняцця ачышчаны
дададзена аўтар user1017072, крыніца

Вам трэба перадаць паказальнік на паказальнік пачатку ў функцыі insert_after

void insert_after(node **start)

замест

void insert_after(node *start)

У адваротным выпадку вы будзеце проста абнавіць лакальную копію * пачатку.

Аналагічна для Initialize

void initialize(node **start)
1
дададзена

Прасцей кажучы, рэкурсіўныя выклікі не ведаюць, арыгінальны пачатковы вузел. Вам трэба будзе дадаць другі вузел * аргумент і перадаць пачатковы вузел праз яго.

0
дададзена
У прататыпе функцыі. У выкліку функцыі.
дададзена аўтар Ignacio Vazquez-Abrams, крыніца
Прывітанне Ігнасіа, дзе я павінен дадаць другі вузел і як прайсці пачатковы вузел. Я прашу прабачэння за які гучыць як нуб, але не маглі б вы паказаць мне, як гэта выправіць, я не магу зразумець. Вялікі дзякуй за вашу дапамогу
дададзена аўтар user1017072, крыніца