Linked list problem

proev (utestet):

void addFirst(int i, struct node *insert, struct node **h)
{
    insert->id = i;
    insert->next = NULL;
    if (*h != NULL)
    {
        *h->next = insert;
    }
    else
    {
        *h = insert;
    }

    *h = *insert;

}

Det giver flg. fejl når jeg compilerer:

linkedListBasic.c: In function ‘addFirst’:
linkedListBasic.c:33: error: request for member ‘next’ in something not a structure or union
linkedListBasic.c:40: error: incompatible types in assignment

linje 33 er:  *h->next = insert;
linje 40 er:  *h = *insert;

kan rette linje 40 sådan: **h = *insert;
Men 'head' er en pointer til en struct og har ikke en next i sig, så måske er det derfor linje 33 giver fejl?

Jeg proever lige og lavet et komplet eksempel som virker.

#include <stdio.h>
#include <stdlib.h>

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

void add(struct node **head, int i);

int main()
{
    struct node *head;
    struct node *n;
    head = NULL;
    add(&head, 5);
    add(&head, 6);
    add(&head, 7);
    n = head;
    while(n != NULL)
    {
        printf("id=%d\n", n->id);
        printf("next=%d\n", n->next);
        n = n->next;
    }
    return 0;
}

void add(struct node **head, int i)
{
    struct node *n;
    struct node *p;
    n = (struct node *)malloc(sizeof(struct node));
    n->id = i;
    n->next = NULL;
    if(*head == NULL)
    {
        *head = n;
    }
    else
    {
        p = *head;
        while(p->next != NULL) p = p->next;
        p->next = n;
    }
}

erhm...det er jo et helt andet eksempel. Hvis jeg skal forstå hvordan det virker så nytter det jo ikke så meget (har set flere kode eksempler på nettet, men jeg kan ikke finde ud af hvad der er galt med min kode.)

Jeg har ikke lavet det om for sjovs skyld.

Du skal ikke referere til baade den globale header og til header der kommer over som argument.

Header skal over som pointer til pointer for at du kan saette den naar den foerste node
indsaettes.

Naar du alligevel sende id med over som argument, saa kan jeg ikke se grunden til at
selve struct'en ogsaa skal med.

Derfor:

void addFirst(int i, struct node *insert, struct node *h)

->

void add(struct node **head, int i)

Og saa har jeg aendret koden i tilfaelde af at head ikke er NULL til at
iterere ned til enden af listen og tilfoeje der.

Jeps der har jeg været før, det andet var en forsøgt lappeløsning da jeg ikke kunne få det til at fungere..
hvorfor bruger du malloc? kan det ikke lade sig gøre uden?

Men vil nu gerne have den nye node ind i starten, derfor metoden addFirst..
bagefter vil jeg formentlig lave addLast..

Jeg synes ikke at det er paent at lave en liste af structs som man har som
lokale variable.

De kunne gaa ud af scope med deraf foelgende memory corruption.

ok jeg kan godt se din pointe, men jeg prøver bare at tage det et step ad gangen. Mit første step er 'hello linked list'.

