[C] Linked list foute verwijzing

[vmsw]

Betreft een vraag over de programmeertaal C. Ik ben hiermee nu al meerdere uren aan het prutsen, en kan niks vinden wat lukt. Ik heb hieronder de betreffende (belangrijke) stukjes gegeven.

code:

typedef struct node1 {
   Triangle t;
   struct node1 *next;
} Node;

Node makeNode (Triangle t)
{
    Node node;
    
    node.t = t;
    node.next = NULL;
    
    return node;
}

code:

Node startnode;

void addTriangle(Triangle t)
{   
    int i = 0;
    Node nieuweNode = makeNode(t);
    Node *vorigenode;
    Node *huidigenode;

    vorigenode = &startnode;
    huidigenode = vorigenode->next;
    
        while (huidigenode != NULL)
        {
            /*if (area(huidigenode->t) > area(nieuweNode.t))
            {
                vorigenode->next = &nieuweNode;
                nieuweNode.next = huidigenode;
                return;
            }*/
            
            vorigenode = huidigenode;
            huidigenode = vorigenode->next;
        }
        
        vorigenode->next = &nieuweNode;

        drukdriehoekrijaf();
}

Beginsituatie van inhoud:
1. Startnode

De eerste node die ik toevoeg gaat prima; de waarde wordt toegevoegd. De inhoud wordt dan volgens mij:
1. startnode
2. node1

Zodra ik de tweede node toevoeg, gaat het mis. De waarde zou moeten worden:
1. startnode
2. node1
3. node2

Echter blijkt node1 niet meer te bestaan, en blijkt node2 naar zichzelf te verwijzen.. in ieder geval blijft hij hangen zodra ik alle waardes langs wil gaan door steeds 'next' te nemen.

Wat doe ik fout?

N.B. [C] in titel vergeten; reeds aangegeven aan mods.

[Robtimus]

vmsw schreef op donderdag 24 juni 2010 @ 21:44:

C:

Node makeNode (Triangle t)
{
    Node node;
    
    node.t = t;
    node.next = NULL;
    
    return node;
}

Correct me if I'm wrong (ik ben beter thuis in Java), maar volgens mij wordt node op de stack opgeslagen, en zodra de method eindigt wordt de stack opgeruimd. Je zult node op de "heap" moeten creëren:

C:

Node* makeNode(Triangle t)
{
    Node* node;

    node = malloc(sizeof(Node));
    node->t = t;
    node->next = NULL;

    return node;
}

Later natuurlijk niet vergeten weer free aan te roepen zodra je ermee klaar bent, anders krijg je een memory leak.

[vmsw]

De oneindige loop is inderdaad weg, wat dat betreft klopt het nu. Gevolg is echter dat de loop-functie de volgende resultaten geeft:

na eerste toevoeging:
- startwaarde
- node1

na tweede toevoeging:
- startwaarde
- node2
- node2

(en zal wel door iets anders komen, maar als ik later nog een keer de functie aanroep krijg ik volgens mij 2 geheugenlocaties ipv waardes)

code:

void drukdriehoekrijaf()
{
    Node *huidigenode = malloc(sizeof(Node));
    huidigenode = &startnode;
    
    huidigenode = huidigenode->next;

    do
    {
        printf("De driehoek heeft oppervlakte %f\n", area(huidigenode->t));
        
        huidigenode = huidigenode->next;
    }
    while (huidigenode != NULL);
}

[user109731]

IceManX schreef op donderdag 24 juni 2010 @ 21:57:
[...]
Correct me if I'm wrong (ik ben beter thuis in Java), maar volgens mij wordt node op de stack opgeslagen, en zodra de method eindigt wordt de stack opgeruimd. Je zult node op de "heap" moeten creëren:

Dat kan, maar is niet de oorzaak hier. In de code van de TS wordt de Node idd op de stack opgeslagen, maar moet wordt (mogelijk) gekopieerd na de functie-aanroep. Wat niet zou mogen is een pointer teruggeven naar een element op de stack.

@TS: pas op, met zulke constructies krijg je memory leaks.

C:

Node *huidigenode = malloc(sizeof(Node));
huidigenode = &startnode;

