data-structuresDémarrer avec les structures de données


Remarques

Cette section fournit une vue d'ensemble des structures de données et des raisons pour lesquelles un développeur peut vouloir l'utiliser.

Il convient également de mentionner tous les grands sujets au sein des structures de données et de les relier aux sujets connexes. La documentation des structures de données étant nouvelle, vous devrez peut-être créer des versions initiales de ces rubriques connexes.

Tableau: une structure de données simple

Une structure de données de tableau est utilisée pour stocker des objets similaires (ou des valeurs de données) dans un bloc de mémoire contigu. Array Data Structure a une taille fixe, qui détermine le nombre de valeurs de données pouvant être stockées.


Array: le mode C ++

En langage de programmation C ++, nous pouvons déclarer un tableau statique comme suit

int arrayName[100];
 

Ici, nous avons déclaré un tableau nommé "arrayName" qui peut stocker jusqu'à 100 valeurs, toutes du même type, c'est-à-dire un entier.

Nous allons maintenant discuter de certains avantages et inconvénients de cette structure de données

  1. Nous pouvons accéder aux valeurs de données stockées dans Array en temps constant, c’est-à-dire que la complexité en temps est O (1) . Donc, si nous voulons accéder à la valeur de données stockée à la i-ème position, nous ne devons pas démarrer à partir de la position de départ et monter à la i-ème position, mais nous pouvons directement passer à la ième position, économisant ainsi du temps de calcul.
  2. L'insertion d'un élément au milieu d'un tableau n'est pas une tâche efficace. Supposons que nous voulions ajouter un nouvel élément dans le tableau à la i-ème position, nous devons d'abord déplacer tous les éléments à (i-th) et (i + 1) position pour créer un espace pour un nouvel élément. Exemple: 1 4 2 0 est un tableau avec 4 éléments, maintenant nous voulons insérer 3 en 2ième position, puis nous devons déplacer 4,2 et 0 une position supplémentaire pour créer un espace pour 3.
  1 3 4 2 0
 
  1. Semblable à l'insertion de l'élément, la suppression d'un élément d'une i-ème position dans un tableau n'est pas non plus efficace car nous avons besoin de déplacer tous les éléments avant l'élément supprimé pour remplir l'espace vide créé par la suppression. élément.

Ce sont 3 caractéristiques simples d'un tableau. Ici, vous pouvez penser que le tableau n'est pas une structure de données efficace, mais en pratique, l'avantage d'un tableau peut surpasser ses inconvénients. Cela dépend en grande partie du type d'objet que vous voulez servir, il est possible que vous ne souhaitiez pas insérer ou supprimer des éléments aussi souvent que vous voulez y accéder. Dans ce cas, un tableau est une structure de données absolument parfaite.

Le seul objectif de cette structure de données est de vous assurer de ne pas choisir la structure de données en fonction du nombre d’avantages et d’inconvénients, mais vous devez toujours analyser l’importance de la structure en tenant compte de votre problème, par exemple: Si vous passez beaucoup de temps à accéder aux valeurs de données par rapport à leur insertion ou à leur suppression, dans ce cas, nous devons donner plus de poids aux avantages et aux inconvénients.

Introduction aux structures de données

Une structure de données est un moyen d'organiser et de stocker des informations.

Laissez un "Bonjour, Monde!" string est l'information dont nous avons besoin pour organiser et stocker dans la mémoire adressable par octet.

Chaque caractère ASCII nécessite 7 bits de stockage. La plupart des systèmes réservent 8 bits (1 octet) pour chaque caractère, donc chaque caractère dans "Hello, World!" est stocké dans une unité de mémoire individuelle de taille octet, l'un après l'autre, consécutivement.

Nous avons besoin d'une seule référence à notre chaîne, même si elle couvre plusieurs adresses mémoire. Nous utilisons donc l'adresse du premier caractère de la chaîne, «H». On peut accéder à tous les autres caractères à l'adresse de «H» + l'index de ce caractère en utilisant des caractères indexés à zéro.

Nous voulons imprimer notre chaîne, "Hello, World!" Nous connaissons son adresse en mémoire, que nous fournissons à la fonction d’impression, mais comment la fonction d’impression sait-elle arrêter d’imprimer des emplacements de mémoire consécutifs? Une approche courante consiste à ajouter le caractère nul '\ 0' à la chaîne. Lorsque la fonction d'impression rencontre le caractère nul, elle sait qu'elle a atteint la fin de la chaîne.

Nous avons défini un moyen d'organiser et de stocker notre chaîne, c'est-à-dire une structure de données! Cette structure de données très simple est un tableau de caractères terminé par un caractère nul, ce qui constitue un moyen d'organiser et de stocker une chaîne.