Discussion :

[Pitou5464]

salut,

je voudrais mettre la moitie d'une liste chainee passe en parametre a gauche de mon arbre et le reste a droite de l'arbre mais je ne sais pas comment coder la fonction ni comment couper une liste en deux.

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
#include <stdlib.h>
 
void    *xmalloc(int size)
{
  void  *temp;
 
  temp = malloc(size);
  if (temp == 0)
    exit(1);
  return (temp);
}
 
typedef struct          s_btree
{
  void                  *item;
  struct s_btree        *left;
  struct s_btree        *right;
}                       t_btree;
 
t_btree         *sorted_list_to_btree(t_list *l, int size)
{
// je ne sais pas quoi mettre ici...
}

[Invité]

salut,

je voudrais mettre la moitie d'une liste chainee passe en parametre a gauche de mon arbre et le reste a droite de l'arbre mais je ne sais pas comment coder la fonction ni comment couper une liste en deux.

et ben moi non plus, carje ne comprends pas ton probleme... peux tu STP reformuler ta question avec des mots pesés pour qu'on comprenne ce que tu as, ce que tu veux, et ce que tu n'arrives pas a faire... ?

[InOCamlWeTrust]

Pour couper une liste en deux, tu as deux algorithmes, qui produisent des résultats différents.

Le premier est tout bête : tu parcours la liste et tu distribues alternativement un élément dans la liste gauche et un autre dans la liste droite.

Le deuxième est plus complexe, mais permet de réellement couper en deux ta liste sans même en calculer la longueur, donc le tout en une seule passe. L'idée est d'avoir deux "indices" débutant tous les deux au début : quand l'un se déplace de deux en deux, l'autre se déplace d'un élément, ainsi tu es assuré que, quand l'"indice" le plus lointain est arrivé en bout de liste, l'autre se situe exactement à la moitié de la liste. Il ne reste donc plus qu'à couper.

Tu auras remarqué que si la liste est de taille N, l'algorithme est en N/2 étapes, ce qui est beaucoup plus optimal que l'algorithme du dessus qui t'oblige à recréer deux listes et à dés-allouer la liste courante.

[koala01]

Salut,

Juste une petite question (quand tu auras donné la réponse, je m'écrirai sans doute "mais comment n'y ai-je pas pensé" ) mais, pourrais tu expliciter ce que tu entend par

je voudrais mettre la moitie d'une liste chainee passe en parametre a gauche de mon arbre et le reste a droite de l'arbre

Car, de la manière dont je l'interprete, peut etre mal, d'ailleurs, tu cherche juste à avoir quelque chose ressemblant à

Code :

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

1
2
3
4
 
     racine de ton arbre binaire
              / \
une demi-liste   l'autre demi-liste

alors que l'utilisation "classique" d'un arbre binaire serait du genre de

Code :

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

1
2
3
4
5
6
 
      el4
     /    \
  el2      el6
   /\       /\
el1  el3 el5  el7

où elN serait le Nieme élément de ta liste triée

A moins, évidemment, que tu ne veuille rentrer dans une logique de "ashtable" ou autre...