Trier la liste liée C ++

Liste liée

Une liste liée est une sorte de structure de données. Les éléments à l'intérieur de la liste liée sont connectés à l'aide de pointeurs. C'est une collection de nœuds. Un nœud contient deux parties. On comprend les données, et la deuxième partie se compose du pointeur. Ce pointeur est utilisé pour stocker l'adresse mémoire de l'élément de nœud adjacent dans la liste liée. L'avantage de la liste liée d'un tableau est qu'elle a une taille dynamique.

Représentation d'une liste liée

Le premier nœud de la liste liée est appelé. Sa valeur est nul dans le cas d'un tableau vide. En C ++, nous utilisons une structure pour représenter un nœud.

Ceci est un simple code C ++ de création de liste liée. Nous avons créé une classe dans laquelle sa partie publique, une variable de données de type entier, est créée avec une variable de pointeur «Next» qui stockera l'adresse du nœud.

Trois nœuds sont créés à l'intérieur du programme principal, le premier nœud supérieur déclaré comme le nœud «tête». Tous les trois points de ces nœuds sont vides, ils sont donc déclarés nuls initialement. Après avoir fait cela, les trois nœuds sont alloués en tas. «tête» deuxième, et le troisième est attribué avec le nouveau nœud.

Nous allons maintenant attribuer des données, et les données peuvent être n'importe quelle valeur aléatoire. Tout d'abord, nous attribuerons des données dans le premier nœud.

Tête-> data = 1;

Cette démonstration d'attribution de données montre que la partie de données du premier nœud contiendra des données. Après avoir attribué des données, nous lierons le premier nœud avec le second

Head-> suivant = seconde;

Nous connectons la partie du pointeur «Next» avec l'autre nœud pour lier deux nœuds. Nous attribuerons des données stockées dans la partie de données du premier nœud. Tandis que la partie «suivante» contiendra l'adresse mémoire du nœud présent après. De même, nous allons désormais attribuer des données au deuxième nœud, et le deuxième nœud sera lié au troisième nœud. Ajoutez maintenant des données dans le troisième nœud. Comme nous n'avons créé que trois nœuds, il n'y a pas d'autre nœud, donc la prochaine partie du troisième pointeur sera déclarée nul; Cela indique que la liste liée est terminée.

Troisième-> suivant = null;

Exemple

Trier la liste liée

Ici, nous avons déclaré une structure représentant un nœud d'une seule liste liée. Comme décrit ci-dessus, le concept de déclaration de liste liée, la variable de données et les variables de pointeur sont prises dans la structure. Comme la partie du pointeur «suivant» qui stocke l'adresse, nous avons également déclaré deux autres variables de type pointeur: tête de nœud et queue de nœud. Ceux-ci sont initialement déclarés nuls.

Comme le nœud d'insertion traite de l'insertion du nœud de données dans la liste liée, nous utiliserons une fonction de l'ajout d'un nœud. Les données attribueront également ce nœud. Ainsi, le paramètre de cette fonction contiendra des données comme argument. Avant l'insertion, le nœud sera créé avec une allocation de mémoire en utilisant une fonction malloc (). La partie de données du nouveau nœud sera attribuée avec les données passées.

NewNode-> data = data;

Et de même, la partie suivante est attribuée comme nul, car il n'y a aucun lien entre ce nœud avec aucun autre. Comme les variables de tête et de queue sont déclarées aider au tri de l'insertion. Maintenant, nous allons les utiliser ici. Tout d'abord, en utilisant une déclaration IF-Else, nous vérifierons si la tête est nul, comme nous l'avons déclaré null ci-dessus, ce qui signifie que toute la liste est vide. C'est pourquoi la tête est vide, donc la tête et les variables de queue pointent vers le nœud nouvellement créé. Sinon, dans la partie ELSE, si la liste n'est pas vide, supposons que lors de la création de la liste que nous avons également saisi des données, alors, dans ce cas, le nouveau nœud sera ajouté à la dernière place.

Tail-> next = newNode;

Et maintenant, ce nouveau nœud agira comme un nouveau conte.

Tail = newNode;

Pour plus d'addition, le même processus se poursuit, mais nous devons trier la liste liée. Nous avons donc ajouté un seul nœud qui agit comme un nœud temporaire pour y stocker temporairement les données.

Après avoir ajouté le nouveau nœud, nous utiliserons une fonction pour trier / organiser la liste. Comme le type de tri n'est pas mentionné ici, par défaut, la liste sera triée par ordre croissant.

Revenant vers l'exemple, un autre pointeur actuel pointe vers la tête, comme nous l'avons déclaré ci-dessus. Ceci est utilisé pour trier les éléments de la liste. Une autre variable de type pointeur sera utilisée ici, puis déclarée nul. Une utilisation plus approfondie sera dans le programme plus tard.

Ici, nous appliquerons un chèque pour identifier si le pointeur de tête est en position nul, puis retourner au programme principal. Sinon nous appliquerons une logique ici qui suivra une boucle de temps. Le pointeur d'index pointera vers la partie suivante du nœud actuel. À l'intérieur de cette boucle, une autre boucle tandis que la boucle est utilisée, et cela durera également jusqu'à ce que le nœud actuel ne soit pas nul. Ici, nous utiliserons une instance IF pour vérifier si les données du nœud actuel sont supérieures aux données du nœud de l'index, puis les données entre elles sont échangées.

La variable temporaire jouera ici un rôle important dans l'échange de données. Tout d'abord, les données du nœud actuel sont transférées à TEMP, puis le nœud actuel est maintenant vide. Ce nœud se verra attribuer la valeur des données indexes. Et à la fin, le nœud d'index vide est attribué par les données présentes dans la variable temporaire.

En dehors de la mise en place de l'IF, le nœud d'index est également incrémenté avec la nouvelle valeur d'un index. De même, en dehors de la boucle while, le nœud actuel est également attribué par la nouvelle valeur.

Ensuite, nous avons utilisé une fonction d'affichage ici pour afficher la valeur de tous les nœuds. Le pointeur actuel pointera vers la tête. Dans un autre cas, une boucle de temps affiche toutes les valeurs jusqu'à ce que le nœud actuel ne soit pas nul.

Considérons maintenant le programme principal, la fonction d'addNode () est appelée avec les valeurs pour ajouter de nouvelles valeurs dans la liste. Ensuite, la fonction d'affichage affichera toutes les valeurs entrées avant de trier. Puis appelez la fonction tri (). Puis encore, appelez la fonction d'affichage pour afficher toute la liste triée.

Enregistrez le fichier de code, puis exécutez-le dans le terminal Ubuntu à l'aide d'un compilateur G ++.

fichier de fichier $ g ++ -o.c

$./déposer

À partir de la valeur résultante, vous pouvez observer que les valeurs sont organisées par ordre croissant car ils ont été entrés au hasard dans la liste liée.

Conclusion

«Trier Linked List C ++» contient la description des connaissances de base concernant la liste liée et sa création. Un exemple de code est suffisant pour démontrer la création de nœuds et le fonctionnement de tous les nœuds de la liste liée. Les éléments à l'intérieur de la liste liée sont organisés par ordre croissant à l'aide d'un processus détaillé en ajoutant de nouveaux nœuds puis en tri via une variable temporaire. L'explication avec le code est effectuée pour aider l'utilisateur.