De plus en plus, je remarque que les personnes autodidactes modernes manquent vraiment de matériel. Tout le monde connaît les langues, mais peu de bases telles que les types de données ou les algorithmes. Un peu sur les types de données.
En 1976, le scientifique suisse
Nicklaus Wirth a écrit le livre
Algorithms + data structures = programmes.Plus de 40 ans plus tard, cette équation est toujours vraie. Et si vous êtes un autodidacte et que vous passez en revue l'article pendant longtemps dans la programmation, vous pouvez le faire en diagonale. Vous pouvez coder le café.
L'article comportera également des questions que vous pourrez entendre lors de l'entretien.
Qu'est-ce qu'une structure de données?
Une structure de données est un conteneur qui stocke des données dans une disposition spécifique. Cette «disposition» permet à la structure de données d'être efficace dans certaines opérations et inefficace dans d'autres.
Quels sont-ils?
Linéaires , les éléments forment une séquence ou une liste linéaire, le contournement des nœuds est linéaire. Exemples: tableaux. Liste liée, piles et files d'attente.
Non linéaire , si le contournement des nœuds est non linéaire et que les données ne sont pas séquentielles. Exemple: graphique et arbres.
Structures de données de base.
- Tableaux
- Piles
- Files d'attente
- Listes associées
- Comtes
- Les arbres
- Arbres préfixés
- Hachage de table
Tableaux
Un tableau est la structure de données la plus simple et la plus utilisée. D'autres structures de données, telles que les piles et les files d'attente, sont dérivées de tableaux.
Image d'un tableau simple de taille 4 contenant des éléments (1, 2, 3 et 4).
Chaque élément de données se voit attribuer une valeur numérique positive (index), qui correspond à la position de l'élément dans le tableau. La plupart des langues définissent l'index de départ d'un tableau à 0.
Il y a
Unidimensionnel , comme indiqué ci-dessus.
Tableaux
multidimensionnels à l' intérieur des tableaux.
Opérations de base
- Insérer-insère un élément à un index donné
- Get-renvoie un élément à un index donné
- Supprimer-supprimer un élément à un index donné
- Taille-obtenir le nombre total d'éléments dans le tableau
Des questions
- Trouver le deuxième élément de tableau minimum
- Les premiers entiers non répétitifs d'un tableau
- Fusionner deux tableaux triés
- Réorganisation des valeurs positives et négatives dans un tableau
Piles
Une pile est un type de données abstrait, qui est une liste d'éléments organisés selon le principe LIFO (dernier entré - premier sorti, dernier arrivé - premier sorti).
Ce ne sont pas des tableaux. C'est le tour.
Inventé par Alan Thuring.Un exemple de pile serait un tas de livres disposés verticalement. Afin d'obtenir le livre, quelque part au milieu, vous devrez supprimer tous les livres qui y sont placés. C'est ainsi que fonctionne la méthode LIFO (Last In First Out). La fonction "Annuler" dans les applications fonctionne sur LIFO.
L'image de la pile, en trois éléments (1, 2 et 3), où 3 est en haut et sera supprimée en premier.
Opérations de base
- Push insère un élément sur le dessus
- Pop-renvoie l'élément supérieur après avoir retiré de la pile
- isEmpty-renvoie true si la pile est vide
- Top-renvoie l'élément supérieur sans le supprimer de la pile
Des questions
- Implémenter une file d'attente à l'aide de la pile
- Trier les valeurs sur la pile
- Implémentation de deux piles dans un tableau
- Inverser une chaîne à l'aide d'une pile
Files d'attente
Comme les piles, une file d'attente stocke un élément de manière séquentielle. Une différence significative par rapport à la pile est l'utilisation de FIFO (First in First Out) au lieu de LIFO.
Un exemple de ligne est une ligne de personnes. Cette dernière a pris le dernier et vous le ferez, et le premier la quittera en premier.
L'image de la file d'attente, en quatre éléments (1, 2, 3 et 4), où 1 est en haut et sera supprimé en premier
Opérations de base
- Enqueue—) - insère un élément à la fin de la file d'attente
- Dequeue () - supprime un élément du début de la file d'attente
- isEmpty () - retourne vrai si la file d'attente est vide
- Top () - retourne le premier élément de la file d'attente
Des questions
- Implémenter une pile à l'aide d'une file d'attente
- Inverser les N premiers éléments d'une file d'attente
- Génération de nombres binaires de 1 à N à l'aide d'une file d'attente
Liste liée
Une liste liée est un tableau dans lequel chaque élément est un objet distinct et se compose de deux éléments - des données et un lien vers le nœud suivant.
Le principal avantage sur le tableau est la flexibilité structurelle: l'ordre des éléments de la liste chaînée peut ne pas coïncider avec l'ordre de l'emplacement des éléments de données dans la mémoire de l'ordinateur, et l'ordre de parcours de la liste est toujours explicitement déterminé par ses relations internes.
Il y a
Unidirectionnel , chaque nœud stocke l'adresse ou le lien vers le nœud suivant dans la liste et le dernier nœud a l'adresse ou le lien suivant comme NULL.
1-> 2-> 3-> 4-> NULL
Bidirectionnel , deux liens associés à chaque nœud, l'un des points forts au nœud suivant et un au nœud précédent.
NULL <-1 <-> 2 <-> 3-> NULL
Circulaire , tous les nœuds sont connectés pour former un cercle. À la fin, il n'y a pas de NULL. Une liste chaînée cyclique peut être une liste chaînée cyclique simple ou double.
1-> 2-> 3-> 1
La liste unidirectionnelle linéaire la plus courante. Un exemple est un système de fichiers.
Opérations de base
- InsertAtEnd - Insère l'élément spécifié à la fin de la liste.
- InsertAtHead - Insère un élément en haut de la liste
- Supprimer - supprime l'élément spécifié de la liste.
- DeleteAtHead - supprime le premier élément de la liste
- Rechercher - renvoie l'élément spécifié de la liste
- isEmpty - renvoie True si la liste chaînée est vide
Des questions
- Inverser la liste liée
- Définition d'une boucle dans une liste chaînée
- Renvoie N élément de la fin dans la liste chaînée
- Supprimer les doublons d'une liste chaînée
Comtes
Un graphe est un ensemble de nœuds (sommets) qui sont connectés les uns aux autres sous la forme d'un réseau par des arêtes (arcs).
Il y a
Orientées , les côtes sont directionnelles, c'est-à-dire il n'y a qu'une seule direction disponible entre deux sommets connectés.
Sans orientation , pour chacune des côtes, vous pouvez aller dans les deux sens.
Mixte
Trouvé sous des formes telles que
- Matrice d'adjacence
- Liste d'adjacence
Algorithmes généraux de traversée de graphe
- Recherche de largeur - exploration de niveau
- Recherche de profondeur - traverser les pics
Des questions
- Implémenter la recherche en largeur et en profondeur
- Vérifiez si le graphique est un arbre ou non
- Compter le nombre d'arêtes dans un graphique
- Trouvez le chemin le plus court entre deux pics
Les arbres
Un arbre est une structure de données hiérarchique composée de nœuds (sommets) et d'arêtes (arcs). Les arbres sont essentiellement des graphes connectés sans boucles.
Des structures arborescentes partout. Tout le monde connaît l'arbre des compétences dans les jeux.
Arbre simple
Types d'arbres
L'arbre binaire est le plus courant.
«Un arbre binaire est une structure de données hiérarchique dans laquelle chaque nœud a une valeur (c'est aussi la clé dans ce cas) et des références aux descendants gauche et droit. »- ProcsTrois façons de contourner un arbre
- Dans l'ordre direct (de haut en bas) - la forme du préfixe.
- Dans l'ordre symétrique (de gauche à droite) - forme infixe.
- Dans l'ordre inverse (de bas en haut) - formulaire postfix.
Des questions
- Trouver la hauteur d'un arbre binaire
- Trouver le plus petit élément N dans un arbre de recherche binaire
- Trouver des nœuds à une distance N de la racine
- Trouver les ancêtres du nœud N dans l'arbre binaire
Trie (arbre de préfixe)
Une sorte d'arbre à cordes, recherche rapide. Dictionnaires T9
C'est ainsi qu'un tel arbre stocke les mots «top», «ainsi» et «leur».
Les mots sont stockés de haut en bas, les nœuds de couleur verte "p", "s" et "r" pointant vers la fin de "haut", "donc" et "leur", respectivement.
Des questions
- Comptez le nombre total de mots
- Imprimer tous les mots
- Trier les éléments du tableau de l'arborescence des préfixes
- Créer un dictionnaire T9
Hachage de table
Le hachage est un processus utilisé pour identifier de manière unique les objets et stocker chaque objet dans un index unique pré-calculé (clé).
Un objet est stocké sous forme de paire clé-valeur, et une collection de ces éléments est appelée dictionnaire. Chaque objet peut être trouvé à l'aide de cette clé.
En substance, il s'agit d'un tableau dans lequel la clé est représentée comme une fonction de hachage.
Les performances de hachage dépendent de
- Fonctions de hachage
- Taille de la table de hachage
- Méthodes de gestion des collisions
Un exemple de correspondance de hachage dans un tableau. L'index de ce tableau est calculé via une fonction de hachage.
Des questions
- Rechercher des paires symétriques dans un tableau
- Rechercher si un tableau est un sous-ensemble d'un autre tableau
- Décrire le hachage ouvert
Liste des ressources
Au lieu d'une conclusion
Le matériel est aussi intéressant que les langues elles-mêmes. Peut-être que quelqu'un verra les structures de base qui lui sont familières et sera intéressé.
Merci d'avoir lu. J'espère ne pas perdre de temps =)
PS: Je m'excuse, car il s'est avéré que la traduction de l'article était déjà là et très récemment, j'ai négligé.
Si cela vous intéresse, la
voici , merci
Hokum , je serai plus prudent.