Structure de stockage liée de la table linéaire

Avons-nous de bonnes solutions aux défauts de la structure séquentielle ?

La structure de stockage liée de la liste linéaire que nous allons présenter aujourd'hui peut très bien résoudre les lacunes de la structure séquentielle. Examinons-la ensemble.

Structure de stockage en chaîne, également appelée structure de stockage liée. Un ensemble d'unités de stockage arbitraires est utilisé dans l'ordinateur pour stocker les éléments de données du tableau linéaire (cet ensemble d'unités de stockage peut être continu ou discontinu).

Introduction de base

Il ne nécessite pas que les éléments logiquement adjacents soient physiquement adjacents. Par conséquent, il n'a pas les faiblesses de la structure de stockage séquentielle, mais il perd également le caractère aléatoire de la liste séquentielle. d'accès.

Caractéristiques

1. La densité de stockage est inférieure à la structure de stockage séquentielle (chaque nœud de la structure de stockage en chaîne se compose d'un champ de données et d'un pointeur Le domaine est composé de deux parties, ce qui augmente l'espace de stockage par rapport à la structure de stockage séquentielle).

2. Les nœuds logiquement adjacents ne doivent pas nécessairement être physiquement adjacents.

3. Insertion et suppression flexibles (pas besoin de déplacer le nœud, il suffit de changer le pointeur dans le nœud).

4. Le stockage chaîné est plus lent que le stockage séquentiel lors de la recherche de nœuds.

5. Chaque nœud est composé d'un champ de données et d'un champ de pointeur.

6. Étant donné que les clusters sont attribués de manière aléatoire, cela réduit également la probabilité d'écrasement après la suppression des données et augmente la possibilité de récupération.

Cours recommandé : Tutoriel du langage C.

Le dernier élément de la liste linéaire n'a pas de successeur direct, donc dans le stockage lié, nous définissons le champ de pointeur du dernier nœud sur null.

Faisons ceci Regardez le Implémentation de code spécifique d'une liste à chaînage unique

typedef struct LNode{     
    ElemType data;          //数据域    
    struct LNode *next;     //指针域，用来指向本节点的直接后继
 }LNode,*LinkList;           //定义节点，以及头指针

De nombreux étudiants ne peuvent pas distinguer la relation et la différence entre le pointeur principal, le nœud principal et le premier nœud. Faisons une distinction simple ci-dessous. .

Pointeur principal : c'est un pointeur vers la liste chaînée. Si la liste chaînée a un nœud principal, elle pointera vers le nœud principal :

Nœud principal : un auxiliaire avant. le premier nœud. Nœud, son suivant pointe vers le premier nœud

Le premier nœud : C'est un nœud, la variable de données stocke les premières données, et la variable pointeur suivante pointe vers le deuxième nœud

Ce qu'il convient de noter ici, c'est que le pointeur principal est un élément nécessaire d'une liste chaînée, mais pas le nœud principal. Alors, quelle est la signification de l'existence du nœud principal ?

Ma compréhension personnelle est de rendre les opérations d'insertion et de suppression du premier nœud cohérentes avec les opérations des nœuds suivants. Sinon, lorsque nous modifions le premier nœud, nous devons modifier le pointeur de tête.

S'il n'y a pas de nœud principal, le pointeur principal pointe directement vers le premier nœud.

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!