Quels sont les quatre types de structures de stockage de données ?

Tutoriels recommandés : Tutoriel de fonctionnement et de maintenance de Windows

Les structures de stockage sont divisées en quatre catégories : stockage séquentiel, stockage lié, stockage d'index et stockage de hachage.

Les structures séquentielles et les structures de liens conviennent aux structures de mémoire.

La structure d'index et la structure de hachage conviennent à la mémoire externe et aux structures d'interaction de mémoire.

1. Stockage séquentiel

Dans un ordinateur, un ensemble d'unités de stockage avec des adresses consécutives sont utilisées pour stocker tableaux linéaires en séquence. Chaque élément de données est appelé une structure de stockage séquentielle d'une liste linéaire.

Caractéristiques :

1. Accédez de manière aléatoire aux éléments du tableau.

　2. Les opérations d'insertion et de suppression nécessitent des éléments mobiles.

2. Stockage lié

Utilisez un ensemble d'unités de stockage arbitraires dans l'ordinateur pour stocker les éléments de données de la table linéaire (Ce groupe d'unités de stockage peut être continu ou discontinu). Il n'est pas nécessaire que les éléments logiquement adjacents soient également physiquement adjacents. Par conséquent, il ne présente pas les faiblesses de la structure de stockage séquentielle, mais il perd également l'avantage de l'accès aléatoire à la liste séquentielle.

Caractéristiques :

1. La densité de stockage est plus petite que la structure de stockage séquentielle (chaque nœud est constitué de données champs Il se compose d'un champ de pointeur et d'un champ de pointeur, donc si le même espace est plein, l'ordre sera supérieur à celui du stockage chaîné).
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.

3. Stockage d'index

En plus de créer des informations sur les nœuds de stockage, des tables d'index supplémentaires sont également créées pour identifier L'adresse du nœud. La table d'index se compose de plusieurs entrées d'index.

Caractéristiques :

La structure de stockage d'index utilise le numéro d'index du nœud pour déterminer l'adresse de stockage du nœud. L'avantage est que la vitesse de récupération est rapide, mais l'inconvénient est que des tables d'index supplémentaires sont ajoutées, ce qui occupe plus d'espace de stockage.

4. Stockage de hachage

Le stockage de hachage, également connu sous le nom de stockage de hachage, est une méthode qui tente de stocker données Une technologie de recherche qui établit une certaine correspondance entre l'emplacement de stockage d'un élément et son code clé.

L'idée de base du stockage de hachage est la suivante : la valeur clé du nœud détermine l'adresse de stockage du nœud. En plus d’être utilisée pour la recherche, la technologie de hachage peut également être utilisée pour le stockage.

Caractéristiques :

Le hachage est un développement du stockage en matrice. Par rapport aux baies, le hachage La vitesse d'accès aux données est. supérieur à celui du tableau, car l'emplacement de stockage des données dans le tableau peut être trouvé sur la base d'une partie des données stockées et les données sont accessibles rapidement. La vitesse d'accès au hachage idéale est très rapide, contrairement au tableau. Dans le processus de parcours, certains éléments du contenu du tableau stocké sont utilisés comme entrée de la fonction de mappage. La sortie de la fonction de mappage est l'emplacement des données stockées. Cette vitesse d'accès permet d'économiser la mise en œuvre du parcours du tableau. la complexité temporelle peut être considérée comme O( 1) et la complexité temporelle du parcours du tableau est O(n).

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!