Piles et tableaux dynamiques

Bonjour,

Je veux créer une pile qui est en fait une structure avec une liste chaînée et l'indice de tête de la pile et la taille de la pile, j'ai donc créé la structure suivante:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

typedef struct maillon *LIST; typedef struct maillon{ LIST next; void* data; };   typedef struct{ LIST pile; int* taille; int* haut; }STACK2;

---

Je voulais ensuite créer les fonctions qui initialise une pile, qui détruit une pile, qui test si une pile est vide, qui ajoute un élément et qui enlève un élément à une pile. Pas de problèmes à la compilation, mais cela plante à l'éxécution et je ne comprend pas pourquoi. J'ai utilisé les même fonctions que pour les listes chaînées mais appliquée au champ "pile" de ma pile. Quelqu'un pourrait m'éclairer ?:?

Ca serait mieux si tu nous montrais tes fonctions mais déjà tu devrais mettre normalement int taille et int haut au lieu de int * taille et int * haut. En fait, size_t c'est encore mieux que int.

En faite j'ai mis des int* car je pensais que ça permettrait de les modifier mais après réflexion je suis plus sur de mon coup, d'autant plus que quelque chose me tracasse, je dois mettre la taille dans ma structure alors que l'intêret de cette structure est qu'on peut y mettre autant d'éléments que l'on veut il me semble...

Voilà le code de mes fonctions:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

STACK2 new_stack2 () { STACK2 p; (p.pile)->next = NULL; p.taille = 50; p.haut = -1; return p; }   void delete_list ( LIST l ) { while( l->next != NULL ) { delete_list(l->next); free(l); } }   void delete_stack2 ( STACK2 p ) { delete_list ( p.pile ); free( p.haut ); free( p.taille); }   int is_empty2 ( STACK2 p ) { if(p.pile == NULL ) return 1; else return 0; }   STACK2 push2 ( STACK2 p , void* d ) { STACK2 p2; LIST l; l = malloc(sizeof(struct maillon)); l->data = d; l->next = p.pile; p2.pile = l; p2.haut = p.haut; p2.taille = p.taille; return p2; }   STACK2 pop2 ( STACK2 p ) { if( is_empty2( p )) return p; else { STACK2 p2; p2.pile = (p.pile)->next; free( (p.pile)->data ); p2.haut = p.haut -1; p2.taille = p.taille; return p2; } }

---

Code:

---

typedef struct maillon *LIST;

---

C'est une mauvaise idée de cacher dans un typedef que le type est un type adresse

Code:

---

1 2 3 4 5 6 7 8 9 10

