Menu

Introduction aux structures de données en C ++

introduction data structures c

Essayez Notre Instrument Pour Éliminer Les Problèmes

Un didacticiel d'introduction sur les structures de données en C ++.

«La structure des données peut être définie comme une collection organisée de données qui aide un programme à accéder aux données de manière efficace et rapide afin que l'ensemble du programme puisse fonctionner de manière efficace. '

Nous savons que dans le monde de la programmation, les données sont le centre et tout tourne autour des données. Nous devons effectuer toutes les opérations de données, y compris le stockage, la recherche, le tri, l'organisation et l'accès aux données de manière efficace, et ce n'est qu'alors que notre programme peut réussir.

=> Voir ici pour explorer la liste complète des didacticiels C ++.

Introduction aux structures de données en C ++ (1)

Ce que vous apprendrez:

Aperçu

Nous devons trouver le moyen le plus efficace de stocker des données qui puisse nous aider à créer des solutions dynamiques. La structure des données nous aide à construire de telles solutions.

Lors de l'organisation ou de l'organisation des données en structures, nous devons nous assurer que l'arrangement représente presque un objet du monde réel. Deuxièmement, cet arrangement devrait être suffisamment simple pour que n'importe qui puisse y accéder facilement et le traiter chaque fois que nécessaire.

Dans cette série, nous apprendrons en détail la structure de données de base et avancée. Nous apprendrons également en détail les différentes techniques de recherche et de tri qui peuvent être effectuées sur des structures de données.

Après avoir appris cette série de tutoriels, le lecteur doit bien se familiariser avec chaque structure de données et sa programmation.

Passons en revue certains des termes que nous utilisons lorsque nous traitons des structures de données:

Par exemple,prenez un élève en particulier. Un élève peut avoir les détails suivants représentés sous forme d'image.

Exemple - Structure des données

  • Données: C'est la valeur élémentaire. Dans la figure ci-dessus, le numéro de rôle de l'élève peut être des données.
  • Élément de groupe: Il s'agit de l'élément de données qui a plus d'un sous-élément. Dans la figure ci-dessus, Student_name a le prénom et le nom.
  • Record: C'est une collection d'éléments de données. Dans l'exemple ci-dessus, des éléments de données tels que le numéro de rôle de l'élève, le nom, la classe, l'âge, la note, etc. forment un enregistrement ensemble.
  • Entité: C'est une classe de disques. Dans le diagramme ci-dessus, l'étudiant est une entité.
  • Attribut ou champ: Les propriétés d'une entité sont appelées attributs et chaque champ représente un attribut.
  • Déposer: Un fichier est une collection d'enregistrements. Dans l'exemple ci-dessus, une entité étudiante peut avoir des milliers d'enregistrements. Ainsi, un fichier contiendra tous ces enregistrements.

Le lecteur doit être conscient de tous ces termes car nous les utilisons de temps en temps lorsque nous utilisons diverses structures de données.

Les structures de données sont la principale composante du programme et en tant que programmeurs, nous devons faire attention à la structure de données à utiliser. La structure de données exacte à utiliser est la décision la plus difficile à prendre en ce qui concerne la programmation.

Discutons de la nécessité d'une structure de données dans la programmation.

Besoin d'une structure de données dans la programmation

Au fur et à mesure que la quantité de données augmente, les applications deviennent de plus en plus complexes, il devient donc difficile pour le programmeur de gérer ces données ainsi que le logiciel.

En règle générale, à tout moment, l'application peut rencontrer les obstacles suivants:

# 1) Recherche de grandes quantités de données: Avec une grande quantité de données traitées et stockées, à tout moment, notre programme peut être amené à rechercher des données particulières. Si les données sont trop volumineuses et mal organisées, il faudra beaucoup de temps pour obtenir les données requises.

Lorsque nous utilisons des structures de données pour stocker et organiser les données, la récupération des données devient plus rapide et plus facile.

# 2) Vitesse de traitement: Des données désorganisées peuvent entraîner une vitesse de traitement lente, car beaucoup de temps sera perdu à récupérer et à accéder aux données.

Si nous organisons correctement les données dans une structure de données lors du stockage, nous ne perdrons pas de temps dans des activités telles que la récupération, l'organisation à chaque fois. Au lieu de cela, nous pouvons nous concentrer sur le traitement des données pour produire le résultat souhaité.

# 3) Demandes simultanées multiples: De nos jours, de nombreuses applications doivent faire une demande simultanée de données. Ces demandes doivent être traitées efficacement pour que les applications fonctionnent correctement.

