Quelle est la structure des données d'un ordinateur ?

La structure des données est la façon dont les ordinateurs stockent et organisent les données. Elle fait référence à un ensemble d'éléments de données qui ont une ou plusieurs relations spécifiques les uns avec les autres ; elle étudie la structure logique des données, la structure physique des données et les relations entre eux. les interrelations, définir les opérations appropriées pour cette structure, concevoir les algorithmes correspondants et s'assurer que la nouvelle structure obtenue après ces opérations conserve toujours le type de structure d'origine.

L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.

Structure des données

La structure des données est la façon dont les ordinateurs stockent et organisent les données. Une structure de données fait référence à un ensemble d'éléments de données qui entretiennent une ou plusieurs relations spécifiques les uns avec les autres. Souvent, des structures de données soigneusement sélectionnées peuvent conduire à une plus grande efficacité de fonctionnement ou de stockage. Les structures de données sont souvent liées à des algorithmes de récupération et à des techniques d'indexation efficaces.

Définition du nom

La structure de données fait référence à une collection d'éléments de données qui ont une ou plusieurs relations les uns avec les autres et aux relations entre les éléments de données de la collection. Marqué comme :
Data_Structure=(D,R)
où D est un ensemble d'éléments de données et R est un ensemble fini de relations entre tous les éléments de l'ensemble.

(1) Structures couramment utilisées

1 Tableau : En programmation, pour faciliter le traitement, plusieurs variables du même type sont organisées sous une forme ordonnée. Ces collections d'éléments de données similaires disposés dans l'ordre sont appelées tableaux. En langage C, les tableaux sont des types de données construits. Un tableau peut être décomposé en plusieurs éléments de tableau, qui peuvent être des types de données de base ou des types construits. Par conséquent, selon le type d'éléments du tableau, les tableaux peuvent être divisés en diverses catégories telles que les tableaux numériques, les tableaux de caractères, les tableaux de pointeurs et les tableaux de structure.

2. Pile : Il s'agit d'une liste linéaire spéciale qui ne peut être insérée et supprimée qu'à une extrémité. Il stocke les données selon le principe du premier entré, dernier sorti. Les données qui entrent en premier sont poussées vers le bas de la pile et les dernières données se trouvent en haut de la pile. Lorsque les données doivent être lues, les données sont extraites. du haut de la pile (les dernières données sont lues en premier).

3. File d'attente : Un tableau linéaire spécial qui permet uniquement les opérations de suppression à l'avant du tableau (avant) et les opérations d'insertion à l'arrière (arrière) du tableau. L'extrémité qui effectue l'opération d'insertion est appelée la queue de la file d'attente, et l'extrémité qui effectue l'opération de suppression est appelée la tête de la file d'attente. Les files d'attente organisent les données selon le principe du « premier entré, premier sorti » ou du « dernier entré, dernier sorti ». Lorsqu’il n’y a aucun élément dans la file d’attente, on parle de file d’attente vide.

4. Liste chaînée : Il s'agit d'une structure de stockage non continue et non séquentielle sur une unité de stockage physique. Elle peut représenter soit une structure linéaire, soit une structure non linéaire. L'ordre logique des éléments de données est lié via des pointeurs dans. la liste chaînée mise en œuvre séquentiellement. Une liste chaînée se compose d'une série de nœuds (chaque élément de la liste chaînée est appelé un nœud) et les nœuds peuvent être générés dynamiquement au moment de l'exécution. Chaque nœud se compose de deux parties : l'une est le champ de données qui stocke les éléments de données et l'autre est le champ de pointeur qui stocke l'adresse du nœud suivant.

5. Arbre : C'est un ensemble fini K contenant n (n>0) nœuds, et une relation N est définie dans K. N satisfait les conditions suivantes :

(1) Il y a et il n'y a qu'un seul nœud Point. K0, qui n’a pas de prédécesseur pour la relation N, est appelé nœud racine de l’arbre. Appelé racine.

(2) Sauf K0, chaque nœud dans K a et n'a qu'un seul prédécesseur pour la relation N.

(3) Chaque nœud de K peut avoir m successeurs (m>=0) pour la relation N.

6. Graphique : Il est composé de l'ensemble fini V des nœuds et de l'ensemble E des arêtes. Parmi eux, afin de le distinguer de la structure arborescente, les nœuds sont souvent appelés sommets dans les structures graphiques, 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.

