Une liste chaînée est une liste linéaire stockée dans une structure de stockage « chaînée ». Les adresses d'unité de stockage occupées par les éléments de données de la liste chaînée peuvent être continues ou discontinues. L'espace de stockage correspondant peut être alloué temporairement et dynamiquement selon les besoins. La relation logique entre les éléments de données peut être exprimée par « chaîne ».
L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.
Afin de surmonter les défauts de la structure de stockage des tables séquentielles, d'utiliser pleinement l'espace de stockage et d'améliorer l'efficacité opérationnelle, les tables linéaires peuvent utiliser une autre structure de stockage - Structure de stockage en chaîne. La structure de stockage liée de la liste linéaire est appelée « liste de liens »
Les adresses des unités de stockage occupées par les éléments de données de la liste chaînée peuvent être continues ou discontinues, selon les besoins. Appliquer temporairement et dynamiquement l'allocation de l'espace de stockage correspondant, et la relation logique entre les éléments de données peut être exprimée sous la forme d'une « chaîne ».
L'insertion et la suppression de listes chaînées ne nécessitent pas de déplacer des éléments de données, seule la chaîne doit être modifiée.
Classification des listes chaînées :
1. Classées par méthode d'allocation de mémoire de liste chaînée
① Liste chaînée dynamique
② Liste chaînée statique
2. Classifiée par méthode de liaison
① Liste chaînée unique
② Circulaire. liste chaînée
③ Liste chaînée double
(Ce sont toutes des listes chaînées dynamiques)
Afin de représenter la relation logique entre chaque élément de données ai et son successeur direct. élément de données ai+1, pour chaque élément de données En plus de stocker ses propres informations , ai a également besoin de stocker des informations indiquant son successeur direct (emplacement de stockage - adresse du successeur).
Le champ qui stocke les informations sur les éléments de données est appelé champ de données, et le champ qui stocke les positions des successeurs directs est appelé champ de pointeur. Les informations stockées dans le champ de pointeur sont appelées un pointeur ou une chaîne.
Ces deux parties d'informations forment l'image de stockage de l'élément de données ai, qui est appelé node.
n nœuds sont liés dans une liste chaînée, qui est la structure de stockage liée de la liste linéaire (a1, a2, a3,...,an). Parce que chaque nœud de la liste chaînée ne contient qu'un seul champ de pointeur, c'est le cas. appelé C'est une liste chaînée unique.
Pour les listes linéaires, il y a toujours une tête et une queue, et les listes chaînées ne font pas exception. Le pointeur vers le premier nœud de la liste chaînée unique dans la liste chaînée est appelé pointeur principal L'accès à l'ensemble de la liste chaînée doit commencer à partir du pointeur principal, et chaque nœud suivant est pointé par le successeur. pointeur du nœud précédent. Le pointeur du dernier nœud de la liste chaînée est "null (généralement représenté par NULL)" - un pointeur nul.
Afin de faciliter la mise en œuvre de diverses opérations sur la liste chaînée, un nœud du même type est défini avant le premier nœud de données de la liste chaînée. Ce nœud est appelé nœud principal.
Le champ de données du nœud principal peut stocker des informations de drapeau spéciales telles que la longueur de la liste chaînée, ou il ne peut stocker aucune donnée.
Le premier nœud de données et le dernier nœud de la liste chaînée sont également appelés nœud principal et nœud de queue.
Pointeur de tête :
Nœud d'en-tête :
/*线性表的单链表存储结构*/ /*结点定义*/ typedef struct Node { ElemType data; struct Node *next; }Node; /*单链表定义*/ typedef struct Node *LinkList;
Supposons que le nœud stockant l'élément e est s, et insérez s derrière le nœud ai.
Réflexion : Les deux phrases du code d'insertion peuvent-elles être échangées ?
Non, si vous le changez, les éléments suivants tels que ai+1 ne peuvent pas être trouvés, car le champ de pointeur de s ne pointe pas vers l'adresse de ai+1.
Supposons que le nœud stockant l'élément ai est q et que l'opération de suppression du nœud q d'une liste à chaînage unique doit être implémentée.
Méthode de stockage :
Performances temporelles :
①Recherche
②Insertion et suppression
Performances spatiales :
Pour plus d'informations. connaissances, veuillez visiter la rubrique FAQ !
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!