Si nos données sont stockées de manière aléatoire, nous ne serons pas en mesure de traiter toutes les demandes simultanées simultanément. Il est donc judicieux d’organiser les données dans une structure de données appropriée afin de minimiser le temps de traitement des demandes simultanées.

Classification de la structure des données

Les structures de données utilisées en C ++ peuvent être classées comme suit.

Classification des structures de données

Une structure de données est une manière d'organiser les données. Nous pouvons donc classer les structures de données comme indiqué en structures de données primitives ou standard et structures de données non primitives ou définies par l'utilisateur.

Nous avons vu tous les types de données pris en charge en C ++. Comme c'est aussi une manière d'organiser les données, nous disons qu'il s'agit d'une structure de données standard.

Les autres structures de données ne sont pas primitives et l'utilisateur doit les définir avant de les utiliser dans un programme. Ces structures de données définies par l'utilisateur sont ensuite classées en structures de données linéaires et non linéaires.

Structure de données linéaire

Les structures de données linéaires ont tous leurs éléments disposés de manière linéaire ou séquentielle. Chaque élément d'une structure de données linéaire a un prédécesseur (élément précédent) et un successeur (élément suivant)

Les structures de données linéaires sont ensuite divisées en structures de données statiques et dynamiques. Les structures de données statiques ont généralement une taille fixe et une fois leur taille déclarée au moment de la compilation, elles ne peuvent pas être modifiées. Les structures de données dynamiques peuvent changer leur taille de manière dynamique et s'adapter.

L'exemple le plus courant de structure de données statique linéaire est un tableau.

Déployer

Un tableau est une collection séquentielle d'éléments du même type. Chaque élément du tableau est accessible en utilisant sa position dans le tableau appelé index ou indice du tableau. Le nom du tableau pointe vers le premier élément du tableau.

déployer

L’illustration ci-dessus est un tableau «a» de n éléments. Les éléments sont numérotés de 0 à n-1. La taille du tableau (n dans ce cas) est également appelée la dimension du tableau. Comme le montre la figure ci-dessus, le nom du tableau pointe vers le premier élément du tableau.

Le tableau est la structure de données la plus simple et est efficace car les éléments sont accessibles directement à l'aide d'indices. Si nous voulons accéder au troisième élément du tableau, il suffit de dire a (2).

Mais ajouter ou supprimer les éléments du tableau est difficile. Par conséquent, nous utilisons des tableaux uniquement dans des applications simples ou dans des applications où l'ajout / la suppression d'éléments n'est pas nécessaire.

Les structures de données dynamiques linéaires populaires sont la liste liée, la pile et la file d'attente.

Liste liée

Une liste chaînée est une collection de nœuds. Chaque nœud contient l'élément de données et un pointeur vers le nœud suivant. Les nœuds peuvent être ajoutés et supprimés dynamiquement. Une liste chaînée peut être une seule liste chaînée dans laquelle chaque nœud a un pointeur vers l'élément suivant uniquement. Pour le dernier élément, le pointeur suivant est défini sur null.

Dans la liste doublement liée, chaque nœud a deux pointeurs, un vers le nœud précédent et le second vers le nœud suivant. Pour le premier nœud, le pointeur précédent est nul et pour le dernier nœud, le pointeur suivant est nul.

Liste liée

Comme le montre la figure ci-dessus, le début de la liste est appelé la tête tandis que la fin de la liste chaînée est appelée la queue. Comme indiqué ci-dessus, chaque nœud a un pointeur vers l'élément suivant. Nous pouvons facilement ajouter ou supprimer des éléments en changeant le pointeur vers le nœud suivant.

Empiler

La pile est une structure de données linéaire dans laquelle les éléments ne peuvent être ajoutés ou supprimés qu'à partir d'une seule extrémité appelée «Haut» de la pile. De cette manière, la pile présente le type d'accès mémoire LIFO (Last In, First Out).

Empiler

Comme indiqué ci-dessus, les éléments de la pile sont toujours ajoutés à une extrémité et également supprimés de la même extrémité. C'est ce qu'on appelle le «sommet» de la pile. Lorsqu'un élément est ajouté, il est poussé vers le bas de la pile et le haut de la pile est incrémenté d'une position.

De même, lorsqu'un élément est supprimé, le haut de la pile est décrémenté. Lorsqu'une pile est vide, le haut de la pile est défini sur -1. Il existe deux opérations principales «Push» et «Pop» qui sont effectuées sur la pile.

File d'attente

