Structure de stockage séquentielle d'une table linéaire

Le tableau linéaire est la structure de données la plus basique, la plus simple et la plus couramment utilisée. Une liste linéaire est un type de structure de données. Une liste linéaire est une séquence finie de n éléments de données ayant les mêmes caractéristiques.

Les tableaux linéaires sont principalement représentés par une représentation séquentielle ou une représentation en chaîne. Dans les applications pratiques, ils sont souvent utilisés sous des formes spéciales telles que des piles, des files d'attente et des chaînes.

La représentation séquentielle fait référence à l'utilisation d'un ensemble d'unités de stockage avec des adresses consécutives pour stocker séquentiellement les éléments de données d'une table linéaire, appelée structure de stockage séquentielle ou mappage séquentiel d'une table linéaire. . Il utilise la « contiguïté de l'emplacement physique » pour représenter la relation logique entre les éléments de données du tableau linéaire et peut accéder de manière aléatoire à n'importe quel élément du tableau.

La structure de stockage résultante est une structure de stockage séquentielle. Habituellement, la structure de stockage séquentielle est décrite à l'aide d'un tableau dans un langage de programmation informatique (tel que c/c++).

Le principal avantage de la structure de stockage séquentiel est d'économiser de l'espace de stockage, car les unités de stockage allouées aux données sont toutes utilisées pour stocker les données des nœuds (indépendamment de la nécessité de spécifier la taille du tableau dans le langage c/c++), les relations logiques entre nœuds n'occupent pas d'espace de stockage supplémentaire. Lorsque cette méthode est adoptée, un accès aléatoire aux nœuds peut être obtenu, c'est-à-dire que chaque nœud correspond à un numéro de série, et l'adresse de stockage du nœud peut être directement calculée à partir de ce numéro de série. Cependant, le principal inconvénient de la méthode de stockage séquentiel est qu'elle n'est pas pratique à modifier. Lors de l'insertion et de la suppression de nœuds, il peut être nécessaire de déplacer une série de nœuds.

Cours recommandé : Tutoriel du langage C.

Code de structure de la structure de stockage séquentielle de table linéaire :

#define MAXSIZE 20    
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;    // 线性表当前长度
} SqList;

L'encapsulation de la structure de stockage séquentielle nécessite trois attributs :

Stockage Le la position de départ de l'espace, l'emplacement de stockage des données du tableau, est l'emplacement de stockage de l'espace de stockage de la table linéaire.

La capacité de stockage maximale de la table linéaire : la longueur du tableau MaxSize.

La longueur actuelle de la table linéaire : length.

Remarque : La longueur du tableau et la longueur actuelle de la table linéaire doivent être distinguées : la longueur du tableau est la longueur totale de l'espace de stockage pour stocker la table linéaire , et ne change généralement pas après l'initialisation. La longueur actuelle du tableau linéaire correspond au nombre d'éléments du tableau linéaire, qui va changer.

Les avantages et les inconvénients de la structure de stockage séquentielle de la table linéaire

La structure de stockage séquentielle de la table linéaire, lors du stockage et de la lecture des données, peu importe où elles se trouvent, la complexité temporelle est O(1). Lors de l'insertion ou de la suppression, la complexité temporelle est O(n).

Cela montre qu'il est plus adapté aux applications où le nombre d'éléments est relativement stable, les éléments ne sont pas fréquemment insérés et supprimés et davantage d'opérations sont utilisées pour accéder aux données.

Avantages :

Il n'est pas nécessaire d'ajouter un espace de stockage supplémentaire pour exprimer la relation logique entre les éléments du tableau.

Peut accéder rapidement aux éléments n'importe où dans le tableau.

Inconvénients :

Les opérations d'insertion et de suppression nécessitent de déplacer un grand nombre d'éléments.

Lorsque la longueur de la table linéaire change considérablement, il est difficile de déterminer la capacité de l'espace de stockage.

Il est facile de provoquer une « fragmentation » de l'espace de stockage.

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!