Les données stockées dans la mémoire de l'ordinateur représentent la totalité des zéros et des unités (bits). Les bits sont combinés dans des séquences: octets, mots, etc. Chaque site mémoire vivequi peut accueillir un octet ou un mot attribué le numéro de séquence (adresse).
Quel sens est conclu dans les données, quels symboles ils sont exprimés - lettrage ou numérique, ce qui signifie quelque chose ou une autre - tout cela est déterminé par le programme de traitement. Toutes les données nécessaires à la résolution de tâches pratiques sont divisées en plusieurs différents types, de plus, le concept un type associé non seulement à la présentation des données dans l'espace d'adressage, mais aussi avec À titre de traitement.
Toute données peut être attribuée à l'un des deux types: le principal (simple), dont la forme est définie par l'architecture de l'ordinateur ou un complexe, conçu par l'utilisateur pour résoudre des tâches spécifiques.
Ce type de type est - symboles, chiffres, etc. Éléments, dont la nouvelle broyage n'a pas de sens. Des données élémentaires, des structures (types complexes) des données sont formées.
Certaines structures:
· Déployer(La fonction avec la zone de définition finale) est un ensemble simple d'éléments du même type de données, un moyen d'exploiter un groupe de données par le même type. Un élément de tableau séparé est défini par l'index. Un tableau peut être unidimensionnel, bidimensionnel, etc. Les espèces de baies unidimensionnelles de longueur variable sont des structures de type anneau, pile, file d'attente et file bilatérale.
· Enregistrer(Production Cartesovo) - ensemble d'éléments de données de différents types. Dans le cas le plus simple, l'enregistrement contient un nombre constant d'éléments appelés des champs. L'ensemble des enregistrements de la même structure est appelé déposer. (Le fichier s'appelle également un ensemble de données dans mémoire externePar exemple, sur disque magnétique). Pour pouvoir extraire des enregistrements individuels du fichier, chaque enregistrement est attribué à un nom ou un numéro unique qui sert d'identifiant et est situé dans un champ séparé. Cet identifiant est appelé clé.
Ces structures de données qu'un tableau ou un enregistrement occupent un montant permanent en mémoire, ils sont donc appelés structures statiques. Les structures statiques s'appliquent également beaucoup de.
Il existe un certain nombre de structures qui peuvent changer leur longueur - le soi-disant structures dynamiques. Ceux-ci incluent le bois, la liste, le lien.
Une structure importante pour la mise en place d'éléments que l'espace d'adresse non linéaire est requis est bois. Il existe un grand nombre de structures de données pouvant être représentées comme des arbres. Ceci, par exemple, la classification, les structures hiérarchiques, récursives et autres. Plus de détails sur les arbres sont racontés au paragraphe 1.2.1.
Figure. 1.1. Classification des types de données
1.1.2. Structures enchères ou modèles de données.
Au-dessus, nous avons examiné plusieurs types de structures qui sont des ensembles d'éléments de données: tableau, bois, enregistrement. Un type de données plus complexe peut inclure ces structures en tant qu'éléments. Par exemple, les éléments d'enregistrement peuvent être une matrice, une pile, un bois, etc.
Il existe une grande variété de types de données complexes, mais des études menées sur un grand matériau pratique ont montré que parmi eux peut être distingué par plusieurs des plus courants. Les structures généralisées sont également appelées modèles de donnéescar Ils reflètent la présentation des données du monde réel de l'utilisateur.
Tout modèle de données doit contenir trois composants:
1. structure de données - Décrit le point de vue de l'utilisateur pour représenter les données.
2. ensemble d'opérations autorisées effectué sur la structure de données. Le modèle de données suppose au minimum la présence d'une langue de définition de données (noyau) décrivant la structure de leur stockage et de leur langage de manipulation de données (NMID), qui inclut l'extraction et la modification des données.
3. limitations de l'intégrité - Mécanisme de conformité des données domaine Basé sur les règles formellement décrites.
Dans le processus de développement historique dans le SGBM, les modèles de données suivants ont été utilisés:
· hiérarchique
· réseau
· relationnel.
DANS dernièrement tout plus important Accompose une approche orientée objet de la présentation de données.
1.2.Methods d'accès aux données
Les problèmes de présentation de données sont étroitement liés aux opérations, avec lesquelles ces données sont traitées. Ces opérations comprennent: sélection, changement, inclusion et une exception Les données. La base de toutes les opérations répertoriées est l'opération accèsqui ne peut être considéré comme indépendamment de la méthode de présentation.
Dans les tâches de recherche, il est supposé que toutes les données sont stockées en mémoire avec une certaine identification et, parlant d'accès, moyennes, d'abord, accès aux données (appelées clés), identifie sans ambiguïté l'ensemble de données associé.
Devons organiser l'accès à un fichier contenant un ensemble d'enregistrements identiques, chacun ayant signification unique Champ clé. Le moyen le plus simple de rechercher est de visualiser séquentiellement chaque entrée du fichier jusqu'à ce qu'elle soit trouvée, dont la valeur clé satisfait aux critères de recherche. Évidemment, cette méthode est très inefficace, car les entrées du fichier ne sont pas commandées par la valeur du champ clé. Le tri des enregistrements dans le fichier n'est pas non plus applicable, car il nécessite encore plus de temps et doit être exécuté après que chaque addition soit ajoutée. Par conséquent, ils viennent comme suit - les clés ainsi que les pointeurs vers les entrées correspondantes du fichier sont copiées sur une autre structure qui vous permet d'effectuer rapidement le tri et les opérations de recherche. Lors de l'accès à des données, au début, dans cette structure, la valeur de clé correspondante est trouvée, puis le pointeur est stocké avec le pointeur avec celui-ci.
Il existe deux classes de méthodes qui implémentent l'accès aux données clés:
· méthodes de recherche d'arbres,
· méthodes d'éclosion.
1.2.1. Compteurs de recherche de bois
Définition: L'arborescence est appelée un ensemble fini constitué d'un ou plusieurs éléments appelés nœuds, tels que:
1. entre les nœuds, il existe un rapport entre le type "Source - généré";
2. il n'y a qu'un seul noeud qui n'a pas de nœud source. On l'appelle la racine;
3. tous les nœuds sauf la racine n'ont qu'une source; Chaque nœud peut avoir plusieurs nœuds générés;
4. le rapport "Source - généré" n'est valable que dans une direction, c'est-à-dire Aucun descendant de certains nœuds ne peut être un ancêtre pour lui.
Le nombre de nœuds individuels générés (le nombre de sous-arbres de cette racine) est appelé degré. Un nœud avec un degré zéro s'appelle une feuille ou un nœud de terminal. Valeur maximum Les degrés de tous les nœuds de cet arbre ont appelé degré de bois.
Si dans un arbre entre les nœuds générés comportant une source commune, leur commande est considérée comme essentielle, l'arbre est appelé commandé. Dans les tâches de recherche, les arbres commandés sont presque toujours considérés.
Un arbre commandé dont le degré n'est pas plus que 2 appelé binaire Arbre. L'arbre binaire est particulièrement souvent utilisé lors de la recherche de RAM. Algorithme de recherche: Initialement, l'argument de recherche est comparé à la clé située à la racine. Si l'argument coïncide avec la clé, la recherche est terminée, si elle ne coïncide pas, alors dans le cas où l'argument est inférieur à la clé, la recherche se poursuit dans le sous-arbre de gauche et dans le cas où la clé est dans le Sous-arbre droit. Augmentation du niveau de 1, répétez la comparaison en comptant la racine de nœud actuelle.
Exemple: Laissez la liste des élèves contenant leurs noms et la performance moyenne des progrès (voir tableau 1.1). Le nom de famille de l'étudiant est utilisé comme clé. Supposons que tous les enregistrements ont une longueur fixe, le numéro d'enregistrement peut être utilisé comme un pointeur. Le décalage de l'écriture dans le fichier dans ce cas sera calculé comme ([Number_aping] -1) * [longueur_instation] . Laissez l'argument de recherche "Petrov". La figure 1.2 montre l'un des arborescences de recherche binaire possibles et le chemin de recherche de cette base de données.
|
Tableau 1.1. |
|
|
Vasilyev |
|
|
Kuznetsov |
|
|
Tikhomirov |
|
Figure. 1.2. Recherche de bois binaire
Notez que voici la règle suivante de comparaison des variables de chaîne: on pense que la valeur du symbole correspond à son numéro de séquence dans l'alphabet. Par conséquent, "et" moins "à", et "à" moins "avec". Si les caractères actuels des lignes comparés sont coïncidés, les caractères sont comparés dans les positions suivantes.
Les arbres binaires sont particulièrement efficaces dans le cas où de nombreuses clés ne sont pas connues à l'avance ou lorsque cet ensemble change de manière intensive. Évidemment, avec une variable plusieurs clés, il vaut mieux avoir arbre équilibré.
Définition: L'arbre binaire est appelé équilibré (équilibré) si la hauteur de la sous-arbre gauche chaque nœud diffère de la hauteur du sous-arbre droit au plus 1.
Lors de la recherche de données dans la mémoire externe, un problème très important est le problème de la réduction du nombre de mouvements de données de la tuyauterie dans la RAM. Par conséquent, dans ce cas, comparé aux arbres binaires, des arbres hautement ramifiés seront plus rentables - parce que Leur hauteur est inférieure, alors lorsque la recherche est requise, moins de contacter la mémoire externe. Dans ce cas, la plus grande application a été obtenue dans des arbres (équilibré)
Définition: Dans une ordonnance d'arbre N, un arbre hautement ramifiant de degré 2n + 1, qui présente les propriétés suivantes:
- Chaque nœud, à l'exception de la racine, contient au moins N et pas plus de 2n clés.
- La racine contient au moins une et pas plus de 2n clés.
- Toutes les feuilles sont situées à un niveau.
- Chaque nœud intermédiaire contient deux listes: ordonnée d'augmenter la liste de la liste des touches et de la liste correspondante des pointeurs (pour les nœuds de feuilles, il n'y a pas de panneaux de signalisation).
Pour un tel arbre:
· les comparatifs peuvent être relativement simplement organisés, car Toutes les feuilles sont situées à un niveau;
· lors de l'ajout et de la modification des touches, toutes les modifications sont limitées, en règle générale, par un nœud.
Figure. 1.3.Le bois équilibré
DANS-Deevo, dans lequel les significations vraies ne sont contenues que dans les feuilles (nœuds terminaux), appelées DANS +- arbre. Dans les nœuds internes d'un tel arbre contient les séparateurs de clés qui définissent la plage de modifications apportées aux touches.
Plus sur divers types d'arbres équilibrés, ainsi que des méthodes de mise en œuvre, vous pouvez lire dans la littérature, dont la liste est donnée à la fin de la page. Il convient de noter que B.- Les arbres sont mieux adaptés uniquement à l'organisation d'un accès à des structures de données assez simples (unidimensionnelles). Pour que l'accès à des structures plus complexes, tels que les données spatiales (multidimensionnelles), on utilise de plus en plus de plus degré de consommation. R-Dervia.
R-bois ( R-Tree) Il s'agit d'une structure d'index d'accès aux données spatiales proposées par A. Guttman (Université de Californie, Berkeley). L'arbre R permet une exécution arbitraire des opérations d'ajout, de suppression et de recherche de données sans ré-indexation périodique.
Les enregistrements sont utilisés pour soumettre des données, chacune d'un identifiant unique (identifiant TUPLE). Dans chaque noeud d'extrémité (feuille) de l'arbre contient une vue du formulaire ( I, tuple-identifiant) où JE. - n.-Les pointes de parallélépiped contenant des données spatiales (il est également appelé rectangle de liaison minimale, MBR) et chaque élément de tuple-identifiant Contient la borne supérieure et inférieure du parallélépiped dans la mesure appropriée.
Les nœuds non consécutifs contiennent des enregistrements de type (I, pointeur d'enfant) où JE. Le parallélépipe minimum restrictif pour le MBR de tous les dérivés de nœuds par rapport à cela. Pointeur d'enfant. - Ceci est un pointeur sur les nœuds dérivés.
Laisser être M. et m. <= M/2 En conséquence, la quantité maximale et mimimale d'éléments pouvant être placés dans le nœud. Ensuite, les propriétés du r-arbre peuvent être décrites comme suit:
· R-Tree est un arbre fortement équilibré, c'est-à-dire Toutes les feuilles sont au même niveau.
· Le nœud racine a au moins deux descendants.
· Pour chaque élément (je, pointeur d'enfant) En nœud non consécutif JE. est un le moins possible Parallélépipède, c'est-à-dire Contient toutes les parallelpipedesd de nœuds dérivés.
· Chaque nœud de terminal (feuille) contient de m. avant que M. Indice des enregistrements.
· Pour chaque enregistrement d'index (I, tuple-identifiant) Dans le nœud Terminal JE. est un parallélépiped qui contient n.- l'objet dimensionnel des données indiquant tuple-identifiant .
1.2.2.Hechancification
Cette méthode est utilisée lorsque toutes les touches multiples sont connues à l'avance et pendant le temps de traitement peuvent être placées dans la RAM. Dans ce cas, une fonction spéciale est construite, affichant plusieurs clés multiples à une pluralité de pointeurs, appelée fonction de hachage (du mot anglais "à hachage" - coupé, écraser). Avoir une telle fonction, vous pouvez calculer l'adresse de l'entrée dans le fichier en fonction de la clé de recherche spécifiée. En général, les données clés utilisées pour déterminer l'adresse d'adresse sont organisées comme une table appelée table de hachage.
Si de nombreuses clés sont inconnues à l'avance ou très grandes, alors de l'idée d'un calcul sans ambiguïté de l'adresse d'adresse par sa clé refuse, et la fonction de hachage est considérée comme une fonction de diffusion de plusieurs clés dans de nombreuses adresses.
Annotation: Le concept global de la structure de données en tant qu'artiste qui organise des données à stocker, d'ajouter et de supprimer, de rechercher, etc. La réalisation de certaines structures sur la base des autres, en particulier, la mise en œuvre de la matrice basée sur le massif. Les plus importantes des structures de données les plus simples sont données: la file d'attente et la pile, ainsi que leur mise en œuvre continue basée sur le massif. De nombreux exemples d'utilisation de la pile dans la programmation sont donnés. L'enregistrement de polonais inverse de la formule (le fonctionnement de l'opération après arguments) est pris en compte et le procédé de calcul sur la machine de pile. À titre d'exemple d'utilisation de l'enregistrement de polonais inverse, le langage graphique PostScript est pris en compte. Le matériau est illustré par le projet "Calculatrice", mis en œuvre dans la langue C.
Structures de données
"Algorithmes + structures de données \u003d programmes". C'est le nom du livre de Niklaus Virut, le célèbre spécialiste de la programmation suisse, auteur de Pascal, Module-2, Oberon. Avec le nom de WIRTH, le développement d'une approche structurelle de la programmation est connecté. N.Virt est également appelé professeur brillant et auteur de manuels classiques.
Les deux composants des programmes alloués par N.VIRT sont également importants. Non seulement l'algorithme imparfait, mais également l'organisation infructueuse de travail avec des données peut entraîner un ralentissement des travaux du programme de dizaines et parfois de plusieurs fois. D'autre part, possession théorie de la programmation Et la capacité de l'appliquer systématiquement dans la pratique vous permet de développer rapidement efficacement et à la fois de beaux programmes esthétiquement.
Le concept général de la structure de données
Structure de données - Il s'agit d'un interprète qui organise des données avec des données, y compris leur stockage, l'ajout et la suppression, la modification, la recherche, etc. Structure de données Soutient un certain ordre d'accès à eux. La structure de données peut être considérée comme une sorte d'entrepôt ou de bibliothèque. Lorsque vous décrivez la structure de données, vous devez énumérer l'ensemble des actions qui lui sont possibles et décrivent clairement le résultat de chaque action. Nous appellerons de telles actions ordonnances. D'un point de vue logiciel, le système de prescription de structure de données correspond à un ensemble de fonctions qui fonctionnent sur des variables communes.
Les structures de données sont les plus correctement implémentées dans les langues orientées objet. En eux, la structure de données correspond à la classe, les données elles-mêmes sont stockées dans les variables de membre de classe (ou l'accès aux données sont effectuées via des variables d'éléments), le système de prescription correspond à un ensemble de méthodes de classe. En règle générale, dans la structure de données orientée objet Les langages sont implémentées comme une bibliothèque de classe standard: ce sont les soi-disant cours de conteneur Langue C ++ incluse dans la bibliothèque de classe standard Stlou des classes qui mettent en œuvre diverses structures de données de la bibliothèque Kit de développeur Java. Langue java.
Cependant, les structures de données sont également implémentées avec succès dans les langages de programmation traditionnels, tels que Fortran ou C. Dans ce cas, le style de programmation orienté objet doit être suivi: il est clairement attribué à un ensemble de fonctions qui fonctionnent avec la structure de données et limitent l'accès aux données uniquement par cet ensemble de fonctions. Les données elles-mêmes sont implémentées comme variables statiques (non globales). Lors de la programmation de la structure de données, deux fichiers avec des textes source sont configurés:
- header ou H-File, qui décrit l'interface de la structure de données, c'est-à-dire Un ensemble de prototypes d'entités correspondant au système de prescriptions de structure de données;
- le fichier de mise en œuvre ou un fichier C, qui définit les variables statiques qui stockent et accédent aux données et sont également implémentées par les fonctions correspondant à la structure de données de la structure de données
Structure de données généralement mis en œuvre sur la base d'un plus simple structure de basedéjà déjà implémenté ou basé sur un tableau et un ensemble de variables simples. Une description de la structure de données d'un point de vue logique doit être clairement distinguée. Il peut y avoir de nombreuses implémentations différentes, du point de vue logique (c'est-à-dire du point de vue de l'utilisateur externe), ils sont tous équivalents et diffèrent, peut-être une vitesse d'exécution des ordonnances.
Le concept de structure de données est tellement fondamental qu'il est difficile pour lui de trouver une définition simple. La tâche est simplifiée si vous essayez de formuler ce concept en ce qui concerne les types de données et de variables. Comme on le sait, le programme est l'unité de l'algorithme (procédures, fonctions) et les données traitées. Les données sont à son tour déterminées par des types de données de base et dérivés - des représentations "idéales" de dimensions fixes variables avec des ensembles d'opérations connues sur eux et leurs composants. Les variables sont les zones de mémoire nommées «affichées» des types de données construits.
Le programme Vous pouvez toujours sélectionner des groupes connectés indirectement (à l'aide des données dans les mêmes procédures et fonctions) et directement liées (selon les relations via des pointeurs) des variables. Ils sont dans la première approximation et peuvent être considérés comme des structures de données.
Les structures simples (basiques, primitiques) (types) des données et intégrées (structurées, composites, complexes) diffèrent. Les simulaires sont appelés de telles structures de données qui ne peuvent pas être disséquées sur des pièces composites, grandes que des bits. Du point de vue de la structure physique, il est important que dans cette architecture de la machine, dans ce système de programmation, nous pouvons toujours dire à l'avance, quelle sera la taille de ce type simple et quelle est la structure de son placement en mémoire . D'un point de vue logique, des données simples sont des unités indivisibles. Données intégrées des structures de données, des composants dont d'autres structures de données sont intégrées ou intégrées à leur tour. Les structures de données intégrées sont conçues par un programmeur utilisant des outils d'intégration de données fournis par les langages de programmation.
Selon l'absence ou la présence de liens explicitement spécifiés entre les éléments de données, des structures non connectées doivent être distinguées (vecteurs, tableaux, lignes, piles, files d'attente) et structures connectées (listes connectées).
Une caractéristique très importante de la structure de données est sa variabilité - une modification du nombre d'éléments et de (ou) des liaisons entre les éléments de la structure. Pour déterminer la variabilité de la structure, le fait de modifier les valeurs des éléments de données n'est pas reflété, car, dans ce cas, toutes les structures de données auraient une propriété de variabilité. Selon le signe de la variabilité, les structures statiques sont distinguées, dynamiques. La classification des structures de données sur le signe de la variabilité est illustrée à la Fig. 1.1. Les structures de données de base, statiques, semi-statiques et dynamiques sont caractéristiques de la RAM et sont souvent appelées structures opérationnelles. Les structures de fichiers sont conformes aux structures de données pour la mémoire externe.
Figure. 1.1. Classification des structures de données
Une caractéristique importante de la structure de données est la nature de la commande de ses éléments. Sous cette caractéristique de la structure peut être divisée en structures linéaires et non linéaires.
En fonction de la nature de la disposition mutuelle d'éléments en mémoire, des structures linéaires peuvent être divisées en structures avec une distribution séquentielle d'éléments en mémoire (vecteurs, chaînes, tableaux, piles, files d'attente) et structures avec une distribution connectée arbitraire d'éléments en mémoire (Listes simples connectées à double liaison). Un exemple de structures non linéaires - Listes multi-connectées, arbres, graphiques.
Dans les langages de programmation, le concept de "structures de données" est étroitement lié au concept de "types de données". Toutes les données, c'est-à-dire Les constantes, les variables, les valeurs des fonctions ou des expressions sont caractérisées par leurs types.
Les informations pour chaque type détermine de manière unique:
· 1) Structure Stockage du type spécifié, c'est-à-dire affectation de la mémoire et de la présentation de données dedans, d'une part, et une interprétation de la représentation binaire, de l'autre;
· 2) De nombreuses valeurs admissibles que l'un ou l'autre objet décrit peut avoir;
· 3) De nombreuses opérations autorisées applicables à l'objet décrit.
La structure de données est un ensemble de types physiquement (types de données) et logiquement (algorithme, fonctions) des variables interdépendantes et de leurs valeurs.
Notez que le concept de la structure de données est associé non seulement aux variables qui le composent, mais également aux algorithmes (fonctions), qui non seulement des variables de liaison logiquement, mais également déterminer les valeurs internes, qui doivent également être caractéristiques de ces données. structure. Par exemple, une séquence de valeurs positives placées dans une matrice et ayant une dimension variable (structure de données) peut avoir un limiteur zéro. Toutes les opérations pour la formation et la vérification de ce limiteur sont mises en œuvre par des fonctions. Ainsi, on peut dire qu'une partie importante de la structure des données "est cousue" dans les algorithmes de son traitement.
Vous savez que la méthode de détermination des variables via des types de données est caractérisée par le fait que, tout d'abord, le nombre de variables dans le programme est fixe et, d'autre part, la dimension ne peut pas être modifiée au cours de l'opération de programme. Si la relation entre ces variables est un caractère plus ou moins permanent, ces structures de données peuvent être appelées statiques.
Structure de données statique - Un ensemble de quantité fixe de dimensions constantes variables avec une nature constante des connexions entre eux
Et inversement, si l'un des paramètres de la structure de données est un nombre de variables, leur dimension ou leur interconnexion entre eux change au cours de l'opération de programme, ces structures de données sont appelées dynamiques.
Structure de données dynamique - un ensemble de variables, quantité, dimension ou nature de la relation entre les changements lors du fonctionnement des programmes.
Les structures de données dynamiques sont basées sur deux éléments linguistiques de programmation:
· Variables dynamiques, dont le nombre peut varier et finalement déterminé par le programme lui-même. De plus, la possibilité de créer des matrices dynamiques nous permet de parler de données de dimension variables;
· Pointeurs qui assurent la relation directe entre les données et la capacité de modifier ces liens.
Ainsi, près de la vérité et une telle définition: les structures de données dynamiques sont des variables dynamiques et des tableaux associés à des pointeurs.
En parlant de structures de données, vous ne devez pas oublier que les variables habituelles sont publiées en RAM (mémoire d'ordinateur interne). Par conséquent, généralement des structures de données sont liées à la mémoire. Cependant, il existe également une mémoire externe, qui dans la langue est disponible indirectement via des opérateurs (Pascal) ou des fonctions (C) fonctionnant avec des fichiers. Dans un mode d'accès arbitraire binaire, tout fichier est un analogue d'une zone de mémoire adressable directement illimitée, c'est-à-dire du point de vue du programme, il ressemble à la mémoire habituelle. Naturellement, le programme peut copier des variables de la mémoire à un emplacement de fichier arbitraire et en arrière, ce qui signifie organiser dans le fichier toutes les structures de données (y compris dynamiques).
La structure de données est un interprète qui organise des données avec des données, y compris leur stockage, l'ajout et la suppression, la modification, la recherche, etc. La structure de données conserve un certain ordre d'accès à eux. La structure de données peut être considérée comme une sorte d'entrepôt ou de bibliothèque. Lorsque vous décrivez la structure de données, vous devez énumérer l'ensemble des actions qui lui sont possibles et décrivent clairement le résultat de chaque action. Nous appellerons de telles actions par les prescriptions. D'un point de vue logiciel, le système de prescription de structure de données correspond à un ensemble de fonctions qui fonctionnent sur des variables communes.
Les structures de données sont les plus correctement implémentées dans les langues orientées objet. En eux, la structure de données correspond à la classe, les données elles-mêmes sont stockées dans les variables de membre de classe (ou l'accès aux données sont effectuées via des variables d'éléments), le système de prescription correspond à un ensemble de méthodes de classe. En règle générale, dans les langages orientés objet, la structure de données est implémentée sous forme de bibliothèque de classe standard: il s'agit des classes de conteneurs soi-disant C ++ qui sont incluses dans la bibliothèque de classe STL standard ou des classes qui mettent en œuvre diverses structures de données à partir de La bibliothèque de kit de développeur Java Java.
Cependant, les structures de données sont également implémentées avec succès dans les langages de programmation traditionnels, tels que Fortran ou C. Dans ce cas, le style de programmation orienté objet doit être suivi: il est clairement attribué à un ensemble de fonctions qui fonctionnent avec la structure de données et limitent l'accès aux données uniquement par cet ensemble de fonctions. Les données elles-mêmes sont implémentées comme variables statiques (non globales). Lors de la programmation de la structure de données, deux fichiers avec des textes source sont configurés:
1. En-tête ou fichier H, qui décrit l'interface de la structure de données, c'est-à-dire Un ensemble de prototypes d'entités correspondant au système de prescriptions de structure de données;
2. Un fichier d'implémentation ou un fichier Si-fichier, qui définit des variables statiques qui stockent et accédent aux données et fonctionnalités correspondant au système de régulation de données
La structure de données est généralement mise en œuvre sur la base d'une structure de base plus simple, déjà déjà mise en œuvre ou sur la base d'une matrice et d'un ensemble de variables simples. Une description de la structure de données d'un point de vue logique doit être clairement distinguée. Il peut y avoir de nombreuses implémentations différentes, du point de vue logique (c'est-à-dire du point de vue de l'utilisateur externe), ils sont tous équivalents et diffèrent, peut-être une vitesse d'exécution des ordonnances.
Une condition préalable à stocker des informations dans la mémoire de l'ordinateur est la possibilité de convertir ces informations à l'ordinateur approprié pour l'ordinateur. Dans le cas où cette condition est effectuée, une structure adaptée à la présentation d'informations doit être déterminée, celle qui fournira l'ensemble requis d'opportunités de travailler avec elle.
Liste des selles
Ici, sous la structure, il est entendu comme une méthode de présentation d'informations, à travers laquelle l'ensemble des éléments prélevés séparément forme quelque chose d'unifié, en raison de leur relation entre eux. Respacée par des règles et des interférences logiquement connexes, les données peuvent être traitées de manière très efficace, car la structure commune pour eux fournit un ensemble d'opportunités de contrôle, dont l'une est obtenue par des résultats élevés dans des solutions de certains objectifs.
Mais tous les objets ne représentent pas de forme arbitraire, et peut-être, il n'ya peut-être qu'une seule méthode d'interprétation, un certain avantage d'un programmeur sera la connaissance de toutes les structures de données existantes. Ainsi, il doit souvent faire un choix entre différentes méthodes de stockage des informations et la productivité du produit dépend de cette sélection.
En parlant de technologie non informatique, vous pouvez montrer un seul cas où les informations indiquent une structure évidente. Un exemple visuel est les livres du contenu le plus différent. Ils sont divisés en pages, paragraphes et chapitres, ont, en règle générale, la table des matières, c'est-à-dire l'interface de l'utilisation. Dans un sens large, la structure a tout être vivant, sans que ce soit un âge organisé pouvait difficilement exister.
Il est probable que le lecteur a dû faire face aux structures de données directement en informatique, par exemple, avec ceux intégrés au langage de programmation. Souvent, ils sont appelés types de données. Ceux-ci incluent: des tableaux, des chiffres, des chaînes, des fichiers, etc.
Méthodes de stockage d'informations appelées "Simple", c'est-à-dire indivisible aux composants, il est préférable d'étudier avec un langage de programmation spécifique, ou profondément approfondir dans l'essence de leur travail. Par conséquent, seules les structures "intégrées", celles qui consistent en simples, à savoir: les tableaux, les listes, les arbres et les graphiques seront pris en compte.
Tableaux.
Un tableau est une structure de données avec un ensemble fixe et commandé d'éléments de type (composants). L'accès à l'un des éléments de la matrice est effectué par nom et numéro (index) de cet élément. Le nombre d'index détermine la dimension de la matrice. Par exemple, le plus souvent rencontre des matrices d'un dimensions (vecteurs) et de deux dimensions (matrice).
Le premier a un index, le deuxième - deux. Soit un tableau unidimensionnel appelé A, puis pour accéder à son élément I-ème, vous devrez spécifier le nom de la matrice et le numéro de l'élément souhaité: A [I]. Lorsqu'une matrice est une matrice, elle est représentée sous la forme d'une table, l'accès aux éléments dont il est effectué par le nom de la matrice, ainsi que les numéros de la chaîne et de la colonne, sur l'intersection de laquelle est la ELEMENT: A, où i est le numéro de ligne, J est le numéro de colonne.
Dans différentes langages de programmation, le travail avec des tableaux peut varier dans quelque chose, mais les principes de base sont généralement un partout. Dans le langage Pascal, l'appel à la matrice unidimensionnel et bidimensionnel se produit exactement comme indiqué ci-dessus et, par exemple, en C ++, le réseau à deux dimensions doit être spécifié comme suit: A [I] [J ]. Les éléments du tableau sont numérotés alternativement. À laquelle la numérotation commence, le langage de programmation est affecté. Le plus souvent, cette valeur est 0 ou 1.
Les matrices décrites par le type sont appelées statiques, mais il existe également des tableaux en fonction de certains signes autres que ceux: dynamiques et hétérogènes. Le dynamisme du premier est caractérisé par l'inconstance de la taille, c'est-à-dire que le programme exécute la taille de la matrice dynamique peut varier. Cette fonction fonctionne avec des données plus flexibles, mais elle doit sacrifier la vitesse et le processus lui-même devient plus compliqué.
Le critère obligatoire du massif statique, comme mentionné, est l'homogénéité des données qui est l'une des heures stockées. Lorsque cette condition n'est pas effectuée, le tableau est hétérogène. Son utilisation est due aux lacunes disponibles dans la forme précédente, mais elle est justifiée dans de nombreux cas.
Ainsi, même si vous avez été déterminé avec la structure, et comme il a été choisi un tableau, cela ne suffit toujours pas. Après tout, la matrice n'est qu'une désignation générale, le genre pour un certain nombre d'implémentations possibles. Par conséquent, il est nécessaire de déterminer la manière spécifique de la représentation, avec la matrice la plus appropriée.
Listes.
La liste est un type de données abstraite qui implémente un ensemble de valeurs commandé. Les listes diffèrent des tableaux dans cet accès à leurs éléments sont effectués de manière séquentielle, tandis que les tableaux sont une structure de données d'accès arbitraire. Ce type de résumé présente plusieurs implémentations sous la forme de structures de données. Certains d'entre eux seront discutés ici.
La liste (liste connectée) est une structure de données, qui est un ensemble fini d'éléments commandés liés à l'autre par d'autres pointeurs. Chaque élément de structure contient un champ avec toutes les informations, ainsi qu'un pointeur à l'élément suivant. Contrairement à la matrice, il n'y a pas d'accès arbitraire à l'élément de la liste.
Liste unique connectéeDans la liste unique connectée, ce qui précède, l'élément initial est la liste de la tête (tête de la liste [nom arbitraire]) et tout le reste est appelé queue. La queue de la liste est les éléments séparés en deux parties: informations (champ d'information) et index (champ suivant). Dans le dernier élément au lieu d'un pointeur, un signe de la fin de la liste est nul.
Une liste unique sensible n'est pas trop pratique, car il est possible de passer d'un point seulement au point suivant, passant ainsi à la fin. Lorsque, outre le pointeur sur l'élément suivant, il y a un pointeur et le précédent, une telle liste s'appelle une telle liste est appelée à deux sens.
Double-liste
La possibilité de bouger les deux vers l'avant et de l'avant est utile pour effectuer certaines opérations, mais des pointeurs supplémentaires nécessitent l'utilisation de grandes quantités de mémoire, ce qui est nécessaire dans une liste équivalente connectée unique.
Pour deux types de listes de la décrire ci-dessus, il existe une sous-espèce appelée liste annulaire. Vous pouvez créer une bague unique connectée dans la bague en ajoutant un seul pointeur au dernier élément de sorte qu'il fait référence au premier. Et pour les doubles, deux pointer auront besoin de: sur les premier et dernier éléments.
Liste des selles
Outre les types de structures de liste considérée, il existe d'autres moyens d'organiser des données sur la "liste" de type, mais elles sont généralement largement similaires à celles désassemblées, elles seront donc omises ici.
En plus des différences de distinction, les listes sont divisées en méthodes de données. Certaines de ces méthodes sont dites plus tard.
Empiler.
Empiler
La pile est caractérisée en ce qu'il est possible d'accéder à son élément d'une extrémité, appelé le haut de la pile, en d'autres termes: la pile est la structure des données fonctionnant sur le principe LIFO (Dernier in - première sortie, "la Le dernier est venu - le premier est sorti. " Pictoir que cette structure de données est meilleure sous la forme d'une liste verticale, par exemple des piles de toutes choses, où utiliser l'une d'entre elles, vous devez élever toutes ces choses qui se situent au-dessus, et il est possible de mettre un objet sur haut d'une pile.
Dans la liste des opérations d'une fois connectée, les opérations sur les éléments se produisent strictement d'une extrémité: pour allumer l'élément souhaité à la cinquième cellule, il est nécessaire d'éliminer l'élément qui prend cette position. S'il s'agissait, par exemple, 6 éléments et insérer un élément spécifique était également requis sur la cinquième cellule, puis deux éléments devraient exclure.
File d'attente.
La structure de données "File d'attente" utilise le principe de l'organisation de la FIFO (premier dans, premier sorti - "premier arrivé - premier sorti"). En un sens, une telle méthode est plus juste que celle sur laquelle la pile fonctionne, car la règle simple sous-jacente aux files d'attente habituelles dans divers magasins, les hôpitaux sont considérés comme assez équitables, à savoir, c'est la base de cette structure. Laissez cette observation être un exemple. Strictement parlant, la file d'attente est une liste, ajoutant des éléments qui ne sont autorisés qu'à sa fin et leur extraction est faite de l'autre côté, appelée le début de la liste.
File d'attente déc
DEQUE DEQUE DEQUE - File d'attente double extrémité, "Double face Queen") - Pile à deux extrémités. En effet, malgré la traduction en béton, Dec peut être déterminé non seulement comme un endroit recto-côté, mais aussi comme une pile ayant deux extrémités. Cela signifie que ce type de liste vous permet d'ajouter des éléments au début et à la fin, et il en va de même pour l'opération d'extraction.
déc Cette structure fonctionne simultanément de deux façons d'organiser des données: FIFO et LIFO. Par conséquent, il est permis d'attribuer à une unité de programme distincte obtenue à la suite de la résumé des deux types de liste précédents.
Graphiques.
La section des mathématiques discrètes impliquées dans l'étude des graphiques s'appelle la théorie des graphiques. En théorie des graphiques, des concepts bien connus, des propriétés, des méthodes de présentation et le domaine d'application de ces objets mathématiques sont considérés en détail. Nous sommes également intéressés, seuls les aspects importants dans la programmation.
Comptez - un ensemble de points connectés par des lignes. Les points sont appelés sommets (nœuds) et les lignes - côtes (arcs).
Comme le montre la figure, la distinction entre deux types principaux de graphiques: orienté et orienté nés. Dans les premières nervures sont dirigées, c'est-à-dire une seule direction disponible entre deux sommets connectés, par exemple, du sommet 1, vous pouvez aller au top 2, mais pas vice versa. Dans une colonne connectée inattendue, chaque sommet peut être transmis à chacun et à l'arrière. Le cas particulier de deux de ces espèces est un graphe mixte. Il est caractéristique de la présence de côtes orientées et non orientées.
Le degré d'entrée du sommet est le nombre de nervures comprises, la sortie correspond à la quantité de bords sortants.
Les bords du graphique peuvent ne pas nécessairement être droits et les sommets sont indiqués par les chiffres, comme indiqué sur la figure. De plus, de tels graphiques sont mis en ligne avec une valeur particulière, ils sont appelés graphiques suspendus et cette valeur pesait les côtes. Lorsque le bord finit les deux coïncidés, c'est-à-dire le bord sort du top f et l'entre dans la partie, puis une telle nervure est appelée boucle.
Les colonnes sont largement utilisées dans les structures créées par une personne, par exemple dans des réseaux informatiques et de transport, technologies Web. Les méthodes de représentation spéciales vous permettent d'utiliser le graphique en informatique (dans les machines informatiques). Les plus célèbres d'entre eux: "matrice de voile", "matrice d'incident", "Liste des adjacences", "Liste de Ryube". Les deux premiers, comme clair du titre, utilisez la matrice pour représenter le graphique et les deux derniers sont la liste.
Des arbres.
Arbre non ordonné
Un arbre comme objet mathématique est une abstraction des co-unités trouvées dans la nature. La similitude de la structure des arbres naturels avec les graphiques d'un type particulier indique l'hypothèse de l'analogie entre eux. Nommément connecté et avec ce graphique acyclique (ne pas avoir de cycles). Ces derniers dans leur structure ressemblent vraiment aux arbres, mais il existe des différences dans lesquelles il existe des différences, par exemple, il est de coutume de représenter des arbres mathématiques avec la racine située au sommet, c'est-à-dire toutes les branches "grandir" de haut en bas. On sait que dans la nature ce n'est pas le cas.
Parce que l'arbre est intrinsèquement un graphique, avec ce dernier, de nombreuses définitions coïncident, ou intuitivement similaires. De sorte que le nœud racine (sommet 6) dans la structure de l'arborescence est le seul sommet (noeud), caractéristique de l'absence d'ancêtres, c'est-à-dire qu'il ne se réfère à aucun autre sommet et du nœud racine lui-même peut être Atteint par l'une des sommets disponibles, ce qui découle de la propriété de la connectivité de cette structure. Les nœuds qui ne font pas référence à d'autres nœuds, en d'autres termes, aucun descendants n'est appelé feuilles (2, 3, 9) ou des nœuds terminaux. Les éléments situés entre le nœud racine et les feuilles sont des nœuds intermédiaires (1, 1, 7, 8). Chaque nœud d'arbre n'a qu'un seul ancêtre ou s'il est root, n'a aucun.
Le support est une partie d'un arbre qui inclut un nœud racine et tous ses nœuds descendants. Par exemple, sur la figure, l'un des supports comprend la racine 8 et les éléments 2, 1, 9.
Avec un arbre, de nombreuses opérations peuvent être effectuées, par exemple, trouvez des éléments, des éléments de suppression et de la subtilation, d'insérer un support, de trouver des ensembles racines pour certains sommets, etc. L'une des opérations les plus importantes est la ronde de bois. Plusieurs méthodes de dérivation sont allouées. Les plus populaires d'entre eux sont: contournement symétrique, direct et inverse. Avec dérivation directe, les ancêtres sont visités avant leurs descendants et, dans l'opposé, respectivement, la situation inverse. Dans une dérivation symétrique, les arbres principaux sont visibles alternativement.
La présentation des données dans la structure considérée est bénéfique dans le cas d'une information sur la hiérarchie explicite. Par exemple, travailler avec des données sur les genres et types biologiques, les positions officielles, les objets géographiques, etc. nécessite une structure prononcée hiérarchiquement, telle que des arbres mathématiques.
La structure de données est une unité logicielle qui vous permet d'enregistrer et de traiter la masse du même type ou des informations logiquement connexes dans les périphériques informatiques. Si vous souhaitez ajouter, trouver, modifier ou supprimer des informations, la structure fournira un package spécifique d'options, qui est son interface.
Qu'est-ce qui inclut le concept de structure de données?
Ce terme peut avoir plusieurs proches, mais toujours distinguant des valeurs. Il:
- type abstrait;
- mise en œuvre d'un type d'information abstraite;
- une instance du type de données, par exemple une liste spécifique.
Si nous parlons de la structure de données dans le contexte de la programmation fonctionnelle, il s'agit d'une unité spéciale qui est enregistrée par changement. Cela peut en dire informellement en tant que structure unique, malgré le fait qu'il peut y avoir des versions différentes.
Qu'est-ce qui fait la structure?
Formulaires utilisant des références et des opérations sur eux dans un langage de programmation spécifique. Il convient de dire que différents types de structures conviennent à la réalisation de différentes applications, par exemple, ont une spécialisation complètement étroite et conviennent uniquement à la production de tâches établies.
Si vous prenez des arbres B, ils conviennent généralement à la formation de bases de données et que pour eux. Dans la même heure, les panneaux de hachage sont toujours utilisés partout dans la pratique pour créer divers dictionnaires, par exemple, pour démontrer des éléments de domaine dans les adresses Internet PC et non seulement pour former les bases.
Au cours de l'élaboration d'un logiciel particulier, la complexité de la mise en œuvre et de la qualité de la fonctionnalité des programmes dépend directement de l'utilisation appropriée des structures de données. Une telle compréhension des choses a donné une impulsion au développement de méthodes formelles de développement et de programmes de programmation, où des structures et non des algorithmes sont mis sur la position de leader dans l'architecture de programme.
Il convient de noter que de nombreuses langues de programmation ont le type de modularité établi, ce qui permet des structures avec des données en toute sécurité utilisées dans diverses applications. Les exemples lumineux sont des langues Java, C # et C ++. Maintenant, la structure classique des données utilisées est représentée dans les langages de programmation standard ou directement, elle est déjà intégrée à la langue elle-même. Par exemple, la table de hachage est intégrée à Lua, Python, Perl, Ruby, TCL et autres. La bibliothèque de modèles standard en C ++ est largement appliquée.
Comparez la structure dans la programmation fonctionnelle et impérative
Il devrait immédiatement faire une réservation que la conception des structures pour les langues fonctionnelles est plus difficile que d'impératif, au moins il y a deux raisons:
- En fait, toutes les structures sont souvent utilisées dans la pratique, qui n'est pas utilisée dans un style purement fonctionnel.
- Les structures fonctionnelles sont des systèmes flexibles. Dans la programmation impérative, les anciennes versions sont simplement remplacées par de nouvelles, et tout fonctionne dans fonctionnel, comme cela a fonctionné. En d'autres termes, dans la programmation impérative, la structure est éphémère et dans la fonctionnalité, elles sont constantes.
Qu'est-ce qui inclut la structure?
Souvent, les données avec lesquelles des programmes fonctionnent sont enregistrées dans des tableaux de langage de programmation appliqués, constants ou variable. Un tableau est la structure la plus simple avec des informations, toutefois, pour résoudre certains problèmes nécessite une plus grande efficacité de certaines opérations, par conséquent, d'autres structures sont appliquées (plus compliquées).
La matrice la plus simple convient à la circulation fréquente aux composants établis par des index et de leur changement, et la suppression des éléments du milieu fonctionne pour le principe O (n) O (n). Si vous devez supprimer des éléments pour résoudre certaines tâches, vous devrez utiliser une autre structure. Par exemple, un arbre binaire (STD :: Set) vous permet de le faire par O (logn) O (log\u2061n), mais elle ne prend pas en charge le travail avec des index, mais uniquement en contournement alternativement les éléments et leur recherche est effectuée. Ainsi, on peut dire que la structure est caractérisée par des opérations qu'il est capable d'effectuer, ainsi que de la vitesse de leurs portes. Par exemple, il vaut la peine d'envisager les structures les plus simples qui ne bénéficient pas d'efficacité, mais ont un ensemble d'opérations appuyées exactement établi.
Empiler
C'est l'un des types de structures de données soumises sous la forme d'une matrice la plus simple. La pile classique ne prend en charge que trois options:
- Faire un élément dans la pile (complexité: O (1) O (1)).
- Extraction de l'élément de la pile (complexité: O (1) O (1)).
- Vérifiez, pile vide ou non (complexité: O (1) O (1)).
Pour clarifier le principe de fonctionnement de la pile, vous pouvez appliquer dans la pratique une analogie avec un biscuit. Imaginez qu'il y a plusieurs biscuits au bas de la cour. Vous pouvez mettre quelques pièces en haut ou vous pouvez au contraire, prendre un cookie d'en haut. Le reste des cookies sera fermé vers le haut et vous ne saurez rien à leur sujet. C'est comme ça que les choses sont et avec une pile. Pour la description du concept, l'abréviation LIFO est utilisée (dernier dans, premier out), qui souligne que le composant tombé dans la dernière pile sera le premier et extrait de celui-ci.
File d'attente
Il s'agit d'un autre type de structure de données, qui prend en charge le même ensemble d'options que la pile, mais elle a la sémantique opposée. L'abréviation FIFO est utilisée pour décrire la file d'attente (premier dans, d'abord out), car l'élément est extrait pour la première fois, qui a été ajouté avant tout. Le nom de la structure parle pour elle-même - le principe de travail coïncide complètement avec les files d'attente qui peuvent être vues dans le magasin, supermarché.
déc
C'est un autre type de structure de données, qui s'appelle également la file d'attente avec deux extrémités. L'option prend en charge l'ensemble d'opérations suivant:
- Faire un élément au début (complexité: O (1) O (1)).
- Extraire un composant du début (complexité: O (1) O (1)).
- Faire un élément à la fin (complexité: O (1) O (1)).
- Extraction de l'élément de la fin (complexité: O (1) O (1)).
- Vérifiez, vide LEE DEC (Complexité: O (1) O (1)).
Listes
Cette structure de données définit la séquence de composants linéaires liés auxquels les options d'ajout de composants dans n'importe quel lieu de la liste et de la suppression sont autorisées. La liste linéaire est définie par le pointeur sur le début de la liste. Opérations typiques sur les listes: contournement, recherche d'un composant spécifique, élément d'insertion, retrait du composant, combinant deux listes dans une seule unité, panne de la liste sur une paire, etc. Il convient de notifier que dans la liste linéaire, en plus de la première, il existe un composant précédent pour chaque élément, non compris par ce dernier. Cela signifie que les composants de la liste sont dans un état ordonné. Oui, le traitement d'une telle liste n'est pas toujours pratique, car il n'existe aucune possibilité de déplacer dans la direction opposée - de la fin de la liste au début. Cependant, dans la liste linéaire, il est possible de marcher progressivement dans tous les composants.
Il y a toujours des listes de sonneries. C'est la même structure que la liste linéaire, mais elle a une relation supplémentaire entre les premier et dernier composants. En d'autres termes, après le dernier élément est le premier composant.
Dans cette liste, les éléments sont égaux. L'allocation de la première et la dernière est une conventionnalité.
Des arbres
Cette combinaison de composants qui sont appelés nœuds dans lesquels il existe un composant principal (un) sous la forme d'une racine, et tous les autres sont cassés en une pluralité d'éléments non interssercents. Chaque ensemble est un arbre et la racine de chaque arbre est le descendant de la racine de l'arbre. En d'autres termes, tous les composants sont interconnectés par la relation de l'ancêtre. En conséquence, vous pouvez observer la structure hiérarchique des nœuds. Si les nœuds n'ont pas de descendance, ils sont appelés des feuilles. Sur l'arborescence définit des opérations telles que: Ajouter un composant et le supprimer, le contournement, la composante de recherche. Les arbres binaires jouent un rôle particulier dans l'informatique. Ce que c'est? Il s'agit d'un cas privé d'un arbre, où chaque nœud ne peut avoir plus de couple de descendants qui sont des racines de la sous-arbre gauche et droite. Si une condition supplémentaire est toujours exécutée pour les nœuds d'arbre que toutes les valeurs des composants à l'échelle gauche sont moins de valeurs racines et que les valeurs des composants de support appropriées sont supérieures à la racine, alors un tel arbre est appelé Un arbre de recherche binaire, et il est destiné aux articles rapides. Comment fonctionne l'algorithme de recherche dans ce cas? La valeur souhaitée est comparée à la valeur de la racine et en fonction du résultat, la recherche se termine ou continue, mais exclusivement dans le sous-arbre à gauche ou à droite. Le nombre total d'opérations de comparaison ne dépassera pas la hauteur de l'arborescence (il s'agit du plus grand nombre de composants sur le chemin de la racine à l'une des feuilles).
Graphiques
Les comptes sont une totalité de composants qui sont appelés sommets avec un complexe de relations entre les sommets qui s'appellent des côtes. L'interprétation graphique de cette structure est présentée sous la forme d'un ensemble de points, responsable des sommets, et certaines paires sont reliées par des lignes ou des flèches, ce qui correspond aux côtes. Le dernier cas suggère que le graphique doit être appelé orienté.
Les comptes peuvent être décrits par des objets structurels, ce sont les moyens principaux de décrire les structures complexes et le fonctionnement de tous les systèmes.
Plus de détails sur la structure abstraite
Pour construire un algorithme, il est nécessaire de former une formalisation des données ou, en d'autres termes, il est nécessaire d'apporter des données à un modèle d'information spécifique, qui a déjà été étudié et écrit. Dès que le modèle est trouvé, on peut affirmer qu'une structure abstraite est installée.
Il s'agit de la structure de données principale qui démontre les signes, la qualité de l'objet, la relation entre les composants de l'objet et l'opération, qui est possible d'effectuer au-dessus de celle-ci. La tâche principale consiste à rechercher et à afficher des formes de visualisation de l'information, confortable pour le réglage de l'ordinateur. Il est nécessaire de faire une réservation à une fois que l'informatique comme une science exacte agit avec des objets formels.
L'analyse des structures de données est effectuée par les objets suivants:
- Nombres entiers et réels.
- Valeurs logiques.
- Symboles.
Pour le traitement sur un ordinateur de tous les éléments, il existe des algorithmes appropriés et des structures de données. Les objets typiques peuvent être combinés en structures complexes. Vous pouvez ajouter des opérations sur eux, les règles à certains composants de cette structure.
La structure de l'organisation de données comprend:
- Vecteurs.
- Structures dynamiques.
- Les tables.
- Tableaux multidimensionnels.
- Graphiques.
Si tous les éléments sont sélectionnés avec succès, il s'agira d'une clé de la formation d'algorithmes efficaces et de structures de données. Si vous appliquez dans la pratique l'analogie des structures et des objets réels, vous pouvez résoudre efficacement les tâches existantes.
Il convient de noter que toutes les structures d'organisation de données existent individuellement dans la programmation. Au-dessus d'eux travaillaient de nombreuses années aux XIXe et XIXe siècles, lorsqu'il n'y avait pas de machine informatique en maman.
Il est possible de développer un algorithme dans les concepts d'une structure abstraite, toutefois, de mettre en œuvre l'algorithme dans un langage de programmation spécifique, vous devrez trouver une méthode de la présentation des types de données, des opérateurs, appuyés par une programmation spécifique. Langue. Pour créer des structures, telles que le vecteur, la plaque, la chaîne, la séquence, dans de nombreuses langues de programmation, des types de données classiques sont des types de données classiques: une matrice unidimensionnelle ou bidimensionnelle, une chaîne, un fichier.
Nous avons traité des caractéristiques des structures de données, maintenant, il convient de faire plus attention à la compréhension du concept de structure. Lors de la résolution, une tâche est absolument nécessaire pour travailler avec certaines données pour produire des opérations sur des informations. Chaque tâche a son propre ensemble d'opérations, mais un ensemble est appliqué dans la pratique plus souvent pour résoudre diverses tâches. Dans ce cas, il est utile de proposer une certaine manière d'organiser des informations, ce qui permettra ces opérations aussi efficaces que possible. Dès que cette méthode est apparue, nous pouvons supposer que vous avez une "boîte noire", dans laquelle les données d'un certain type seront enregistrées et qui seront effectuées par ces transactions de données ou d'autres. Cela vous permettra d'être distraire des détails et de vous concentrer complètement sur les caractéristiques de la tâche. Cette boîte noire peut être mise en œuvre de quelque manière que ce soit, s'il est nécessaire de s'efforcer autant que possible la mise en œuvre.
Qui a besoin de savoir?
Je vais vous familiariser avec des informations avec des programmeurs novices qui souhaitent trouver leur place dans ce domaine, mais ne savent pas où aller. Ce sont les fondements de chaque langue de programmation, il ne sera donc pas superflu de savoir immédiatement sur les structures de données et après avoir travaillé avec eux sur des exemples spécifiques et avec une certaine langue. Nous ne devrions pas oublier que chaque structure est possible de caractériser des idées logiques et physiques, ainsi qu'une combinaison d'opérations sur ces idées.
N'oubliez pas: si vous parlez d'une structure particulière, gardez à l'esprit sa représentation logique, car la représentation physique dissimule complètement l'observateur externe.
De plus, gardez à l'esprit qu'une représentation logique ne dépend pas complètement du langage de programmation et de la machine informatique, et le physique, au contraire dépend des traducteurs et des ordinateurs. Par exemple, une matrice bidimensionnelle dans "Fortran" et "Pascal" peuvent être représentées d'une manière identique, et la représentation physique dans la même machine de calcul dans ces langues varie.
Ne vous précipitez pas pour commencer à apprendre des structures spécifiques, il est préférable de comprendre leur classification, de vous familiariser avec tout le monde en théorie et de préférence dans la pratique. Il convient de rappeler que la variabilité est une caractéristique importante de la structure et indique une position statique, dynamique ou demi-histoire. Apprenez les fondations avant de procéder à des choses plus mondiales, cela vous aidera à développer davantage.
