[C] Geheugen van Linked Lists teruggeven

[Joshua822]

Hallo allemaal.
Ik heb een vraag. Met de funcite malloc zorg ik voor een plaats in het geheugen voor een deel van mijn Linked List, maar na een tijdje heb ik deze niet meer nodig, en wil ik het geheugen dat ik met de Linked List bezet houd, teruggeven met bijvoorbeeld de functie free, hoe kan ik dit doen ?

Trouwens, hier is mijn test programma :

Code: [Selecteer]

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

 struct node
 {
   int waarde;
   struct node *volgende;
 };

 int main()
 {
    struct node *root;       
    struct node *machinist; 

    root = malloc( sizeof( struct node ) ); 
   
    root->volgende = malloc( sizeof( struct node ) );   
   
    machinist = root;
   
      while ( machinist->volgende != 0)
      {
        printf( "%s", "Geef een geheel getal :");
        scanf( "%d", &machinist->waarde );
        printf( "%d \n", machinist->waarde );
        machinist = machinist->volgende;
        machinist->volgende = malloc ( sizeof ( node struct ) );
     
      } 
   

    return 0;
}

Opmerking : ja, ik weet dat de while lus oneindig is. Dit zal ik zometeen even oplossen, als ik weet hoe ik het in beslag genomen geheugen weer terug geef.

Alvast bedankt.

[profoX]

De volledige gelinkte lijst? Dat kan o.a. zo:

Code: [Selecteer]

machinist = root;
    while (machinist) {
    struct node *toDelete = machinist;
    machinist = machinist->volgende;
    free(toDelete);
}

[profoX]

nog even enkele opmerkingen:

- je moet void* typecasten naar struct node*
- node struct != struct node
- je doet steeds 2 extra allocaties die niet nodig zijn
- formatters zijn niet verplicht in printf wanneer je ze niet nodig hebt

voorbeeld van een versie waar met bovenstaande punten rekening wordt gehouden:

Code: [Selecteer]

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

struct node {
    int waarde;
    struct node *volgende;
};

int main(void) {
    int i;
    struct node *root = NULL, *machinist = NULL;
   
    /* Getallen inlezen in dynamisch gelinkte lijst */
    for (i = 0; i < 4; ++i) {
        if (!root) {
            machinist = (struct node*)malloc(sizeof(struct node));
            root = machinist;
        } else {
            machinist->volgende = (struct node*)malloc(sizeof(struct node));
            machinist = machinist->volgende;
        }
        printf("Geef een geheel getal: ");
        scanf("%d", &machinist->waarde);
        printf("%d\n", machinist->waarde);
        machinist->volgende = NULL;
    }

    /* Geheugen vrijmaken */
    machinist = root;
    while (machinist) {
        struct node *toDelete = machinist;
        machinist = machinist->volgende;
        free(toDelete);
    } 

    return 0;
}
nog enkele tips:

- compileer met gcc -Wall -ansi -pedantic file.c -o file om te controleren of je programma aan de strikte ANSI C standaard voldoet
- gebruik valgrind --leak-check=full om te controleren of je programma geheugenlekken bevat

[Joshua822]

Bedankt voor het antwoord.

Echter, nu heb ik nog één vraag om het perfect volgens de standaard te maken.

Dit is de code :

Code: [Selecteer]

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

 struct node
 {
   char waarde;
   struct node *volgende;
 };

 int main()
 {
    struct node *root;       
    struct node *machinist; 

    root = (struct node*)malloc(sizeof(struct node)); 
   
    root->volgende = (struct node*)malloc(sizeof(struct node));   
   
    machinist = root;
   
    while ( machinist->volgende )
    {
        printf("%s","Geef een geheel getal :");
        scanf("%s",&machinist->waarde);
        if(machinist->waarde == 'q')
        {
         struct node *freemem = machinist;
         machinist = machinist->volgende;
         free(freemem);
         return 0;
        }
        else
        {
        printf("%s",machinist->waarde);
        machinist = machinist->volgende;
        machinist->volgende = (struct node*)malloc(sizeof(struct node));
        }
    }

    return 0;
}
Echter, met het commando gcc -Wall -ansi -pedantic test.c -o test krijg ik de volgende foutmelding :

Code: [Selecteer]

test.c:34: let op: format ‘%s’ expects type ‘char *’, but argument 2 has type ‘int’
Dit is lijn 34 :

Code: [Selecteer]

printf("%s",machinist->waarde);
Dit is de defininitie van struct node :

Code: [Selecteer]

struct node
 {
   char waarde;
   struct node *volgende;
 };
Dat is dus wat ik niet begrijp, het element waarde is gedefiniëerd als char, en toch klaagt hij dat argument 2 van lijn 34 een integer zou zijn.

Alvast bedankt.

[profoX]

Voor enkele karakters moet je %c gebruiken in plaats van %s in je format string

edit - om nog een beetje te verduidelijken:
de warning die je krijgt meldt dat er char* wordt verwacht (en niet char), dus een pointer naar characters, oftewel een C string
chars zijn in C achter de schermen eigenlijk van het numerieke type (integers van 1 byte), daarom klaagt hij dat je een int geeft terwijl een char* werd verwacht

[Joshua822]

Het probleem is dat ik wil dat tekenreeksen van meer dan één teken mogelijk zijn. Dus 125 moet bijvoorbeeld ook mogelijk zijn.

