Se connecter
Se connecter
Inscription
Mot de passe perdu
Connexion:
[Actualités]
Nvidia prévient d'une pénurie de GPU ce trimestre, avec une reprise début 2025
[Actualités]
Les Technos #469 : Un jour sans fin
[Actualités]
Test Farming Simulator 25 (PS5) - Des innovations intéressantes mais des perfor...
[Actualités]
Qualcomm souhaite réduire davantage les prix des PC Windows basés sur ARM
[Actualités]
Finalement, Google préparerait une nouvelle tablette mais la Pixel Tablet 2 ser...
[Actualités]
Windows 10 version 22H2 : erreur de mise à jour et de désinstallation
[Actualités]
OpenAI prépare désormais son propre navigateur
[Actualités]
WhatsApp bat Telegram : les transcriptions des messages vocaux arrivent pour tou...
[Actualités]
Unreal et Unreal Tournament désormais gratuits sur Internet Archive
[Actualités]
Windows 10 : Microsoft affiche des publicités en plein écran pour les PC équi...
[Articles]
Dungeons 4 - Nintendo Switch Edition
[Articles]
The Bridge Curse 2 : The Extrication
[Articles]
Farmagia
[Articles]
I*CHU: Chibi Edition
[Articles]
Farming Simulator 25
[Articles]
Goblin Slayer -Another Adventurer- Nightmare Feast
[Articles]
Deel lance des programmes en marque blanche et pour les revendeurs pour plus de ...
[Articles]
ESET Research : WolfsBane, nouvelle porte dérobée de cyber-espionnage Linux cr...
[Articles]
Devoteam présente son nouveau plan stratégique « AMPLIFY » avec un fort acce...
[Articles]
LEGO Horizon Adventures
Actualités
Lettre d'information
Proposer une actualité
Archives
Actualités
Articles
Programmation
Press Release
Matériel
Logiciels
Livres
Interviews
Derniers commentaires
Jeux Vidéos
XBox One
XBox 360
Wii U
PSP
PS4
PS3
PC
DS
GameCube
3DS
Forum
Derniers messages
Informatique
Fun
Divers
Logithèque
Blogs
Divers
A Propos
Annonceurs
Contact
Recherche
RSS
Editer un article
Titre
Mots Clés
Texte
[size=18] [b]Nom[/b] [/size] tsearch, tfind, tdelete, twalk - Manipulation d'arbre binaire. [size=18] [b]Résumé[/b] [/size] .nf [b]#include
[/b] [b][i]void *tsearch (const void * key , void ** rootp ,[/i][/b] [b][i] int (* compar )(const void *, const void *));[/i][/b] [b][i]void *tfind (const void * key , const void ** rootp ,[/i][/b] [b][i] int (* compar )(const void *, const void *));[/i][/b] [b][i]void *tdelete (const void * key , void ** rootp ,[/i][/b] [b][i] int (* compar )(const void *, const void *));[/i][/b] [b][i]void twalk (const void * root , void (* action ) (const void * nodep ,[/i][/b] [b][i] const VISIT which ,[/i][/b] [b][i] const int depth ));[/i][/b] [b]#define _GNU_SOURCE[/b] [b][/b] [b]#include
[/b] [b][i]void tdestroy (void * root , void (* free_node )(void * nodep ));[/i][/b][/col][/row][/table] .fi [size=18] [b]Description[/b] [/size] [b]tsearch[/b], [b]tfind[/b], [b]twalk[/b], et [b]tdelete[/b] permettent de manipuler un arbre binaire. Ces fonctions implémentent une généralisation de l'algorithme T de Knuth (6.2.2). Le premier membre de chaque noeud de l'arbre est un pointeur vers la donnée elle-même (le programme appelant doit prendre en charge le stockage de ces données). [i]compar[/i] pointe sur une routine de comparaison prenant en argument deux pointeurs sur ces données. Elle doit renvoyer un entier négatif, nul, ou positif suivant que le premier élément est inférieur, égal ou supérieur au second. [b]tsearch[/b] recherche un élément dans l'arbre. [i]key[/i] pointe sur l'élément à chercher. Si l'arbre est vide, alors [i]rootp[/i] doit pointer sur une variable pointant sur [b]NULL[/b]. Si l'élément est trouvé dans l'arbre, [b]tsearch[/b] renvoie un pointeur sur celui-ci. Sinon [b]tsearch[/b] ajoute l'élément dans l'arbre et renvoie un pointeur sur lui. [b]tfind[/b] fonctionne comme [b]tsearch[/b], sauf que si l'élément n'est pas trouvé, alors la fonction [b]tfind[/b] renvoie [b]NULL[/b]. [b]tdelete[/b] supprime un élément de l'arbre. Ses arguments sont les mêmes que ceux de [b]tsearch[/b]. [b]twalk[/b] exécute un balayage en profondeur d'abord, de gauche à droite, de l'arbre binaire. [i]root[/i] pointe sur le noeud de départ du balayage. S'il ne s'agit pas de la vraie racine de l'arbre, seule une partie de celui-ci sera balayée. [b]twalk[/b] appelle la fonction [i]action[/i] chaque fois qu'un noeud est rencontré (c'est à dire trois fois pour un noeud interne et une seule fois pour une feuille de l'arbre). [i]action[/i], doit accepter trois arguments. Le premier est un pointeur sur le noeud rencontré. Le second est un entier prenant l'une des valeurs suivantes : [b]preorder[/b], [b]postorder[/b], et [b]endorder[/b] suivant qu'il s'agisse de la première, deuxième ou troisième rencontre du noeud, ou encore [b]leaf[/b] s'il s'agit d'un noeud feuille. (Ces symboles sont définis dans [i]
[/i].) Le troisième argument est la profondeur du noeud dans l'arbre, zéro correspondant à la racine. (Plus généralement, [b]preorder[/b], [b]postorder[/b], et [b]endorder[/b] sont vus comme [b]preorder[/b], [b]inorder[/b], et [b]postorder[/b]: avant de visiter le noeud fils, après le premier et avant le second, après avoir visité les enfants. Ainsi, le choix du nom [b]post[/b]%order est un peu déroutant.) [b]tdestroy[/b] supprime tous l'arbre pointé par [i]root[/i], libérant toutes les ressources allouées par la fonction [b]tsearch[/b]. Pour libérer les données de chaque noeud, la fonction [i]free_node[/i] est invoquée. Le pointeur sur les données est passé en argument à cette fonction. Si aucune libération n'est nécessaire, [i]free_node[/i] doit pointer vers une fonction ne faisant rien. [size=18] [b]Valeur renvoyée[/b] [/size] [b]tsearch[/b] renvoie un pointeur sur un élément correspondant de l'arbre, sur l'élément nouvellement ajouté, ou [b]NULL[/b] s'il n'y avait pas assez de mémoire pour ajouter le noeud. [b]tfind[/b] renvoie un pointeur sur l'élément recherché ou [b]NULL[/b] si aucune correspondance n'a été trouvée. Si plusieurs éléments correspondent à la clé, celui renvoyé n'est pas spécifié. [b]tdelete[/b] renvoie un pointeur sur le noeud père de celui détruit, ou [b]NULL[/b] si l'élément n'a pas été trouvé. [b]tsearch[/b], [b]tfind[/b], et [b]tdelete[/b] renvoient également [b]NULL[/b] si [i]rootp[/i] valait [b]NULL[/b]. [size=18] [b]Attention[/b] [/size] [b]twalk[/b] utilise un pointeur sur la racine, alors que les autres fonctions utilisent un pointeur sur une variable pointant sur la racine. Pour [b]twalk[/b], [b]postorder[/b] signifie "après le sous-arbre de gauche, mais avant le sous-arbre de droite". Certains préfèreraient appeler ceci "inorder", et réserver "postorder" pour indiquer "après les deux sous-arbres". [b]tdelete[/b] libère la mémoire nécessaire au stockage du noeud dans l'arbre. Le programme appelant est responsable de la libération de la mémoire occupée par l'élément de donnée correspondant. Le programme d'exemple s'appuie sur le fait que [b]twalk[/b] ne fait plus jamais référence à un noeud après avoir appelé la fonction utilisateur avec l'argument "endorder" ou "leaf". Ceci fonctionne avec l'implémentation de la bibliothèque GNU, mais n'est pas spécifié sous SysV. [size=18] [b]Exemple[/b] [/size] Le programme suivant insère douze nombres aléatoires dans un arbre binaire, où les doublons sont regroupés, puis affiche les nombres classés. .nf #include
#include
#include
#include
void *root=NULL; void *xmalloc(unsigned n) { void *p; p = malloc(n); if(p) return p; fprintf(stderr, "pas assez de mémoire "); exit(1); } int compare(const void *pa, const void *pb) { if(*(int *)pa < *(int *)pb) return -1; if(*(int *)pa > *(int *)pb) return 1; return 0; } void action(const void *nodep, const VISIT which, const int depth) { int *datap; void *val; switch(which) { case preorder: break; case postorder: datap = *(int **)nodep; printf("%6d ", *datap); break; case endorder: break; case leaf: datap = *(int **)nodep; printf("%6d ", *datap); break; } return; } int main() { int i, *ptr; void *val; for (i = 0; i < 12; i++) { ptr = (int *)xmalloc(sizeof(int)); *ptr = rand()&0xff; val = tsearch((void *)ptr, &root, compare); if(val == NULL) exit(1); } twalk(root, action); return 0; } .fi [size=18] [b]Conformité[/b] [/size] SVID. La fonction [b]tdestroy()[/b] est une extension GNU. [size=18] [b]Voir aussi[/b] [/size] [b]qsort (3),[/b] [b]bsearch (3),[/b] [b]hsearch (3),[/b] [b]lsearch (3)[/b] [size=18] [b]Traduction[/b] [/size] Christophe Blaess, 1996-2003.
Fichier
Forum
-
Derniers messages
Bavardages
Aujourd'hui, je rénove ou je construis ^^
Software
problème sur windows 10
Réseaux et Télécom
Administrateur Réseau - Cisco
Réseaux et Télécom
Problème wifi (POE)
Software
Postfix - Need help
Bavardages
Oh râge oh désespoir !
Programmation
Enregistrement client et envoi mail
Software
SÉCURITÉ MACBOOK
Hardware
conseil matos réseau?
Hardware
nVidia Shield Android TV
Actualités
-
Archives
Matériel
Nvidia prévient d'une pénurie de GPU ce trimestre, avec une reprise début 2025
Les Technos
Les Technos #469 : Un jour sans fin
Jeux Vidéos
Test Farming Simulator 25 (PS5) - Des innovations intéressantes mais des performances à revoir
Matériel
Qualcomm souhaite réduire davantage les prix des PC Windows basés sur ARM
Tablettes
Finalement, Google préparerait une nouvelle tablette mais la Pixel Tablet 2 serait abandonnée
Ada
CSS
Cobol
CPP
HTML
Fortran
Java
JavaScript
Pascal
Perl
PHP
Python
SQL
VB
XML
Anon URL
DailyMotion
eBay
Flickr
FLV
Google Video
Google Maps
Metacafe
MP3
SeeqPod
Veoh
Yahoo Video
YouTube
6px
8px
10px
12px
14px
16px
18px
Informaticien.be
- © 2002-2024
Akretio
SPRL - Generated via
Kelare
The Akretio Network:
Akretio
-
Freedelity
-
KelCommerce
-
Votre publicité sur informaticien.be ?