Fiche de révision : Introduction aux structures de données en C

📋 Plan du Cours

1. Recherche dichotomique dans un vecteur ordonné
2. Algorithmes de tris simples : sélection, insertion et bulle
3. Concepts fondamentaux des pointeurs en C
4. Principes et critères des fonctions récursives
5. Algorithmes de tris complexes : tri rapide et tri par tas
6. Représentation et manipulation des chaînes de caractères en C
7. Définition, déclaration et utilisation des structures en C
8. Gestion des fichiers séquentiels : lecture, écriture et modification
9. Introduction aux tables de hachage et définition des clés
10. Fonctions de hachage : calculs et conversion de chaînes en indices
11. Gestion des collisions dans les tables de hachage et optimisation
12. Utilisation des fichiers en C : création, lecture séquentielle et accès direct

📖 1. Recherche dichotomique dans un vecteur ordonné

🔑 Notions clés & Définitions

• Vecteur ordonnés : Structure de données linéaire dont les éléments sont rangés selon un ordre précis, ce qui impose des contraintes spécifiques pour la gestion et permet d'exploiter cet ordre dans les algorithmes.
• Principe : Si on recherche une valeur w dans un intervalle v=[inf, sup], le milieu de l’intervalle est inf+sup div 2.
• Recherche dichotomique : Recherche dichotomique d’une valeur dans un vecteur ordonné.
• Intervalle de recherche : Le vecteur entier.

📝 Points essentiels

• La recherche dichotomique exploite l'ordre du vecteur pour diviser l'intervalle de recherche en deux à chaque étape.
• Le milieu de l'intervalle est calculé par (inf + sup) div 2 pour comparer la valeur recherchée.
• La recherche dichotomique est plus performante que la recherche séquentielle dans un vecteur ordonné.
• Au départ l’intervalle de recherche est le vecteur entier.
• → si w est inférieur a v[milieu] on continue la recherche dans l’intervalle → sinon on continue la recherche dans l’intervalle [milieu+1,sup] on s’arrête quand l’intervalle v est vide, c’est a dire quand inf>sup ou que l’élément est trouvé.

💡 À retenir

La recherche dichotomique optimise la recherche dans un vecteur ordonné en réduisant exponentiellement l'espace de recherche à chaque étape.

📖 2. Algorithmes de tris simples : sélection, insertion et bulle

🔑 Notions clés & Définitions

• Tri par sélection : Méthode qui consiste à déterminer l'élément minimum dans un sous-vecteur et à l'échanger avec l'élément en position courante, répétée pour chaque position du vecteur, avec une complexité en O(n²).
• Tri par insertion : Algorithme qui suppose les i-1 premiers éléments triés et insère le ième élément à sa place dans cette partie triée en décalant les éléments nécessaires, avec une complexité en O(n²).
• Tri à bulle : Procédé qui compare et échange des éléments adjacents si le premier est supérieur au second, faisant remonter les plus grands éléments vers la fin du vecteur, répété jusqu'à ce que le vecteur soit trié, avec une complexité en O(n²).
• Tris par sélection : tris par sélection du minimum.

📝 Points essentiels

• Le tri par insertion insère chaque nouvel élément à sa place dans la partie déjà triée du vecteur.
• Le tri à bulle compare et échange les éléments adjacents pour faire remonter les plus grands éléments vers la fin du vecteur.
• Ces algorithmes sont simples mais ont une complexité quadratique, peu adaptés aux grands vecteurs.

💡 À retenir

Le tri par insertion insère chaque nouvel élément à sa place dans la partie déjà triée du vecteur.

📖 3. Concepts fondamentaux des pointeurs en C

🔑 Notions clés & Définitions

• Tampon : Un espace mémoire temporaire utilisé pour stocker des données lors de leur lecture ou écriture, facilitant la gestion des flux ou fichiers.
• Passage par valeur : Un mode de transmission des paramètres où une copie locale de la valeur est créée dans la fonction appelée, sans affecter la variable d'origine.
• Pointeur : Une variable stockant une adresse mémoire pointant vers une donnée d'un type spécifique, permettant d'accéder et de manipuler directement cette donnée en mémoire.

📝 Points essentiels

• Un pointeur est une variable contenant une adresse mémoire d'un type connu, permettant de manipuler directement la mémoire.
• L'opérateur * permet d'accéder à la valeur pointée par un pointeur.
• Le passage par valeur crée une copie locale des paramètres, tandis que le passage par adresse utilise des pointeurs pour modifier les variables originales.
• L'utilisation des pointeurs permet de manipuler directement les données en mémoire et d'échanger des valeurs via des fonctions.

💡 À retenir

Un pointeur est une variable contenant une adresse mémoire d'un type connu, permettant de manipuler directement la mémoire.

📖 4. Principes et critères des fonctions récursives

🔑 Notions clés & Définitions

• Appel récursif : L'invocation d'une fonction par elle-même au sein de son propre corps, utilisée pour traiter des problèmes pouvant être divisés en sous-problèmes similaires.
• Condition d'arrêt : La condition d’arrêt porte sur la valeur d’un des arguments de la fonction.
• Fonctions récursives : fonctions récursives terminales.

📝 Points essentiels

• Une fonction récursive doit posséder au moins un cas de base avec une condition d'arrêt sans appel récursif.
• Le compilateur empile l'adresse de retour et les variables locales avant chaque appel récursif, puis dépile à chaque retour.
• Les fonctions récursives terminales optimisent la récursivité en évitant l'empilement supplémentaire, en remplaçant l'appel précédent.
• Il faut s'assurer que le nombre d'appels récursifs est fini pour éviter les boucles infinies.
• Une telle condition s’appelle condition d’arrêt ou test d’arrêt et amène au cas de base.

💡 À retenir

La récursivité repose sur un équilibre entre auto-appels et conditions d'arrêt pour garantir la terminaison et la gestion efficace de la pile.

📖 5. Algorithmes de tris complexes : tri rapide et tri par tas

🔑 Notions clés & Définitions

• Pivot : Élément choisi dans le tri rapide pour diviser le vecteur en deux parties, celles inférieures et celles supérieures à cet élément, facilitant ainsi la partition du tableau.
• Tris les plus : Algorithmes de tri plus performants et complexes, comme le tri rapide et le tri par tas, qui utilisent des structures ou stratégies avancées pour optimiser le tri sur de grands ensembles de données.
• Chaque appel : Chaque invocation récursive traite un sous-ensemble du tableau initial, progressant vers un cas de base où le sous-ensemble est suffisamment petit ou trié, assurant la terminaison de l'algorithme.

📝 Points essentiels

• Le tri rapide utilise la méthode diviser pour régner en choisissant un pivot pour partitionner le vecteur.
• Le choix du pivot influence la performance du tri rapide, avec des stratégies comme le pivot aléatoire ou médian pour optimiser le coût moyen.
• Le tri par tas construit un tas binaire pour extraire successivement les éléments maximums, améliorant la complexité à O(n log n).
• Le tri par tas est plus performant que les tris simples sur de grandes données, notamment grâce à sa structure de tas binaire.
• Il est basé sur la méthode diviser pour pour régner.

💡 À retenir

Les tris complexes combinent des structures et stratégies avancées pour optimiser le tri sur de grands ensembles de données.

📖 6. Représentation et manipulation des chaînes de caractères en C

🔑 Notions clés & Définitions

• Solution : 1 on passe en récursive terminale si on peut.
• Représentation binaire : La représentation binaire d'une chaîne de caractères en C correspond à la séquence des codes ASCII de ses caractères stockés dans un tableau.

📝 Points essentiels