Is er nog een andere oplossing ? Of zal ik het moeten oplossen met een if statement dat kijkt of de tekenreeks numeriek is of niet en dan printf op de goede manier uitvoert ?

[profoX]

Als je getallen wil opslaan/weergeven, dan moet je ipv char een ander numeriek type, zoals int gebruiken.
Die lees je dan in met
scanf("%d", &machinist->waarde);
en die weergeef je met
printf("%d\n", machinist->waarde);

als je hele willekeurige strings wil opslaan, dan heb je 2 mogelijkheden:
- de makkelijke mogelijkheid die meer geheugen in beslag neemt en een limiet legt op het aantal in te voeren karakters, namelijk door een character array te declareren ipv 1 enkel character van bijvoorbeeld 100 karakters; elke "machinist" zal dan echter (op een doorsnee 32bit systeem) 104 bytes groot zijn (100 bytes voor de karakters + pointer naar volgende van 4 bytes)
- de moeilijkere manier - maar veel optimaler - is om een C string op te slaan en telkens de nodige grootte te alloceren voor elke string - op een doorsnee 32bit systeem zal dit per "machinist" (8 + aantal karakters) bytes geheugen in beslag nemen

kanttekening: strings in low-level C zijn een groot pijnpunt; meestal maakt men gebruik van extra libraries (of in geval van C++ van de STL) om hier omheen te werken...

[profoX]

Misschien kan dit nuttig zijn indien je volledige strings wil inlezen in C:

voor een project dat puur in C geschreven moest worden moest ik ook strings inlezen, in plaats van gebruik te maken van een buffer wou ik een veiliger (geen buffer overflow mogelijk) en optimaler (minder geheugengebruik nodig) systeem implementeren, en toen heb ik deze functies geschreven:

Code: [Selecteer]

/* Verwijdert de newline achteraan een string
   -> Geeft de string terug, zonder newline achteraan */
char *chomp(char *str)
{
    int length = strlen(str);
    if (length > 0 && str[length - 1] == '\n')
        str[length - 1] = '\0';
    return str;
}

/* Een lijn van eender welke lengte inlezen van stdin
   -> Geeft een dynamisch gealloceerde string terug
   OPMERKING: Hetgeen deze functie teruggeeft moet na gebruik gedealloceerd worden d.m.v. free() ! */
char *getLine()
{
    int length, count = 0;
    char buffer[100];
    char *out = NULL;

    do {
        fgets(buffer, 100, stdin);
        length = strlen(buffer);
        out = (char *)realloc(out, (count + 1) * 99 + 1);
        strcpy(&out[count * 99], buffer);
        ++count;
    } while (length > 0 && buffer[length - 1] != '\n');

    chomp(out);
    return out;
}
Misschien heb je er wat aan... voorbeeldgebruik:

Code: [Selecteer]

printf("Wat wil je zeggen? ");
char *cstring = getLine();
printf("Je zei: %s\n", cstring);
free(cstring);

[Joshua822]

Ja, ik zal hier eens naar kijken.

Maar ik begrijp iets niet, de functie fgets haalt toch een lijn uit een bestand 

[profoX]

Eigenlijk van een stream en niet van een bestand. En stdin is de standaard stream voor input (via console)
http://www.cplusplus.com/reference/clibrary/cstdio/fgets/

Aangezien gets() een zeer gevaarlijke/onveilige functie is maak ik gebruik van fgets(buffer, length, stdin) om maar max. 100 karakters per keer uit de buffer te lezen

zie ook:
http://www.cplusplus.com/reference/clibrary/cstdio/gets/
meer bepaald:

Notice that gets does not behave exactly as fgets does with stdin as argument: First, the ending newline character is not included with gets while with fgets it is. And second, gets does not let you specify a limit on how many characters are to be read, so you must be careful with the size of the array pointed by str to avoid buffer overflows.

[Joshua822]

Oké, nog een vraagje, soms doe je iets als dit :

Code: [Selecteer]

str[length - 1] == '\n')
Wat wil dit zeggen ?

[profoX]

Ik heb die code die ik heb gepost nog eens herlezen, en eigenlijk is die helemaal niet zo optimaal
ik heb even een herziene functie geschreven die zo optimaal mogelijk omspringt met het geheugen:

Code: [Selecteer]

/* Een lijn van eender welke lengte inlezen van stdin
   -> Geeft een dynamisch gealloceerde string terug
   OPMERKING: Hetgeen deze functie teruggeeft moet na gebruik gedealloceerd worden d.m.v. free() ! */
char *getLine()
{
    int length, count = 0;
    char buffer[100] = {0};
    char *out = NULL;
    int finished = 0;
    
    do {
        fgets(buffer, 100, stdin);
        length = strlen(buffer);
        if (length > 0 && buffer[length - 1] == '\n') {
            buffer[length - 1] = '\0';
            --length;
            finished = 1;
        }
        out = (char *)realloc(out, count * 99 + length + 1);
        strcpy(&out[count * 99], buffer);
        ++count;
    } while (!finished);

    return out;
}
if (length > 0 && buffer[length - 1] == '\n') controleert of het laatste karakter in de buffer het newline-teken is, wat zou betekenen dat het stuk in de huidige buffer het einde van de ingevoerde regel bevat