La file d'attente est encore une autre structure de données linéaire dans laquelle les éléments sont ajoutés à une extrémité appelée «arrière» et supprimés d'une autre extrémité appelée «avant». Queue montre FIFO (First In, First Out) le type de méthodologie d'accès à la mémoire.

File d

Le diagramme ci-dessus montre une file d'attente avec des extrémités arrière et avant. Lorsque la file d'attente est vide, les pointeurs arrière et avant coïncident l'un avec l'autre.

Structure de données non linéaire

Dans les structures de données non linéaires, les données ne sont pas organisées de manière séquentielle, mais plutôt de manière non linéaire. Les éléments sont connectés les uns aux autres dans un arrangement non linéaire.

Les structures de données non linéaires sont des arbres et des graphiques.

la meilleure application de téléchargement de mp3 pour android

Des arbres

Les arbres sont des structures de données multiniveaux non linéaires ayant une relation hiérarchique entre les éléments. Les éléments de l'arborescence sont appelés nœuds.

Le nœud en haut est appelé la racine de l'arbre. La racine peut avoir un ou plusieurs nœuds enfants. Les nœuds suivants peuvent également avoir un ou plusieurs nœuds enfants. Les nœuds qui n'ont pas de nœuds enfants sont appelés nœuds feuilles.

Des arbres

Dans le diagramme ci-dessus, nous avons montré un arbre à 6 nœuds. Parmi ces trois nœuds sont les nœuds feuilles, un nœud supérieur est la racine et les autres sont des nœuds enfants. En fonction du nombre de nœuds, de nœuds enfants, etc. ou de la relation entre les nœuds, nous avons différents types d'arbres.

Graphiques

Le graphe est un ensemble de nœuds appelé sommets connectés les uns aux autres au moyen des liens appelés Bords . Les graphes peuvent avoir un cycle à l'intérieur, c'est-à-dire que le même sommet peut être un point de départ ainsi que le point final d'un chemin particulier. Les arbres ne peuvent jamais avoir de cycle.

Graphiques

Le diagramme ci-dessus est un graphique non orienté. Nous pouvons également avoir des graphiques orientés où nous représentons les arêtes à l'aide de flèches dirigées.

Opérations sur la structure des données

Toutes les structures de données effectuent diverses opérations sur ses éléments.

Celles-ci sont communes à toutes les structures de données et sont répertoriées comme suit:

  • Recherche: Cette opération est effectuée pour rechercher un élément particulier ou une clé. Les algorithmes de recherche les plus courants sont la recherche séquentielle / linéaire et la recherche binaire.
  • Tri: L'opération de tri consiste à organiser les éléments dans une structure de données dans un ordre particulier croissant ou décroissant. Il existe différents algorithmes de tri disponibles pour les structures de données. Les plus populaires d'entre eux sont Quicksort, Selection sort, Merge sort, etc.
  • Insertion: L'opération d'insertion concerne l'ajout d'un élément à la structure de données. C'est l'opération la plus importante et à la suite de l'ajout d'un élément, la disposition change et nous devons veiller à ce que la structure des données reste intacte.
  • Effacement: L'opération de suppression supprime un élément de la structure de données. Les mêmes conditions qui doivent être prises en compte pour l'insertion doivent également être remplies en cas d'opération de suppression.
  • Traversée: Nous disons que nous traversons une structure de données lorsque nous visitons chaque élément de la structure. La traversée est nécessaire pour effectuer certaines opérations spécifiques sur la structure de données.

Dans nos rubriques suivantes, nous apprendrons d'abord les différentes techniques de recherche et de tri à effectuer sur les structures de données.

Avantages de la structure des données

  • Abstraction: Les structures de données sont souvent implémentées en tant que types de données abstraits. Les utilisateurs accèdent uniquement à son interface externe sans se soucier de l'implémentation sous-jacente. Ainsi, la structure des données fournit une couche d'abstraction.
  • Efficacité: Une bonne organisation des données se traduit par un accès efficace aux données, ce qui rend les programmes plus efficaces. Deuxièmement, nous pouvons sélectionner la structure de données appropriée en fonction de nos besoins.
  • Réutilisabilité: Nous pouvons réutiliser les structures de données que nous avons conçues. Ils peuvent également être compilés dans une bibliothèque et distribués au client.

Conclusion

Avec cela, nous concluons ce tutoriel sur l'introduction aux structures de données. Nous avons présenté brièvement chacune des structures de données dans ce didacticiel.

Dans nos tutoriels ultérieurs, nous explorerons plus en détail les structures de données ainsi que les différentes techniques de recherche et de tri.

=> Cliquez ici pour la série de formations Absolute C ++.

lecture recommandée

^