INFO 3
mardi 17 octobre 2023 19:56
sizeof fournit la taille (en octets) du type ou de la variable qui suit.
Sa syntaxe est : sizeof ( type ou nom de variable)
Les arbres :
• Qu'est-ce qu'un arbre ?
Tout comme les listes chaînées, les arbres servent à mémoriser des données. Ils sont constitués d'éléments que
l'on appelle souvent des nœuds. Ils sont semblables aux listes chaînées par le fait que les éléments sont chaînés
les uns avec les autres, mais avec la possibilité que plusieurs branches partent d'un nœud, d'où leur nom (on
pourrait très bien voir une liste chaînée comme un arbre à une seule branche). Il est courant d'appeler le
premier élément d'un arbre la racine. La racine est un nœud qui n'a pas de parent. On peut aussi entendre parler
de feuilles, ce sont les nœuds qui sont au bout des branches et qui n'ont donc pas d'enfants.
Un arbre binaire est un arbre ou chaque nœud peut avoir au maximum deux branches. Pour différencier les
branches, on les nomme souvent droite ou gauche (right, left).
• Le parcours en profondeur préfixe d’un arbre binaire consiste à parcourir sa racine, puis son sous-arbre
gauche, puis son sous-arbre droit.
• Le parcours en profondeur infixe d’un arbre binaire consiste à parcourir son sous-arbre gauche, puis sa
racine, puis son sous-arbre droit.(je note l'élément lorsque j'en peut plus descendre à gauche)
• Le parcours en profondeur postfixe d’un arbre binaire consiste à parcourir son sous-arbre gauche, puis son
sous-arbre droit, puis sa racine.(je note l'élément qu'on j'en peut plus descendre)
• La parcours en largeur d’un arbre binaire consiste à le parcourir par niveau.
Je pose au premier niveau la racine ,après je compare le nouveau élément avec la racine si lui est
inferieur alors je le mis à gauche si supérieur à droite et je continue avec les autres élément de
même.
Ajout , recherche , suppression des clés :
• Pour l'ajout, on compare chaque élément à la racine et on le place à gauche ou à droite selon sa
valeur. Si lui est inférieur je mis la valeur à gauche si lui est supérieur je la mis à droite .
• Pour la recherche, on compare également chaque élément à la racine et on parcourt l'arbre
jusqu'à le trouver ou tomber sur une feuille(ou le vide).
• Pour la suppression, on remplace l'élément à supprimer par le plus grand élément du sous-
arbre gauche (s'il a un fils en gauche )ou par le plus petit du sous-arbre droit.
(Supprimer une feuille est simple, il suffit de la retirer, par contre si je veux supprimer un fils ou
un parent ou bien même la racine on le remplace par le plus grand élément du sous-arbre
gauche ou le plus petit du sous-arbre droit.)
Tri d'une liste simplement chainée:
Si je veux un tri décroissant
Croissant Il suffit de faire
p->data > temp->data
Box *trier(Box *debut)
Si on a la donnée de la
{
liste de type char on
Box * temp ,*p;
Int pr; utilise strcpy()
If(debut !=NULL)
{
for(temp=debut ;temp->suivant!=NULL;temp=temp->suivant)
{
for(p=temp->suivant;p!=NULL;p=p->suivant)
{
If(p->data < temp->data)
pr=p->data;
P->data=temp->data;
Temp->data=pr;
}
}
}
Return debut;
}
La fonction donnée semble être une implémentation de l'algorithme de tri de
sélection, destinée à trier une liste chaînée de structures "Box" en fonction de la
valeur de leur attribut "data". Voici une explication détaillée de cette fonction :
1. Déclaration et initialisation des variables :
- `Box *temp` : un pointeur temporaire utilisé pour parcourir la liste.
- `Box *p` : un pointeur utilisé pour comparer les éléments avec le pointeur
temporaire.
- `int pr` : une variable temporaire utilisée pour stocker la valeur de l'élément "p-
>data" lors d'un échange.
2. Vérification de la validité du pointeur de début :
- `if(debut != NULL)` : vérifie si le pointeur "debut" ne pointe pas vers NULL (une
liste vide).
3. Boucle externe pour sélectionner l'élément de la liste non triée à chaque itération
:
- `for(temp = debut; temp->suivant != NULL; temp = temp->suivant)` : initialise le
pointeur temporaire "temp" avec le pointeur de début et itère tant que "temp" n'est
pas le dernier élément de la liste.
4. Boucle interne pour trouver le minimum et échanger les éléments :
- `for(p = temp->suivant; p != NULL; p = p->suivant)` : initialise le pointeur "p" avec
l'élément suivant de "temp" et itère tant que p n'est pas NULL (la fin de la liste).
- `if(p->data < temp->data)` : vérifie si la valeur de "p->data" est inférieure à la
valeur de "temp->data" (le minimum est trouvé).
- Échange des valeurs des attributs "data" pour placer le minimum à la position
actuelle :
- `pr = p->data;` : stocke la valeur de "p->data" dans la variable temporaire "pr".
- `p->data = temp->data;` : remplace la valeur de "p->data" par la valeur de "temp-
>data".
- `temp->data = pr;` : remplace la valeur de "temp->data" par la valeur
précédemment stockée dans "pr".
5. Retour de la liste triée :
- `return debut;` : renvoie le pointeur de début, qui pointe maintenant vers la liste
triée.