typedef struct maillon{ struct maillon * next; void* data; } Maillon;   typedef struct{ Maillon * pile; int taille; int haut; // A quoi sert ce champ ? }STACK2;

---

Code:

---

1 2 3 4 5 6 7 8

STACK2 new_stack2 () { STACK2 p; (p.pile)->next = NULL; // Ici, on va planter // p.pile vaut n'importe quoi et par conséquent (p.pile)->next est dans les décors // Pour indiquer que la pile est vide p.pile = NULL suffit. .... }

---

Code:

---

1 2 3 4 5 6 7 8

void delete_list ( LIST l ) { while( l->next != NULL ) { delete_list(l->next); free(l); } }

---

est mal foutu : soit tu optes pour une solution itérative, soit pour une solution récursive. Mais le mélange des deux ...

Code:

---

1 2 3 4 5 6 7 8

void delete_stack2 ( STACK2 p ) { delete_list ( p.pile ); free( p.haut );// On va planter ici free( p.taille); // et ici // p.haut et p.taille n'ont pas été initialisés par un malloc. // D'ailleurs, ce ne sont pas des adresses mais des entiers. }

---

Pour cette fonction, elle cherche à modifier des éléments de la structure utilisée pour représenter la pile. Il faut donc passer l'adresse de cette structure, sinon on ne va modifier que la copie locale :

Code:

---

1 2 3 4 5 6

void delete_stack2 ( STACK2 * p ) { delete_list ( p->pile ); p->pile = NULL ; .... }

---

On verra la suite plus tard

En faite je suis parti sur une autre structure et ça marche presque, il doit juste y avoir un problème avec ma fonction qui empile. Le code est le suivant:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

typedef struct STACK2{ void** data; int tete; int size; }STACK2;   STACK2* new_stack2 () { STACK2* p; p =(STACK2*)malloc(sizeof(STACK2) + sizeof(void*)); p->tete = -1; p->size = 0; return p; }   void delete_stack2 ( STACK2* p ) { free( p ); p->tete = -1; p->size = 0; }   int is_empty2 ( STACK2* p ) { if(p->tete == -1 ) return 1; else return 0; }   void push2( STACK2* p , void* d ) { p = (STACK2*)realloc(p,p->size + sizeof(void*));// on augmente la taille de l'espace disponible pour p de la taille de void* *(p->data+p->size) = d;// on fait pointé la zone de la pile encore inexploitée vers d p->tete++; p->size += sizeof(void*);// on augmente la taille de la pile de la taille de void* }   void pop2 ( STACK2* p ) { if( is_empty2( p )) return; else { p->size -=sizeof(void*); p->tete--; p = (STACK2*)realloc(p , p->size ); } }   void verif_stack2( STACK2* p ) { if( is_empty2( p ) ) { printf("la pile est vide"); return; } else { printf("size = %d\ntete = %d\n",p->size,p->tete); int i; for( i = 0 ; i <= p->size ; i++ ) { printf("p->data (%d) = %d\n",i,*(int*)*(p->data + i*sizeof(void*))); } printf("\n"); } }

---

Voilà je ne vois pas où ça plante :?

------------------

Code:

---

1 2 3 4 5 6 7 8

STACK2* new_stack2 () { STACK2* p; p =(STACK2*)malloc(sizeof(STACK2) + sizeof(void*)); p->tete = -1; p->size = 0; return p; }

---

- Il n'y a aucune raison d'ajouter sizeof(void*) à sizeof(STACK2).
- Il est inutile (et certains considèrent que c'est plutôt néfaste) de caster en C le retour de malloc.
- Il faut tester le retour de malloc pour vérifier que l'allocation a réussi.
On obtient :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

STACK2* new_stack2 (void) { STACK2* p; p = malloc(sizeof(STACK2)); if( p != NULL) { p->tete = -1; p->size = 0; p->data = NULL; } return p; }

---

------------------

Code:

---

1 2 3 4 5 6

void delete_stack2 ( STACK2* p ) { free( p ); p->tete = -1; p->size = 0; }

---

Une fois fait le free(p), on n'a plus le droit de faire p->... puisque la mémoire pointée cesse de nous être allouée. Il suffit de faire :

Code:

---

1 2 3 4

void delete_stack2 ( STACK2* p ) { free( p ); }

---

Par contre, on peut se demander que faire si la pile n'est pas vide lors de cette destruction puisqu'alors, les éléments de la pile ne sont plus accessibles et restent quelque part en mémoire. Plus proprement, il faudrait vider la pile avant de faire le free(p).

Code:

---

1 2 3 4 5

void delete_stack2 ( STACK2* p ) { free(p->data); // et dans cet ordre free( p ); }

---

------------------

Code:

---

1 2 3 4 5 6 7

void push2( STACK2* p , void* d ) { p = (STACK2*)realloc(p,p->size + sizeof(void*));// on augmente la taille de l'espace disponible pour p de la taille de void* *(p->data+p->size) = d;// on fait pointé la zone de la pile encore inexploitée vers d p->tete++; p->size += sizeof(void*);// on augmente la taille de la pile de la taille de void* }

---

- Est incorrect : Ce n'est pas le redimensionnemnt de STACK2 qu'il faut faire, sa taille est inchangée. Par contre, il faut redimensionner le tableau de void* qui pointent sur les données.
- De plus, il faut absolument tester le retour de realloc qui peut échouer.
- p->data+p->size est faux : Dans ton code, si je ne me trompe, p->size contient la taille en byte du tableau de pointeur void* . Si il y a n pointeur, il vaut n*sizeof(void*). Or p->data est un pointeur et c'est l'arithmétique des pointeurs qui s'applique : Si j'écris p->data+1 je rajoute à l'adresse (en bytes) non pas un byte mais 1*(taille de l'objet pointé) soit 1*sizeof(void*). En byte, p->data+p->size rajoute p->size*sizeof(void*) soit n*sizeof(void*)*sizeof(void*) !
Il vaut mieux que size stocke le nombe de pointeurs dans le tableau, pas la taille totale allouée au tableau de pointeurs (ce qui rend inutile le champ tete).
On aura alors plutôt quelque chose du genre :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

int push2( STACK2* p , void* d ) { void** q; q = realloc(p->data,(p->size+1)*sizeof(void*));// on augmente la taille de l'espace disponible pour p de la taille de void* if(q != NULL) { p->data = q; // parce que realloc peut changer le tableau de place p->data[p->size] = d;// on fait pointé la zone de la pile encore inexploitée vers d p->size ++; } return q != NULL ; // renvoie FAUX si le realloc (et le push)a échoué et VRAI si il a réussi }

---

On verra la suite plus tard après tes modifications