★ À maîtriser
📌 En C, l’opérateur & récupère l’adresse d’une variable et l’opérateur unaire * permet d’accéder au contenu de la variable pointée.
📌 La fonction malloc réserve un bloc de la taille demandée en octets et renvoie son adresse, ou NULL si la mémoire disponible est insuffisante.
📌 Après une allocation dynamique, il faut tester le pointeur retourné contre NULL, puis libérer la mémoire obtenue avec malloc, calloc ou realloc à l’aide de free lorsqu’elle n’est plus utilisée.
Compléments
📌 La fonction calloc alloue la mémoire pour un nombre donné d’éléments et initialise cette zone à zéro, tandis que realloc réduit ou augmente la taille d’un bloc existant.
Adresse → pointeur → contenu
★ À maîtriser
🔄 Processus — La recherche séquentielle compare successivement chaque élément du tableau avec l’objet recherché et s’arrête lorsque l’objet est trouvé ou que tous les éléments ont été examinés.
🔄 Processus — La recherche dichotomique découpe à chaque étape une collection triée autour d’un indice médian et poursuit la recherche dans la moitié inférieure ou supérieure selon la comparaison.
🔄 Processus — Le tri par sélection recherche le plus petit élément de la partie non triée et le permute avec le premier élément de cette partie.
🔄 Processus — Le tri à bulles compare des cases contiguës et fait remonter les plus petits éléments vers le début en répétant les passages dans le tableau.
🔄 Processus — Le calcul récursif de la factorielle utilise le cas de base 0! = 1 et la relation n! = n × (n−1)! pour les autres valeurs de n.
⚡ La recherche repose sur une relation d’équivalence telle que l’égalité, tandis que le tri repose sur une relation d’ordre total telle que l’infériorité ou l’égalité.
Compléments
🧮 Formule — Le tri par sélection et le tri à bulles présentés ont une complexité en temps de l’ordre de O(n²) dans le cas étudié.
Chercher, ordonner, s’appeler
★ À maîtriser
🔄 Processus — La manipulation d’un fichier suit l’ordre général ouverture, lecture ou écriture, puis fermeture.
📌 La fonction fopen associe un fichier physique à un descripteur FILE* et renvoie NULL si l’ouverture échoue.
📌 La fonction fread lit des éléments binaires dans un tampon et la fonction fwrite écrit des éléments binaires depuis un tampon, en utilisant leur taille et leur nombre.
⚡ Un fichier texte est une suite de caractères à accès séquentiel, tandis qu’un fichier binaire est organisé en enregistrements et permet notamment l’accès direct.
Compléments
📌 La fonction fseek déplace le descripteur d’un nombre d’octets calculé depuis SEEK_SET, SEEK_CUR ou SEEK_END, et renvoie zéro en cas de réussite.
Ouvrir → traiter → fermer
★ À maîtriser
🔄 Processus — L’initialisation d’une liste consiste à affecter NULL à debut et fin et zéro à taille avant toute autre opération.
🔄 Processus — L’insertion d’un maillon consiste à déclarer ou créer l’élément, allouer sa mémoire, remplir ses données, mettre à jour les pointeurs nécessaires et incrémenter la taille de la liste.
🔄 Processus — L’initialisation d’une liste simplement chaînée met les pointeurs debut et fin à NULL et la taille à zéro avant toute autre opération.
🔄 Processus — Pour insérer en tête, on crée un maillon, on lui affecte la donnée, on fait pointer son champ suivant vers debut, on actualise debut et, si la liste était vide, fin, puis on incrémente la taille.
🔄 Processus — La suppression en tête sauvegarde le premier maillon, avance debut vers son successeur, décrémente la taille, met fin à NULL si la liste devient vide, récupère la donnée puis libère le maillon.
⚡ Les tableaux offrent un accès direct au iᵉ élément sans dépendre de i, tandis que les listes chaînées nécessitent un parcours séquentiel depuis la tête et utilisent un espace supplémentaire pour les pointeurs.
Compléments
🔄 Processus — L’insertion après une position donnée est refusée si la position est inférieure à 1 ou supérieure ou égale à la taille, et sinon le nouveau maillon est relié entre l’élément courant et son successeur avant l’incrémentation de la taille.
🔄 Processus — L’affichage parcourt les maillons de debut jusqu’à NULL, tandis que la destruction supprime successivement les maillons en tête jusqu’à obtenir une taille nulle, puis libère la structure de liste.
Tête → maillon → queue
★ À maîtriser
🔄 Processus — Lors d’une insertion dans une liste doublement chaînée, les pointeurs suivant et precedent du nouveau maillon ainsi que les pointeurs des maillons voisins sont actualisés, avec une mise à jour de debut ou fin si nécessaire.
🔄 Processus — La suppression par position traite le premier élément, le dernier ou un élément intermédiaire en reliant ses voisins, en récupérant sa donnée, en libérant sa mémoire et en décrémentant taille.
Compléments
🔄 Processus — L’initialisation d’une liste doublement chaînée affecte NULL à debut et fin et zéro à taille après l’allocation de la structure.
⚡ Une liste doublement chaînée permet un affichage direct de debut vers fin et un affichage inverse de fin vers debut grâce à ses deux pointeurs de liaison.
Suivant et précédent
★ À maîtriser
🔄 Processus — L’empilement crée un maillon, place la donnée dans ce maillon, le relie à l’ancien debut, actualise debut et incrémente taille.
🔄 Processus — Le dépilement retire le maillon pointé par debut, avance debut vers le maillon suivant, récupère la donnée, libère le maillon et décrémente taille, sauf si la pile est vide.
🔄 Processus — L’enfilement crée un maillon et l’ajoute à fin, en faisant aussi pointer debut vers ce maillon lorsque la file est vide, puis incrémente taille.
🔄 Processus — Le défilement retire le maillon pointé par debut, avance debut, récupère sa donnée, libère le maillon, décrémente taille et met fin à NULL si la file devient vide.
LIFO contre FIFO
★ À maîtriser
🔄 Processus — Pour reconnaître un mot bien parenthésé, on empile chaque parenthèse ouvrante et on dépile la parenthèse correspondante à chaque parenthèse fermante; le mot est accepté si la pile n’est jamais vide lors d’une fermeture et est vide à la fin.
🔄 Processus — L’évaluation postfixée empile les valeurs et, pour chaque opérateur, dépile ses opérandes, applique l’opération dans l’ordre approprié, puis empile le résultat; la seule valeur restante est le résultat final.
🔄 Processus — La conversion infixe-postfixée envoie directement les opérandes dans la sortie, empile les opérateurs selon leur précédence et dépile les opérateurs de précédence supérieure ou égale avant d’empiler l’opérateur courant.
⚡ La notation infixée place les opérateurs entre leurs opérandes, la notation préfixée place l’opérateur avant ses opérandes et la notation postfixée place l’opérateur après ses opérandes.
Compléments
Empiler pour analyser et calculer
★ À maîtriser
⚡ Dans un arbre, la racine n’a pas de père, une feuille n’a pas de fils et un nœud interne possède au moins un fils.
🧮 Formule — La hauteur d’un arbre vide vaut 0 et celle d’un arbre non vide vaut 1 plus le maximum des hauteurs de ses sous-arbres gauche et droit.
⚡ Un parcours en profondeur explore complètement une branche avant de passer à la suivante, tandis qu’un parcours en largeur visite les nœuds niveau par niveau.
Compléments
🧮 Formule — Le nombre de nœuds d’un arbre vide vaut 0 et celui d’un arbre non vide vaut 1 plus la somme des nombres de nœuds de ses deux sous-arbres.
Racine, fils, feuilles
★ À maîtriser
🔄 Processus — Le nombre de nœuds d’un arbre vide vaut 0 ; sinon il vaut 1 plus la somme des nombres de nœuds de ses sous-arbres gauche et droit.
🔄 Processus — Le nombre de feuilles d’un arbre vide vaut 0 ; celui d’un arbre dont la racine est une feuille vaut 1 ; sinon il est égal à la somme des nombres de feuilles de ses deux sous-arbres.
🔄 Processus — Le nombre de nœuds internes d’un arbre vide ou d’un arbre réduit à une feuille vaut 0 ; sinon il vaut 1 plus la somme des nombres de nœuds internes de ses sous-arbres.
Vide = 0 ; sinon on décompose en sous-arbres
★ À maîtriser
📌 Dans un parcours préfixe RGD, on traite la racine avant le fils gauche puis le fils droit.
📌 Dans un parcours infixe GRD, on traite le fils gauche, puis la racine, puis le fils droit ; appliqué à un arbre binaire de recherche, il fournit les valeurs dans l’ordre croissant.
📌 Dans un parcours postfixe GDR, on traite le fils gauche, puis le fils droit, puis la racine.
Compléments
🔄 Processus — La fonction DFS parcourt récursivement un arbre non vide en plaçant le traitement de la racine avant l’appel gauche pour le préfixe, entre les appels gauche et droit pour l’infixe, ou après l’appel droit pour le postfixe.
RGD, GRD, GDR : la position de la racine change
★ À maîtriser
🔄 Processus — La création d’un arbre à partir d’un élément et de deux sous-arbres consiste à allouer un nœud, à lui attribuer sa valeur et à placer les deux sous-arbres dans ses fils gauche et droit, puis à renvoyer un pointeur vers ce nœud.
🔄 Processus — L’insertion simple cherche récursivement un fils vide ; si l’arbre est vide, elle crée un arbre, si un fils est vide, elle y insère le nouvel élément, et sinon elle poursuit l’insertion du côté choisi, par exemple à gauche.
📌 Dans un arbre binaire de recherche contenant des entiers, les valeurs du sous-arbre gauche sont inférieures à la racine et celles du sous-arbre droit lui sont supérieures ou égales, les valeurs égales étant insérées à droite.
Compléments
🔄 Processus — Pour insérer une valeur dans un arbre binaire de recherche, on crée un nœud si l’arbre est vide ; sinon on compare la valeur à la racine et on poursuit récursivement à gauche si elle est plus petite, ou à droite dans le cas contraire.
Créer, puis insérer selon la structure choisie
★ À maîtriser
🔄 Processus — Dans un arbre quelconque, la recherche renvoie 0 si l’arbre est vide, 1 si la racine contient la valeur cherchée, et sinon le résultat logique de la recherche dans les sous-arbres gauche et droit.
🔄 Processus — Dans un arbre binaire de recherche, la recherche renvoie 0 pour un arbre vide, 1 si la racine contient la valeur cherchée, puis explore le sous-arbre gauche si la valeur cherchée est plus petite que la racine et le sous-arbre droit sinon.
🔄 Processus — La suppression complète d’un arbre consiste à supprimer récursivement le sous-arbre gauche, puis le sous-arbre droit, avant de libérer la racine ; elle correspond donc à un parcours postfixe.
⚡ Dans un arbre quelconque, la recherche peut explorer les deux sous-arbres, tandis que dans un arbre binaire de recherche elle suit une seule branche grâce à l’ordre des valeurs.
Compléments
📌 Dans le cours, la suppression d’un nœud est limitée à la suppression d’une feuille, car supprimer un nœud possédant des fils impose de réorganiser ou de supprimer ses sous-arbres.
Recherche guidée ou exhaustive ; suppression des feuilles
| Dimension | Tableau | Liste chaînée |
|---|---|---|
| Accès | Direct au iᵉ élément | Séquentiel depuis la tête |
| Mémoire | Éléments contigus | Maillons dispersés possibles |
| Taille | Fixée à l’avance | Adaptée au nombre d’éléments |
| Insertion et suppression | Peu flexibles | Réalisées par modification des pointeurs |
| Structure | Insertion | Suppression | Ordre |
|---|---|---|---|
| Pile | Tête | Tête | LIFO |
| File | Queue | Tête | FIFO |
Teste tes connaissances sur Listes, piles, files et arbres avec 46 questions à choix multiples et corrections détaillées.
1. Quel type d’adressage permet d’accéder au contenu d’une variable en utilisant le nom de cette variable ?
2. Dans un programme C, qu’est-ce qu’un pointeur contient précisément ?
Mémorisez les concepts clés de Listes, piles, files et arbres avec 91 flashcards interactives.
Qu'est-ce que l’adressage direct en programmation ?
Accéder au contenu d’une variable par son nom.
Qu'est-ce qu'un pointeur en C ?
Une variable qui contient l’adresse d’une autre variable et est typée.
Que fait l’opérateur & en langage C ?
Il récupère l’adresse d’une variable.
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches