Introduction aux tableaux dans la structure de données

Un tableau est un type de structure de données qui est utilisé pour stocker des données homogènes dans des emplacements de mémoire contigus. Cela met en œuvre l'idée de stocker les différents éléments de sorte qu'ils puissent être récupérés ou accessibles en une seule fois.

Ici, index fait référence à l'emplacement d'un élément dans le tableau. Imaginons si P (L) est le nom du tableau où «P» est le nom de la variable et «L» est la longueur du tableau, c'est-à-dire le nombre d'éléments présents dans le tableau. Alors P (i) représente l'élément à cette position «i + 1» dans le tableau.

Par exemple:

P (6) = 72 signifie élément à 6 + 1ème emplacement du tableau.

Need of Array: Il permet de représenter un grand nombre d'éléments à l'aide d'une seule variable. Il rend également l'accès à l'élément plus rapide plus facile à stocker dans l'emplacement mémoire en utilisant l'index du tableau qui représente l'emplacement de l'élément dans le tableau.

Comment fonctionnent les tableaux dans la structure de données?

Array stocke les variables à des emplacements contigus et leur donne un index particulier. Lorsque quelqu'un veut récupérer les données, il utilise cet index. Dans le tableau ci-dessus 'P', dites l'adresse de base pour tableau = 100, puis les éléments sont stockés comme ci-dessous:


La mémoire allouée à un tableau peut être calculée comme suit:

  • Tableau unidimensionnel: mémoire totale allouée à un tableau = nombre d'éléments * taille d'un élément Par exemple: dans le cas ci-dessus, mémoire = 7 * (taille de l'int)
  • Ordre principal des lignes: mémoire totale allouée à la matrice 2D = nombre d'éléments * taille d'un élément
    = Nombre de lignes * Nombre de colonnes * Taille d'un élément
  • Ordre des colonnes majeures: mémoire totale allouée au tableau 2D = nombre d'éléments * taille d'un élément
    = Nombre de lignes * Nombre de colonnes * Taille d'un élément

Comment définir des tableaux?

Ainsi, Array peut être défini comme une structure de données dérivée pour stocker des données homogènes de type de données primitif à des emplacements de mémoire contigus. Voici les opérations pouvant être effectuées sur des tableaux:

1. Insertion: il s'agit d'insérer un élément dans le tableau à un index particulier. Cela peut être effectué avec une complexité O (n).

2. Suppression: Il s'agit de supprimer un élément à un index particulier. Cette opération nécessite un décalage des éléments après suppression donc prend la complexité O (n).

3. Recherche: Cela fait référence à l'accès à un élément à un index particulier d'un tableau.

4. Traversée: Il s'agit d'imprimer tous les éléments d'un tableau l'un après l'autre.

Propriétés des tableaux dans la structure de données

Voici les propriétés des tableaux dans la structure de données:

  • Il s'agit d'un type de données dérivé, composé d'une collection de divers types de données primitifs tels que int, char, float, etc.
  • Les éléments d'un tableau sont stockés dans des blocs contigus dans la mémoire principale.
  • Le nom du tableau stocke l'adresse de base du tableau. Il agit comme un pointeur sur le bloc de mémoire où le premier élément a été stocké.
  • Les indices de tableau commencent de 0 à N-1 dans le cas d'un tableau à une dimension où n représente le nombre d'éléments dans un tableau.
  • Les éléments du tableau ne peuvent être composés que de constantes et de valeurs littérales.

Comment créer des tableaux?

Nous pouvons créer des tableaux en utilisant la syntaxe ci-dessous:

1. Tableau dimensionnel: var = (c1, c2, c3, …… .cn)

Ici, var fait référence à la variable de tableau qui stocke l'emplacement de base du tableau. Et c1, c2… sont des éléments du tableau.

Exemple: int a = (4, 6, 7, 8, 9)

Longueur du tableau = n

2. Tableau multidimensionnel: var = ((r 01, … r 0n ), (r 10, … ..r 1n )… .. (r m0 … .r mn ))

Ici, var fait référence au nom du tableau de m lignes et n colonnes.

Comment accéder à l'élément de tableaux?

Les index d'un tableau commencent de 0 à -1, 0 qui indique le premier élément du tableau et -1 indique le dernier élément du tableau. De même, -2 indique le dernier mais un élément du tableau. Disons qu'il y a un tableau 'A' ayant 10 éléments. Ensuite, ici Une variable stocke la référence de la première variable du tableau et cela s'appelle «Adresse de base» d'un tableau. Après cela, si quelqu'un veut accéder à l'élément du tableau, l'adresse de cet élément est calculée à l'aide de la formule ci-dessous.

Adresse du ième élément = Adresse de base + i * taille de chaque élément

Ici, la taille de chaque élément fait référence à la mémoire occupée par divers types de données primitifs que le tableau contient. Par exemple, int prend 2 octets d'espace et float prend 4 octets d'espace en C.

Accès à un tableau multidimensionnel

Disons que A (r l, …… .., r u ) (c u, ……, c l ) est un tableau multidimensionnel et rl, r u, c u, c l sont des bornes inférieure et supérieure pour les lignes et les colonnes. Que le nombre de lignes dans A, disons NR = r u - r l +1 et le nombre de colonnes dans A, disons NC = c l - c u +1.

Maintenant, pour trouver l'adresse d'un élément dans le tableau, il existe 2 méthodes:

  1. Ligne majeure: où nous traversons ligne par ligne.

Adresse de A (i) (j) = Adresse de base + ((i - r l ) * NC + (j- c l )) * taille de chaque élément.

  1. Colonne majeure: où nous parcourons colonne par colonne.

Adresse de A (i) (j) = Adresse de base + ((i - r l ) + (j- c l ) * NR) * taille de chaque élément.

Complexité: L' accès à n'importe quel élément du tableau est beaucoup plus facile et peut être fait dans la complexité O (1).

Conclusion

Les tableaux sont un moyen très unique de structurer les données stockées de manière à ce qu'elles soient facilement accessibles et puissent être interrogées pour récupérer la valeur à un nombre particulier à l'aide de la valeur d'index. Bien que l'insertion d'un élément dans un tableau prenne beaucoup de temps car elle nécessite un réarrangement complet et un décalage des éléments existants d'un tableau. Pourtant, il est utilisé pour implémenter diverses autres structures de données complexes telles que l'arborescence, la file d'attente ou la pile et également utilisé dans divers algorithmes.

Article recommandé

Ceci est un guide des tableaux dans la structure de données. Nous expliquons ici comment créer et accéder aux éléments de tableau dans la structure de données avec les propriétés. Vous pouvez également consulter nos autres articles connexes pour en savoir plus -

  1. Comment créer des tableaux en PHP?
  2. Tableaux en programmation Java Avantages et inconvénients
  3. Tableaux en programmation C (exemples)
  4. Top 10 des questions d'entrevue sur la structure des données

Catégorie:

Développement de logiciels