Discussion :

[gogo5]

Bonjour je suis en licence d'informatique et je dois faire un tri par tas en langage c. je n'y arrive pas je ne vois pas mon erreur. Pourriez vous m'aidez?

[WhiteCrow]

Bonjour,
il y a plusieurs problèmes dans ton code … tout d'abord sa présentation, il n'est pas très lisible, mais aussi ton implémentation qui n'est pas des plus classiques. On remarque rapidement que tu n'es pas à l'aise en C. Par exemple dans la fonction :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
void tri(Tas* t)
{
    Tas arbre= {{},10};
    Tas *p=&arbre;
    printf("%d taille arbre",arbre.len);
    for(int i=0; i<10; i++) {
        Ajout_elt(p,(*t).noeuds[i]);
    }
    for(int j=0; j<20; j++) {
        printf("nombre :%d\n",(*p).noeuds[j]);
    }
    t=p;
}

On voit que tu as peur des pointeurs. Une expression comme (*t).noeuds[i] est plus lisible en t->noeuds[i]. Ensuite il y a un gros problème : les variables locales comme arbre ont une durée de vie égale à celle de la fonction. Une fois sortie de la fonction elles n'existent plus. Tu fais pointer t vers une variable locale qui n'existera plus lorsque tu reviendra à l'appelant.

Il faut aussi écrire des fonctions … parce qu'on a du mal à comprendre ce que tu fais et pourquoi tu le fais,

Dans un heapsort classique on prend comme représentation d'arbre (du tas) une représentation simple, le nœud i a pour fils gauche le nœud 2*i+1 et comme fils droit le nœud 2*i+2 (quand on commence à indexer à partir de 0), il aura pour père le nœud (i-1)/2. Pour un tas de N nœuds, le dernier nœud qui n'est pas une feuille est le père du dernier ⇒ ((N-1)-1)/2 = N/2-1.
Tu dois écrire une fonction heapify qui crée/restaure la structure de tas. Dans un premier temps tu dois créer un tas max de tout ton tableau, puis échanger le max avec la dernière position de ton, décrémenter la taille du tas et recommencer …

Pour info, correctement indenté ton fichier devrait ressembler à quelque chose comme :

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
#include <stdio.h>
 
#define Taille 100
 
typedef struct {
    int noeuds[Taille];
    int len;
 
} Tas;
 
Tas* Ajout_elt( Tas* t,int noeud)
{
    (*t).len+=1;
    int l=(*t).len;
    (*t).noeuds[l-1]=noeud;
    int ex=(*t).noeuds[l-1];
    int i=l-1;
    while ((i!=0) &&((*t).noeuds[(i-1)/2]<(*t).noeuds[i])) {
 
        int temp=(*t).noeuds[(i-1)/2];
        printf("echange %d avec %d\n",(*t).noeuds[(i)],(*t).noeuds[(i-1)/2]);
        (*t).noeuds[(i-1)/2]=(*t).noeuds[i];
        (*t).noeuds[i]=temp;
        i=(i-1)/2;
 
    }
    return t;
}
 
void Supprimeracine(Tas* t)
{
    int temp=(*t).noeuds[0];//creer un tampon pour echanger le dernier et le premier
    (*t).noeuds[0]=(*t).noeuds[(*t).len -1];
    (*t).noeuds[(*t).len -1]=temp;
    (*t).len-=1;//modifie la len a -1 pour enterrer la racine
    int i=0;
    while ((i!=(*t).len-1)&&((*t).noeuds[(i+1)*2]>(*t).noeuds[i])&&((*t).noeuds[(i)*2+2]>(*t).noeuds[i])) {
        printf("i=%d \n",i);
        if(((*t).noeuds[(i)*2+2])>((*t).noeuds[(i)*2+1])) { //on regarde lequelle de ses fils est le plus grands.
            printf("%d plus grand que %d",(*t).noeuds[(i)*2+2],(*t).noeuds[(i)*2+1]);
            temp=(*t).noeuds[(i)*2+2];
            (*t).noeuds[(i)*2+2]=(*t).noeuds[(i)];
            (*t).noeuds[(i)]=temp;
            i=(i)*2+2;
        } else {
            temp=(*t).noeuds[(i)*2+1];
            (*t).noeuds[(i)*2+1]=(*t).noeuds[(i)];
            (*t).noeuds[(i)]=temp;
            i=(i)*2+1;
 
        }
    }
}
 
void tri(Tas* t)
{
    Tas arbre= {{},10};
    Tas *p=&arbre;
    printf("%d taille arbre",arbre.len);
    for(int i=0; i<10; i++) {
        Ajout_elt(p,(*t).noeuds[i]);
    }
    for(int j=0; j<20; j++) {
        printf("nombre :%d\n",(*p).noeuds[j]);
    }
    t=p;
}
 
