Définition
La structure de données est un ensemble d'éléments de données ayant des caractéristiques structurelles. Il étudie la structure logique des données et la structure physique des données, ainsi que l'interaction entre elles Relations, et conçoit les calculs correspondants pour cette définition de structure, et s'assure que la nouvelle structure obtenue après ces calculs conserve toujours le type de structure d'origine. En bref, une structure de données est un ensemble d'éléments de données qui ont une ou plusieurs relations spécifiques les uns avec les autres, c'est-à-dire un ensemble d'éléments de données avec une "structure". « Structure » fait référence à la relation qui existe entre les éléments de données, qui est divisée en structure logique et structure de stockage.
La structure logique et la structure physique des données sont deux aspects étroitement liés de la structure des données. Une même structure logique peut correspondre à des structures de stockage différentes. La conception de l'algorithme dépend de la structure logique des données, et la réalisation de l'algorithme dépend de la structure de stockage spécifiée.
Le contenu de recherche de la structure des données est la base de la construction de systèmes logiciels complexes, et sa technologie de base est la décomposition et l'abstraction. Les données peuvent être divisées en trois niveaux par décomposition ; puis par abstraction, abandonnant le contenu spécifique des éléments de données, la structure logique est obtenue. De même, en divisant les exigences de traitement en diverses fonctions, puis en faisant abstraction des détails de mise en œuvre, la définition de l'opération est obtenue. La combinaison des deux aspects ci-dessus peut transformer le problème en une structure de données. Il s'agit d'un processus allant du concret (c'est-à-dire des problèmes concrets) à l'abstrait (c'est-à-dire des structures de données). Ensuite, en augmentant la prise en compte des détails de mise en œuvre, la structure de stockage et le calcul de mise en œuvre sont encore obtenus, complétant ainsi la tâche de conception. Il s'agit d'un processus allant de l'abstraction (c'est-à-dire la structure des données) au concret (c'est-à-dire la réalisation concrète).
Objet de recherche
La structure logique des données
Référez-vous à la structure de données qui reflète la relation logique entre les éléments de données. La relation logique est entre les éléments de données. La relation entre avant et après, et n'a rien à voir avec leur emplacement de stockage dans l'ordinateur. La structure logique comprend :
1. Ensemble : Il n'y a pas d'autre relation entre les éléments de la structure de données, à l'exception de la relation mutuelle d'« appartenance au même ensemble » ;
2. Structure linéaire : les éléments de la structure de données ont une relation un à un ;
3. Structure arborescente : les éléments de la structure de données ont une relation un-à-plusieurs ;
4. Structure graphique : Les éléments de la structure de données ont une relation plusieurs-à-plusieurs.
La structure physique des données
fait référence à la forme de stockage de la structure logique des données dans l'espace de stockage de l'ordinateur.
La structure physique des données est la représentation de la structure des données dans l'ordinateur (également appelée image), qui comprend la représentation interne des éléments de données et la représentation interne des relations. Comme il existe plusieurs méthodes de mise en œuvre spécifiques telles que séquence, lien, index, hachage, etc., une structure de données peut être exprimée sous la forme d'une ou plusieurs structures de stockage.
Représentation dans la machine des éléments de données (méthode de mappage) : une chaîne de bits de bits binaires (bit) est utilisée pour représenter les éléments de données. Ce type de chaîne de bits est généralement appelé nœud. Lorsqu'un élément de données se compose de plusieurs éléments de données, la chaîne de sous-bits correspondant à chaque élément de données dans la chaîne de bits est appelée un champ de données. Par conséquent, le nœud est la représentation interne (ou image interne) de l'élément de données.
Représentation dans la machine des relations (méthode de mappage) : La représentation dans la machine des relations entre les éléments de données peut être divisée en images séquentielles et en images non séquentielles. Deux structures de stockage couramment utilisées : la structure de stockage séquentiel et la structure de stockage en chaîne. Le mappage de séquence utilise la position relative des éléments dans la mémoire pour représenter la relation logique entre les éléments de données. Le mappage non séquentiel utilise des pointeurs qui indiquent les emplacements de stockage des éléments pour représenter les relations logiques entre les éléments de données.
Structure de stockage des données
La forme de stockage de la structure logique des données dans l'espace de stockage informatique est appelée structure physique des données (également appelée structure de stockage). D'une manière générale, la structure logique d'une structure de données peut être exprimée sous la forme d'une variété de structures de stockage selon les besoins. Les structures de stockage courantes incluent le stockage séquentiel, le stockage en chaîne, le stockage d'index et le stockage de hachage.
La caractéristique de la structure de stockage séquentiel des données est : la relation logique entre les éléments de données est exprimée par la position relative de l'élément dans la mémoire ; la caractéristique du stockage non séquentiel est : la donnée est exprimée par le pointeur indiquant l'adresse de stockage de l'élément La relation logique entre les éléments.
Classification
Il existe de nombreux types de structures de données. D'une manière générale, les données sont simplement classées selon leur structure logique, y compris les structures linéaires et non linéaires.
Structure linéaire
En termes simples, une structure linéaire signifie que chaque nœud de la table a une relation linéaire. Si elle est décrite dans le langage de la structure de données, la structure linéaire doit inclure les points suivants :
1. La structure linéaire est un ensemble non vide.
2. La structure linéaire a un et un seul nœud de départ et un seul nœud de fin.
3. Tous les nœuds de la structure linéaire ont au plus un nœud prédécesseur direct et un nœud successeur direct.
Les tables linéaires sont des structures linéaires typiques, et les piles, les files d'attente et les chaînes sont toutes des structures linéaires.
Structure non linéaire
En termes simples, une structure non linéaire signifie qu'il existe plusieurs correspondances entre chaque nœud de la table. Si elle est décrite dans le langage de structure de données, la structure non linéaire doit inclure les points suivants :
1. La structure non linéaire est un ensemble non vide.
2. Un nœud d'une structure non linéaire peut avoir plusieurs nœuds prédécesseurs directs et plusieurs nœuds successeurs directs.
Dans les applications pratiques, les structures de données telles que les tableaux, les tableaux généralisés, les structures arborescentes et les structures graphiques sont toutes des structures non linéaires.
Structures de données couramment utilisées
Au cours du développement de l'informatique, les structures de données ont également évolué. Les structures de données couramment utilisées dans la conception de programmes sont les suivantes.
Tableau (tableau)
Array est un type de données agrégé, qui est une collection de plusieurs variables du même type organisées ensemble de manière ordonnée. On peut dire que le tableau est la structure de données la plus basique, qui correspond à divers langages de programmation. Un tableau peut être décomposé en plusieurs éléments de tableau. Selon les types d'éléments de données, le tableau peut être divisé en tableaux d'entiers, tableaux de caractères, tableaux à virgule flottante, tableaux de pointeurs et tableaux de structures. Les tableaux peuvent également être exprimés sous des formes unidimensionnelles, bidimensionnelles et multidimensionnelles.
Empiler
Stack est une table linéaire spéciale. Il ne peut insérer et supprimer des nœuds de données que sur une extrémité fixe d'une table. La pile stocke les données selon le principe du dernier entré, premier sorti, c'est-à-dire que les premières données insérées seront poussées au bas de la pile et les dernières données insérées seront au sommet de la pile. Lors de la lecture des données, elles seront lues une par une depuis le haut de la pile. La pile est souvent utilisée pour la protection sur site des données importantes dans les programmes en langage assembleur. Lorsqu'il n'y a pas de données dans la pile, cela s'appelle une pile vide.
File d'attente
La file d'attente est similaire à la pile, et c'est aussi une table linéaire spéciale. Contrairement à la pile, la file d'attente n'autorise les opérations d'insertion qu'à une extrémité de la table et les opérations de suppression à l'autre extrémité. D'une manière générale, la fin qui effectue l'opération d'insertion est appelée la queue de la file d'attente et la fin qui effectue l'opération de suppression est appelée la tête de la file d'attente. Lorsqu'il n'y a aucun élément dans la file d'attente, elle est appelée file d'attente vide.
Liste liée
La liste chaînée est une structure de données dans laquelle les éléments de données sont stockés selon une structure de stockage chaînée. Cette structure de stockage est physiquement non continue. La liste chaînée est composée d'une série de nœuds de données, et chaque nœud de données comprend deux parties : un champ de données et un champ de pointeur. Parmi eux, le champ de pointeur contient l'adresse où l'élément suivant dans la structure de données est stocké. L'ordre logique des éléments de données dans la structure de la liste chaînée est réalisé par l'ordre des liens des pointeurs dans la liste chaînée.
Arbre
L'arbre est une structure non linéaire typique, qui est un ensemble fini K comprenant deux nœuds. Dans l'arborescence, il y a un et un seul nœud racine, qui n'a pas de nœud prédécesseur. Tous les autres nœuds de l'arborescence ont un et un seul nœud prédécesseur, et il peut y avoir deux nœuds successeurs, m≥0.
Graphique
Le graphique est une autre structure de données non linéaire. Dans la structure du graphe, les nœuds de données sont généralement appelés sommets et les arêtes sont des paires ordonnées de sommets. S'il y a une arête entre deux sommets, cela signifie que les deux sommets ont une relation adjacente.
Tas
Le tas est une structure de données en forme d'arbre spéciale, et les tas généralement discutés sont des tas binaires. La caractéristique du tas est que la valeur du nœud racine est la plus petite ou la plus grande parmi tous les nœuds, et les deux sous-arbres du nœud racine sont également une structure de tas.
Table de hachage (Hash)
La table de hachage est dérivée de la fonction de hachage (fonction de hachage). L'idée est que s'il y a un enregistrement avec le mot-clé égal à T dans la structure, alors il doit L'enregistrement peut être trouvé dans l'emplacement de stockage de F(T), de sorte que l'enregistrement vérifié puisse être obtenu directement sans opération de comparaison .
Algorithmes couramment utilisés
Le contenu de la recherche de structure de données : comment organiser les données selon une certaine structure logique, et choisir la méthode de représentation de stockage appropriée pour stocker les données organisées dans la structure logique Dans la mémoire de l'ordinateur. Le but de la recherche d'algorithmes est de traiter les données plus efficacement et d'améliorer l'efficacité de l'exploitation des données. Le calcul des données est défini sur la structure logique des données, mais la réalisation spécifique du calcul doit être effectuée sur la structure de stockage. En règle générale, il existe les opérations courantes suivantes :
(1) Recherche. La récupération consiste à trouver des nœuds qui remplissent certaines conditions dans la structure de données. Généralement, étant donné la valeur d'un certain champ, recherchez le nœud avec la valeur du champ.
(2) Insérer. Ajoutez de nouveaux nœuds à la structure de données.
(3) Supprimer. Supprime le nœud spécifié de la structure de données.
(4) Mise à jour. Modifiez la valeur d'un ou plusieurs champs du nœud spécifié.
(5) Trier. Réorganisez les nœuds dans un ordre spécifié. Par exemple, incrémenter ou décrémenter.