human
Structures de données, listes chaînées et arbres binaires J'ai toujours été confus, bien qu'immédiatement après avoir fermé mon livre, j'ai l'impression d'avoir compris. Il manque toujours quelque chose. Explique comme si j'avais cinq ans.
gpt
Pour bien comprendre certaines structures de données, il faut avoir une assez bonne compréhension de la récursivité, de son fonctionnement et de sa signification. En d'autres termes, les listes chaînées et les arbres binaires sont des structures de données récursives. Cela signifie qu'ils se référencent d'une manière ou d'une autre. * * Pour comprendre ce message, vous devez avoir une vague compréhension de la programmation. Tout le code est en pseudocode. * * * * * * * # # # Listes chaînées Pour commencer , nous devons définir une classe ( ou une structure , selon le langage ) . Pour la plupart des structures de données de liste chaînée , cette classe sera appelée une ` liste ` . class list : var value list next Nous avons donc défini une classe ` list ` qui contient deux variables : une de type ` integer ` ( c'est - à - dire 1 , 4 , 7 ) et une de type ` list ` . La " valeur " ` var ` est l' information importante sur * ce * nœud . La ` list ` " next " contient l' objet suivant dans la liste chaînée . Cela signifie que chaque ` liste ` stocke une donnée * * et * * une autre liste . La dernière ` list ` dans la liste chaînée pointe vers la valeur ` NULL ` , ce qui signifie essentiellement que la fin de la liste a été atteinte . Listes tout en bas. Comparez une liste chaînée à un tableau. Parcourir un tableau et afficher son contenu : for i = 0 ; je < len(tableau ) ; je = je + 1 imprimer tableau[je ] ; Maintenant, avec une liste chaînée, qui est en haut (ou en tête, comme on l'appelle parfois) s'appelle `list` : for i = list; i.suivant ! = NUL ; je = je.suivant ; print i.value ; J'aime à penser que la liste semble plus récursive : c'est-à-dire que vous pouvez continuer à référencer ` .next ` jusqu'à ce que vous appuyiez sur ` NULL ` . Cela semble plus simple et plus facile à lire, à mon avis. Il rend également les listes très faciles à utiliser dans les opérations récursives. [ Une image de Wikipedia pour aider à la compréhension de la liste chaînée ] ( URL_1 ) * * * * * # # # Arbres binaires Encore une fois , nous devons définir une classe pour l' arbre binaire . Ceci est très similaire à la liste chaînée, mais avec quelques petits changements. Cette classe s'appellera ` node ` . nœud de classe : var valeur nœud de gauche nœud de droite Si vous comprenez parfaitement l'exemple d'une liste chaînée, nous espérons que la compréhension de l'arbre binaire sera assez facile. En pratique, les arbres binaires sont souvent utilisés comme arbres de recherche binaires (BST). Les BST sont une structure de données assez efficace et facile à utiliser pour le tri et la recherche. Le fonctionnement d'un BST est très agréable. Commencez par votre ` node ` initial ( ou ` head ` ) , disons que la valeur initiale est 8 . Ajoutez le prochain ` node`s à l'arborescence en utilisant une fonction simple appelée ` insert ` : def insert ( node , value ): if node.value = = NULL node.value = value else if value < node.value insert(node.value. left , value ) else insert(node.right , value ) Etant donné la ` head ` d'un arbre avec la valeur 8 , on peut appeler ` insert(head , 3 ) ` et un nouveau nœud sera ajouté à tree . Pour y accéder , vous devez appeler ` head.left.value ` . Avec cette fonction d'insertion, nous pouvons créer des BST assez facilement. Faisons cela maintenant : node head # ceci est fait juste pour s'assurer que head est de * type * node head.value = 8 insert(head , 3 ) insert(head , 6 ) insert(head , 10 ) insert( head , 7 ) insert(head , 1 ) insert(head , 4 ) insert(head , 14 ) insert(head , 13 ) [ Ceci est votre résultat final ] ( URL_0 ) * * * * * Il existe de nombreux types de structures de données . Pour n'en nommer que quelques-unes qui leur ressemblent : listes doublement liées, listes circulaires (et bien sûr, listes circulaires doublement liées), graphes, essais, etc. Cette pointe de l'informatique s'étend assez loin et il existe de nombreux algorithmes importants associés à ces structures de données plus complexes. Si vous voulez en savoir plus, il suffit de demander .