CS- semaine 5

Explication détaillée de la structure des données: du tableau à l'arbre, puis à la table de hachage

Cet article traite de plusieurs structures de données communes en profondeur, notamment des tableaux, des listes liées, des arbres de recherche binaires (BST) et des tables de hachage, et explique leur organisation en mémoire et leurs avantages et inconvénients.

Structure d'information et structure de données abstraite

La structure de l'information fait référence à la façon dont les informations sont organisées en mémoire, tandis que les structures de données abstraites sont notre compréhension conceptuelle de ces structures. Comprendre les structures de données abstraites nous aide à mieux mettre en œuvre diverses structures de données dans la pratique.

---

Pile et file d'attente

Les files d'attente sont une structure de données abstraite qui suit le principe FIFO (premier dans, premier sorti), similaire à l'attente en ligne. Ses principales opérations incluent la mise en file d'attente (ajoutant des éléments à la queue de la file d'attente) et la désactivation (en supprimant les éléments de la tête de la file d'attente).

La pile suit le principe LIFO (dernier dans le premier sortie), tout comme l'empilement d'une plaque. Ses opérations incluent la poussée (ajoutant des éléments au sommet de la pile) et en retirant les éléments supérieurs de la pile).

---

Tableau

Un tableau est une structure qui stocke en continu les données en mémoire. Comme le montre la figure ci-dessous, les tableaux occupent l'espace de stockage continu en mémoire.

D'autres programmes, fonctions et variables peuvent exister en mémoire, ainsi que des données redondantes qui ont été utilisées auparavant. Si vous devez ajouter de nouveaux éléments au tableau, vous devez réaffecter la mémoire et copier l'intégralité du tableau, qui peut être inefficace.

Bien que la pré-allocation de trop de mémoire puisse réduire les opérations de copie, elle gaspillera les ressources du système. Par conséquent, il est crucial d'allouer la mémoire en fonction des besoins réels.

---

Liste de liens

Les listes liées sont de puissantes structures de données qui permettent la concaténation des valeurs situées dans différentes régions de mémoire dans une liste et prennent en charge l'expansion ou la réduction dynamique.

Chaque CS- semaine 5 contient deux valeurs: la valeur de données et un pointeur vers le CS- semaine 5 suivant. La valeur du pointeur du dernier CS- semaine 5 est nul, indiquant la fin de la liste liée.

En langue C, les CS- semaine 5s peuvent être définis comme suit:

 <code class="c">typedef struct node { int number; struct node *next; } node;</code>

L'exemple suivant montre le processus de création d'une liste liée:

Les inconvénients des listes liées incluent la nécessité de pointeurs de stockage de mémoire supplémentaires et l'incapacité d'accès directement aux éléments via des index.

---

Arbre de recherche binaire (BST)

Un arbre de recherche binaire est une structure d'arbre qui stocke, recherche et récupère efficacement les données.

Les avantages de BST sont dynamiques et l'efficacité de recherche (O (log n)), et l'inconvénient est que l'efficacité de recherche tombe à O (n) lorsque l'arbre est déséquilibré et nécessite des pointeurs de stockage de mémoire supplémentaires.

---

Table de hachage

Une table de hachage est similaire à un dictionnaire et contient des paires de valeurs clés. Il utilise une fonction de hachage pour cartographier les clés pour les indices de tableau, réalisant ainsi le temps de recherche moyen de O (1).

Les conflits de hachage (plusieurs clés mappés au même indice) peuvent être résolus par des listes liées ou d'autres méthodes. La conception des fonctions de hachage est cruciale pour les performances des tables de hachage. Un exemple de fonction de hachage simple est le suivant:

 <code class="c">#include <ctype.h> unsigned int hash(const char *word) { return toupper(word[0]) - 'A'; }</ctype.h></code>

Cet article est compilé sur la base du code source CS50X 2024.

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!