C Vector/ArrayList/LinkedList

Ik doe een klein programma in C en ik heb een soort vector/ArrayList/LinkedList nodig, maar ik werk met C. Enig idee hoe ik dat soort dingen in C kan doen?

Ik wil structs opslaan en er enkele toevoegen/verwijderen.

Antwoord 1, autoriteit 100%

Voor aanpasbare arrays kun je malloc()en realloc()gebruiken. Hiermee kunt u een bepaalde hoeveelheid ruimte op de heap reserveren (met malloc()) en de grootte wijzigen (met realloc()). Ze worden op deze manier gebruikt:

int* a = malloc(10 * sizeof(int));
if(a == NULL) {}     // malloc() was unable to allocate the memory, handle the
                     // error and DO NOT use this pointer anymore
// now you can treat a as a normal array of 10 ints:
a[4] = 51;
// suppose 10 ints aren't no more enough:
a = realloc(a, 20 * sizeof(int));
if(a == NULL) {}     // same thing as before
// here you have 20 ints, the previous 10 are still there
a[18] = a[4]
// don't forget to free the memory when you have finished:
free(a);

Vervang ‘int’ gewoon door je struct-type. 😉

Antwoord 2, autoriteit 86%

Gebruik een bestaande implementatie. Er zijn miljarden. Glibis waarschijnlijk een goede plek om te beginnen, of LibH.

Antwoord 3, autoriteit 57%

Ik heb het antwoord van @conrad meyer gebruikt. Downloaded Laatste glib bibliotheek van hier en samengesteld met Deze handleiding. Glib-bibliotheken testen die ik dit test. Mogelijk hebt u fouten tijdens het compileren van de testcode. Dit helpt u om uw probleem op te lossen.

Ik heb ook gevonden dat er een soort geheugenlek in de testcode is. Valgrind Resultaat met het uitvoeren van de originele code:

==20350== HEAP SUMMARY:
==20350==     in use at exit: 4,632 bytes in 12 blocks
==20350==   total heap usage: 12 allocs, 0 frees, 4,632 bytes allocated
==20350== 
==20350== LEAK SUMMARY:
==20350==    definitely lost: 0 bytes in 0 blocks
==20350==    indirectly lost: 0 bytes in 0 blocks
==20350==      possibly lost: 992 bytes in 4 blocks
==20350==    still reachable: 3,640 bytes in 8 blocks
==20350==         suppressed: 0 bytes in 0 blocks

Dus heb ik één regel in de code ingevoegd:

#include <stdio.h>
#include <glib.h>
int main(int argc, char** argv) {
    GList* list = NULL;
    list = g_list_append(list, "Hello world!");
    printf("The first item is '%s'\n", (char *)g_list_first(list)->data);
    g_list_free(list);
    return 0;
}

VALGINEN Nieuwe resultaten:

==20310== HEAP SUMMARY:
==20310==     in use at exit: 4,632 bytes in 12 blocks
==20310==   total heap usage: 12 allocs, 0 frees, 4,632 bytes allocated
==20310== 
==20310== LEAK SUMMARY:
==20310==    definitely lost: 0 bytes in 0 blocks
==20310==    indirectly lost: 0 bytes in 0 blocks
==20310==      possibly lost: 0 bytes in 0 blocks
==20310==    still reachable: 4,632 bytes in 12 blocks
==20310==         suppressed: 0 bytes in 0 blocks

Ditantwoord vertelt dat u zich geen zorgen hoeft te maken over still reachablegeheugen.

Antwoord 4, autoriteit 29%

C wordt niet geleverd met enige vorm van een standaardverzameling (in tegenstelling tot talen op een hoger niveau zoals C++ en Java), dus je hebt een paar opties:

1. Gebruik een bestaande gemaakt door een groep/een individu (zoals hierboven vermeld)
2. Maak je eigen

Je moet precies bedenken wat je voor dit programma nodig hebt om te bepalen wat je gebruikt. Van wat je vraagt, ben je waarschijnlijk op zoek naar een van de twee opties:

1. Een array die dynamisch groeit wanneer je hebt toegewezen. In wezen moet u bijhouden hoeveel elementen zich op dat moment in uw array bevinden. Als u op enig moment tijdens het invoegen het maximale aantal elementen overschrijdt, moet u een nieuwe array maken, de elementen naar de nieuwe array kopiëren, het nieuwe element invoegen en tenslotte de oude array verwijderen. Dit is meestal sneller in termen van toegangstijd (omdat het indexeerbaar is), maar traag en geheugenverslindend als u te veel toewijst. Zie BlackBear’s code voor een voorbeeld.
2. Een gekoppelde lijst die dynamisch groeit door ontwerp. Zie hier: http://en.wikipedia.org/wiki/ Linked_list#Singly-.2C_doubly-.2C_and_multiply-linked_lists. Dit heeft als belangrijkste voordeel geen extra onderhoud in het speciale geval, maar het nadeel van langzame toegang (kijk naar elk element totdat u het gewenste element vindt).

Zie de Wikipedia-pagina voor meer informatie over afwegingen tussen de twee soorten gegevensstructuren.