7. Heap : En informatique, un tas est une structure de données arborescente spéciale, chaque nœud a une valeur. Habituellement, ce que nous appelons la structure de données d'un tas fait référence à un tas binaire. La caractéristique d'un tas est que le nœud racine a la valeur la plus petite (ou la plus grande), et les deux sous-arbres du nœud racine forment également un tas.

8. Table de hachage (également appelée table de hachage) : S'il existe un enregistrement avec la clé égale à K dans la structure, il doit se trouver à l'emplacement de stockage de f(K). Ainsi, les enregistrements recherchés peuvent être obtenus directement sans comparaison. Cette correspondance f est appelée fonction de hachage (Hash function), et la table construite sur la base de cette idée est une table de hachage.

9. Huit algorithmes de tri : les algorithmes de tri peuvent être divisés en tri interne et tri externe. Le tri interne consiste à trier les enregistrements de données en mémoire, tandis que le tri externe est dû au fait que les données triées sont très volumineuses et ne peuvent pas accueillir tous les enregistrements triés en un seul. temps. Le processus de tri nécessite un accès à la mémoire externe. Les algorithmes de tri internes courants incluent : le tri par insertion, le tri Hill, le tri par sélection, le tri à bulles, le tri par fusion, le tri rapide, le tri par tas, le tri par base, etc.

1. Structure logique des données : fait référence à la structure des données qui reflète la relation logique entre les éléments de données. La relation logique fait référence à la relation avant et après entre les éléments de données, quel que soit leur emplacement de stockage dans l'ordinateur.

Les structures logiques comprennent :

1) Ensembles
Il n'y a pas d'autre relation entre les éléments de la structure de données sauf qu'ils "appartiennent au même ensemble"

2) Structure linéaire
Il y a une paire d'éléments dans les données ; structure 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 ; -beaucoup de relations.

2. 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 informatique.
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 dans la machine des éléments de données et la représentation dans la machine des relations. Étant donné que les méthodes de mise en œuvre spécifiques incluent la séquence, la liaison, l'indexation, le hachage, etc., une structure de données peut être exprimée sous la forme d'une ou plusieurs structures de stockage.
Représentation en machine des éléments de données (méthode de mappage) : les éléments de données sont représentés par des chaînes de bits de bits binaires. Cette chaîne de bits est généralement appelée nœud. Lorsqu'un élément de données est constitué 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 champ de données. Par conséquent, un nœud est une représentation dans la machine (ou une image dans la machine) d'un élément de données. Représentation sur machine des relations (méthode de mappage) : La représentation sur 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 : les structures de stockage séquentielles et les structures de stockage en chaîne. Une carte séquentielle représente la relation logique entre les éléments de données au moyen de leurs positions relatives dans la mémoire. Les images non séquentielles représentent des relations logiques entre les éléments de données à l'aide de pointeurs qui indiquent les emplacements de stockage des éléments.

3. Opérations sur la structure des données

On pense généralement qu'une structure de données est organisée par éléments de données selon certaines connexions logiques. La description de la relation logique entre les éléments de données est appelée la structure logique des données ; les données doivent être stockées dans l'ordinateur, et la structure de stockage des données est en outre la forme de mise en œuvre de la structure des données et sa représentation dans l'ordinateur ; lorsque l'on discute d'une structure de données, nous devons également discuter des opérations effectuées sur ce type de données qui ont du sens. Une structure de données logique peut avoir plusieurs structures de stockage, et diverses structures de stockage affectent l'efficacité du traitement des données.

      Dans la conception de nombreux types de programmes, le choix des structures de données est une considération fondamentale en matière de conception. L'expérience de construction de nombreux systèmes à grande échelle montre que la difficulté de mise en œuvre du système et la qualité de la construction du système dépendent sérieusement de la sélection de la structure de données optimale. Souvent, une fois la structure des données déterminée, l’algorithme est facile à trouver. Parfois, les choses vont dans l’autre sens et nous choisissons une structure de données adaptée à un algorithme spécifique. Dans les deux cas, le choix de la structure de données appropriée est très important.
