Structures de données et algorithmes C ++
Structures de données et algorithmes C ++ - signifie organiser ou organiser les éléments d'une manière particulière. Lorsque nous disons que nous devons organiser les éléments, ces éléments peuvent être organisés sous différentes formes. Par exemple, les chaussettes peuvent être arrangées de différentes manières. Vous pouvez simplement le garder dans votre placard tout foiré. Ou vous pouvez le garder soigneusement plié. La meilleure façon peut être de les plier et de les disposer en couleurs. Donc, pour rechercher une paire de chaussettes particulière, le troisième arrangement est parfait.
D'une manière similaire d'organisation des chaussettes, les données peuvent également être organisées de différentes manières ou formes. Ces différentes façons d'organiser les données sont appelées structure de données. Voyons une définition formelle d'une structure de données et les bases des structures de données et des algorithmes.
Structures de données et algorithmes C ++:
Le modèle logique ou mathématique d'une organisation particulière de données.
OU
C'est une façon particulière d'organiser les données dans un ordinateur afin qu'elles puissent être utilisées.
Comme pour les chaussettes; organisation différente des structures de données de liste et des algorithmes C ++ disponibles est -
- Array
- Liste liée
- Empiler
- Queue
- Arbre
- Graphique
- Table de hachage
- Tas
- Records
- les tables
Ces structures de données et algorithmes C ++ sont très importants lors de la programmation. Un bon programmeur met toujours l'accent sur la structure des données plutôt que sur le code. Chaque langage de programmation fonctionne sur différentes structures de données et algorithmes en C ++. Les structures de données disponibles en C ++ sont les suivantes.
- Array
- Liste liée
- Empiler
- Queue
- Arbre
- Graphique
- Table de hachage
- Tas
Discutons-en un par un:
# 1 Array
Array est un type le plus simple de structures de données et d'algorithmes C ++. Le tableau est défini comme une collection séquentielle de taille fixe d'éléments de données du même type de données. Par exemple a0 = 12, a1 = 21, a2 = 14, a3 = 15… .Nous pouvons représenter un tableau unidimensionnel comme le montre la figure:
Où
0, 1, 2, 3… ..n est appelé indice ou indice
a (1), a (2), … a (n) est appelée variable d'indice
Il peut être unidimensionnel, bidimensionnel, tridimensionnel et ainsi de suite multidimensionnel.
Dans la mémoire, la matrice est stockée dans des emplacements de mémoire contigus.
L'adresse la plus basse correspond au premier élément
L'adresse la plus élevée correspond au dernier élément
Nous pouvons déclarer un tableau 1-D (1-Dimensional) en C ++ comme suit
dataType arrayName (arraySize);
Par exemple, int num (5);
Initialisation d'un tableau en C ++
num = (23, 10, 12, 3, 6);
Nous pouvons combiner la déclaration et l'initialisation en une seule instruction comme suit.
int num = (23, 10, 12, 3, 6);
Lorsque nous voulons allouer dynamiquement la taille d'un tableau, nous devons un nouvel opérateur comme suit
int * a = new int (taille);
L'inconvénient du tableau est l'insertion et la suppression d'éléments est lente comme dans le tableau ordonné et son stockage de taille fixe.
# 2 Liste liée
La liste fait référence à une collection linéaire d'articles. Une liste chaînée est une série de nœuds connectés (élément de données) comme indiqué sur la figure 3. Le nœud d'en-tête pointe vers le premier nœud de la liste et le dernier nœud pointe vers NULL indiqué par Æ. Comme chaque nœud en contient au moins.
- Une donnée (tout type)
- Pointeur vers le nœud suivant dans la liste
La liste liée est représentée en mémoire à l'aide de deux tableaux. Un tableau stocke des informations appelées informations qui sont des données à stocker et d'autres stockent le champ du pointeur suivant appelé LINK qui est une adresse du nœud suivant.
Un avantage d'une liste chaînée sur un tableau:
Un tableau et une liste liée sont tous deux des représentations d'une liste d'éléments en mémoire. La différence importante est la manière dont les éléments sont liés entre eux. La principale limitation du tableau est l'insertion d'élément dans le tableau et la suppression d'élément du tableau ordonné est difficile car les éléments restants doivent être déplacés. L'insertion et la suppression d'éléments d'une liste chaînée sont très simples.
Apprenez à concevoir et personnaliser des programmes pour diverses plates-formes. Codez, testez, déboguez et implémentez des applications logicielles. Développer des compétences pour assurer le bon fonctionnement des applications.
Les types de liste liée sont:
1. Liste liée individuellement : contient un seul champ lié qui contient l'adresse du nœud suivant dans la liste et les informations enregistrées qui contiennent les informations à stocker.
2. La liste liée circulaire unique est une liste unique uniquement, mais le dernier nœud de la liste contient l'adresse du premier nœud au lieu de null. C'est le contenu de la tête et du champ suivant du dernier nœud sont les mêmes.
3. La liste doublement liée contient deux champs liés précédent et suivant. Un champ précédemment lié qui contient une adresse du nœud précédent dans la liste et le champ lié suivant contient l'adresse du nœud suivant dans la liste et les informations enregistrées contiennent les informations pour être un magasin.
4. La double liste liée circulaire est une liste doublement liée, mais le champ suivant du dernier nœud contient l'adresse du premier nœud au lieu de null.
Cours recommandés
- Cours sur VB.NET
- Formation à la programmation de la science des données
- Cours en ligne ISTQB
- Cours de formation Kali Linux
La mise en œuvre de la liste chaînée en C ++ implique la création d'un nœud, la suppression d'un nœud de la liste, l'insertion d'un nœud nouvellement créé dans la liste et la recherche d'un nœud avec une clé particulière.
Le code de création du nœud est donné comme suit:
L'insertion d'un nœud dans la liste implique trois cas
1. Insérer un nœud au début signifie insérer le nœud nouvellement créé comme nœud de départ. Pour insérer un nœud au début, créez d'abord un nouveau nœud et faites en sorte que le nouveau nœud pointe vers l'ancien début, puis mettez à jour le début pour pointer vers le nouveau nœud, comme illustré dans la figure ci-dessous:
Code pour insérer un nœud au début:
2. Insérer un nœud à la fin signifie insérer le nœud nouvellement créé comme dernier nœud. Pour insérer le nœud en tant que nœud de queue, vous devez créer un nouveau nœud et faire en sorte que l'ancien dernier nœud pointe vers le nouveau nœud, puis mettre à jour la queue pour pointer vers le nouveau nœud.
3. L' insertion d'un nœud à une position donnée implique la création d'un nouveau nœud temporaire, Il faut ensuite trouver la position d'insertion du nœud nouvellement créé.
Code pour l'insertion du nœud à une position donnée:
La suppression d'un nœud de la liste implique la suppression d'un nœud de la liste existante. La suppression du nœud de la liste de liens est simple que l'insertion d'un nœud dans la liste. En C ++, le code de suppression du nœud est donné comme suit:
Traverser un nœud avec une clé (valeur) particulière dans une liste recherchera un nœud dans la liste dont les informations correspondront à la clé d'un nœud donné. Le code C ++ suivant traversera une liste. structures de données et algorithmes C ++
# 3 pile
Une pile est une liste d'éléments dans lesquels un élément ne peut être inséré ou supprimé qu'à une extrémité, appelé le haut de la pile. Prenons l'exemple d'une tour de Hanoi. Ici, lorsque nous devons insérer un disque, nous devons l'insérer uniquement par le haut et de la même manière, le retrait du disque s'effectue uniquement par le haut.
La pile utilise le principe LIFO signifie qu'elle fonctionne dans l'ordre Last in First Out. C'est le dernier élément ajouté à la pile est le premier élément de suppression. Il y a donc quatre opérations de base qui peuvent être effectuées sur la pile:
- Isempty: cette opération vérifie si la pile est vide.
- Push : Cette opération ajoute un nouvel élément à empiler.
- Pop: cette opération supprime un élément de l'élément de pile ajouté le plus récemment.
- Haut: Cette opération renvoie l'élément qui a été ajouté à la pile le plus récemment.
La figure suivante est un exemple de la pile où l'insertion dans la pile et le retrait d'une pile de l'article ont lieu du haut de la pile et nulle part ailleurs.
Débordement de pile
Condition résultant de la tentative de pousser un élément sur une pile complète.
Dépassement de pile
Condition résultant de la tentative de création d'une pile vide.
Ici, nous avons montré quelques opérations push et pop sur la pile. Supposons au départ que la pile soit vide, puis nous avons ajouté F, A, M, R, N. Ensuite, éclatez deux fois et appuyez sur N, H, B, T, K, O, P.
Implémentation de Stack:
Il peut être implémenté à l'aide d'un tableau ou d'une liste liée à la fois.
Le code donné suivant illustre comment la pile est implémentée en C ++ à l'aide de Class. Ici, ont défini une classe nommée comme une pile dans laquelle créé un tableau nommé comme un bâton avec une taille dynamique et deux fonctions principales push and pop.
Débordement de pile: en haut> = taille-1
Dépassement de pile: Lorsque le haut <0
Articles Liés:-
Voici quelques articles qui sont liés aux structures de données et aux algorithmes C ++ qui vous aideront à obtenir plus de détails sur les algorithmes C ++ et les structures de données et les algorithmes, veuillez donc passer par le lien ci-dessous. si vous aimez les structures de données de l'article et les algorithmes C ++, donnez-nous votre précieux commentaire.
- Aide-mémoire pour le langage de programmation C ++
- Linux vs Ubuntu
- Questions d'entrevue C ++ que vous devez savoir
- D'entretiens chez Data Structures And Algorithms | Le plus utile
- Le meilleur article pour les algorithmes et la cryptographie (exemples)
- 8 questions et réponses d'entrevue Awesome Algorithm
- Guide étonnant sur Kali Linux vs Ubuntu
- C ++ Vector vs Array: Quelles sont les meilleures fonctions