Les Piles / Files

Version imprimable

Les Piles / Files

Bonsoir,
les piles/files marche bien comme sa pour savoir si j'ai bien assimilé (les piles/files -> ajout/suppression d'un élément,sommet de pile/file)

PILES Last In First out

Tableau statique: (ajout/suppression en fin de tableau)

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
 
#include<stdio.h>
#include<stdlib.h>
#define MAX 50
typedef struct pile{
  int taille;
  int tab[MAX];
}pile;
 
void init(pile *p){
  p->taille=0;
}
 
void push(pile *p,int val){
  if(p->taille!=MAX){
    p->tab[p->taille]=val;
    p->taille++;
  }
}
 
void pop(pile *p) {
  if(p->taille==0)
    return;
  p->taille--;
}
 
void affiche(pile p){
  int i;
  for(i=0;i<p.taille;i++)
    printf("%d\n",p.tab[i]);
}
int top(pile p){
  return p.tab[p.taille];
}
 
int main(void){
  pile p;
  init(&p);
  push(&p,5);
  push(&p,6);
  affiche(p);
  printf("REMOVE\n");
  pop(&p);
  affiche(p);
  printf("top=%d\n",top(p));
  return 0;
}

Tableau dynamique

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
 
#include<stdio.h>
#include<stdlib.h>
typedef struct pile{
  int taille;
  int *tab;
}pile;
 
void init(pile *p){
  p->taille=0;
  p->tab=NULL;
}
 
void push(pile *p,int val){
  p->tab=realloc(p->tab,sizeof(int *)*(p->taille+1));
  p->tab[p->taille]=val;
  p->taille++;
 
}
 
void pop(pile *p) {
  if(p->taille==0)
    return;
  p->taille--;
}
 
void affiche(pile p){
  int i;
  for(i=0;i<p.taille;i++)
    printf("%d\n",p.tab[i]);
}
int top(pile p){
  return p.tab[p.taille];
}
 
int main(void){
  pile p;
  init(&p);
  push(&p,5);
  push(&p,6);
  affiche(p);
  printf("REMOVE\n");
  pop(&p);
  affiche(p);
  printf("top=%d\n",top(p));
  return 0;
}

liste chaînée: (ajout/suppression au début de la liste chaînée)

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
 
#include<stdio.h>
#include<stdlib.h>
typedef struct _pile{
  int Elt;
  struct _pile *suivant;
}pile;
 
void init(pile **p){
  *p=NULL;
}
 
void push(pile **p,int val){
  pile *p2;
  p2=malloc(sizeof(pile));
  p2->Elt=val;
  p2->suivant=*p;
  *p=p2;
}
 
void pop(pile **p){
  pile *p2;
  p2=*p;
  *p=(*p)->suivant;
  free(p2);
}
 
int top(pile *p){
  if(p==NULL) printf("erreur, pile vide");
  else{
    if(p->suivant==NULL)
      return p->Elt;
    while(p->suivant!=NULL){
      p=p->suivant;
    }
    return p->Elt;
  }
}
 
void affiche(pile *p){
  while(p!=NULL){
    printf("%d\n",p->Elt);
    p=p->suivant;
  }
}
 
int main(void){
  pile *p;
  init(&p);
  push(&p,5);
  push(&p,3);
  affiche(p);
  printf("top=%d\n",top(p));
  pop(&p);
  affiche(p);
  return 0;
}

Les FILES First In First Out
tableau statique: (ajout fin de tableau, supréssion début de tableau)

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
 
#include<stdio.h>
#include<stdlib.h>
#define MAX 50
typedef struct file{
  int taille;
  int tab[MAX];
}file;
 
void init(pile *p){
  p->taille=0;
}
 
void push(file *p,int val){
  if(p->taille!=MAX){
    p->tab[p->taille]=val;
    p->taille++;
  }
}
 
void pop(file *p) {
  int i;
  if(p->taille==0)
    return;
  for(i=0;i<(p->taille -1);i++){
    p->tab[i]=p->tab[i+1];
  }
  p->taille--; 
}
 
void affiche(file p){
  int i;
  for(i=0;i<p.taille;i++)
    printf("%d\n",p.tab[i]);
}
int top(file p){
  return p.tab[p.taille];
}
 
int main(void){
  file p;
  init(&p);
  push(&p,5);
  push(&p,6);
  affiche(p);
  printf("REMOVE\n");
  pop(&p);
  affiche(p);
  printf("top=%d\n",top(p));
  return 0;
}

tableau dynamique:

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
 
#include<stdio.h>
#include<stdlib.h>
typedef struct File{
  int taille;
  int *tab;
}file;
 
void init(file *p){
  p->taille=0;
  p->tab=NULL;
}
 
void push(file *p,int val){
  p->tab=realloc(p->tab,sizeof(int *)*(p->taille+1));
  p->tab[p->taille]=val;
  p->taille++;
}
 
void pop(file *p) {
  int i;
  if(p->taille==0)
    return;
  for(i=0;i<(p->taille -1);i++){
    p->tab[i]=p->tab[i+1];
  }
  p->taille--; 
}
 
void affiche(file p){
  int i;
  for(i=0;i<p.taille;i++)
    printf("%d\n",p.tab[i]);
}
int top(file p){
  return p.tab[p.taille];
}
 