Après avoir choisi la structure des données, l'algorithme est également déterminé. Les données, et non les algorithmes, sont le facteur clé dans la construction du système. Cette idée a conduit à l’émergence de nombreuses méthodes de conception de logiciels et langages de programmation, et les langages de programmation orientés objet en font partie.
Lorsqu'un ordinateur résout un problème spécifique, il doit généralement passer par les étapes suivantes : Tout d'abord, il doit extraire un modèle mathématique approprié du problème spécifique, puis concevoir un algorithme (Algorithme) pour résoudre le modèle mathématique, et enfin compiler le programmez et effectuez des tests, ajustez jusqu'à ce que vous obteniez la réponse finale.
L'essence de la recherche d'un modèle mathématique est d'analyser le problème, d'extraire les objets opérationnels, de découvrir les relations entre ces objets opérationnels, puis de les décrire en langage mathématique. Lorsque les gens utilisent des ordinateurs pour résoudre des problèmes de calcul numérique, les modèles mathématiques utilisés sont décrits par des équations mathématiques. Les opérandes impliqués sont généralement des données entières simples, réelles et logiques, de sorte que le programmeur se concentre principalement sur les compétences en programmation plutôt que sur le stockage et l'organisation des données. Cependant, d'autres domaines d'application informatique sont les « problèmes informatiques non numériques ». Leurs modèles mathématiques ne peuvent pas être décrits par des équations mathématiques, mais par des structures de données. La clé pour résoudre de tels problèmes est de concevoir des structures de données appropriées pour décrire des problèmes informatiques non numériques. Le modèle mathématique des problèmes numériques est décrit par des structures telles que des tableaux linéaires, des arbres et des graphiques.
Les algorithmes informatiques sont étroitement liés à la structure des données. Les algorithmes dépendent tous de structures de données spécifiques. Les structures de données sont directement liées à la sélection et à l'efficacité des algorithmes. L'opération est complétée par l'ordinateur, ce qui nécessite la conception d'algorithmes d'insertion, de suppression et de modification correspondants. En d’autres termes, la structure de données doit également fournir des algorithmes pour diverses opérations définies par chaque type de structure. Un objet de données est une collection d'éléments de données ayant les mêmes propriétés et constitue un sous-ensemble de données. Les objets de données peuvent être finis ou infinis. Le traitement des données fait référence au processus opérationnel de recherche, d'insertion, de suppression, de fusion, de tri, de statistiques et de calculs simples sur les données.

(2) Classification de la structure

La structure des données fait référence à la relation entre les éléments de données dans la même classe d'éléments de données. Les structures de données sont respectivement une structure logique, une structure de stockage (structure physique) et des opérations de données. La structure logique des données est un modèle mathématique abstrait de problèmes spécifiques. Elle décrit les caractéristiques mathématiques des éléments de données et leurs relations. Parfois, la structure logique est simplement appelée structure de données. Une structure logique est une image stockée sur ordinateur, formellement définie comme (K, R) (ou (D, S)), où K est un ensemble fini d'éléments de données et R est un ensemble fini de relations sur K.

Selon les différentes caractéristiques de la relation entre les éléments de données, il existe généralement les quatre types de structures de base suivants :

⑴ Structure d'ensemble. La relation entre les éléments de données de cette structure est « appartenant au même ensemble ».

⑵Structure linéaire. Il existe une relation biunivoque entre les éléments de données de cette structure.

⑶Arborescence. Il existe une relation un-à-plusieurs entre les éléments de données de cette structure

⑷Structure graphique. Il existe une relation plusieurs-à-plusieurs entre les éléments de données de cette structure, également appelée structure de réseau. À partir du concept de structure de données introduit ci-dessus, nous pouvons savoir qu'une structure de données comporte deux éléments. L’un est un ensemble d’éléments de données et l’autre est un ensemble de relations. Formellement, une structure de données peut généralement être représentée par un tuple.

La forme de la structure de données est définie comme : la structure de données est un tuple : Data_Structure=(D, R), où D est un ensemble fini d'éléments de données et R est un ensemble fini de relations sur D. La caractéristique de la structure linéaire est qu'il existe une relation linéaire entre les éléments de données et que les éléments de données sont « disposés les uns après les autres ». Les types d'éléments de données dans un tableau linéaire sont les mêmes, ou un tableau linéaire est une structure linéaire composée d'éléments de données du même type. Il existe de nombreux exemples de tableaux linéaires dans les problèmes pratiques.Par exemple, le tableau d'informations sur le statut de l'étudiant est un tableau linéaire : le type des éléments de données dans le tableau est de type étudiant ; les éléments du tableau sont de type caractère, etc.
     Le tableau linéaire est la structure linéaire la plus simple, la plus basique et la plus couramment utilisée. Un tableau linéaire est une séquence finie de n (n>=0) éléments de données avec le même type de données, généralement écrit sous la forme : (a1, a2,… ai-1, ai, ai+1,…an), où n est la table est longue, lorsque n=0 on l'appelle une liste vide. Il dispose de deux méthodes de stockage : le stockage séquentiel et le stockage en chaîne. Ses principales opérations de base sont l'insertion, la suppression et la récupération.

