Discussion :

[Kadiatou]

Bonjour , je suis nouvelle dans ce forum. Je ne suis pas trés bonne programmeuse donc j'aurai besoin d'aide. Je dois présenter un tri par fusion externe en C qui lit des listes et qui utilisent en meme tps une structure de file fifo( avec des chaines de caractères ). je ne sais pas par ou commencer et j'aurai vraiment besoin d'aide. Merci!!

[ternel]

Montre nous de quoi tu pars:
Comment fais-tu tes listes?
Sais-tu quelle est la logique d'une file?

Nous pourrons te guider, corriger des erreurs, et répondre à tes questions.

Mais nous ne donnons pas de solution toute faite, parce que soit elle ne correspond pas au besoin spécifique, soit ca détruit l'intérêt même de l'exercice (si c'en est un)

[Kadiatou]

J'ai déja fait le code pour le file fifo a base de liste chainées:
Voici le fichier file.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*
 * MODULE file : file.h
 *
 * Description
 *   le file.h est un module presentant des files chainées
 *en utilisant des listes chainées.
 *
 *
 * Type file
 *   La structure contient deux pointeurs : le premier pointe sur
 *   le premier element de la file, le dernier pointe sur le dernier.
 *   On represente chaque element de la file par une structure
 *   Cela facilite les ajouts. Chaque element de la file est represente
 *   par une structure cellule comportant deux champs : la valeur de
 *   l'element obj et un pointeur sur l'element suivant.
 */
 #include<stdio.h>
 #include<stdlib.h>
#ifndef FILE_H
#define FILE_H
typedef int element;
typedef struct cellule
        {
  element valeur;
  struct cellule *suivant;
} cellule;
 
typedef struct {
  cellule *tete;
  cellule *queue;
 } file;
 void file_vide(file *f);
 int file_est_vide(file *f);
 file enfiler(file *f, element e);
 file defiler(file *f);
 element sommet(file *f);
 void AfficherFile(file *f);
 void Detruire(file *f);
 
 /* PROCEDURE : file_vide()
 * PARAMETRES :
 * DESCRIPTION
 *  On fait vider la file de son contenu.
 *  Les champs premier(tete) et dernier(queue) sont initialise
 *  a NULL
 * PRECONDITIONS
 */
 /* PROCEDURE : creer
 * PARAMATRE :
 * DESCRIPTIF
 * Dans le cas de la liste chaine on se contente de faire appel
 * a la fonction initialser.
void Initialiser(TFile *file);
 */
#define creer(f) file_vide()
 
/* PROCEDURE : file_est_vide.
 * PARAMATRE :
 * 1) resultat file f.
 * DESCRIPTIF :
 * On fait un test. On teste si la file
 * est vide, si oui on return 1(vrai), sinon
 * on retourne 0 (faux).
 *PRECONDTION
 */
 int file_est_vide(file *f);
 /* PROCEDURE : enfiler
  * PARAMETRE : file f, element e
  * DESCRIPTIF :
  * On ajoute a la file courante un nouveau
  * element. On l'ajoute en tete de la file.
  * PRECONDITION
  * Il est necessaire de faire un teste pour
  * verifier la validite de la file: c'est a dire
  * si on a de la memoire ou pas.
  */
file enfiler(file *f, element e);
 
/* PROCEDURE : defiler
 * PARAMETRES :
 *  1) resultat file f;
 *  2) resultat cellule e.
 * DESCRIPTION
 *  La valeur de l'element en debut de liste
 *  est place dans le parametre p. le premier
 *  element est supprime
 *  et la liste mise a jour
 * PRECONDITION
 *  file doit correspondre a une file valide
 *  et non vide
 *
 */
file defiler(file *f);
 
/* PROCEDURE : Afficher
 * PARAMETRES :
 *  1) resultat file *f
 * DESCRIPTION
 *  Affiche a l'ecran le contenu de la file
 * PRECONDITIONS
 *  la file doit etre valide
 */
void AfficherFile(file *f);
 
/* FONCTION : Sommet
 * PARAMETRES :
 *  1) resultat file *f
 * RETOUR : element
 * DESCRIPTION
 *  retourne la valeur du premier reel de la
 *  liste.
 *  La liste n'est pas modifiee
 * PRECONDITIONS
 *  file doit etre valide et non vide
 */
element sommet(file *f);
 
/* PROCEDURE : Detruire
 * PARAMETRES :
 *  1) resultat file *f
 * DESCRIPTION
 *  Detruit la file fournie en parametre.
 *  La memoire occupee par les elements de
 *  la liste est recuperee
 * On remit a niveau la file.
 * PRECONDITIONS
 *  la file doit etre valide
 */
void Detruire(file *f);
 
#endif

Et voici le le fichier file.c:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
/*
 * MODULE file : file.c ... lie a une implementation
 *               d'une file sous forme d'une liste chainee
 */
 
#include <stdio.h>
#include <stdlib.h>
 
#include "file.h"
 
 void file_vide(file *f)
{
  f->tete=f->queue= NULL;
}
 
int file_est_vide(file *f)
{
if((f->tete==f->queue) && (f->queue=NULL))
return 1;
else return 0;
}
 
file enfiler (file *f, element e) {
  cellule *c;
  c = (cellule*) malloc(sizeof(cellule));
  if (c == NULL) {
    printf("erreur allocation memoire\n");
  }
  else {
    c->valeur=e;
    c->suivant = NULL;
    if (file_est_vide(f))
    f->tete=f->queue=c;
    else f->queue->suivant = c;
    f->queue = f->queue->suivant;
  }
}
 
file defiler(file *f)
{
    if(file_est_vide(f))
    printf("la file est vide");
    else
    {
        if((f->tete)==(f->queue))
         f=file_vide();
         else
        {
            cellule *p;
            p=f->tete;
            f->tete=(f->tete)->suivant;
            free(p);
            return f;
        }
    }
}
 
element sommet(file *f)
{
    return f->tete->valeur;
}
 
void AfficherFile (file *f)
 {
  element *c;
  int pos;
  printf("file: ");
  pos=0;
  for (c=f->tete; c!=NULL; c=c->suiv) {
    printf("%.2f ", c->valeur);
    pos++;
  }
  printf("\n");
}
 
void Detruire (file *f)
 {
  element *c, *p;
  c = f->tete;
  while (c != NULL) {
    p = c;
    c = c->suiv;
    free(p);
  }
  f->tete = NULL;
  f->queue = NULL;
}

Donc je dois implanter cette structure dans mon tri. Il y'a beaucoup d'erreurs aussi dans les deux codes.

[ternel]

Ton en tete déclare toutes les fonctions deux fois, ce n'est pas utile, et potentiellement une source d'erreur.

D'un point de vue conception, tu as choisis la file (que j'appelle) observable, c'est-à-dire: avec une fonction sommet(), et un defiler() qui retourne la file.
Il existe une autre version, la file (que j'appelle) "aveugle": pas de sommet(), mais un defiler() qui renvoie la valeur au sommet.

Du point de vue implémentation, ta fonction file-vide est dangereuse, parce qu'elle perd l'information de la file (tant mieux), mais ne la détruit pas, ce qui peut/va produire des erreurs de segmentations (en anglais: segfault(s) )
Si sa vocation est de créer une file, il vaudrait mieux ne pas l'avoir en argument, allouer la mémoire dans la fonction, et la retourner.

D'une manière générale, il faut faire très attention à tous les états possibles dans les fonctions: file vide, file à un élément, file longue, non-file (argument null)

Essaye d'être résistante à l'utilisateur. par exemple, ta fonction sommet() devrait tester si la file existe, et si elle n'est pas vide.