• Les chaînes de caractères en C sont des tableaux de caractères terminés par un caractère nul '\0'.
• Les fonctions atoi, atol et atof convertissent une chaîne en entier, long ou flottant respectivement.
• → comment passer d’une chaîne de caractère a un entier.

💡 À retenir

La manipulation des chaînes en C repose sur des conventions et fonctions standard permettant la gestion efficace des textes.

📖 7. Définition, déclaration et utilisation des structures en C

🔑 Notions clés & Définitions

📝 Points essentiels

• Une structure en C est un type composite regroupant plusieurs champs de types différents.
• La déclaration d'une structure crée un nouveau type sans réserver de mémoire.
• La mémoire est réservée lors de la déclaration d'une variable de ce type.
• L'accès aux champs se fait via l'opérateur point (.) pour une variable structure.
• Il est possible de copier une structure entière dans une autre du même type.
• → en travaillant de manière globale sur l’ensemble de la structure, il est possible d’affecter a une structure le contenu d’une structure définie a partir du même modèle.
• La désignation du champs ce note en faisant suivre le nom de la variable structuré de l’opérateur point (prioritaire) suivit du nom du champ tel qu’il a était définit dans le modèle.

💡 À retenir

Les structures en C permettent de modéliser des données complexes en regroupant plusieurs champs sous un même type.

📖 8. Gestion des fichiers séquentiels : lecture, écriture et modification

🔑 Notions clés & Définitions

• Lecture : Opération consistant à extraire les données d'un fichier en lisant les enregistrements dans l'ordre où ils apparaissent.
• Char ch(20) : Déclaration en langage C d'une chaîne de caractères pouvant contenir jusqu'à 20 caractères, utilisée pour stocker des séquences de caractères.

📝 Points essentiels

• La lecture et l'écriture dans un fichier séquentiel se font dans l'ordre des enregistrements.
• La modification directe d'un enregistrement dans un fichier séquentiel est généralement impossible.
• Pour modifier un fichier, on crée un nouveau fichier en copiant les données avec les modifications souhaitées.
• La fin de fichier est détectée par une fonction spécifique (ex : feof en C).
• Les fichiers séquentiels sont adaptés au traitement linéaire des données.
• //w= écriture, r= lecture, a = modifier/écrire en fin de fichier.
• On peut utiliser l’accès séquentiel pour lire tout les enregistrements du fichier dans l’ordre ou ils apparaissent.

💡 À retenir

La gestion des fichiers séquentiels privilégie la simplicité d'accès linéaire au prix de contraintes sur la modification directe.

📖 9. Introduction aux tables de hachage et définition des clés

🔑 Notions clés & Définitions

• Tables de hachage : Des structures de données reposants sur les tableaux.
• Dans le tableau : Disposition des éléments rangés en fonction de leur clé dans un tableau, permettant un accès direct à un élément par le calcul de sa position à partir de cette clé.

📝 Points essentiels

• Une table de hachage est une structure statique basée sur un tableau pour un accès rapide aux éléments.
• La clé discriminante identifie de manière unique un élément dans la table.
• L'accès à un élément est immédiat en connaissant sa clé, contrairement à une recherche séquentielle.

💡 À retenir

Une table de hachage est une structure statique basée sur un tableau pour un accès rapide aux éléments.

📖 10. Fonctions de hachage : calculs et conversion de chaînes en indices

🔑 Notions clés & Définitions

• Fonction de hachage : Être injective car sinon on aurait H(K1)=H(K2)=i.

📝 Points essentiels

• La fonction de hachage transforme une clé en un indice dans un tableau de taille fixe.
• Pour les chaînes, la fonction de hachage peut sommer les codes ASCII pondérés des caractères.
• Le résultat est souvent réduit modulo la taille du tableau pour obtenir un indice valide.

💡 À retenir

Les fonctions de hachage convertissent efficacement des clés complexes en indices numériques exploitables dans des tableaux.

📖 11. Gestion des collisions dans les tables de hachage et optimisation

🔑 Notions clés & Définitions

• Collision : Situation où deux clés différentes sont associées au même indice dans la table de hachage en raison d'une fonction de hachage non injective.

📝 Points essentiels

• Le choix de la taille de la table et du pas d'incrément doit être premier pour une bonne dispersion.
• Un taux d'occupation élevé augmente le nombre de collisions et ralentit les recherches.

💡 À retenir

La gestion efficace des collisions est cruciale pour préserver la rapidité d'accès dans les tables de hachage.

📖 12. Utilisation des fichiers en C : création, lecture séquentielle et accès direct

🔑 Notions clés & Définitions

• Création : Processus d'ouverture d'un fichier avec fopen en mode écriture ou ajout, permettant de créer un nouveau fichier ou d'écraser un fichier existant.
• Sortie : Action de fermer un fichier avec fclose afin de libérer les ressources associées.
• Lecture : Opération de lecture de données depuis un fichier en manipulant des blocs de mémoire avec fread.
• Inconvénient : On ne peut accéder a certaine cases que par d’autres.
• Attention : M et p doivent être premier.

📝 Points essentiels

• La création et ouverture d'un fichier se fait avec fopen en mode lecture, écriture ou ajout.
• La lecture et écriture se font avec fread et fwrite en manipulant des blocs de mémoire.
• L'accès direct est possible avec fseek pour se déplacer à une position précise dans le fichier.
• La fermeture du fichier se fait avec fclose pour libérer les ressources.
• OUVRIR (nom_fichier) (écrasent et ) ouverture en écriture.

💡 À retenir

La création et ouverture d'un fichier se fait avec fopen en mode lecture, écriture ou ajout.

🧩 Compléments de couverture

