La structure des données est un moyen de définir, stocker et récupérer les données de manière structurelle et systémique. Une structure de données peut contenir différents types d'éléments de données.

La disponibilité de la structure de données peut varier selon les langages de programmation. Les structures de données couramment disponibles sont la liste, les tableaux, la pile, les files d'attente, le graphique, l'arborescence, etc.

L'algorithme est une procédure étape par étape, qui définit un ensemble d'instructions à exécuter dans un certain ordre pour obtenir la sortie souhaitée.

Un problème peut être résolu de plusieurs manières. Ainsi, de nombreux algorithmes de solution peuvent être dérivés pour un problème donné. Nous analysons les algorithmes disponibles pour trouver et mettre en œuvre le meilleur algorithme approprié.

Un algorithme est généralement analysé sur deux facteurs - le temps et l'espace. Autrement dit, combienexecution temps et combien extra space requis par l'algorithme.

L'analyse asymptotique d'un algorithme fait référence à la définition de la limite / cadrage mathématique de ses performances d'exécution. En utilisant une analyse asymptotique, nous pouvons très bien conclure le meilleur cas, le cas moyen et le pire scénario d'un algorithme.

L'analyse asymptotique peut fournir trois niveaux de liaison mathématique du temps d'exécution d'un algorithme -

• Le meilleur des cas est représenté par la notation Ω (n).
• Le pire des cas est représenté par la notation Ο (n).
• La casse moyenne est représentée par la notation Θ (n).

Une structure de données linéaire a des éléments de données arrangés séquentiellement. La prochaine fois peut être localisée dans la prochaine adresse mémoire. Il est stocké et accédé de manière séquentielle. Le tableau et la liste sont des exemples de structure de données linéaire.

Les opérations suivantes sont généralement effectuées sur n'importe quelle structure de données -

• Insertion - ajout d'une donnée

• Deletion - suppression d'une donnée

• Traversal - accéder et / ou imprimer tous les éléments de données

• Searching - trouver une donnée particulière

• Sorting - organiser les éléments de données dans une séquence prédéfinie

Il existe trois approches couramment utilisées pour développer des algorithmes -

• Greedy Approach - trouver une solution en choisissant la meilleure option suivante

• Divide and Conquer - plonger le problème à un sous-problème minimum possible et le résoudre indépendamment

• Dynamic Programming - plonger le problème à un sous-problème minimum possible et les résoudre ensemble

Les problèmes donnés ci-dessous trouvent leur solution en utilisant une approche d'algorithme glouton -

• Problème de vendeur itinérant
• Algorithme d'arbre couvrant minimal de Prim
• Algorithme d'arbre couvrant minimal de Kruskal
• Algorithme d'arbre couvrant minimal de Dijkstra
• Graphique - Coloration de la carte
• Graphique - Couverture de sommet
• Problème de sac à dos
• Problème de planification des travaux

Les problèmes donnés ci-dessous trouvent leur solution en utilisant l'approche de l'algorithme de division et de conquête -

• Tri par fusion
• Tri rapide
• Recherche binaire
• Multiplication matricielle de Strassen
• Paire la plus proche (points)

Les problèmes donnés ci-dessous trouvent leur solution en utilisant l'approche de l'algorithme de division et de conquête -

• Série de numéros de Fibonacci
• Problème de sac à dos
• La tour de Hanoi
• Chemin le plus court de toutes les paires par Floyd-Warshall
• Chemin le plus court par Dijkstra
• Planification du projet

Une liste chaînée est une liste d'éléments de données reliés par des liens, c'est-à-dire des pointeurs ou des références. La plupart des langages de programmation de haut niveau modernes ne fournissent pas la fonctionnalité d'accéder directement à l'emplacement de la mémoire, par conséquent, les listes liées ne sont pas prises en charge ou disponibles sous la forme de fonctions intégrées.

Dans la structure de données, pile est un type de données abstrait (ADT) utilisé pour stocker et récupérer des valeurs dans la méthode Last In First Out.

Les piles suivent la méthode LIFO et l'ajout et la récupération d'un élément de données ne prennent que Ο (n) temps. Les piles sont utilisées lorsque nous devons accéder aux données dans l'ordre inverse ou à leur arrivée. Les piles sont couramment utilisées dans les appels de fonctions récursifs, l'analyse d'expressions, la première traversée en profondeur des graphiques, etc.

Les opérations ci-dessous peuvent être effectuées sur une pile -

• push() - ajoute un élément à empiler

• pop() - supprime l'élément supérieur de la pile

• peek() - donne la valeur de l'article haut sans le supprimer

