Discussion :

[tomasi]

bonjour,

je suis en train d'essayer d'implémenter le tri par fusion sur une liste chainée

pour cela j'ai ecrit une fonction récursive trier

Code :

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

1
2
3
4
5
6
7
8
9
10
11
void trier(PTR tete, PTR queue)
{
  if(tete->indice > queue->indice)
  {
   trier(tete->indice, (tete->indice + queue->indice)/2);
   trier((((tete->indice + queue->indice)/2)+1), tete->indice);
   //fusion(tete->indice, queue->indice);
  }
 
  return;
}

lors des appels récursifs de la fonction trier les paramètres sont des entiers
et bien sur à la compilation cela me donne "'trier' makes pointer from integer without a cast" car la fonction n'est appellée avec les bons paramètres.

Mais j'ai besoin des pointeurs tete et queue pour pouvoir lire la valeur de l'entier indice...

comment résoudre ce problème ?

Merci

[Emmanuel Delahaye]

Code :

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

1
2
3
void trier(PTR tete, PTR queue)
{
}

lors des appels récursifs de la fonction trier les paramètres sont des entiers
et bien sur à la compilation cela me donne "'trier' makes pointer from integer without a cast" car la fonction n'est appellée avec les bons paramètres.
i

Pourquoi ne pas mettre le bon type au lieu de ce PTR dont la définition n'est pas visible ?

[tomasi]

le bon type ?

c'est à dire int ?

j'ai essayé et voila ce que ca donne

Code :

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

1
2
3
4
5
6
7
8
9
10
11
void trier(int tete, int queue)
{
  if(tete->indice > queue->indice)
  {
   trier(tete->indice, (tete->indice + queue->indice)/2);
   trier((((tete->indice + queue->indice)/2)+1), tete->indice);
   //fusion(tete->indice, queue->indice);
  }
 
  return;
}

et ca me retourne un paquet d'erreurs

[Skyounet]

Peut-être parce que PTR, c'est pas un int.

Comment est définie PTR?

Montre nous le typedef.

[tomasi]

voici le code en entier

la fonction fusion n'est pas encore écrite, je ne sais pas trop encore comment m'y prendre...

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
//longueur de la liste
#define N 5
 
//définition de l'identificateur MAILLON
typedef struct maillon MAILLON;
////définition de l'identificateur PTR comme pointeur vers un MAILLON
typedef MAILLON *PTR;
 
/*définition de la structure maillon composée d'un entier
  et d'un pointeur vers une structure définie comme celle-ci
*/
struct maillon
{
  int valeur;
  int indice;
  struct maillon *suivant;
};
 
/*au commencement la liste est vide,
  le pointeur de tete pointe donc vers NULL
*/
PTR tete = NULL, queue;
 
 
void creer_liste(PTR p)
{
  int i,j=0;
 
/*permet d'avoir une séquence différente à chaque lancement du programme,
  passage une valeur 'changeante' à srand(),
  utilisation de la valeur retournée par time()
  qui change une fois par seconde indépendemment du programme
*/
  srand((unsigned) time(NULL));
 
  for(i = 0; i < N; ++i)
  {
    p = malloc(sizeof(MAILLON));
    if(p == NULL)
    {
      printf("Probleme d'allocation de mémoire \n");
      exit(-1);
    }
 
    p->valeur = rand() % (N+1);
    p->indice = j++;
    p->suivant = NULL;
    if(tete == NULL)
      tete = p;
    else
      //recupération du dernier élément de la liste avec le pointeur queue
      queue->suivant = p;
    queue = p;
  }
 
  return;
}
 
 
void trier(int tete, int queue)
{
  if(tete->indice > queue->indice)
  {
   trier(tete->indice, (tete->indice + queue->indice)/2);
   trier((((tete->indice + queue->indice)/2)+1), tete->indice);
   //fusion(tete->indice, queue->indice);
  }
 
  return;
}
 
 
void fusion(PTR tete, PTR queue)
{
 
 
  return;
}
 
 
void afficher(int cas, PTR p)
{
  if(cas == 1)
  printf("Voici la liste non triée : \n");
  else if(cas == 2)
  printf("Voici la liste triée : \n");
 
  for(p = tete; p != NULL; p = p->suivant)
    printf(" *%d - %d* ", p->valeur, p->indice);
    //printf(" *%d* ", p->valeur);
  printf("\n");
 
  return;
}
 
 
int main()
{
  PTR p;
 
  creer_liste(p);
 
  afficher(1, p);
 
  system("pause")
 
  return EXIT_SUCCESS;
}

[Emmanuel Delahaye]

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
 
struct maillon
{
  int valeur;
  int indice;
  struct maillon *suivant;
};
 
void trier(PTR tete, PTR queue)
{
  if(tete->indice > queue->indice)
  {
   trier(tete->indice, (tete->indice + queue->indice)/2);
   trier((((tete->indice + queue->indice)/2)+1), tete->indice);
   //fusion(tete->indice, queue->indice);
  }
 
  return;
}

Les paramètres de trier() sont de type PTR . Le seul pointeur que je vois dans un PTR est "struct maillon *suivant;".

Mais j'ai un peu du mal à comprendre ta liste, et notamment le rôle de indice...

Un parcours récursif de liste se fait en principe comme ceci :

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
 
struct node
{
   struct node *p_next;
 
   /* data... */
};
 
void parcourir (struct node *p)
{
   if (p != NULL)
   {
     /* traitement en croissant */
      parcourir (p->p_next);
     /* traitement en decroissant */
   }
}