1. Détail source à réviser : des matières Chapitre 1 : vecteur ordonnés : recherche et tris simple.......................................................................2 I. Recherche dichotomique d’une valeur dans un vecteur ordonné................ (Source: "des matières Chapitre 1 : vecteur ordonnés : recherche et tris simple.......................................................................2 I. Recherche dichotomique d’une valeur dans un vecteur ordonné.................................................2 II. algorithme de tris")
2. Détail source à réviser : Chapitre 2 : les pointeurs...................................................................................................................... 4 Chapitre 3 : récursivité................................................. (Source: "Chapitre 2 : les pointeurs...................................................................................................................... 4 Chapitre 3 : récursivité......................................................................................................................... 7 I.")
3. Détail source à réviser : 8 IV. fonctions récursives terminales................................................................................................. 8 V. danger et précautions........................................................... (Source: "8 IV. fonctions récursives terminales................................................................................................. 8 V. danger et précautions..................................................................................................................9 Chapitre 4 : les tris")
4. Détail source à réviser : Performance..........................................................................................................................10 4. Choisir le meilleur pivot........................................................ (Source: "Performance..........................................................................................................................10 4. Choisir le meilleur pivot....................................................................................................... 11 5.")
5. Détail source à réviser : ....................................................................................................12 3. amélioration possible............................................................................................. (Source: "....................................................................................................12 3. amélioration possible............................................................................................................ 12 Chapitre 5 : les données")
6. Détail source à réviser : .................................................................................. 14 1. en algorithme...................................................................................................................... (Source: ".................................................................................. 14 1. en algorithme.........................................................................................................................14 2. en")
7. Détail source à réviser : ............................................................................21 2.lecture sequentielle.................................................................................................................21 3.a (Source: "............................................................................21 2.lecture sequentielle.................................................................................................................21 3.accès direct............................................................................................................................. 22")
8. Détail source à réviser : ...............................................................24 IV. exemple de fonction de hachage..............................................................................................25 V. autre méthode pour l (Source: "...............................................................24 IV. exemple de fonction de hachage..............................................................................................25 V. autre méthode pour la gestion des collisions : hachage linéaire...............................................26 Chapitre 1 : vecteur ordonnés : recherche et")
9. Détail source à réviser : pour rechercher un élément on va diviser le vecteur en 2 et chercher dans quelle partie il faut poursuivre la recherche. On itère (recommence) ce mécanisme jusqu’à trouver l’élément ou jusqu’à ce que l’intervalle de rech (Source: "pour rechercher un élément on va diviser le vecteur en 2 et chercher dans quelle partie il faut poursuivre la recherche. On itère (recommence) ce mécanisme jusqu’à trouver l’élément ou jusqu’à ce que l’intervalle de recherche soit vide. Principe : si on recherche une valeur w dans un intervalle v=[inf, sup], le milieu de l’intervalle est inf+sup")
10. Détail source à réviser : alphabétique pour les chaînes de caractères. 1. tris par sélection du minimum. Soit le vecteur v de nb éléments la méthode consiste a déterminer l’élément v[k] minimum et a l’échanger avec le premier élément v[1]. Puis a (Source: "alphabétique pour les chaînes de caractères. 1. tris par sélection du minimum. Soit le vecteur v de nb éléments la méthode consiste a déterminer l’élément v[k] minimum et a l’échanger avec le premier élément v[1]. Puis a recommencer avec un sous vecteur de nb -1 éléments entre les indices 2 et nb. On détermine alors l’élément v[k] minimum entre les")
11. Détail source à réviser : on range le deuxième élément par rapport au premier. Puis on prend un troisième élément que l’on met a sa place et ainsi de suite jusqu’au dernier élément. Principe : on suppose les i-1 premier élément du vecteur trier. (Source: "on range le deuxième élément par rapport au premier. Puis on prend un troisième élément que l’on met a sa place et ainsi de suite jusqu’au dernier élément. Principe : on suppose les i-1 premier élément du vecteur trier. On prend le ième élément et on essai de le mettre a sa place dans les i-1 éléments déjà trié. On continue ainsi jusqu’à i=nb. Pour classer")
12. Détail source à réviser : la suite du tri. Principe : soit le le vecteur v de nb éléments. Le tri a bulle consiste a comparer deux éléments consécutifs et a les permuté s’ils ne sont pas correctement ordonné c’est a dire si l’élément v[i] est sup (Source: "la suite du tri. Principe : soit le le vecteur v de nb éléments. Le tri a bulle consiste a comparer deux éléments consécutifs et a les permuté s’ils ne sont pas correctement ordonné c’est a dire si l’élément v[i] est supérieur au suivant, v[i+1]. Pour cela il faut parcourir séquentiellement le vecteur entre les indices 1 et sup. Sup variant de nb à 2.")
13. Détail source à réviser : tout les trois avec une complexité O(n²). Il existe beaucoup d’autre algorithmes de tris beaucoup plus performant mais aussi beaucoup plus complexe. Chapitre 2 : les pointeurs. 1. un pointeur est une variables dont les v (Source: "tout les trois avec une complexité O(n²). Il existe beaucoup d’autre algorithmes de tris beaucoup plus performant mais aussi beaucoup plus complexe. Chapitre 2 : les pointeurs. 1. un pointeur est une variables dont les valeurs sont des adresses de type connu. Il s’agit en fait d’un type abstrait de donnée obéissant au spécification suivante : a. c’est")
14. Détail source à réviser : aussi pointé par p). et il est noté *p. on appelle cela aussi la déréférenciation ou la indirection. Ex : int *p ; int a ; c. modificateurs. Il y a trois moficateurs. → l’affectation : affecter une variable a un pointeur (Source: "aussi pointé par p). et il est noté *p. on appelle cela aussi la déréférenciation ou la indirection. Ex : int *p ; int a ; c. modificateurs. Il y a trois moficateurs. → l’affectation : affecter une variable a un pointeur. Ex : p=&a ; (p = adresse de a). → allocation mémoire : permet de faire des tableau dynamique. Ex : p=malloc(taille) ; int *tab ; int")
15. Détail source à réviser : papier ! /*exemple 2. */ int i ; char caract,c ; char mot[6]= « bravo » ; char *pc, *pmot, *ptr ; /schéma papier/ pc=&c ; c=’a’ ; printf(« %c »,*pc) ; /A/ caract=*pc ; printf(« %c »,caract) ; /A/ pmot=&mot[0] ; ptr (Source: "papier ! /*exemple 2. */ int i ; char caract,c ; char mot[6]= « bravo » ; char *pc, *pmot, *ptr ; /schéma papier/ pc=&c ; c=’a’ ; printf(« %c »,*pc) ; /A/ caract=*pc ; printf(« %c »,caract) ; /A/ pmot=&mot[0] ; ptr=pmot ; printf(« %c », *ptr) ; /B/ ptr=ptr+1 ; printf(« %c »,*ptr) ; /R/ printf(« %c », *(ptr+1)) ; /A/ printf(« %c », *ptr+1) ;")
16. Détail source à réviser : paramètres principal était le passage par valeur. int somme(int n) { int som ; int i ; som=0 ; for (i=1, i<=n, i++){ som=som+i ;} return(som) ;} pp cin>>x ; cout<< « la somme est : »<<somme(x) ; void echange(int &a, int& (Source: "paramètres principal était le passage par valeur. int somme(int n) { int som ; int i ; som=0 ; for (i=1, i<=n, i++){ som=som+i ;} return(som) ;} pp cin>>x ; cout<< « la somme est : »<<somme(x) ; void echange(int &a, int&b){ int temp ; temp=0 ; a=b ; b=temp ;} c’est une méthode C++, en C cela ne marche pas. void echange(int *pa, int *pb){ int temp ; temp=*pa")
17. Détail source à réviser : v passé par valeur 1. la création d’une variable locale appelé vlocale, du même type que v. 2. l’initialisation de vlocale à v, c’est a dire la recopie de tout le contenu de v à vlocale. 3. la substitution de toute les o (Source: "v passé par valeur 1. la création d’une variable locale appelé vlocale, du même type que v. 2. l’initialisation de vlocale à v, c’est a dire la recopie de tout le contenu de v à vlocale. 3. la substitution de toute les occurrences de v par vlocale dans le bloc relatif au sous programme. → paramètres et variables d’un sous programme récursif. Le")
18. Détail source à réviser : conditionnelle dont l’un au moins des cas même a une expression évaluable sans appel récursif. Une telle condition s’appelle condition d’arrêt ou test d’arrêt et amène au cas de base. 2. il faut s’assurer que pour toute (Source: "conditionnelle dont l’un au moins des cas même a une expression évaluable sans appel récursif. Une telle condition s’appelle condition d’arrêt ou test d’arrêt et amène au cas de base. 2. il faut s’assurer que pour toute valeurs du ou des arguments il suffira d’un nombre finit d’appel récursifs pour atteindre la condition d’arrêt. Ces deux règles assure la")
19. Détail source à réviser : est l’appel récursif est que nous soustrayons 1 a chaque appel jusqu’à ce que n=1 qui est la condition de sortie. Lorsque la fonction rencontre la condition de sortie elle remonte dans tout les appels précédents pour cal (Source: "est l’appel récursif est que nous soustrayons 1 a chaque appel jusqu’à ce que n=1 qui est la condition de sortie. Lorsque la fonction rencontre la condition de sortie elle remonte dans tout les appels précédents pour calculer n avec la valeur précédemment trouvée. Voir papier. Les appels des fonctions récursives sont empilées, pile qui est une")
20. Détail source à réviser : un autre type de récursivité, c’est la récursivité terminale. IV. fonctions récursives terminales. C’est une récursivité avec uniquement une phase de descente sans remontée. Ceci est possible si la dernière expression de (Source: "un autre type de récursivité, c’est la récursivité terminale. IV. fonctions récursives terminales. C’est une récursivité avec uniquement une phase de descente sans remontée. Ceci est possible si la dernière expression de la fonction renvoie directement la valeur obtenu par l’appel récursif courant sans qu’il y est d’autre opérations a faire. En")
21. Détail source à réviser : courant du sous programme voir trace sur papier. V. danger et précautions. Le sous programmes récursifs sont un moyen assez puissant pour résoudre différents problèmes de façons élégante, ils n’en restent pas moins dange (Source: "courant du sous programme voir trace sur papier. V. danger et précautions. Le sous programmes récursifs sont un moyen assez puissant pour résoudre différents problèmes de façons élégante, ils n’en restent pas moins dangereux et ce pour plusieurs raisons. 1. dépassement de capacité. → Une des causes assez fréquente quand on travaille sur de très grands")
22. Détail source à réviser : du programme. Dans la pile on met : adresse de retours, variables locales et paramètre/argument passé par valeur (ou copie). Solution : 1 on passe en récursive terminale si on peut. 2 on essaie de minimiser le nombres de (Source: "du programme. Dans la pile on met : adresse de retours, variables locales et paramètre/argument passé par valeur (ou copie). Solution : 1 on passe en récursive terminale si on peut. 2 on essaie de minimiser le nombres de variables locale. 3, si on ne peut pas faire de récursive terminale, on passe en paramètre stocker par valeur en paramètre passé")
23. Détail source à réviser : supérieurs soit a sa droite. Cette opération s’appelle le partitionnement. Pour chacun des deux sous tableau, on définit un nouveau pivot et on répéte l’opération de partitionnement. Ce processus est répéter jusqu’à ce q (Source: "supérieurs soit a sa droite. Cette opération s’appelle le partitionnement. Pour chacun des deux sous tableau, on définit un nouveau pivot et on répéte l’opération de partitionnement. Ce processus est répéter jusqu’à ce que l’ensemble des éléments soit trié. 10 12 6 19 23 8 5 17 5 12 8 19 8 5 6 10 23 19 12 17 6 5 8 10 23 19 12 17 5 6 8 10 5 6 8 10 17 23")
24. Détail source à réviser : aléatoire, soit on choisi le pivot aléatoirement. Dans la pratique, pour les partitions avec un faible nombre d’éléments (15 a peut-près) on retourne souvent sur un tri par insertion qui sera plus efficace que le tri rap (Source: "aléatoire, soit on choisi le pivot aléatoirement. Dans la pratique, pour les partitions avec un faible nombre d’éléments (15 a peut-près) on retourne souvent sur un tri par insertion qui sera plus efficace que le tri rapide sur un petit nombre d’éléments. Grâce a ses bonnes performance et a sont implémentation facile Quick Sort est l’un des algo")
25. Détail source à réviser : trois solutions courante pour choisir le pivot : 1. prendre l’élément du milieu. 2. choisir le médian du premier, dernier et milieu. 3. choisir un pivot aléatoirement. 5. implémentation Cf tp ! II. Tri par tas (ou HeapSo (Source: "trois solutions courante pour choisir le pivot : 1. prendre l’élément du milieu. 2. choisir le médian du premier, dernier et milieu. 3. choisir un pivot aléatoirement. 5. implémentation Cf tp ! II. Tri par tas (ou HeapSort) Découvert en 1964 par Wialliams. Aussi appelé tris maximier. Ce tri est une accélération du tri par sélection et échange. Une")
26. Détail source à réviser : même profondeur. Dans l’algorithme, on cherche a obtenir un tas, c’est a dire un arbre binaire vérifiant les propriétés suivantes : 1→ la différence maximale de profondeur entre deux feuille est de 1. c’est a dire que to (Source: "même profondeur. Dans l’algorithme, on cherche a obtenir un tas, c’est a dire un arbre binaire vérifiant les propriétés suivantes : 1→ la différence maximale de profondeur entre deux feuille est de 1. c’est a dire que toute les feuilles ce trouve sur la dernière ou l’avant dernière ligne. 2→ les feuilles de profondeur maximale sont tassé a gauche. 3→ chaque")
27. Détail source à réviser : A, on commence par construire un tas en ajoutant successivement a[1] puis a[2] etc jusqu’à avoir le tas complet. On peur répéter les opérations suivante : 1. prendre le maximum. 2. le retirer du tas. 3. le ranger dans le (Source: "A, on commence par construire un tas en ajoutant successivement a[1] puis a[2] etc jusqu’à avoir le tas complet. On peur répéter les opérations suivante : 1. prendre le maximum. 2. le retirer du tas. 3. le ranger dans le tableau en commençant par la droite. 2. algorithme. Algo voir papier. (a mettre après le premier algo) pour organiser un tableau en tas")
28. Détail source à réviser : par tas mélange d’abord avant de retrié. L’algorithme SmoothSort évite ce problème. A la fin du tri par tas, c’est a die environs 15 éléments on était trié, l’algorithme effectue plusieurs fois de suite les même inversio (Source: "par tas mélange d’abord avant de retrié. L’algorithme SmoothSort évite ce problème. A la fin du tri par tas, c’est a die environs 15 éléments on était trié, l’algorithme effectue plusieurs fois de suite les même inversions. On peut a la place arrêter l’algorithme quand il reste peut d’éléments et passer a un algorithme plus simple de tri. Les données qui")
29. Détail source à réviser : une chaîne de caractère sous forme d’un vecteur de caractères. Le ième caractère de la chaîne ch ce notant ch[i]. pour la déclarations : on écrira directement : ch : chaîne(taille). Pour l’affectation : ch ← « mercredi » (Source: "une chaîne de caractère sous forme d’un vecteur de caractères. Le ième caractère de la chaîne ch ce notant ch[i]. pour la déclarations : on écrira directement : ch : chaîne(taille). Pour l’affectation : ch ← « mercredi ». on peut tester l’égalité de deux chaîne : SI (ch1=ch2) alors… mais aussi la comparaison entre 2 chaîne : SI (ch1<ch2) alors…")
30. Détail source à réviser : de connaître la position d’une sous-chaîne, de supprimer des caractères, d’ajouter des caractères. #include <string.h> .longueurs : strlen(ch) .concaténation : strcat(but,source) . concaténation partielle : srtcat(but,so (Source: "de connaître la position d’une sous-chaîne, de supprimer des caractères, d’ajouter des caractères. #include <string.h> .longueurs : strlen(ch) .concaténation : strcat(but,source) . concaténation partielle : srtcat(but,source,longueur) ex : cha ch1[20]= « bonjour » ; char *ch2= « monsieur » ; strcat(ch1,ch2,6) ; // ‘bonjour monsi’ . comparaison :")
31. Détail source à réviser : en flottant. II. structures. 1. en algorithme. On définit une structure Elmt_str comme un élément complexe composé de plusieurs champs de nature différentes. Elmt_str est le nom global de l’élément il représente un nouve (Source: "en flottant. II. structures. 1. en algorithme. On définit une structure Elmt_str comme un élément complexe composé de plusieurs champs de nature différentes. Elmt_str est le nom global de l’élément il représente un nouveau type. On peut le décrire par : Elm_str : DEB_STRUCT champ1 : type champ 2 : type champn : type FIN_STRUCT ex Spersonne : DEB_STRUCT")
32. Détail source à réviser : : Soit une personne individu de la structure Spersonne, on accède au champ de individu par individu.nom, individu.prenom, individu.tel etc. les imbrication de structure sont possible mais la syntaxe est très liée au lang (Source: ": Soit une personne individu de la structure Spersonne, on accède au champ de individu par individu.nom, individu.prenom, individu.tel etc. les imbrication de structure sont possible mais la syntaxe est très liée au langage de programmation utilisé. 2. en c. .déclaration d’une structure : stuct enreg { //enreg = nom de la structure. int numero ; int")
33. Détail source à réviser : article1.numéro = 15 ; //15 est affecter au champ numéro de article1. → en travaillant de manière globale sur l’ensemble de la structure, il est possible d’affecter a une structure le contenu d’une structure définie a pa (Source: "article1.numéro = 15 ; //15 est affecter au champ numéro de article1. → en travaillant de manière globale sur l’ensemble de la structure, il est possible d’affecter a une structure le contenu d’une structure définie a partir du même modèle. Ex : article2=article1 ; //on copie tout les champs de article 1 dans article2. Attention : article1==article2")
34. Détail source à réviser : Spersonne : { char nom[30] char prénom[20] float heures[31]}, struct Spersonne employe ; employe.heure[4] //float employe.nom[0] //caractère employer.nom //chaîne .tableaux contenant des structures. Structure Spoint { ch (Source: "Spersonne : { char nom[30] char prénom[20] float heures[31]}, struct Spersonne employe ; employe.heure[4] //float employe.nom[0] //caractère employer.nom //chaîne .tableaux contenant des structures. Structure Spoint { char nom ; float x ; float y;}, Struct Spoint courbe[50] ; courbe[2].nom=caractère courbe[4]=struct Spoint .imbrication de")
35. Détail source à réviser : un champs : …(*employer).nom… //employer → nom .transmition d’une structure en valeur de retour d’une fonction. → Struct Spersonne fct (…) {struct Spersonne employe ; return(employer);} Chap 6 : Fichier. I . En algorithm (Source: "un champs : …(*employer).nom… //employer → nom .transmition d’une structure en valeur de retour d’une fonction. → Struct Spersonne fct (…) {struct Spersonne employe ; return(employer);} Chap 6 : Fichier. I . En algorithme le terme fichier désigne un ensemble d’informations situé sur une mémoire de masse. C’est une suite finie homogène d’éléments ayant la")
36. Détail source à réviser : structure ce font par lecture ou écriture d’une variable de même type que cette structure. On appelle cette variable le tampon du fichier. Il est impossible d’accéder directement de manière individuelle a un champs d’une (Source: "structure ce font par lecture ou écriture d’une variable de même type que cette structure. On appelle cette variable le tampon du fichier. Il est impossible d’accéder directement de manière individuelle a un champs d’une structure de fichier, que ce soit lors de la lecture ou lors de l’écriture dans le fichier. .primitives d’accès séquentiel. → ouverture")
37. Détail source à réviser : direct : atteindre le début de l’enregistrement de rang : ATTEINDRE (nom-fichier, rang) ATTEINDRE (nom_fichier,o) → positionner la tête de lecture au début du fichier. Rang de l’enregistrement prêt a être lu : RANG.COURA _(Source: "direct : atteindre le début de l’enregistrement de rang : ATTEINDRE (nom-fichier, rang) ATTEINDRE (nom_fichier,o) → positionner la tête de lecture au début du fichier. Rang de l’enregistrement prêt a être lu : RANG.COURANT(nom_fichier) → entier. //0 si début de fichier. ATTEINDRE (nom_fichier, RANG.COURANT (nom_fichier)1) .Parcours séquentiel : arrêt si")
38. Détail source à réviser : personnemmi(DON fpers : FICHIER de Spersonne, RES indiviu : Spersonne) VARIABLES autrepers : Spersonne DEBUT ATTEINDRE(fpers,0) SI NON FDF(fpers) ALORS LIRE(fpers,individu) TANTQUE NON FDF(fpers) FAIRE LIRE (fpers, autre (Source: "personnemmi(DON fpers : FICHIER de Spersonne, RES indiviu : Spersonne) VARIABLES autrepers : Spersonne DEBUT ATTEINDRE(fpers,0) SI NON FDF(fpers) ALORS LIRE(fpers,individu) TANTQUE NON FDF(fpers) FAIRE LIRE (fpers, autrepers) SI (autrepers.nom <individu.nom) ALORS indiviu ← autrepers SINON ecrire(« fichier vide ! ») FIN .recherche de 1 fichier : mr x")
39. Détail source à réviser : TANTQUE (NON FDF (fpers1)) FAIRE LIRE(fpers1,tampon) ECRIRE(fpers2, tampon) FERMER(fpers2) FIN .modification d’un champ d’un enregistrement. PROCEDURE modif(DON rang : ENTIER, DON_RES : fpersonne : FICHIER de Spersonne) (Source: "TANTQUE (NON FDF (fpers1)) FAIRE LIRE(fpers1,tampon) ECRIRE(fpers2, tampon) FERMER(fpers2) FIN .modification d’un champ d’un enregistrement. PROCEDURE modif(DON rang : ENTIER, DON_RES : fpersonne : FICHIER de Spersonne) VARIABLES tampon : Spersonne DEBUT ATTEINDRE SI(NON FDF(fpers)) ALORS LIRE(fpers, tampon) ECRIRE(« nouveau numero de tel »)")
40. Détail source à réviser : → le pointeur null = plan d’ouverture. .remplissage du fichier : fwrite (&n, sizeof(…), nb, sortie) ; //&n=&individu, ex sizeof (Spersonne) .fermeture : fclose(sortie) ; ex : int main() { char nom [21] ; int n ; file *so (Source: "→ le pointeur null = plan d’ouverture. .remplissage du fichier : fwrite (&n, sizeof(…), nb, sortie) ; //&n=&individu, ex sizeof (Spersonne) .fermeture : fclose(sortie) ; ex : int main() { char nom [21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n)")
41. Détail source à réviser : SEEK_SET/SEEK_CUR/SEEK_END) ; O si tout est OK. Chapitre 7 : les tables de hachage. I.Introduction les tables de hachage sont des structures de données reposants sur les tableaux. C’est une structure de données statique. (Source: "SEEK_SET/SEEK_CUR/SEEK_END) ; O si tout est OK. Chapitre 7 : les tables de hachage. I.Introduction les tables de hachage sont des structures de données reposants sur les tableaux. C’est une structure de données statique. Associée à un algo de recherche très performant dont le but est d’accélérée la recherche d’un élément. La position de l’élément dans le")
42. Détail source à réviser : ses caractéristiques. Exemple : elt : étudiant (nom, prénom, coord,…) clé : n° d’étudiant. elt: abonné téléphonique. Clé : n° téléphone. .organisation de table. → séquentielle O(n). → relative (par table). Les éléments s (Source: "ses caractéristiques. Exemple : elt : étudiant (nom, prénom, coord,…) clé : n° d’étudiant. elt: abonné téléphonique. Clé : n° téléphone. .organisation de table. → séquentielle O(n). → relative (par table). Les éléments sont ranger en fonction de leur clés, on aura alors un accès direct avec un coût O(1). II. fonction de hachage le but des fonctions de")
43. Détail source à réviser : de H(ki). tab[h(ki)]=Ai⇒ donc si on a h(0381111144)=1, h(0381333367)=3, h(0381122222)=4, h(038112346)=6. Tab 1 Pierre Durand_0381111144 2 3 Paul Dupond_ 0381333367 4 Jean Bon_ 0381122222 5 6 Guillaume Tell_ 038112346 ... (Source: "de H(ki). tab[h(ki)]=Ai⇒ donc si on a h(0381111144)=1, h(0381333367)=3, h(0381122222)=4, h(038112346)=6. Tab 1 Pierre Durand_0381111144 2 3 Paul Dupond 0381333367 4 Jean Bon_ 0381122222 5 6 Guillaume Tell_ 038112346 ... ... 10 La recherche dans une telle table est immédiate, connaissant k le numéro de téléphone, l’indice dans le tableau est donnée")_
44. Détail source à réviser : nombre d’éléments a mettre dedans). Quand elle existe elle est parfois complexe et le calcul de H(k) peut être très coûteux. III. Collision. Dans la pratique, on utilise souvent des fonctions non injective, ce qui a pour (Source: "nombre d’éléments a mettre dedans). Quand elle existe elle est parfois complexe et le calcul de H(k) peut être très coûteux. III. Collision. Dans la pratique, on utilise souvent des fonctions non injective, ce qui a pour conséquences d’avoir deux clés différentes avec le même indice de tableau, on dit qu’il y a collision. .1er méthode : chaînage externe. →")
45. Détail source à réviser : gérer des pointeurs. → 2e méthode : tableau de collision (résolution/ calculs). = hachage coalescent ? On augmente la taille du tableau a M’>M. Les emplacements de M à M’ serviront a stoker les éléments en collision pour (Source: "gérer des pointeurs. → 2e méthode : tableau de collision (résolution/ calculs). = hachage coalescent ? On augmente la taille du tableau a M’>M. Les emplacements de M à M’ serviront a stoker les éléments en collision pour cette méthode il est nécessaire de créer un tableau supplémentaire appelé col en parallèle du tableau tab pour permettre de gérer les")
46. Détail source à réviser : en mémoire et elle est séquentielle. Avantage : pas de pointeurs. Inconvénient : le chemin peut être long, cela prend plus de place mémoire, et c’est limité par la zone de débordement. IV. exemple de fonction de hachage. (Source: "en mémoire et elle est séquentielle. Avantage : pas de pointeurs. Inconvénient : le chemin peut être long, cela prend plus de place mémoire, et c’est limité par la zone de débordement. IV. exemple de fonction de hachage. . méthode de division : on suppose que K est un nombre entier. Prendre comme indice dans le tableau le reste de la division de la")
47. Détail source à réviser : nom. H(nom) = somme entre L et i=1 de (ascii(nom[i]ti-1). ascii(‘n’)=110 ascii(‘b’)=98 H(‘nb’)=110100 + 98101 = 110 + 980 = 1090. tab[1090] = elt K= ‘nb’. Autre fonction : addition des représentation binaire : on addi _(Source: "nom. H(nom) = somme entre L et i=1 de (ascii(nom[i]ti-1). ascii(‘n’)=110 ascii(‘b’)=98 H(‘nb’)=110100 + 98101 = 110 + 980 = 1090. tab[1090] = elt K= ‘nb’. Autre fonction : addition des représentation binaire : on additionne la représentation binaire des caractères du mot, éventuellement en neutralisant les maj et mes min, puis on fait modulo N.")_
48. Détail source à réviser : 15 16 17 18 19 Problème : en cas de conflit fréquent certaines zones vont ce remplir plus vite que d’autres. Entre les cases 1 et 7 on verra une accumulation. Plus il y a de conflit pour une même case, plus il sera long (Source: "15 16 17 18 19 Problème : en cas de conflit fréquent certaines zones vont ce remplir plus vite que d’autres. Entre les cases 1 et 7 on verra une accumulation. Plus il y a de conflit pour une même case, plus il sera long de trouver un espace disponible. Pour disperser les points d’accumulation, on va chercher les nouvelles cases vides de p en p. attention :")
49. Détail source à réviser : I. Recherche dichotomique d’une valeur dans un vecteur ordonné (Source: "I. Recherche dichotomique d’une valeur dans un vecteur ordonné")
50. Détail source à réviser : ...........................................10 4. Choisir le meilleur pivot....................................................................................................... 11 5. (Source: "...........................................10 4. Choisir le meilleur pivot....................................................................................................... 11 5.")
51. Détail source à réviser : 1. création séquentielle de fichier (Source: "1. création séquentielle de fichier")
52. Détail source à réviser : V. autre méthode pour la gestion des collisions : hachage linéaire (Source: "V. autre méthode pour la gestion des collisions : hachage linéaire")
53. Détail source à réviser : 2. → si w est égal a v[milieu] la recherche est terminée (Source: "2. → si w est égal a v[milieu] la recherche est terminée")
54. Détail source à réviser : Ex : 44 26 95 4 8 88 96 34 Va jusqu’à n 26 44 95 4 8 88 96 34 26 44 95 4 8 88 96 34 4 26 44 95 8 88 96 34 4 8 26 44 95 88 96 34 4 8 26 44 88 95 96 34 4 8 26 44 88 95 96 34 4 8 26 34 44 88 95 96 3 (Source: "Ex : 44 26 95 4 8 88 96 34 Va jusqu’à n 26 44 95 4 8 88 96 34 26 44 95 4 8 88 96 34 4 26 44 95 8 88 96 34 4 8 26 44 95 88 96 34 4 8 26 44 88 95 96 34 4 8 26 44 88 95 96 34 4 8 26 34 44 88 95 96 3")
55. Détail source à réviser : le nom du type pointeurs sur UnElement s’écrit en c : UnElement * 2. les opérations possibles sont : a. initialisation automatique a la déclaration. Un pointeur s’initialise tout seul avec une valeur nulle. Ex : int *a ; (Source: "le nom du type pointeurs sur UnElement s’écrit en c : UnElement * 2. les opérations possibles sont : a. initialisation automatique a la déclaration. Un pointeur s’initialise tout seul avec une valeur nulle. Ex : int *a ; (définit un pointeur d’entier nommé a). Une case en mémoire signalise a vide. b. observateur. Seul est observable l’élément référencer p...")
56. Détail source à réviser : n) { int som ; int i ; som=0 ; for (i=1, i<=n, i++){ som=som+i ;} return(som) ;} pp cin>>x ; cout<< « la somme est : »<<somme(x) ; void echange(int &a, int&b){ int temp ; temp=0 ; a=b ; b=temp ;} c’est une méthode C++, e (Source: "n) { int som ; int i ; som=0 ; for (i=1, i<=n, i++){ som=som+i ;} return(som) ;} pp cin>>x ; cout<< « la somme est : »<<somme(x) ; void echange(int &a, int&b){ int temp ; temp=0 ; a=b ; b=temp ;} c’est une méthode C++, en C cela ne marche pas")
57. Détail source à réviser : 2. l’initialisation de vlocale à v, c’est a dire la recopie de tout le contenu de v à vlocale (Source: "2. l’initialisation de vlocale à v, c’est a dire la recopie de tout le contenu de v à vlocale")
58. Détail source à réviser : IV. fonctions récursives terminales (Source: "IV. fonctions récursives terminales")
59. Détail source à réviser : 2. débordement de pile (erreur : stack over flow) (Source: "2. débordement de pile (erreur : stack over flow)")
60. Détail source à réviser : 3. Performance Si le pivot est correctement choisi, c’est une des méthode de tris les plus rapides dans le cas moyen, c’est a dire ordre totalement aléatoire (Source: "3. Performance Si le pivot est correctement choisi, c’est une des méthode de tris les plus rapides dans le cas moyen, c’est a dire ordre totalement aléatoire")
61. Détail source à réviser : II. Tri par tas (ou HeapSort) Découvert en 1964 par Wialliams (Source: "II. Tri par tas (ou HeapSort) Découvert en 1964 par Wialliams")
62. Détail source à réviser : 1. représentation comme il n’existe pas de type chaînes de caractères dans tout les langages (Source: "1. représentation comme il n’existe pas de type chaînes de caractères dans tout les langages")
63. Détail source à réviser : C. initialisation d’une chaîne : char *adr ; adr = « bonjour » ; autre méthode : char ch(20)= « bonjour » ; char ch(20)= {‘b’,’o’,’n’,’j’,’o’,’u’,’r’,’\0’} ; char ch() = « bonjour » ; En c il existe de nombreuses fonctio (Source: "C. initialisation d’une chaîne : char *adr ; adr = « bonjour » ; autre méthode : char ch(20)= « bonjour » ; char ch(20)= {‘b’,’o’,’n’,’j’,’o’,’u’,’r’,’\0’} ; char ch() = « bonjour » ; En c il existe de nombreuses fonctions permettant de copier une chaîne ou une partie de chaîne, de connaître la position d’une sous-chaîne, de supprimer des caractères, d’aj...")
64. Détail source à réviser : On peut le décrire par : Elm_str : DEB_STRUCT champ1 : type champ 2 : type champn : type FIN_STRUCT ex Spersonne : DEB_STRUCT nom : chaîne(20) prénom : chaîne(15) num_rue : chaîne(7) nom_rue : chaîne(20) code_postal : ch (Source: "On peut le décrire par : Elm_str : DEB_STRUCT champ1 : type champ 2 : type champn : type FIN_STRUCT ex Spersonne : DEB_STRUCT nom : chaîne(20) prénom : chaîne(15) num_rue : chaîne(7) nom_rue : chaîne(20) code_postal : chaîne(5) ville : chaîne(10) tel : chaîne(10) FIN_STRUCT attention de réservation mémoire a cette étape, on ne fait que créer un nouveaux type")
65. Détail source à réviser : Ex : typedef int entier ; int a ,b ; soit entier a,b ; ex : typedef struct enreg Senreg ; struct enreg,art1,art2 ; on peut maintenant directement mettre Senreg art1,art2 ; encore mieux (Source: "Ex : typedef int entier ; int a ,b ; soit entier a,b ; ex : typedef struct enreg Senreg ; struct enreg,art1,art2 ; on peut maintenant directement mettre Senreg art1,art2 ; encore mieux")
66. Détail source à réviser : Nombre d’enregistrement du fichier : TAILLE (nom_fichier) fin de fichier (en lecture seulement) : FDF (nom_fichier) → booléen (Source: "Nombre d’enregistrement du fichier : TAILLE (nom_fichier) fin de fichier (en lecture seulement) : FDF (nom_fichier) → booléen")
67. Détail source à réviser : fpers, autrepers) SI (autrepers.nom <individu.nom) ALORS indiviu ← autrepers SINON ecrire(« fichier vide ! ») FIN .recherche de 1 fichier : mr x existe-il ? FONCTION recherche( DON fpers : FICHIER de Spersonne, nomindivi (Source: "fpers, autrepers) SI (autrepers.nom <individu.nom) ALORS indiviu ← autrepers SINON ecrire(« fichier vide ! ») FIN .recherche de 1 fichier : mr x existe-il ? FONCTION recherche( DON fpers : FICHIER de Spersonne, nomindividu.CHAINE(30)) : BOOLEEN VARIABLES tampon : Sper")
68. Détail source à réviser : .fin de fichier : feof(sortie) ; int main() { char nom [21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { fread(&n,sizeof(int),1,sortie) ; if (!l=feof(sorti (Source: ".fin de fichier : feof(sortie) ; int main() { char nom [21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { fread(&n,sizeof(int),1,sortie) ; if (!l=feof(sortie)) cout<<n ; else cout<< « fin de fichier » ; }while (!feof")
69. Détail source à réviser : II. fonction de hachage le but des fonctions de hachage est de ranger N éléments dans un tableaux de taille M afin d’optimiser la rechercher d’un élément donnés (Source: "II. fonction de hachage le but des fonctions de hachage est de ranger N éléments dans un tableaux de taille M afin d’optimiser la rechercher d’un élément donnés")
70. Détail source à réviser : 3 4 5 6 Guillaume Tell 0381123456 7 … Avantages : permet de gérer les collision et on reste avec un tableau simple ne contenant que des pointeurs (Source: "3 4 5 6 Guillaume Tell 0381123456 7 … Avantages : permet de gérer les collision et on reste avec un tableau simple ne contenant que des pointeurs")
71. Détail source à réviser : Pour l’annuaire inversé on a 500k abonné a ranger dans une table de taille 1 000 003. on aura donc H(K) = K MOD 1 000 003. on aura donc H(0381123456) = 122 313. tab[122 313] = {Guillaume, Tell, 0381123456}. → comment pas (Source: "Pour l’annuaire inversé on a 500k abonné a ranger dans une table de taille 1 000 003. on aura donc H(K) = K MOD 1 000 003. on aura donc H(0381123456) = 122 313. tab[122 313] = {Guillaume, Tell, 0381123456}. → comment passer d’une chaîne de caractère a un entier. Soit L la longueur de la chaîne que l’on appelle nom, ascii(nom[i]) le code askii du ie caract...")
72. Détail source à réviser : N. changement de base : on considère par exemple que la clé est écrite en base 11 et on la convertie en base 10, puis modulo (Source: "N. changement de base : on considère par exemple que la clé est écrite en base 11 et on la convertie en base 10, puis modulo")
73. Détail source à réviser : 003. on aura donc H(K) = K MOD 1 000 003 (Source: "003. on aura donc H(K) = K MOD 1 000 003")
74. Détail source à réviser : 313. tab[122 313] = {Guillaume, Tell, 0381123456} (Source: "313. tab[122 313] = {Guillaume, Tell, 0381123456}")
75. Détail source à réviser : p. attention : m et p doivent être premier (Source: "p. attention : m et p doivent être premier")
76. Détail source à réviser : c. le nom du type pointeurs sur UnElement s’écrit en c : UnElement * 2 (Source: "c. le nom du type pointeurs sur UnElement s’écrit en c : UnElement * 2")
77. Détail source à réviser : 2. */ int i ; char caract,c ; char mot[6]= « bravo » ; char *pc, *pmot, *ptr ; /schéma papier/ pc=&c ; c=’a’ ; printf(« %c »,*pc) ; /A/ caract=*pc ; printf(« %c »,caract) ; /A/ pmot=&mot[0] ; ptr=pmot ; printf(« %c (Source: "2. */ int i ; char caract,c ; char mot[6]= « bravo » ; char *pc, *pmot, *ptr ; /schéma papier/ pc=&c ; c=’a’ ; printf(« %c »,*pc) ; /A/ caract=*pc ; printf(« %c »,caract) ; /A/ pmot=&mot[0] ; ptr=pmot ; printf(« %c », *ptr) ; /B/ ptr=ptr+1 ; printf(« %c »,*ptr) ; /R/ printf(« %c », *(ptr+1)) ; /A/ printf(« %c », *ptr+1) ; /S/ pmot=mot ; prin...")
78. Détail source à réviser : 5. le nombre d’accès pour trouver un élément ne dépend pas de la taille du tableau mais du taux d’occupation (Source: "5. le nombre d’accès pour trouver un élément ne dépend pas de la taille du tableau mais du taux d’occupation")
79. Détail source à réviser : 21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { fread(&n,sizeof(int),1,sortie) ; if (!l=feof(sortie)) cout<<n ; else cout<< « fin de fichier » ; }while (! (Source: "21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { fread(&n,sizeof(int),1,sortie) ; if (!l=feof(sortie)) cout<<n ; else cout<< « fin de fichier » ; }while (!feof(sortie)) ; fclose(sortie);} 3.accès direct .deplacement")
80. Détail source à réviser : ermeture : fclose(sortie) ; ex : int main() { char nom [21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n) fwrit (Source: "ermeture : fclose(sortie) ; ex : int main() { char nom [21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n) fwrite(&n,sizeof(int),1,sortie) ; }while(n) ; false(sortie);} 2.l")
81. Détail source à réviser : ut “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n) fwrite(&n,sizeof(int),1,sortie) ; }while(n) ; false(sortie);} 2.lecture sequentielle .lectur (Source: "ut “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n) fwrite(&n,sizeof(int),1,sortie) ; }while(n) ; false(sortie);} 2.lecture sequentielle .lecture : fread(&n,sizeof(…),nb,sortie) ; .fin de fichi")
82. Détail source à réviser : 1. définition la récursivité est un programme ou un sous programme qui a la faculté de s’appelait lui même (Source: "1. définition la récursivité est un programme ou un sous programme qui a la faculté de s’appelait lui même")
83. Détail source à réviser : 1. avant chaque appel récursif, empilé l’adresse de retour et toute les variables locales, y compris celles crée pour les paramètres passé par valeurs (Source: "1. avant chaque appel récursif, empilé l’adresse de retour et toute les variables locales, y compris celles crée pour les paramètres passé par valeurs")
84. Détail source à réviser : 2. a chaque sortie d’un sous programme récursif, donc a chaque retour d’appel récursif, dépilé toute les variables locales et l’adresse de retour et ce rendre ensuite a cette adresse (Source: "2. a chaque sortie d’un sous programme récursif, donc a chaque retour d’appel récursif, dépilé toute les variables locales et l’adresse de retour et ce rendre ensuite a cette adresse")
85. Détail source à réviser : 1. un algorithme récursif doit être définit par une expression conditionnelle dont l’un au moins des cas même a une expression évaluable sans appel récursif (Source: "1. un algorithme récursif doit être définit par une expression conditionnelle dont l’un au moins des cas même a une expression évaluable sans appel récursif")
86. Détail source à réviser : 2. il faut s’assurer que pour toute valeurs du ou des arguments il suffira d’un nombre finit d’appel récursifs pour atteindre la condition d’arrêt (Source: "2. il faut s’assurer que pour toute valeurs du ou des arguments il suffira d’un nombre finit d’appel récursifs pour atteindre la condition d’arrêt")
87. Détail source à réviser : 1. c’est a dire que toute les feuilles ce trouve sur la dernière ou l’avant dernière ligne (Source: "1. c’est a dire que toute les feuilles ce trouve sur la dernière ou l’avant dernière ligne")
88. Détail source à réviser : « w ») ; do { fread(&n,sizeof(int),1,sortie) ; if (!l=feof(sortie)) cout<<n ; else cout<< « fin de fichier » ; }while (!feof(sortie)) ; fclose(sortie);} 3.accès direct .deplacement des fichier : fseek(sortie, sizeof(...) (Source: "« w ») ; do { fread(&n,sizeof(int),1,sortie) ; if (!l=feof(sortie)) cout<<n ; else cout<< « fin de fichier » ; }while (!feof(sortie)) ; fclose(sortie);} 3.accès direct .deplacement des fichier : fseek(sortie, sizeof(...)*(nb-1), SEEK_SET/SEEK_CUR/SEEK_END) ; O si tout")
89. Détail source à réviser : IV. exemple de fonction de hachage (Source: "IV. exemple de fonction de hachage")
90. Détail source à réviser : p=1 Elt : e1 e2 e3 e4 e5 e9 e6 e7 e8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Problème : en cas de conflit fréquent certaines zones vont ce remplir plus vite que d’autres (Source: "p=1 Elt : e1 e2 e3 e4 e5 e9 e6 e7 e8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Problème : en cas de conflit fréquent certaines zones vont ce remplir plus vite que d’autres")
91. Détail source à réviser : 1. un pointeur est une variables dont les valeurs sont des adresses de type connu (Source: "1. un pointeur est une variables dont les valeurs sont des adresses de type connu")
92. Détail source à réviser : 3. les pointeurs permettent de ne pas réserver que la place juste nécessaire a un instant donné avec les instructions malloc et free (Source: "3. les pointeurs permettent de ne pas réserver que la place juste nécessaire a un instant donné avec les instructions malloc et free")
93. Détail source à réviser : 3. la substitution de toute les occurrences de v par vlocale dans le bloc relatif au sous programme (Source: "3. la substitution de toute les occurrences de v par vlocale dans le bloc relatif au sous programme")
94. Détail source à réviser : 21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n) fwrite(&n,sizeof(int),1,sortie) ; }while(n) ; false(sortie);} (Source: "21] ; int n ; file *sortie ; cout “ « nom du fichier à créer ? » ; cin >>nom ; sortie = fopen(nom , « w ») ; do { cout<< « donner 1 entier » ; cin >>n ; if(n) fwrite(&n,sizeof(int),1,sortie) ; }while(n) ; false(sortie);} 2.lecture sequentielle .lecture : fread(&n,sizeof(…),nb,sor")
95. Détail source à réviser : 1 Pierre Durand 0381111144 -1 2 3 Paul Dupond 0381333367 8 4 5 6 Guillaume Tell 0381123456 -1 7 8 Jean Bon 0381222222 -1 9 10 En jaune : tab, en vert : col (Source: "1 Pierre Durand 0381111144 -1 2 3 Paul Dupond 0381333367 8 4 5 6 Guillaume Tell 0381123456 -1 7 8 Jean Bon 0381222222 -1 9 10 En jaune : tab, en vert : col")
96. Détail source à réviser : changement de base : on considère par exemple que la clé est écrite en base 11 et on la convertie en base 10, puis modulo (Source: "changement de base : on considère par exemple que la clé est écrite en base 11 et on la convertie en base 10, puis modulo")

📊 Tableaux de Synthèse

Tri par algorithmes simples et complexes

Gestion des fichiers en C

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre recherche séquentielle et dichotomique dans un vecteur ordonné.
2. Erreur dans le calcul du milieu lors de la recherche dichotomique.
3. Mauvaise gestion des collisions dans une table de hachage, comme ne pas choisir une taille de table première.
4. Utilisation incorrecte de malloc et free pour la gestion dynamique de mémoire.
5. Confusion entre chaînes terminées par ' ull' et autres représentations en C.
6. Oublier de fermer un fichier après ouverture, entraînant des fuites de ressources.
7. Choix inadéquat du pivot dans le tri rapide, menant à des performances dégradées.

✅ Checklist Examen

1. Vérifier la compréhension de la recherche dichotomique.
2. Savoir implémenter les tris simples et complexes.
3. Maîtriser la manipulation des chaînes en C.
4. Connaître la déclaration et l'utilisation des structures en C.
5. Comprendre le fonctionnement des tables de hachage et la gestion des collisions.
6. Savoir ouvrir, lire, écrire et fermer un fichier en C.
7. Maîtriser la conversion de chaînes en entiers ou flottants.
8. Connaître les principes de base des pointeurs en C.
9. Savoir utiliser malloc et free pour la gestion dynamique.
10. Comprendre la représentation des chaînes en binaire.
11. Savoir utiliser fseek pour l'accès direct dans un fichier.
12. Connaître les critères de sélection d'un bon algorithme de tri.