Je alloceert een blok geheugen, vervolgens stel je de pointer in op een andere node en het blok geheugen is verloren.

[ Voor 20% gewijzigd door user109731 op 24-06-2010 22:28 ]

[RayNbow]

JanDM schreef op donderdag 24 juni 2010 @ 22:21:
[...]

Dat kan, maar is niet de oorzaak hier. In de code van de TS wordt de Node idd op de stack opgeslagen, maar moet wordt (mogelijk) gekopieerd na de functie-aanroep. Wat niet zou mogen is een pointer teruggeven naar een element op de stack.

Dat laatste is wel het probleem in de originele code:

C:

    Node nieuweNode = makeNode(t);

C:

                vorigenode->next = &nieuweNode;

Het adres van nieuweNode is onzinnig wanneer addTriangle() verlaten wordt.

[user109731]

Ah ik keek alleen naar de makeNode-code omdat die werd ge-quote, maar je hebt idd gelijk dat het in een ander stuk wel misgaat.

edit: laat maar
edit 2: het hele vorigenode/huidigenode gebeuren kan eenvoudiger met zoiets:

C:

Node* node = &start;

while(node->next != NULL)
  node = node->next;

node->next = nieuweNode;

Misschien ook handig om een pointer naar je laatste node op te slaan, zodat je nieuwe nodes kunt toevoegen in constante tijd

[ Voor 106% gewijzigd door user109731 op 24-06-2010 23:03 ]

[Robtimus]

JanDM had volgens mij gelijk. Structs worden member voor member gekopieerd zodra je ze meegeeft als parameter of als return value.

Voorbeeld:

C:

#include <stdio.h>

typedef struct test
{
    int i;
} Test;


Test create_test()
{
    struct test t;
    t.i = 13;
    return t;
}

void print_test(Test t)
{
    fprintf(stdout, "%d\n", t.i);
}

int main(int argc, char** argv)
{
    Test t = create_test();
    print_test(t);
    return 0;
}

Dit print gewoon 13.

[prototype]

IceManX schreef op donderdag 24 juni 2010 @ 21:57:
[...]

Correct me if I'm wrong (ik ben beter thuis in Java), maar volgens mij wordt node op de stack opgeslagen, en zodra de method eindigt wordt de stack opgeruimd. Je zult node op de "heap" moeten creëren:

C:

Node* makeNode(Triangle t)
{
    Node* node;

    node = malloc(sizeof(Node));
    node->t = t;
    node->next = NULL;

    return node;
}

Later natuurlijk niet vergeten weer free aan te roepen zodra je ermee klaar bent, anders krijg je een memory leak.

Met een enkele free ben je er nog niet helemaal mee klaar he? Stel je hebt:

code:

A -> B -> C

Stel, je free'ed nu B. Dan heb je nu een dangling pointers in A naar een adres waar B __zat__. Dit kan mogelijk tot segfaults leiden indien je de pointer probeert te accessen.

Aangezien je hier te maken hebt met een single-linked list moet je de hele list nu traversen op zoek naar nodes die verwijzen naar B om die juist te connecten. Kan nogal inefficient worden heletijd zo'n linear search. Ik zou dan ook van harte aanraden om een double-linked list te overwegen als je de overhead van een extra pointer per node kan missen, waarbij elke node dus ook een pointer naar zijn vorige element heeft. Verwijder je nu een element als B, dan kan je het volgende doen:

C:

void freeNode(Node *node) {
    if (node == NULL) return;

    Node *prevNode = node->prev;
    Node *nextNode = node->next;
    
    if (prevNode != NULL) {
        prevNode->next = nextNode;
    }
    
    if (nextNode != NULL) {
        nextNode->prev = prevNode;
    }
    
    free(node);
    node = NULL;
}

Verder wil je ook het advies van JanDM overwegen indien je met veel elementen werkt om nog ergens een ptr bij te houden naar de laatste element in de list zodat je elementen in constante tijd kan toevoegen en/of een andere datastructuur. Ook het advies van Raynbow over stack allocated vars en addressen wil je denk ik even naar kijken.

[Reptile209]

vmsw schreef op donderdag 24 juni 2010 @ 22:13:
De oneindige loop is inderdaad weg, wat dat betreft klopt het nu. Gevolg is echter dat de loop-functie de volgende resultaten geeft:

