Une liste chaînée est une liste linéaire stockée dans quelle structure de stockage

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 »

1 Aperçu de la liste chaînée

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)

2. Définition de liste chaînée unique

1 Définition

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.

2. Les similitudes et les différences entre le pointeur de tête et le nœud de tête

Pointeur de tête :

• Le pointeur de tête fait référence au pointeur pointant vers le premier nœud de la liste chaînée si la liste chaînée a un. nœud principal, il pointe vers le pointeur principal vers le nœud.
• Le pointeur de tête a une fonction d'identification, et le pointeur de tête est souvent utilisé comme nom de la liste chaînée.
• Peu importe que la liste chaînée soit vide ou non, le pointeur de tête n'est pas vide. Le pointeur de tête est un élément nécessaire de la liste chaînée.

Nœud d'en-tête :

• Le nœud de tête est établi pour l'unification et la commodité des opérations. Il est placé avant le nœud du premier élément, et son champ de données est généralement involontaire.
• Avec le nœud principal, les opérations d'insertion d'un nœud avant le nœud du premier élément et de suppression du premier nœud sont unifiées avec celles des autres nœuds.
• Le nœud principal n'est pas nécessairement un élément nécessaire de la liste chaînée.

3. Démonstration de code

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

3. Opérations de liste chaînée unique

1. Opération d'insertion

1) Simulation d'insertion

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.

2) Idée d'algorithme pour insérer la i-ième donnée dans le nœud d'une liste chaînée unique

• Déclarez un nœud p pour pointer vers le premier nœud de la liste chaînée, initialisez j=1 ;
• Quand j
• Si p est vide à la fin de la liste chaînée, cela signifie que le i-ème élément n'existe pas si ; la recherche est réussie, un nœud vide s est généré (à l'aide de la fonction malloc)
• Attribuez l'élément de données e à s->data, c'est-à-dire insérez l'instruction standard pour s->data=e;
•  : s->next=p->next; p->next=s;
• Retour réussi.

2. Opération de suppression

1) Simulation de suppression

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.

2) Idée d'algorithme de suppression du i-ème nœud de données dans une liste chaînée

• Déclarez un nœud p pointant vers le premier nœud de la liste chaînée, initialisez j=1;
• Quand j< ;i, traverse Dans la liste chaînée, laissez le pointeur de p reculer et pointer continuellement vers le nœud suivant, j++;
• Si p est vide à la fin de la liste chaînée, cela signifie que le i-ième élément ne existe ; si la recherche réussit, le nœud p-> Assign à côté de q
• Insérez l'instruction standard : p->next=q->next;
• Attribuez le nœud q à e, qui est e=. q->data;
• Relâchez le nœud q
• Renvoyez le succès.

4. Comparaison entre la structure de liste chaînée unique et la structure de liste séquentielle

Méthode de stockage :

• La table séquentielle utilise une unité de stockage continue pour stocker les éléments de données dans la liste linéaire en séquence
• La liste chaînée simple utilise un stockage lié structure, utilisant un groupe d'unités de stockage arbitraires stocke des éléments de table linéaires

Performances temporelles :

①Recherche

• Table séquentielle O(1)
• Liste chaînée unique O(n)

②Insertion et suppression

• Séquentielle table O(n )
• Liste chaînée unique O(1)

Performances spatiales :

• La table de séquence nécessite un espace de stockage pré-alloué Si elle est divisée en une grande taille, ce sera un gaspillage. divisée en une petite taille, cela provoquera facilement un débordement.
• La liste chaînée n'a pas besoin de pré-allouer de l'espace de stockage. Vous pouvez en allouer autant que vous en avez besoin, et le nombre d'éléments n'est pas limité

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!