Har omstruktureret efter dine (arne v's) anvisninger (venter lige med malloc dog, med mindre det er den som er problemet). Men som sagt har været her før, det giver også præcis samme output som jeg pastede ind i toppen..

void addFirst(int i, struct node **h){
       
    struct node nyNode;   
    nyNode.id = i;

    if (*h != NULL){  //hvis listen ikke er tom
       
        nyNode.next = *h;  //hvis jeg udkommenterer denne bliver next = NULL, på den sidste node, og nyNode.next = **h
                                                    //vil compileren ikke være med til såå nogen gode idéer?
    } else {
        nyNode.next = NULL;
    }

    *h = &nyNode;
    structInfo(nyNode, *h);
}

alt andet end: nyNode.next = *h; ser ud til at opføre sig som det skal..

Nå har fundet fejlen, det var selvfølgelig en mindre tanketorsk. Problemet var at jeg (som arne v, i virkeligheden også var inde på), at jeg opretter Noderne lokalt når addFirst køres. Dvs. de bliver lagt i addFirst's stack (som jo er lokal) og når vi kommer tilbage til mainmetoden igen, peger head på noget som måske allerede er blevet ændret eller i hvertfald med stor sandsynlighed bliver det næste gang addFirst bliver kørt. Den simpleste løsning er, at oprette noden i main, og derefter sende referencen til den node som skal oprettes i listen + ref. til head til addFirst. Så længe mainmetoden kører (og det gør den så længe programmet kører, ligger alle noderne (dvs. hele den linkede liste) i main metoden stack og det vil derfor virke. Den lidt smukkere metode er måske (som arne v også var inde på) at bruge malloc til at at allokere plads til noderne i heap'en. Anyway, arne v da du har ledt mig på rette spor synes jeg du skal have points'ne, så smid et svar, hvis du vil have points:)..

//glemte at paste koden;
//----------------------------

#include <stdio.h>

void addFirst();
void structInfo();
void printList();

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


int main(){

    struct node n1, n2;
    struct node *head;
   
    n1.id = 1;
    n2.id = 2;
   
    addFirst(&n1, &head);
    structInfo(&n1, &head);
    addFirst(&n2, &head);
    structInfo(&n2, &head);
    //printList(&head);
   
    return 0;
}

void addFirst(struct node *add, struct node *head){
       
    if (head->next != NULL){ 
        add->next = head->next;
    }

    head->next = add;
}

void structInfo(struct node *p, struct node *head){
   
    printf("Struct infos: -------\n");
    if (head->next != NULL){
                    printf("global head: %d\n", head->next->id);
            } else {
                    printf("global head: NULL\n");
            }
       
            printf("id        : %d\n", p->id);
            if (p->next != NULL){
                printf("Next->id  : %d\n", p->next->id);
            } else {
                printf("Next->id = NULL!\n"); 
            }
}

void printList(struct node *h){
    printf("Hele den linkede liste (id'er): ---\n");
    while(h->next != NULL){
        printf("%d ", h->next->id);
        h = h->next;
    }
   
    printf("\n---------------\n");
   
}

Hmm...ser dog lige med friske øjne at nok har været en anden..

Hvis en kan give den fede og pædagogiske forklaring, smider jeg gerne points'ne der (eftersom det ikke ser ud til at arne v, dukker op, og jeg desuden egentlig løste det ved at gå et stykke tilbage og bygge det op endnu engang, og ikke rigtigt forstod hans forklaring)..

well kom frisk! den gode og pædagogiske pointer udredning, er der helt sikkert mange som vil værtsætte så det er helt klart 200 point værd fra mig.

koden 03/06-2008 09:30:06 er helt gal.

struct node *head; // head = sted på stak som peger på tilfældigt sted i memory

addFirst(&n1, &head); // kalder med adressen på head
structInfo(&n1, &head); // kalder med adressen på head

void addFirst(struct node *add, struct node *head){
void structInfo(struct node *p, struct node *head){
 
head->next // tror at der ligger en struct node på det sted på stak hvor der ligger en pointer

Det kan godt være at struct node *head; peger et tilfældigt sted i memory, men den bliver tilgengæld ved med at pege det samme tilfældige sted, da den ligger i main metoden. head->next //nope der ligger head. prøv at kør denne (indsætter lidt flere noder og kører printLint, ellers er koden den samme).

#include <stdio.h>

void addFirst(); //'præsenter' metoden
void structInfo();
void printList();

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


int main(){

    struct node n1, n2, n3, n4, n5;
    struct node *head;
   
    n1.id = 1;
    n2.id = 2;
    n3.id = 3;
    n4.id = 4;
   
    addFirst(&n1, &head);
    addFirst(&n2, &head);
    addFirst(&n3, &head);
    addFirst(&n4, &head);

    printList(&head);
   
    return 0;
}

void addFirst(struct node *add, struct node *head){
       
    if (head->next != NULL){ 
        add->next = head->next;
    }

    head->next = add;
}


void structInfo(struct node *p, struct node *head){
   
    printf("Struct infos: -------\n");
    if (head->next != NULL){
                    printf("global head: %d\n", head->next->id);
            } else {
                    printf("global head: NULL\n");
            }
       
            printf("id        : %d\n", p->id);
            if (p->next != NULL){
                printf("Next->id  : %d\n", p->next->id);
            } else {
                printf("Next->id = NULL!\n"); 
            }
}


void printList(struct node *h){
    printf("Hele den linkede liste (id'er): ---\n");
    while(h->next != NULL){
        printf("%d ", h->next->id);
        h = h->next;
    }
   
    printf("\n---------------\n");
   
}

Programmet er defekt. Og med GCC 4.2.0 på Windows så crasher det.

Du kan se det ved at indsætte følgende debug:

#include <stdio.h>

void addFirst(); //'præsenter' metoden
void structInfo();
void printList();

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


int main(){

    struct node n1, n2, n3, n4, n5;
    struct node *head;
 
    n1.id = 1;
    n2.id = 2;
    n3.id = 3;
    n4.id = 4;

    printf("main: pointeren head ligger på addresse %p\n", &head);
    printf("main: pointeren head peger på addresse %p\n", head);
 
    addFirst(&n1, &head);
    addFirst(&n2, &head);
    addFirst(&n3, &head);
    addFirst(&n4, &head);

    printList(&head);
 
    return 0;
}

void addFirst(struct node *add, struct node *head){
    printf("addfirst: pointeren head ligger på addresse %p\n", &head);
    printf("addfirst: pointeren head peger på addresse %p\n", head);
     
    if (head->next != NULL){
        add->next = head->next;
    }

    head->next = add;
}


void structInfo(struct node *p, struct node *head){
 
    printf("Struct infos: -------\n");
    if (head->next != NULL){
                    printf("global head: %d\n", head->next->id);
            } else {
                    printf("global head: NULL\n");
            }
     
            printf("id        : %d\n", p->id);
            if (p->next != NULL){
                printf("Next->id  : %d\n", p->next->id);
            } else {
                printf("Next->id = NULL!\n");
            }
}


void printList(struct node *h){
    printf("Hele den linkede liste (id'er): ---\n");
    while(h->next != NULL){
        printf("%d ", h->next->id);
        h = h->next;
    }
 
    printf("\n---------------\n");
 
}

Det virker dog perfekt i gcc 4.01 på Mac
output:
main: pointeren head ligger på addresse 0xbffffa00
main: pointeren head peger på addresse 0x0
addfirst: pointeren head ligger på addresse 0xbffff9bc
addfirst: pointeren head peger på addresse 0xbffffa00
addfirst: pointeren head ligger på addresse 0xbffff9bc
addfirst: pointeren head peger på addresse 0xbffffa00
addfirst: pointeren head ligger på addresse 0xbffff9bc
addfirst: pointeren head peger på addresse 0xbffffa00
addfirst: pointeren head ligger på addresse 0xbffff9bc
addfirst: pointeren head peger på addresse 0xbffffa00
Hele den linkede liste (id'er): ---
4 3 2 1
---------------
debug:
main: pointeren head ligger på addresse 0xbffffa00    //her ligger head
main: pointeren head peger på addresse 0x0                //peger ikke på noget endnu

addfirst: pointeren head peger på addresse 0xbffffa00  //(peger på den adresse i main hvor head ligger (som stadig er
                                                                                                  // den samme))                 
addfirst: pointeren head ligger på addresse 0xbffff9bc  //dette er jo addFirst's lokale pointer til main's head, derfor har den                         
                                                                                                  //en anden adresse

Hvad mener du med at din gcc crasher? kommer den op med nogen fejl?

Anyway, hvis det du ville var at se hvad den virkelige 'head' (fra mainmetoden) peger på skal det jo være sådan:

void addFirst(struct node *add, struct node *head){
    printf("addfirst: pointeren head ligger på addresse        %p\n", &head);
    printf("addfirst: pointeren (lokal) head peger på addresse %p\n", head);
    printf("addfirst: pointeren head (main) peger på addresse  %p\n", head->next);
     
    if (head->next != NULL){
        add->next = head->next;
    }

    head->next = add;
}

Hvis gcc i windows ikke kan lide det burde man i hvertfald kunne gøre sådan..
int main(){

    struct node n1, n2, n3, n4, h;
    struct node *head = &h;

......

så er det skåret ud i pap..

Nej det virker ikke perfekt.

Hvis du kigger paa:

main: pointeren head ligger på addresse 0xbffffa00
main: pointeren head peger på addresse 0x0
addfirst: pointeren head ligger på addresse 0xbffff9bc
addfirst: pointeren head peger på addresse 0xbffffa00

saa ser du at nede i addfirst peger dens head paa det sted i memory hvor
der kun ligger en pointer ikke en struct.

Og det betyder at naar addfirst opdaterer i den struct saa overskriver den
det memory som tilfaeldigvis ligger efter head i main.

----

Hvis du lod prototypen for addFirst angive argumenter, saa ville compileren ogsaa
brokke sig.

----

struct node *head = &h;

faar head til at pege paa noget validt. Men det loeser ikke problemet, da det ikke
er det som head peger paa, men derimod det lige efter head som bliver overskrevet.

>saa ser du at nede i addfirst peger dens head paa det sted i memory hvor
der kun ligger en pointer ikke en struct.<

Præcis, den peger på main's head som er en pointer.

>Hvis du lod prototypen for addFirst angive argumenter, saa ville compileren ogsaa
brokke sig.<

Det må du nok udspecificere. Prototypen, lyder lidt som java-tankegang, jeg instantierer den jo ikke ligefrem (måske mener du noget helt andet(?)).

>faar head til at pege paa noget validt. Men det loeser ikke problemet, da det ikke
er det som head peger paa, men derimod det lige efter head som bliver overskrevet.<

'head' peger lige nu på en 'dummy struct'. Som sagt min gcc har ingen problemer her, men jeg lavede det i tilfælde af, at ældre compilere ikke kan lide at det det er uspecificeret hvor en pointer peger hen..

Jeg har desuden svært ved at forestille mig hvordan en linked liste kan blive til hvis headpointeren ikke virker efter hensigten, og hvorfor det virker giver også fint mening for mig:

output:

main: pointeren head ligger på addresse 0xbffffa00    //her ligger den officielle 'head' i main's stack, denne bliver liggende her
main: pointeren head peger på addresse 0xbffff9f8    //den peger nu på dummystruct'et 'head' (da jeg har updateret koden med       
                                                                                              //indlæg fra 18:50:15)       
                                   
addfirst: pointeren (lokal) head ligger på addresse        0xbffff9bc 
/*Denne pointer bliver deklareret som argument til addFirst. Hvis f.eks. vi har en metode: minMetode(int x, int *yPointer){} 
bliver 'x' og 'yPointer' lagt i 'minMetode's stack. int'en indeholder (formentlig) en int værdi, mens pointeren indeholder en adresse. Altså er 'yPointer' lokal lige så vel som 'x'. I mit linked list tilfælde hedder de bare begge head (for at forvirre mest muligt....(joke:)).
*/

addfirst: pointeren (lokal) head peger på addresse 0xbffffa00  //dette er addFirst's adresse til head'pointeren i main

addfirst: pointeren head (main) peger på addresse  0x0    //dette er den officielle 'head' som ikke endnu peger på noget endnu
addfirst: pointeren (lokal) head ligger på addresse        0xbffff9bc //placeringen af addFirst's lokale pointer er naturligvis
                                                                                                                    //uændret
addfirst: pointeren (lokal) head peger på addresse 0xbffffa00      //peger stadig på main's head (som forventet)
addfirst: pointeren head (main) peger på addresse  0xbffff9d8    //dette er adressen til den nye node som skal indsættes
addfirst: pointeren (lokal) head ligger på addresse        0xbffff9bc //same same (se sidste gang adressen var repræsenteret)
addfirst: pointeren (lokal) head peger på addresse 0xbffffa00        //peger stadig på main's head (som forventet)
addfirst: pointeren head (main) peger på addresse  0xbffff9e0      //ny node...
addfirst: pointeren (lokal) head ligger på addresse        0xbffff9bc //same same (se sidste gang adressen var repræsenteret)
addfirst: pointeren (lokal) head peger på addresse 0xbffffa00      //peger stadig på main's head (som forventet)
addfirst: pointeren head (main) peger på addresse  0xbffff9e8    //ny node..
Hele den linkede liste (id'er): ---
4 3 2 1
---------------
Voila! ikke (for mig) overraskende en linked liste..

ps. ny node = sidste nye node, da printsætningen står før main's 'head' bliver updateret...

Bare ret:

void addFirst(); //'præsenter' metoden
void structInfo();
void printList();

til:

void addFirst(struct node *add, struct node *head); //'præsenter' metoden
void structInfo(struct node *p, struct node *head);
void printList(struct node *h);

så får du compile fejlene.

Og det er forkert at head i metoden peger på head i main - den skal pege på det
samme som head i main peger på.

Jeps du har ret i 04:06:43, den havde jeg overset tak for det!
med hensyn til 04:07:17, er det jo ikke forkert, der bare flere måder at implementere en linked liste på, og head bliver desuden opdateret som den skal.

Men tak for diskussionerne, det har da trukket mig godt og grundigt rundt i stoffet må man sige! Jeg synes du fortjener nogle points så smid et svar, hvis du vil have dem, (og så kan vi få lukket debatten:)..

omstrukturering:

#include <stdio.h>

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

void addFirst(struct node *add, struct node **head);
void printList(struct node *h);

struct node *head = NULL;

int main(){

    struct node n1, n2, n3, n4;

    n1.id = 1;
    n2.id = 2;
    n3.id = 3;
    n4.id = 4;
   
    addFirst(&n1, &head);
    addFirst(&n2, &head);
    addFirst(&n3, &head);
    addFirst(&n4, &head);

    printList(head);
   
    return 0;
}

void addFirst(struct node *add, struct node **h){
       
    if (*h != NULL){ 
        add->next = *h;
    }
    *h = add;
}


void printList(struct node *h){
    printf("Hele den linkede liste (id'er): ---\n");
       
    while(h != NULL){
        printf("%d ", h->id);
        h = h->next;
    }
   
    printf("\n---------------\n");
   
}

udover at det selvfølgelig giver bedre mening her at flytte struct node *head = NULL;  ind i main her

og så den helt pæne med malloc (tak arne v)

#include <stdio.h>
#include <stdlib.h>

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

void addFirst(int i);
void printList();

struct node *head = NULL;
   
int main(){
   
    int a = 1, b = 2, c = 3, d = 4;
   
    addFirst(a);
    addFirst(b);
    addFirst(c);
    addFirst(d);
    printList();
   
    return 0;
}

void addFirst(int i){
   
    struct node *n;                     
    n = (struct node*) malloc(sizeof(struct node)); 
    n->id = i;
           
    if (head != NULL){ 
        n->next = head;
    }
    head = n;
}

void printList(){
    printf("Hele den linkede liste (id'er): ---\n");
               
        while(head != NULL){
            printf("%d ", head->id);
            head = head->next;
        }
       
        printf("\n---------------\n");
   
}

ja og så lige den sidste rettelse:

void printList(){
    printf("Hele den linkede liste (id'er): ---\n");
       
    struct node *localHead = head;
               
        while(localHead != NULL){
            printf("%d ", localHead->id);
            localHead = localHead->next;
        }
       
        printf("\n---------------\n");
   
}

ellers kan man kun printe listen ud én gang..

svar