int main(void){
  file p;
  init(&p);
  push(&p,5);
  push(&p,6);
  affiche(p);
  printf("REMOVE\n");
  pop(&p);
  affiche(p);
  printf("top=%d\n",top(p));
  return 0;
}

liste chaînée: (ajout au début de la liste, supréssion à la fin de la liste)

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
 
#include<stdlib.h>
#include<stdio.h>
typedef struct _file{
  int Elt;
  struct _file *suivant;
}file;
 
void init(file **p){
  *p=NULL;
}
 
void push(file **p,int val){
  file *p2=malloc(sizeof(file));
  p2->Elt=val;
  p2->suivant=*p;
  *p=p2;
}
 
void pop(file **p){
  if(*p==NULL)
    return;
  if((*p)->suivant==NULL)
    free(*p);
  file *p2=*p;
  file *p3=(*p)->suivant;
  while(p3->suivant!=NULL){
    p2=p2->suivant;
    p3=p3->suivant;
  }
  p2->suivant=p3->suivant;
  free(p3);   
}
 
int top(file *p){
  if(p==NULL) printf("erreur, pile vide");
  else{
    if(p->suivant==NULL)
      return p->Elt;
    while(p->suivant!=NULL){
      p=p->suivant;
    }
    return p->Elt;
  }
}
 
void affiche(file *p){
  while(p!=NULL){
    printf("%d\n",p->Elt);
    p=p->suivant;
  }
}
int main(void){
  file *p;
  init(&p);
  push(&p,5);
  push(&p,3);
  affiche(p);
  printf("top=%d\n",top(p));
  pop(&p);
  printf("REMOVE\n");
  affiche(p);
  return 0;
}

Merci d'avance pour votre aide.

08/12/2008, 00h44
elmcherqui

8O8O c'est moi qui suis aveugle ou y'a pas de question ?? 8O8O
il est ou le probleme ?
08/12/2008, 02h12
LittleWhite

Je suis un peu près comme elmcherqui... Y a pas de questions il me semble.

De plus tu demande de voir si ton programme marche correctement ... ( pour savoir si tu as bien compris les Piles / Files )
Serieux , je pense que personne ne va lire le programme enitèrement ligne par ligne pour savoir si ça marche.
L'informatique c'est pas théorique , c'est pratique ;) ... Donc tu vas compiler ton programme , et faire un main qui va tester plein de cas possible de ta Pile / File et afficher assez souvent les valeurs contenu dans tes structures de données pour savoir si tes fonctions font ce que tu attends.
Normalement ton main , va testé le cas d'ajout de données , le cas de suppression de données , le cas de dépassement de mémoire , le cas ou on essaie d'enlever une donnée lorsque qu'il y en a pas ... et tu affiche souvent de façon à savoir si les données sont modifiés comme tu veux.

Par contre si tu as un problème , et que ton programme ne fais pas ce que tu veux , tu peux poser pleins de questions , et y aura toujours quelqu'un pour répondre.

Finalement :

( la pile en statique semble OK )
( la fonction "init()" de la pile en dynamique me semble fausse , il faut que tu faisse un truc du genre p->tab = malloc( sizeof(int * MAX ) ) ( n'oublie pas de définir un MAX , si tu ne le fais pas ton tableau n'est pas près à recevoir des éléments )
Euh excuse , j'avais pas vu que tu utilisais un realloc , mais bon je trouve que c'est couteux en temps machine ... si je me rapelle bien chaque appel système de base et couteux , et appeler realloc souvent peut devenir très couteux ... )
( par contre , tu peux faire une première allocation à 10 éléments , et après une fois que tu as atteint 10 tu double la taille ... comme ça tu fais moi d'appel système ;) )
Et je crois qu'il manque la destruction du tableau d'éléments à la fin du programme ( soit fuite de mémoire )
Rajoute une fonction du genre destruction , qui fait un free sur ton tableau , cette fonction tu l'appelera à la fin de ton main ... juste avant le return.

Pour la File en statique , me semble juste , par contre , décalé les valeurs à chaque fois peut être lourd , donc je te conseille de te pencher sur un truc que l'on apelle le tableau circulaire . ( Ou au sinon tu implémente un élément start , qui est incrémenter à chaque fois que tu enlève un élément )

Même remarque pour les Files en dynamique ( remarque à propos de la lourdeur du décalage , et la lourdeur des appels systèmes )

Euh , pardon mais je lirai pas le code des listes chainées ( il faut avoir une bonne représentation en mémoire , et ne pas se perdre ( ou prendre une feuille ). Donc sérieusement suis la chose que j'ai dit , du compile tu teste, ça plante tu débugue , et tu reteste ... Faut pas croire que l'on est capable de lire des codes comme ça et de savoir si ça marche... ( enfin pas moi )

mais tu remarquera que j'ai dit semble ... car je ne suis pas un compilateur , ni une machine , et que je fais des erreurs.
08/12/2008, 09h34
Delnir

Euh oui désolé, j'ai oublié les questions à la fin concernant les files :oops:
Mais bon tu a répondu à mes questions merci :)
(Sinon une fois compilé tous marche)