La représentation (image) de la structure des données dans l'ordinateur est appelée structure physique (stockage) des données. Il comprend la représentation des éléments de données et la représentation des relations. Il existe deux méthodes de représentation différentes de la relation entre les éléments de données : le mappage séquentiel et le mappage non séquentiel, et ainsi deux structures de stockage différentes sont obtenues : la structure de stockage séquentielle et la structure de stockage en chaîne.

Méthode de stockage séquentiel : elle stocke les nœuds logiquement adjacents dans des unités de stockage physiquement adjacentes. La relation logique entre les nœuds est reflétée par la relation de contiguïté des unités de stockage. La représentation de stockage résultante est appelée structure de stockage séquentielle. La structure de stockage séquentielle est la méthode de représentation du stockage la plus élémentaire, généralement implémentée à l'aide de tableaux dans les langages de programmation.

Méthode de stockage de liens : elle ne nécessite pas que les nœuds logiquement adjacents soient également physiquement adjacents. La relation logique entre les nœuds est représentée par des champs de pointeur supplémentaires. La représentation de stockage résultante est appelée structure de stockage chaînée. La structure de stockage chaînée est généralement implémentée à l'aide de types de pointeurs dans les langages de programmation. Méthode de stockage d'index : en plus d'établir les informations sur le nœud de stockage, une table d'index supplémentaire est également établie. adresse du nœud.

Méthode de stockage Hash : Il s'agit de calculer directement l'adresse de stockage du nœud en fonction du mot-clé du nœud.

Dans la structure des données, logiquement (structure logique : relation logique entre les éléments de données), la structure des données peut être divisée en structure linéaire et structure non linéaire. La structure de stockage séquentielle d'une structure linéaire est une structure de stockage à accès séquentiel, et la structure de stockage liée d'une liste linéaire est une structure de stockage à accès aléatoire. Si un tableau linéaire est représenté par un stockage en chaîne, les adresses des unités de stockage entre tous les nœuds peuvent être continues ou discontinues. La structure logique n'a rien à voir avec la forme, le contenu, la position relative ou le nombre de nœuds contenus dans l'élément de données lui-même.

(3) Algorithme structurel La conception de l'algorithme dépend de la structure (logique) des données, et la mise en œuvre de l'algorithme dépend de la structure de stockage utilisée. La structure de stockage des données est essentiellement la réalisation de leur structure logique dans la mémoire de l'ordinateur. Afin de refléter de manière exhaustive la structure logique d'une donnée, son image dans la mémoire comprend deux aspects, à savoir les informations entre les éléments de données et la relation entre les éléments de données. entre. Différentes structures de données ont leurs opérations correspondantes. Les opérations sur les données sont des algorithmes d'opération définis sur la structure logique des données, tels que la récupération, l'insertion, la suppression, la mise à jour et le tri.

La structure des données est différente du type de données et de l'objet de données. Elle doit non seulement décrire l'objet de données du type de données, mais également décrire la relation entre les éléments de l'objet de données.

Un type de données est un ensemble de valeurs et un ensemble d'opérations définies sur cet ensemble de valeurs. Les types de données peuvent être divisés en deux catégories : les types atomiques et les types structurels. D’une part, dans les langages de programmation, chaque donnée appartient à un certain type de données. Les types spécifient explicitement ou implicitement la plage de valeurs des données, la manière dont elles sont stockées et les opérations autorisées. On peut considérer que les types de données sont des structures de données qui ont été implémentées en programmation. En revanche, lors du processus de programmation, lorsqu'une nouvelle structure de données doit être introduite, la structure de stockage des données est toujours décrite à l'aide des types de données fournis par le langage de programmation. La plus petite unité de données représentée dans un ordinateur est un bit d'un nombre binaire, appelé bit. Nous représentons un élément de données avec une chaîne de bits formée par une combinaison de plusieurs bits. Cette chaîne de bits est généralement appelée élément ou nœud. Lorsqu'un élément de données est constitué 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 champ de données. Les éléments ou nœuds peuvent être considérés comme l'image d'éléments de données dans l'ordinateur.

Un cadre de système logiciel doit être construit sur des données et non sur des opérations. Un module logiciel contenant des types de données abstraits doit contenir trois parties : définition, représentation et implémentation.