• isempty() - vérifie si la pile est vide

• isfull() - vérifie si la pile est pleine

La file d'attente est une structure de données abstraite, quelque peu similaire à stack. Contrairement à stack, la file d'attente est ouverte aux deux extrémités. Une extrémité est toujours utilisée pour insérer des données (mise en file d'attente) et l'autre est utilisée pour supprimer des données (dequeue). La file d'attente suit la méthodologie du premier entré, premier sorti, c'est-à-dire que l'élément de données stocké en premier sera consulté en premier.

Comme les files d'attente suivent la méthode FIFO, elles sont utilisées lorsque nous devons travailler sur des éléments de données dans l'ordre exact de leur arrivée. Chaque système d'exploitation maintient des files d'attente de divers processus. Les files d'attente prioritaires et la première traversée en largeur des graphiques sont quelques exemples de files d'attente.

Les opérations ci-dessous peuvent être effectuées sur une pile -

• enqueue() - ajoute un élément à l'arrière de la file d'attente

• dequeue() - supprime l'élément de l'avant de la file d'attente

• peek() - donne de la valeur à l'article avant sans le retirer

• isempty() - vérifie si la pile est vide

• isfull() - vérifie si la pile est pleine

La recherche linéaire tente de trouver un élément dans un type de données organisé de manière séquentielle. Ces éléments de données disposés séquentiellement, appelés tableau ou liste, sont accessibles dans un emplacement de mémoire incrémenté. La recherche linéaire compare l'élément de données attendu avec chacun des éléments de données d'une liste ou d'un tableau. La complexité temporelle moyenne de la recherche linéaire est Ο (n) et la complexité du cas le plus défavorable est Ο (n ² ). Les données des tableaux / listes cibles n'ont pas besoin d'être triées.

Une recherche binaire ne fonctionne que sur des listes ou des tableaux triés. Cette recherche sélectionne le milieu qui divise la liste entière en deux parties. Tout d'abord, le milieu est comparé.

Cette recherche compare d'abord la valeur cible au milieu de la liste. S'il n'est pas trouvé, il prend la décision de savoir si.

Le tri à bulles est un algorithme basé sur la comparaison dans lequel chaque paire d'éléments adjacents est comparée et les éléments sont échangés s'ils ne sont pas dans l'ordre. Étant donné que la complexité temporelle est Ο (n ² ), elle ne convient pas pour un grand ensemble de données.

Le tri par insertion divise la liste en deux sous-listes, triées et non triées. Il prend un élément à la fois et le trouve à l'emplacement approprié dans la sous-liste triée et l'insère là-bas. La sortie après insertion est une sous-liste triée. Il fonctionne de manière itérative sur tous les éléments de la sous-liste non triée et les insère dans la sous-liste triée dans l'ordre.

Le tri par sélection est une technique de tri sur place. Il divise l'ensemble de données en deux sous-listes: triées et non triées. Ensuite, il sélectionne l'élément minimum de la sous-liste non triée et le place dans la liste triée. Cela se répète à moins que tous les éléments de la sous-liste non triée ne soient consommés dans une sous-liste triée.

Les deux techniques de tri conservent deux sous-listes, triées et non triées, et prennent toutes deux un élément à la fois et le placent dans une sous-liste triée. Le tri par insertion fonctionne sur l'élément actuel en main et le place dans le tableau trié à l'emplacement approprié en conservant les propriétés du tri par insertion. Tandis que, le tri par sélection recherche le minimum dans la sous-liste non triée et le remplace par l'élément actuel en main.

Le tri par fusion est un algorithme de tri basé sur une approche de programmation de division et de conquête. Il continue à diviser la liste en sous-liste plus petite jusqu'à ce que toutes les sous-listes n'aient qu'un seul élément. Et puis il les fusionne de manière triée jusqu'à ce que toutes les sous-listes soient consommées. Il a une complexité d'exécution de Ο (n log n) et il a besoin de Ο (n) espace auxiliaire.

Le tri shell peut être considéré comme une variante du tri par insertion. Le tri Shell divise la liste en sous-liste plus petite en fonction de certainsgapvariable, puis chaque sous-liste est triée à l'aide du tri par insertion. Dans le meilleur des cas, il peut fonctionner jusqu'à Ο (n log n).

Le tri rapide utilise l'approche diviser pour conquérir. Il divise la liste en plus petites «partitions» en utilisant «pivot». Les valeurs qui sont plus petites que le pivot sont disposées dans la partition de gauche et les valeurs supérieures sont disposées dans la partition de droite. Chaque partition est triée de manière récursive à l'aide du tri rapide.

Un graphique est une représentation picturale d'un ensemble d'objets où certaines paires d'objets sont reliées par des liens. Les objets interconnectés sont représentés par des points appelés sommets et les liens qui relient les sommets sont appelés arêtes.

L'algorithme de recherche en profondeur (DFS) parcourt un graphique dans un mouvement vers la profondeur et utilise une pile pour se souvenir d'obtenir le sommet suivant pour démarrer une recherche lorsqu'une impasse se produit dans une itération.

L'algorithme de première recherche en largeur (BFS) parcourt un graphe dans un mouvement vers la largeur et utilise une file d'attente pour se souvenir d'obtenir le sommet suivant pour démarrer une recherche lorsqu'une impasse se produit dans une itération.

Un arbre est un graphe minimalement connecté n'ayant ni boucles ni circuits.

Un arbre binaire a une condition spéciale selon laquelle chaque nœud peut avoir deux enfants au maximum.

Un arbre de recherche binaire est un arbre binaire avec une disposition spéciale où l'enfant gauche d'un nœud doit avoir une valeur inférieure à la valeur de son parent et l'enfant droit du nœud doit avoir une valeur supérieure à sa valeur parent.

La traversée d'arbre est un processus pour visiter tous les nœuds d'un arbre. Parce que tous les nœuds sont connectés via des bords (liens), nous partons toujours du nœud racine (tête). Il y a trois façons que nous utilisons pour traverser un arbre -

• Traversée en ordre
• Précommander Traversal
• Traversée post-commande

• Traversée dans l'ordre - 10 14 19 27 31 35 42
• Parcours de précommande - 27 14 10 19 35 31 42
• Traversée post-commande - 10 19 14 31 42 35 27

Les arbres AVL sont un arbre de recherche binaire d'équilibrage de la hauteur. L'arbre AVL vérifie la hauteur des sous-arbres gauche et droit et garantit que la différence n'est pas supérieure à 1. Cette différence est appelée facteur d'équilibre.

BalanceFactor = height(left-sutree) − height(right-sutree)

Un arbre couvrant est un sous-ensemble du graphe G, qui a tous les sommets couverts avec un nombre minimum d'arêtes possible. Un Spanning Tree n'a pas de cycles et il ne peut pas être déconnecté.

Cela dépend de la connexion du graphique. Un graphe non orienté complet peut avoir au maximum n ^n-1 nombre d'arbres couvrant, où n est le nombre de nœuds.

Cet algorithme traite le graphe comme une forêt et chaque nœud comme un arbre individuel. Une arborescence se connecte à une autre uniquement et uniquement si elle a le moindre coût parmi toutes les options disponibles et ne viole pas les propriétés MST.

L'algorithme de Prim traite les nœuds comme un seul arbre et continue d'ajouter de nouveaux nœuds à l'arbre couvrant à partir du graphe donné.

Dans un graphique pondéré, un arbre couvrant minimum est un arbre couvrant qui a un poids minimum que tous les autres arbres couvrant du même graphique.

Heap est une structure de données d'arborescence binaire équilibrée spéciale où la clé du nœud racine est comparée à ses enfants et arrangée en conséquence. Un min-heap, un nœud parent a une valeur de clé inférieure à ses enfants et un nœud parent max-heap a une valeur supérieure à ses enfants.

Une fonction récursive est une fonction qui s'appelle elle-même, directement ou appelle une fonction qui à son tour l'appelle. Chaque fonction récursive suit les propriétés récursives -base criteria où les fonctions cessent de s'appeler et progressive approach où les fonctions essaient de répondre aux critères de base à chaque itération.

Tour de Hanoi, est un puzzle mathématique qui se compose de trois tour (chevilles) et plus d'un anneaux. Tous les anneaux sont de taille différente et empilés les uns sur les autres où le grand disque est toujours en dessous du petit disque. Le but est de déplacer la tour de disque d'une cheville à une autre, sans casser ses propriétés.

La série Fibonacci génère le numéro suivant en ajoutant deux numéros précédents. Par exemple - 0 1 1 2 3 5 8 13.

Le hachage est une technique pour convertir une plage de valeurs de clé en une plage d'index d'un tableau. En utilisant des tables de hachage, nous pouvons créer un stockage de données associatif où l'index de données peut être trouvé en fournissant ses valeurs de clé.

La recherche par interpolation est une variante améliorée de la recherche binaire. Cet algorithme de recherche fonctionne sur la position de sondage de la valeur requise.

Notation de préfixe - * + ab + cd

Notation Postfix - ab + cd + *