void print(int t, int *p)
{
    for(int i=0; i<t; i++) {
        printf("%d\n",*p);
        p+=1;
    }
}
 
int  main(void)
{
    // Tas arbre={{18,14,-3,-5,-2,-4},6};
    Tas arbre= {{7,8,9,18,14,11,10,6,3,5},10};
    Tas *p_arbre;
    p_arbre=&arbre;
    print((*p_arbre).len,(*p_arbre).noeuds);
    int newnoeuds=0;
    Ajout_elt(p_arbre,newnoeuds);
    // Supprimeracine(p_arbre);
    printf("hello word \n");
    tri(p_arbre);
    print((*p_arbre).len,(*p_arbre).noeuds);
 
    return 0;
}

[gerald3d]

Bonjour.

Tout d'abord sur la forme de ton post. Vu que le code source est court utilises plutôt les balises . C'est l'icône #. Tu copies le code source entre les balises. Ca sera plus confortable pour tout le monde plutôt que d'être obligé d'ouvrir ta pièce jointe.

Maintenant sur le fond, voila juste la fonction main (); et la fonction print (); revues. J'ai l'impression que la manipulation des pointeurs est encore perfectible même si ici ton code est fonctionnel. Il ne donne pas les résultats escomptés mais au moins il n'y a pas de segdefault .
Puisque tu sais accéder à l'adresse d'une variable quel est l’intérêt de la variable p_arbre ? Ici aucun alors autant s'en passer. D'autant que son utilisation t'oblige à utiliser des * et des () pour transmettre les paramètres à tes autres fonctions. Voila donc ce petit bout de code corrigé pour que tu vois le chemin que tu dois emprunter pour arriver à un code simple et fonctionnel :

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
void print (int t, int *p){
  for(int i=0;i<t;i++){
    printf("%d ", *p);
    p+=1;    }
}

int  main(int argc, char **argv) {
  // Tas arbre={{18,14,-3,-5,-2,-4},6};
  Tas arbre={{7,8,9,18,14,11,10,6,3,5},10};
  // Tas *p_arbre;

  p_arbre=&arbre; // Inutile. Autant passé directement le pointeur plutôt que de créer une variable contenant ce même pointeur
  printf ("Tableau initiale : ");
  print (arbre.len, arbre.noeuds);
  printf ("\n\n");

  int newnoeuds=0;
  Ajout_elt (&arbre, newnoeuds);

  // Supprimeracine(p_arbre);
  printf("hello word \n");

  tri (&arbre);
  print (arbre.len, arbre.noeuds);

  return 0;
}

Il faut ensuite penser sécurité. Tu transmets des paramètres à tes différentes fonctions sans jamais vérifier s'ils sont correctes. Prenons un simple exemple avec la fonction print ();. Si j'envoie un pointeur NULL en lieu est place de l'adresse d'une variable int que va-t-il se passer ? Tu comprends bien que ton programme va planter sur un segdefault. Ajoute à toutes tes fonctions des instructions de test des paramètres reçus. Renvois un résultat permettant à la fonction appelante de traiter l'erreur au cas où.
Pour revenir à print (); on n'est pas forcé de renvoyer quelque chose. On peut par exemple écrite un message d'erreur dans le canal réservé à cet effet et quitter la fonction :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void print (int t, int *p){
  if (!p) {
    fprintf (stderr, "p must be not NULL in %s (t, *p);\n", __func__);
    return;
  }
  if (t < 1) {
    fprintf (stderr, "t must be greater than 0 in %s (t, *p)\n",  __func__);
    return;
  }
 
  for(int i=0;i<t;i++){
    printf("%d ", *p);
    p+=1;    }
}

Pour aller encore plus loin avec cette fonction pourquoi lui fournir les arguments de Tas ? Autant lui transmettre directement l'adresse d'une variable de type Tas non ?

Code :

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

1
2
3
4
5
6
7
8
9
void print (Tas *tas){
  if (!tas) {
    fprintf (stderr, "tas must be not NULL in %s (Tas *tas);\n", __func__);
    return;
  }
 
  for(int i=0; i<tas->len; i++)
    printf("%d ", tas->noeuds [i]);
}

Voila vers quoi tu dois tendre pour avoir une écriture concise et précise. À partir de là tu pourras commencer à entrevoir les problèmes qui t’amènent ici.

Histoire de poser une petite question pour ton sujet je ne comprends pas la fonction Tas* Ajout_elt (Tas* t, int noeud);. Au vu de son nom elle devrait permettre d'ajouter un élément au tas. Mais apparemment elle essaie de changer un élément du tas. que veux-tu faire exactement ?

[gogo5]

Bonjour,
Merci pour tous vos conseils.
La fonction ajoute_element permet d'ajouter un nouveau noeud au tas. il doit donc se placer correctement dans le tas.
Je retravaille mon code ce soir avec tous vos conseilles.