Pour chaque structure de données, il doit y avoir un ensemble d'opérations étroitement liées à celle-ci. Si le type et le nombre d'opérations sont différents, même si la structure logique est la même, la structure des données peut jouer des rôles différents.

Différentes structures de données ont différents ensembles d'opérations, mais les opérations suivantes sont indispensables :

1 Génération de la structure
2. Destruction de la structure
3. Recherche d'éléments de données qui répondent à des conditions spécifiées ; structure ;
4. Insérer de nouveaux éléments de données dans la structure ;
5. Supprimer les éléments de données existants dans la structure 
6. Traverser.

       Type de données abstrait : un modèle mathématique et un ensemble d'opérations définies sur le modèle. Un type de données abstrait est en fait la définition de cette structure de données. Parce qu'il définit une structure logique de données et un ensemble d'algorithmes sur cette structure. Les types de données abstraits peuvent être représentés par le triplet suivant : (D, S, P). D est un objet de données, S est un ensemble de relations sur D et P est un ensemble d'opérations de base sur D. La définition d'ADT est la suivante : nom du type de données abstrait ADT : {objet de données : (ensemble d'éléments de données), relation de données : (combinaison de tuples de relations de données), opération de base : (liste des fonctions opérationnelles)} ; Les types de données abstraits ont deux caractéristiques importantes :

Abstraction des données : lors de l'utilisation d'ADT pour décrire les entités traitées par le programme, l'accent est mis sur ses caractéristiques essentielles, les fonctions qu'il peut remplir et son interface avec les utilisateurs externes (c'est-à-dire comment le monde extérieur utilise cette méthode).

Encapsulation des données : séparez les caractéristiques externes d'une entité de ses détails de mise en œuvre interne et masquez ses détails de mise en œuvre interne aux utilisateurs externes.

Les données sont porteuses d'informations, qui peuvent être reconnues, stockées et traitées par des ordinateurs. C’est la matière première traitée par les programmes informatiques et les applications traitent toutes sortes de données. En informatique, ce qu'on appelle les données font l'objet d'un traitement informatique. Il peut s'agir de données numériques ou de données non numériques. Les données numériques sont des nombres entiers, des nombres réels ou des nombres complexes, principalement utilisés dans les calculs techniques, les calculs scientifiques et le traitement commercial. Les données non numériques comprennent des caractères, du texte, des graphiques, des images, des voix, etc.

L'élément de données est l'unité de base des données. Dans différentes conditions, les éléments de données peuvent également être appelés éléments, nœuds, sommets, enregistrements, etc. Par exemple, un enregistrement dans le tableau d'informations sur les étudiants dans le système de recherche d'informations sur les étudiants est appelé un élément de données. Parfois, un élément de données peut être composé de plusieurs éléments de données. Par exemple, chaque élément de données du tableau d'informations sur l'étudiant dans le système de gestion du statut de l'étudiant est un dossier d'étudiant. Il comprend des éléments de données tels que le numéro d'étudiant, le nom, le sexe, le lieu d'origine, la date de naissance et les notes. Ces éléments de données peuvent être divisés en deux types : l'un est appelé éléments élémentaires, tels que le sexe des étudiants, le lieu d'origine, etc. Ces éléments de données sont les plus petites unités qui ne peuvent pas être divisées lors du traitement des données ; comme les notes des élèves, il peut être subdivisé en termes plus petits tels que mathématiques, physique, chimie, etc. En règle générale, chaque dossier d'étudiant est consulté et traité comme une unité de base lors de la résolution de problèmes d'application pratiques.

Un objet de données ou une classe d'éléments de données est une collection d'éléments de données ayant les mêmes propriétés. Dans un problème spécifique, les éléments de données ont tous les mêmes propriétés (les valeurs des éléments ne sont pas nécessairement égales), appartiennent au même objet de données (classe d'éléments de données) et l'élément de données est une instance de la classe d'éléments de données. Par exemple, dans le réseau de circulation du système d'avis de circulation, tous les sommets sont une classe d'éléments de données. Le sommet A et le sommet B représentent chacun une ville et sont deux instances de la classe d'éléments de données. Les valeurs de leurs éléments de données sont A. et B. La structure des données fait référence à un ensemble d'éléments de données qui entretiennent une ou plusieurs relations les uns avec les autres. Dans tout problème, les éléments de données ne sont pas isolés. Il existe des relations d'une sorte ou d'une autre entre eux. Cette relation entre les éléments de données est appelée structure.

Pour plus de connaissances connexes, veuillez visiter la rubrique FAQ !

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!