na eerste toevoeging:
- startwaarde
- node1

na tweede toevoeging:
- startwaarde
- node2
- node2

(en zal wel door iets anders komen, maar als ik later nog een keer de functie aanroep krijg ik volgens mij 2 geheugenlocaties ipv waardes)
[...]

Ik zal, even los van alle offtopic discussies over optimalisaties, dubbele linked lists, enz., proberen op je probleem in te gaan.

Wat je nu ziet gebeuren, komt meestal door a) fouten in je code/logica, of b) gerommel met pointers, leidend tot a). Ben je al eens met een debugger door je addNode-code heengestapt? Al eens op papier uitgeschreven welke route door de code je programma volgens jou zou moeten volgen, en dat daarna met de debugger vergeleken?

[NC83]

vmsw schreef op donderdag 24 juni 2010 @ 21:44:
Betreft een vraag over de programmeertaal C. Ik ben hiermee nu al meerdere uren aan het prutsen, en kan niks vinden wat lukt. Ik heb hieronder de betreffende (belangrijke) stukjes gegeven.

code:

typedef struct node1 {
   Triangle t;
   struct node1 *next;
} Node;

Node makeNode (Triangle t)
{
    Node node;
    
    node.t = t;
    node.next = NULL;
    
    return node;
}

code:

Node startnode;

void addTriangle(Triangle t)
{   
    int i = 0;
    Node nieuweNode = makeNode(t);
    Node *vorigenode;
    Node *huidigenode;

    vorigenode = &startnode;
    huidigenode = vorigenode->next;
    
        while (huidigenode != NULL)
        {
            /*if (area(huidigenode->t) > area(nieuweNode.t))
            {
                vorigenode->next = &nieuweNode;
                nieuweNode.next = huidigenode;
                return;
            }*/
            
            vorigenode = huidigenode;
            huidigenode = vorigenode->next;
        }
        
        vorigenode->next = &nieuweNode;

        drukdriehoekrijaf();
}

Beginsituatie van inhoud:
1. Startnode

De eerste node die ik toevoeg gaat prima; de waarde wordt toegevoegd. De inhoud wordt dan volgens mij:
1. startnode
2. node1

Zodra ik de tweede node toevoeg, gaat het mis. De waarde zou moeten worden:
1. startnode
2. node1
3. node2

Echter blijkt node1 niet meer te bestaan, en blijkt node2 naar zichzelf te verwijzen.. in ieder geval blijft hij hangen zodra ik alle waardes langs wil gaan door steeds 'next' te nemen.

Wat doe ik fout?

N.B. [C] in titel vergeten; reeds aangegeven aan mods.

Als je make node eens verandert in dit

C:

typedef struct node1 {
   Triangle t;
   struct node1 *next;
} Node;

Node* makeNode (Triangle t)
{
    Node* node = node = malloc(sizeof(Node));
    
    node->t = t;
    node->next = NULL;
    
    return node;
}

je andere code wordt dan

C:

Node* startnode; //Wordt ergens aangemaakt

void addTriangle(Triangle t)
{
    Node* currentNode = startNode;
    while(currentNode)
    {
        currentNode = currentNode->Next;
    }

    currentNode->Next = makeNode(t);
}

En opruimen wordt

C:

void deleteNodes()
{
    Node* currentNode = startNode;
    while(currentNode)
    {
        Node* nodeToDelete = currentNode;
        currentNode = currentNode->Next;
        free(nodeToDelete);
    }
}

Het probleem waar je tegen aan aan het lopen was is idd dat je de node in je huidige code op de stack aanmaakt, de stack wordt na een {} block volledig weggegooid. Als je dus waardes wil bewaren en op meerdere plaatsen wil gebruiken moet je of gebruik maken van globals, wat trouwens niet netjes is maar soms nodezakelijk, of alles op de heap alloceren. Als je spullen op de heap alloceert dan moet je er zorg voor dragen om dit op te ruimen.

Als je lijst nu erg lang wordt heeft een dubbel linked list voordelen omdat het makkelijker is om nodes midden in de lijst toe te voegen.

[ Voor 10% gewijzigd door NC83 op 25-06-2010 17:40 ]