Arraylist in C ne fonctionne pas

Question

Je suis en train d'écrire un programme pour mettre en œuvre un arraylist (ou tableau dynamique) en C. Hmm ... Je pense que j'ai 70-80% fait avec, cependant, j'ai trouvé un sérieux problème avec mon code en les testant sur un couple de machines. En résumé, j'ai inséré un groupe de chaînes (char *) dans mon arraylist, et j'ai essayé de les obtenir et de les afficher après des couples d'opérations. Cependant, ce que je suis:

CHECK: 1 
CHECK: 2 
CHECK: ܗ¿èۗ¿ 
CHECK: EàEàHAÿE؉Ⱥ 
CHECK: 5 
CHECK: 6 

Malheureusement, je ne peux toujours pas savoir où le problème est dans mes codes, même si je l'ai revu deux fois mes codes.

arraylist.h

#ifndef _ARRAYLIST_H 
#define _ARRAYLIST_H 

#include <stdio.h> 

typedef char* value_type; 

struct arraylist { 
    int size; 
    value_type* data; 
}; 

extern void arraylist_initial(struct arraylist *list); 
extern int arraylist_get_size(const struct arraylist list); 
extern value_type* arraylist_get_data_collection(const struct arraylist list); 
extern void arraylist_set_data_collection(struct arraylist *list, value_type* data); 
extern void arraylist_add(struct arraylist *list, value_type value); 
extern value_type arraylist_get(const struct arraylist list, int index); 
extern int arraylist_indexof(const struct arraylist list, value_type value); 

#endif 

arraylist.c

#include "arraylist.h" 

void arraylist_initial(struct arraylist *list) { 
    list->size = 0; 
    list->data = NULL; 
} 

int arraylist_get_size(const struct arraylist list) { 
    return list.size; 
} 

value_type* arraylist_get_data_collection(const struct arraylist list) { 
    return list.data; 
} 

void arraylist_set_data_collection(struct arraylist *list, value_type* data) { 
    list->data = data; 
} 

void arraylist_add(struct arraylist *list, value_type value) { 
    int size = arraylist_get_size(*list); 
    value_type new_data[size + 1]; 

    int index = 0; 
    for(; index != size; ++index) { 
    new_data[index] = arraylist_get(*list, index); 
    } 
    new_data[index] = value; 

    arraylist_set_data_collection(list, new_data); 

    ++list->size; 
} 

value_type arraylist_get(const struct arraylist list, int index) { 
    if(index < arraylist_get_size(list)) { 
    return list.data[index]; 
    } 
    else { 
    return NULL; 
    } 
} 

int arraylist_indexof(const struct arraylist list, value_type value) { 
    int index = 0; 
    for(; index != arraylist_get_size(list); ++index) { 
    if(strcmp(list.data[index], value) == 0) { 
     return index; 
    } 
    } 

    return -1; 
} 

int main(void){ 
    struct arraylist list; 

    arraylist_initial(&list); 

    arraylist_add(&list, "1"); 
    arraylist_add(&list, "2"); 
    arraylist_add(&list, "3"); 
    arraylist_add(&list, "4"); 
    arraylist_add(&list, "5"); 
    arraylist_add(&list, "6"); 

    int index = 0; 
    for(; index != 6; ++index) { 
    printf("CHECK: %s\n", arraylist_get(list, index)); 
    } 

    return 0; 
} 

Answer 1

Comme d'autres l'ont noté, le problème est dans la fonction arraylist_add(), qui doit allouer dynamiquement de la mémoire. Ce problème est en fait parfaitement adapté pour realloc(), qui élargira le tableau alloué dynamiquement (ce qui signifie que vous ne devez pas faire la boucle de copie):

void arraylist_add(struct arraylist *list, value_type value) { 
    int size = arraylist_get_size(*list); 
    value_type *new_data; 

    new_data = realloc(list->data, (size + 1) * sizeof new_data[0]); 

    if (new_data) 
    { 
     new_data[size] = value; 
     arraylist_set_data_collection(list, new_data); 
     ++list->size; 
    } 
} 

Cela même travailler pour la première répartition, puisque realloc() fonctionne comme malloc() si vous lui transmettez un NULL.

PS:

Pour rendre la mise en œuvre plus efficace, vous ne devriez pas étendre le tableau par une entrée à chaque fois - au lieu, garder une trace du nombre de blocs alloués séparément du nombre d'entrées.

Answer 2

Dans la méthode arraylist_add vous stockez l'adresse d'une variable locale new_data dans la liste. Cette variable sera détruite dès que le contrôle sortira de la fonction. Par conséquent, vous avez des pointeurs invalides qui, lorsqu'ils sont supprimés, invoquent un comportement indéfini. Pour résoudre ce problème, vous devez allouer de la mémoire pour la chaîne de tas en utilisant malloc, c'est-à-dire que vous devez faire quelque chose comme value_type* new_data = (value_type*)malloc((size + 1) * sizeof(value_type));. Souvenez-vous également que vous devez libérer cette mémoire en utilisant free.

Answer 3

À première vue: dans arraylist_add, vous déclarez new_data en tant que variable locale. Lorsque vous passez cela à arraylist_set_data_collection, il passe le pointeur sur cette donnée. Cependant, une fois que arraylist_add retourne à main, new_data est hors de portée, et n'est donc plus valide. Pensez à effectuer une copie en profondeur et à gérer la mémoire manuellement avec malloc et gratuitement.

Answer 4

La racine de votre problème est ici:

void arraylist_add(struct arraylist *list, value_type value) { 
    int size = arraylist_get_size(*list); 
    value_type new_data[size + 1]; 
    ... 
    arraylist_set_data_collection(list, new_data); 
    ... 
    ++list->size; 
} 

new_data est déclaré sur la pile. Il n'est plus sûr d'utiliser cette mémoire après le retour de l'appel. Vous devez allouer de l'espace pour les données avec malloc, par ex.