Sous Linux, le compilateur de C est gcc. Il est installé de base sur plusieurs distributions, mais sur Debian (et celles qui en découlent) il faudra l'installer (aptitude install gcc).

gcc

Tout d'abord, il faut savoir ce que signifie l'abréviation GCC: GNU Compiler Collection. En fait, il est le compilateur créé par le projet GNU. Il s'agit d'une collection de logiciels libres intégrés capables de compiler divers langages de programmation, dont C, C++, Objective-C, Java, Ada et Fortran.
GCC est utilisé pour le développement de la plupart des logiciels libres. Le noyau Linux dépend notamment étroitement des fonctionnalités de GCC.
En pratique, l'abréviation GCC est utilisée pour nommer trois entités légèrement différentes :

1. la collection complète de compilateurs ;
2. la partie commune à tous les compilateurs ;
3. le compilateur C lui-même.

Pour faire référence précisément aux compilateurs de chaque langage, on parle de :

• GCC pour C ;
• G++ pour C++ ;
• GCJ pour Java ;
• GNAT pour Ada ;
• Gfortran pour Fortran ;
• GPC pour le Pascal;
• GHDL pour le VHDL.

GCC dispose également d'un outil de débuggage, GNU Debugger (gdb). Bien que ne faisant pas partie de GCC, Valgrind est cependant préféré pour des tests plus en profondeurs, notamment pour rechercher les fuites de mémoire.

Syntaxe de GCC

Je voudrais donner ici les deux principales commandes de GCC pour le c, après je vous renvoie à

man gcc

;-)

$ gcc masource.c # crée un exécutable du nom de a.out, que l'on lancera avec ./a.out.

$ gcc -o <nom_du_programme_que_l'on_souhaite_donner> -c <masource>.c # L'argument -o vous permet de choisir le nom de l'exécutable qui naîtra de cette compilation.

Lire la suite

[Langage C] C/C++ Erreur de segmentation »

Qu'est ce qu'une erreur de segmentation

Vous êtes en train de développer une application sous Linux en
C/C++. Tout va bien, ça compile, les oiseaux chantent.
Donc vous lancez votre application pour la tester.

Et vous obtenez l'un de ces deux messages:

Erreur de segmentation

ou

Segmentation fault

Autant lorsque vous avez une erreur avec un programme écrit dans un langage de très haut niveau (perl, python, java etc...), vous aurez un message de debuggage détaillé: quel type d'exception s'est produit? A quel ligne du programme ça correspond etc...
Autant avec un langage compilé (donc transformé en langage directement compréhensible par votre processeur) comme c ou c++, votre programme n'est sous la tutelle d'aucun interpréteur ou machine virtuelle. Donc personne pour surveiller vos erreurs et les analyser.

Heureusement il existe des programmes appelés debuggeurs et qui sont là pour vous faciliter la tâche.

Il faut savoir qu'un système d'exploitation moderne (Windows nt/2000/XP/ ; Linux) alloue une portion de mémoire pour chaque application. Si une application essaie de pénétrer directement dans une zone-mémoire qui ne lui appartient pas ou dans une zone mémoire incorrecte, le système d'exploitation va stopper l'application en cours et va générer une erreur (sous Linux: Erreur de segmentation)

En C

Prenons par exemple un programme en C tout à fait débile qui se plante volontairement et génère une erreur de segmentation:

void lance_erreur_segmentation() 
{ 
 int *pointeur_dangereux=(int *) 100; 
 int test=*pointeur_dangereux; 
} 

int main(int argc, char ** argv) 
{ 
 lance_erreur_segmentation(); 
 return 0; 
}

Dans la fonction lance_erreur_segmentation, le pointeur_dangereux pointe vers l'adresse 100 dans la mémoire.
C'est une adresse qui ne peut pas appartenir à une application normale.
Au moment où pointeur_dangereux tentera de lire ce qu'il ya dans l'adresse mémoire 100 pour mettre la valeur située à cette adresse dans la variable test, le programme va crasher.
Et vous obtiendrez le message "Erreur de segmentation".

Pour débugger ce programme nous allons commencer par le compiler en lui chargeant ses symboles de débuggage. Cela permet notamment de charger les noms de fonctions et variables utilisés dans le programme une fois qu'il est compilé, ainsi le debugger pourra tracer l'erreur en vous indiquant les noms des fonctions concernées plutôt que de donner juste leur adresse.
Je parle ici de l'option -g

On compile:

gcc -g test.c -o test

Et on lance le programme dans le debugger:

gdb ./test

Vous allez apercevoir une invite de commande commençant par:

(gdb)

Tapez la commande run

Observons ce qu'il se passe:

(gdb) run 
Starting program: ~/test  

Program received signal SIGSEGV, Segmentation fault. 
0x08048334 in lance_erreur_segmentation () at test.c:4 
4               int test=*pointeur_dangereux;

Que demander de plus: le debuggeur vous indique la ligne dans votre fichier source qui est à l'origine de l'erreur, ainsi que la fonction concernée et le contenu de la ligne:
C'est une erreur dans la fonction lance_erreur_segmentation dans le fichier source test.c à la ligne 4 dont le contenu est

int test=*pointeur_dangereux;

Admettons maintenant que vous vouliez savoir quelle fonction a appelé quelle autre fonction depuis le début du programme jusqu'à l'arrivée de l'erreur.

Tapez la commande bt:

(gdb) bt 
#0  0x08048334 in lance_erreur_segmentation () at test.c:4 
#1  0x0804834e in main () at test.c:9

Et vous avez encore une fois ce qu'il vous faut :-)

En C++

Pour en rester au même problème: les erreurs de segmentation, il n'y a pas grand chose à ajouter pour le C++, hormis qu'il s'agit d'utiliser la commande g++ avec l'option -g de la même façon qu'avec gcc.

Le rapport de gdb sera le même mais avec des détails sur les classes concernées.

Exemple:

//Fichier test.cpp 
class Test{ 
 public: 
  int a; 
  Test(){}; 
  ~Test(){}; 
  int incremente_a(){ a++; }; 
}; 

int main() 
{ 
 Test *t; 
 t=(Test *)100; 
 t->incremente_a(); 
 return 0; 
}

On compile comme ceci:

g++ -g test.cpp -o test

On lance le déboggeur:

gdb ./test

Puis on y tape les mêmes commandes qu'avant et tous les détails s'affichent:

(gdb) run 
Starting program: ~/test  

Program received signal SIGSEGV, Segmentation fault. 
0x080483fc in Test::incremente_a (this=0x64) at test.cpp:7 
7                       int incremente_a(){ a++; }; 
(gdb) bt 
#0  0x080483fc in Test::incremente_a (this=0x64) at test.cpp:7 
#1  0x080483e7 in main () at test.cpp:14 

Et voilà.

Liens

• Excellent tutoriel sur le déboggage C++ en utilisant gdb de manière plus agréable(fr)

Lire la suite

Générer des nombres aléatoires efficacement avec rand() »

Générer des nombres aléatoires efficacement avec rand()

Vous avez peut-être remarqué qu'en C, en utilisant la fonction rand() de la bibliothèque standard, vous obtenez des résultats décevants, trop souvent les mêmes.

Prenons un exemple, vous voulez générer 5 nombres aléatoires d'affilée:

#include <stdlib.h>
#include <stdio.h>

int main()
{
    int i;
    for(i=0; i<5; i++)
    {
        printf("%d\n", rand());
    }
    return 0;
}

Exécutons ce programme et regardons ce qu'il nous écrit:

41
18467
6334
26500
19169

C'est bien, ce sont des résultats sensiblement différents. Mais si vous relancez votre programme, vous aurez la même série de nombres.

Pour modifier le comportement du générateur de nombres aléatoires, on peut modifier une variable sur laquelle il se base pour ses calculs. On appelle ça une graine (ou seed).
Cette graine se modifie avec la fonction srand():

srand(valeur de la graine)

Il faut un nombre que l'on ne peut pas prévoir facilement et qui varie toujours d'un instant à l'autre.
Par exemple, vous pouvez prendre le nombre de cycles utilisés par votre processeur depuis le démarrage.
Il peut être obtenu, sur les processeurs x86 (intel, Amd etc...), avec la commande assembleur rdtsc.
L'écriture d'une fonction rdtsc() appelant cette commande en assembleur pourra vous faciliter la vie, la syntaxe suivante fonctionne avec gcc sous Linux, que vous pouvez retrouver d'ailleurs avec dev C++ sous Windows.

#include <stdlib.h>
#include <stdio.h>

int rdtsc()
{
    __asm__ __volatile__("rdtsc");
}

int main()
{
    int i;
    for(i=0; i<5; i++)
    {
        srand(rdtsc());
        printf("%d\n", rand());
    }
    return 0;
}

Avec ce code, vous aurez déjà des nombres aléatoires plus efficaces.

Attention, cette solution ne fonctionne que sur les processeurs x86. Si votre programme doit être portable sur d'autres architectures de processeurs, il faudra envisager autre chose.

Evitez également d'activer des optimisations dans le compilateur (option -O1, -O2, -O3 etc...) ; si vous utilisez cette fonction rdtsc, vous risquez d'avoir un comportement étrange....

Lire la suite

Manipuler des entiers en 64 bits »

Manipuler des entiers en 64 bits

En C, un entier traditionnel non signé sur 32 bits ne peut pas dépasser la valeur de 4 294 967 295.
Il se peut que vous soyiez amenés à manipuler des nombres plus grands et pour celà vous aurez besoin des
entiers codés sur 64 bits. Toutefois, ce type ne se manipule pas toujours de la même façon qu'un entier ordinaire. En effet, les constantes entières et l'affichage de ces nombres ne sont pas définis de la même façon.

Entiers 64 bits non signés

Type: unsigned long long
Formatage pour l'affichage: %llu
Suffixe pour définir une constante: ULL

Exemple:

//Affecte la valeur 4294967296 dans a
unsigned long long a = 4294967296ULL;
//Affiche cette valeur
printf("%llu", a);

Entiers 64 bits signés

Type: long long
Formatage pour l'affichage: %lld
Suffixe pour définir une constante: LL

Exemple:

//Affecte la valeur 4294967296 dans a
long long a = 4294967296LL;
//Affiche cette valeur
printf("%lld", a);

Pourquoi un suffixe bizzare pour définir une valeur constante?

Si vous essayez ceci par exemple:

unsigned long long a = 4294967296

Votre compilateur vous répondra que ce nombre est trop large pour le type "long". C'est à dire un entier sur 32 bits. Les constantes ont ce type par défaut. Au final, cette notion est directement liée à l'architecture des processeurs 32 bits. Un registre 32 bits de processeur est limité et votre compilateur essaiera par défaut de caser les nombres dans un seul registre. Mais avec un suffixe comme LL et ULL, votre compilateur stockera votre nombre sur 2 registres, c'est à dire sur 64 bits, ce qui laisse une capacité beaucoup plus grande.

Lire la suite

Liste simplement chaînée »

LISTES SIMPLEMENT CHAINÉES

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur

INTRODUCTION

Cette article a pour but la compréhension des listes simplement chaînées.
L'implémentation en fonction des besoins et des performances vous appartient.
Les listes chaînées peuvent être utilisées quand plusieurs opérations d'insertion/suppression d'éléments sont nécessaires.

Définition

Les listes chaînées sont des structures de données semblables aux tableaux sauf que l'accès à un élément ne se fait pas par index mais à l'aide d'un pointeur.
L'allocation de la mémoire est faite au moment de l'exécution.

Dans une liste les éléments sont contigus en ce qui concerne l'enchaînement.


En revanche, par rapport aux tableaux où les éléments sont contigus dans la mémoire, les éléments d'une liste sont éparpillés dans la mémoire.
La liaison entre les éléments se fait grâce à un pointeur.
En réalité, dans la mémoire la représentation est aléatoire en fonction de l'espace alloué.

Le pointeur suivant du dernier élément doit pointer vers NULL (la fin de la liste).

Pour accéder à un élément la liste est parcourue en commençant avec la tête, le pointeur suivant permettant le déplacement vers le prochain élément.
Le déplacement se fait dans une seule direction, du premier vers le dernier élément.
Si vous voulez vous déplacer dans les deux directions (en avant/en arrière) utilisez les listes doublement chaînées.

La construction du prototype d'un élément de la liste

Pour définir un élément de la liste le type struct sera utilisé.
L'élément de la liste contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur "suivant" permettra l'accès vers le prochain élément.

typedef struct ElementListe { 
  char                *donnee; 
  struct ElementListe *suivant; 
}Element; 

Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.


Pour réaliser cela une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition:

typedef struct ListeRepere { 
  Element *debut; 
  Element *fin; 
  int taille; 
}Liste; 

Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.

Quelque soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelque soit l'opération effectuée sur la liste.

Opérations sur les listes chaînées

Pour l'insertion ainsi que pour la suppression, une seule fonction est largement suffisante si elle est bien conçue en fonction des besoins.
Toutefois je vous rappelle que cet article est purement didactique.
C'est la raison pour laquelle j'ai écrit une fonction pour chaque opération d'insertion et de suppression.

Initialisation

Prototype de la fonction :

void initialisation (Liste *liste);

Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (Liste *liste){ 
  liste->debut = NULL; 
  liste->fin = NULL; 
  taille = 0; 
} 

Insertion d'un élément dans la liste

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
  • Cas particulier : dans une liste avec un seul élément, le 1er est en même temps le dernier.
  • mettre à jour la taille de la liste

Pour ajouter un élément dans la liste il y a plusieurs situations :

• 1. Insertion dans une liste vide
• 2. Insertion au début de la liste
• 3. Insertion à la fin de la liste
• 4. Insertion ailleurs dans la liste

Insertion dans une liste vide

Prototype de la fonction :

int ins_dans_liste_vide (Liste *liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes :

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointera vers NULL (vu que l'insertion est faite dans une liste vide on utilise l'adresse du pointeur debut qui vaut NULL)
• les pointeurs debut et fin pointeront vers le nouvel élément
• la taille est mise à jour

La fonction

/* insertion dans une liste vide */ 
int ins_dans_liste_vide (Liste * liste, char *donnee){ 
  Element *nouveau_element; 
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  nouveau_element->suivant = NULL; 
  liste->debut = nouveau_element; 
  liste->fin = nouveau_element; 
  liste->taille++; 
  return 0; 
} 

Insertion au début de la liste

Prototype de la fonction :

int ins_debut_liste (Liste *liste,char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointe vers le 1er élément
• le pointeur debut pointe vers le nouvel élément
• le pointeur fin ne change pas
• la taille est incrémentée

La fonction

/* insertion au début de la liste */ 
int ins_debut_liste (Liste * liste, char *donnee){ 
  Element *nouveau_element; 
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  nouveau_element->suivant = liste->debut; 
  liste->debut = nouveau_element; 
  liste->taille++; 
  return 0; 
} 

Insertion à la fin de la liste

Prototype de la fonction :

int ins_fin_liste (Liste *liste, Element *courant, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du dernier élément pointe vers le nouvel élément
• le pointeur fin pointe vers le nouvel élément
• le pointeur debut ne change pas
• la taille est incrémentée

La fonction

/*insertion à la fin de la liste */ 
int ins_fin_liste (Liste * liste, Element * courant, char *donnee){ 
  Element *nouveau_element; 
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  courant->suivant = nouveau_element; 
  nouveau_element->suivant = NULL; 

  liste->fin = nouveau_element; 

  liste->taille++; 
  return 0; 
} 

Insertion ailleurs dans la liste

Prototype de la fonction :

int ins_liste (Liste *liste, char *donnee,int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

L'insertion s'effectuera après une certaine position passée en argument à la fonction.
Si la position indiquée ne doit pas être le dernier élément. Dans ce cas il faut utiliser la fonction d'insertion à la fin de la liste.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• choisir une position dans la liste (l'insertion se fera après la position choisie)
• le pointeur suivant du nouvel élément pointe vers l'adresse sur laquelle pointe le pointeur suivant d'élément courant. (cette explication est un peu tordue, mais l'image vous éclaira ;-)
• le pointeur suivant du l'élément courant pointe vers le nouvel élément
• les pointeurs debut et fin ne change pas
• la taille est incrémentée d'une unité

La fonction

/* insertion à la position demandée */ 
int ins_liste (Liste * liste, char *donnee, int pos){ 
  if (liste->taille < 2) 
    return -1; 
  if (pos < 1 || pos >= liste->taille) 
    return -1; 

  Element *courant; 
  Element *nouveau_element; 
  int i; 

  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 

  courant = liste->debut; 
  for (i = 1; i < pos; ++i) 
    courant = courant->suivant; 
  if (courant->suivant == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  nouveau_element->suivant = courant->suivant; 
  courant->suivant = nouveau_element; 
  liste->taille++; 
  return 0; 
} 

Suppression d'un élément dans la liste

Voici l'algorithme de suppression d'un élément de la liste :

• utilisation d'un pointeur temporaire pour sauvegarder l'adresse d'éléments à supprimer
• l'élément à supprimer se trouve après l'élément courant

Faire pointer le pointeur suivant de l'élément courant vers l'adresse du pointeur suivant de l'élément à supprimer

• libérer la mémoire occupée par l'élément supprimé
• mettre à jour la taille de la liste

Pour supprimer un élément dans la liste il y a plusieurs situations :

• 1. Suppression au début de la liste
• 2. Suppression ailleurs dans la liste

Suppression au début de la liste

Prototype de la fonction:

int supp_debut (Liste *liste);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


Étapes:

• le pointeur supp_elem contiendra l'adresse du 1er élément
• le pointeur debut pointera vers le 2ème élément
• la taille de la liste sera décrémentée d'un élément

La fonction

/* suppression au début de la liste */ 
int supp_debut (Liste * liste){ 
  if (liste->taille == 0) 
    return -1; 
  Element *supp_element; 
  supp_element = liste->debut; 
  liste->debut = liste->debut->suivant; 
  if (liste->taille == 1) 
    liste->fin = NULL; 
  free (supp_element->donnee); 
  free (supp_element); 
  liste->taille--; 
  return 0; 
} 

Suppression ailleurs dans la liste

Prototype de la fonction:

int supp_dans_liste (Liste *liste, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes:

• le pointeur supp_elem contiendra l'adresse vers laquelle pointe le pointeur suivant d'élément courant
• le pointeur suivant de l'élément courant pointera vers l'élément sur lequel pointe le pointeur suivant de l'élément qui suit l'élément courant dans la liste

Si l'élément courant est l'avant dernier élément, le pointeur fin doit être mis à jour

• la taille de la liste sera décrémentée d'un élément

La fonction

/* supprimer un element après la position demandée */ 
int supp_dans_liste (Liste * liste, int pos){ 
  if (liste->taille <= 1 || pos < 1 || pos >= liste->taille) 
    return -1; 
  int i; 
  Element *courant; 
  Element *supp_element; 
  courant = liste->debut; 

  for (i = 1; i < pos; ++i) 
    courant = courant->suivant; 

  supp_element = courant->suivant; 
  courant->suivant = courant->suivant->suivant; 
  if(courant->suivant == NULL) 
          liste->fin = courant; 
  free (supp_element->donnee); 
  free (supp_element); 
  liste->taille--; 
  return 0; 
} 

Affichage de la liste

Pour afficher la liste entière il faut se positionner au début de la liste (le pointeur debut le permettra).
Ensuite en utilisant le pointeur suivant de chaque élément la liste est parcourue du 1er vers le dernier élément.
La condition d'arrêt est donnée par le pointeur suivant du dernier élément qui vaut NULL.

La fonction

/* affichage de la liste */ 
void affiche (Liste * liste){ 
  Element *courant; 
  courant = liste->debut; 
  while (courant != NULL){ 
      printf ("%p - %s\n", courant, courant->donnee); 
      courant = courant->suivant; 
  } 
} 

Destruction de la liste

Pour détruire la liste entière, j'ai utilisé la suppression au début de la liste tant que la taille est plus grande que zéro.

La fonction

/* détruire la liste */ 
void detruire (Liste * liste){ 
  while (liste->taille > 0) 
    supp_debut (liste); 
} 

Exemple complet

liste.h

/* ---------- liste.h ----------- */ 
typedef struct ElementListe 
{ 
  char *donnee; 
  struct ElementListe *suivant; 
} Element; 

typedef struct ListeRepere 
{ 
  Element *debut; 
  Element *fin; 
  int taille; 
} Liste; 

/* initialisation de la liste */ 
void initialisation (Liste * liste); 


/* INSERTION */ 

/* insertion dans une liste vide */ 
int ins_dans_liste_vide (Liste * liste, char *donnee); 

/* insertion au début de la liste */ 
int ins_debut_liste (Liste * liste, char *donnee); 

/* insertion à a fin de la liste */ 
int ins_fin_liste (Liste * liste, Element * courant, char *donnee); 

/* insertition ailleurs */ 
int ins_liste (Liste * liste, char *donnee, int pos); 


/* SUPPRESSION */ 

int supp_debut (Liste * liste); 
int supp_dans_liste (Liste * liste, int pos); 


int menu (Liste *liste,int *k); 
void affiche (Liste * liste); 
void detruire (Liste * liste); 
/* -------- FIN liste.h --------- */ 

liste_function.h

/***************************\ 

 
     liste_function.h    * 
\***************************/ 
void 
initialisation (Liste * liste) 
{ 
  liste->debut = NULL; 
  liste->fin = NULL; 
  liste->taille = 0; 
} 

/* insertion dans une liste vide */ 
int ins_dans_liste_vide (Liste * liste, char *donnee){ 
  Element *nouveau_element; 
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  nouveau_element->suivant = NULL; 
  liste->debut = nouveau_element; 
  liste->fin = nouveau_element; 
  liste->taille++; 
  return 0; 
} 

/* insertion au début de la liste */ 
int ins_debut_liste (Liste * liste, char *donnee){ 
  Element *nouveau_element; 
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  nouveau_element->suivant = liste->debut; 
  liste->debut = nouveau_element; 
  liste->taille++; 
  return 0; 
} 

/*insertion à la fin de la liste */ 
int ins_fin_liste (Liste * liste, Element * courant, char *donnee){ 
  Element *nouveau_element; 
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  courant->suivant = nouveau_element; 
  nouveau_element->suivant = NULL; 

  liste->fin = nouveau_element; 

  liste->taille++; 
  return 0; 
} 

/* insertion à la position demandée */ 
int ins_liste (Liste * liste, char *donnee, int pos){ 
  if (liste->taille < 2) 
    return -1; 
  if (pos < 1 || pos >= liste->taille) 
    return -1; 

  Element *courant; 
  Element *nouveau_element; 

  int i; 

  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) 
    return -1; 
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) 
      == NULL) 
    return -1; 

  courant = liste->debut; 
  for (i = 1; i < pos; ++i) 
    courant = courant->suivant; 
  if (courant->suivant == NULL) 
    return -1; 
  strcpy (nouveau_element->donnee, donnee); 

  nouveau_element->suivant = courant->suivant; 
  courant->suivant = nouveau_element; 
  liste->taille++; 
  return 0; 
} 

/* suppression au début de la liste */ 
int supp_debut (Liste * liste){ 
  if (liste->taille == 0) 
    return -1; 
  Element *supp_element; 
  supp_element = liste->debut; 
  liste->debut = liste->debut->suivant; 
  if (liste->taille == 1) 
    liste->fin = NULL; 
  free (supp_element->donnee); 
  free (supp_element); 
  liste->taille--; 
  return 0; 
} 

/* supprimer un element après la position demandée */ 
int supp_dans_liste (Liste * liste, int pos){ 
  if (liste->taille <= 1 || pos < 1 || pos >= liste->taille) 
    return -1; 
  int i; 
  Element *courant; 
  Element *supp_element; 
  courant = liste->debut; 

  for (i = 1; i < pos; ++i) 
    courant = courant->suivant; 

  supp_element = courant->suivant; 
  courant->suivant = courant->suivant->suivant; 
  if(courant->suivant == NULL) 
          liste->fin = courant; 
  free (supp_element->donnee); 
  free (supp_element); 
  liste->taille--; 
  return 0; 
} 

/* affichage de la liste */ 
void affiche (Liste * liste){ 
  Element *courant; 
  courant = liste->debut; 
  while (courant != NULL){ 
      printf ("%p - %s\n", courant, courant->donnee); 
      courant = courant->suivant; 
  } 
} 

/* detruire la liste */ 
void detruire (Liste * liste){ 
  while (liste->taille > 0) 
    supp_debut (liste); 
} 

int menu (Liste *liste,int *k){ 
  int choix; 
  printf("********** MENU **********\n"); 
  if (liste->taille == 0){ 
    printf ("1. Ajout du 1er element\n"); 
    printf ("2. Quitter\n"); 
  }else if(liste->taille == 1 || *k == 1){ 
    printf ("1. Ajout au debut de la liste\n"); 
    printf ("2. Ajout a la fin de la liste\n"); 
    printf ("4. Suppression au debut de la liste\n"); 
    printf ("6. Detruire la liste\n"); 
    printf ("7. Quitter\n"); 
  }else { 
    printf ("1. Ajout au debut de la liste\n"); 
    printf ("2. Ajout a la fin de la liste\n"); 
    printf ("3. Ajout apres la position specifie\n"); 
    printf ("4. Suppression au debut de la liste\n"); 
    printf ("5. Suppression apres la position specifie\n"); 
    printf ("6. Detruire la liste\n"); 
    printf ("7. Quitter\n"); 
  } 
  printf ("\n\nFaites votre choix : "); 
  scanf ("%d", &choix); 
  getchar(); 
  if(liste->taille == 0 && choix == 2) 
    choix = 7; 
  return choix; 
} 
/* -------- FIN liste_function.h --------- */ 

liste.c

/**********************\ 

 
     liste.c        * 
\**********************/ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include "liste.h" 
#include "liste_function.h" 

int main (void) 
{ 
  char choix; 
  char *nom; 
  Liste *liste; 
  Element *courant; 

  if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL) 
    return -1; 
  if ((nom = (char *) malloc (50)) == NULL) 
    return -1; 
  courant = NULL; 
  choix = 'o'; 

  initialisation (liste); 
  int pos, k; 

  while (choix != 7){ 
      choix = menu (liste, &k); 
      switch (choix){ 
        case 1: 
          printf ("Entrez un element : "); 
          scanf ("%s", nom); 
          getchar (); 
          if (liste->taille == 0) 
            ins_dans_liste_vide (liste, nom); 
          else 
            ins_debut_liste (liste, nom); 
          printf ("%d elements:deb=%s,fin=%s\n", liste->taille, 
                  liste->debut->donnee, liste->fin->donnee); 
          affiche (liste); 
          break; 
        case 2: 
          printf ("Entrez un element : "); 
          scanf ("%s", nom); 
          getchar (); 
          ins_fin_liste (liste, liste->fin, nom); 
          printf ("%d elements:deb=%s,fin=%s\n", liste->taille, 
                  liste->debut->donnee, liste->fin->donnee); 
          affiche (liste); 
          break; 
        case 3: 
          printf ("Entrez un element : "); 
          scanf ("%s", nom); 
          getchar (); 
          do{ 
              printf ("Entrez la position : "); 
              scanf ("%d", &pos); 
     } 
          while (pos < 1 || pos > liste->taille); 
          getchar (); 
          if (liste->taille == 1 || pos == liste->taille){ 
              k = 1; 
              printf("-----------------------------------------------\n"); 
              printf("/!\\Insertion echouée.Utilisez le menu {1|2} /!\\\n"); 
              printf("-----------------------------------------------\n"); 
              break; 
     } 
          ins_liste (liste, nom, pos); 
          printf ("%d elements:deb=%s,fin=%s\n", liste->taille, 
                  liste->debut->donnee, liste->fin->donnee); 
          affiche (liste); 
          break; 
        case 4: 
          supp_debut (liste); 
          if (liste->taille != 0) 
            printf ("%d elements:deb=%s,fin=%s\n", liste->taille, 
                    liste->debut->donnee, liste->fin->donnee); 
          else 
            printf ("liste vide\n"); 
          affiche (liste); 
          break; 
        case 5: 
          do{ 
              printf ("Entrez la position : "); 
              scanf ("%d", &pos); 
     } 
          while (pos < 1 || pos > liste->taille); 
          getchar (); 
          supp_dans_liste (liste, pos); 
          if (liste->taille != 0) 
            printf ("%d elements:deb=%s,fin=%s\n", liste->taille, 
                    liste->debut->donnee, liste->fin->donnee); 
          else 
            printf ("liste vide\n"); 
          affiche (liste); 
          break; 
        case 6: 
          detruire (liste); 
          printf ("la liste a ete detruite : %d elements\n", liste->taille); 
          break; 
      } 
  } 
  return 0; 
} 

Voir aussi

• les listes doublement chaînées
• les listes circulaires
• les piles
• les files

Ce document intitulé « Liste simplement chaînée » issu de CommentCaMarche.net (CCM) (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

LISTES DOUBLEMENT CHAINÉES

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînéess (facultatif)

I. INTRODUCTION

Cette article a pour but la compréhension des listes doublement chaînées.
L'implémentation en fonction des besoins et des performances vous appartient.
Les listes doublement chaînées peuvent être utilisées quand plusieurs opérations d'insertion/suppression d'éléments sont nécessaires.

II. Définition

Les listes doublement chaînées sont des structures de données semblables aux listes simplement chaînées .
L'allocation de la mémoire est faite au moment de l'exécution.




En revanche, par rapport aux listes simplement chaînées la liaison entre les éléments se fait grâce à deux pointeurs (un qui pointe vers l'élément précédent et un qui pointe vers l'élément suivant).



Le pointeur precedent du premier élément doit pointer vers NULL (le début de la liste).
Le pointeur suivant du dernier élément doit pointer vers NULL (la fin de la liste).

Pour accéder à un élément la liste peut être parcourue dans les deux sens :

• en commençant avec la tête, le pointeur suivant permettant le déplacement vers le prochain élément.
• en commençant avec la queue, le pointeur precedent permettant le déplacement vers l'élément précédent.

En bref, le déplacement se fait dans les deux directions, du premier vers le dernier élément et/ou du dernier vers le premier élément.

III. La construction du prototype d'un élément de la liste

Pour définir un élément de la liste le type struct sera utilisé.
L'élément de la liste contiendra un champ donnee, un pointeur precedent et un pointeur suivant.

Les pointeurs precedent et suivant doivent être du même type que l'élément, sinon ils ne pourront pas pointer vers un élément de la liste.
Le pointeur "precedent" permettra l'accès vers l'élément précédent tandis que le pointeur suivant permettra l'accès vers le prochain élément.

typedef struct dl_ElementListe {
  char *donnee;
  struct dl_ElementListe *precedent;
  struct dl_ElementListe *suivant;
}dl_Element;

Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.


Pour réaliser cela une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition :

typedef struct dl_ListeRepere {
  dl_Element *debut;
  dl_Element *fin;
  int taille;
}dl_Liste;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.

Quelque soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelque soit l'opération effectuée sur la liste.

IV. Opérations sur les listes doublement chaînées

Pour l'insertion ainsi que pour la suppression, une seule fonction est largement suffisante si elle est bien conçue en fonction des besoins.
Toutefois je vous rappelle que cet article est purement didactique.
C'est la raison pour laquelle j'ai écrit une fonction pour chaque opération d'insertion et de suppression.

A. Initialisation

Prototype de la fonction :

void initialisation (Liste *liste);

Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (Liste *liste){
  liste->debut = NULL;
  liste->fin = NULL;
  taille = 0;
}

B. Insertion d'un élément dans la liste

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour les pointeurs vers l'élément précédent et l'élément suivant
• mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
  • Cas particulier : dans une liste avec un seul élément, le 1er est en même temps le dernier.
  • mettre à jour la taille de la liste

Pour ajouter un élément dans la liste il y a plusieurs situations :

• 1. Insertion dans une liste vide
• 2. Insertion au début de la liste
• 3. Insertion à la fin de la liste
• 4. Insertion avant un élément
• 5. Insertion après un élément

1. Insertion dans une liste vide

Prototype de la fonction :

int ins_dans_liste_vide (dl_Liste * liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes :

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur precedent du nouvel élément pointera vers NULL (vu que l'insertion est faite dans une liste vide on utilise l'adresse du pointeur debut qui vaut NULL)
• le pointeur suivant du nouvel élément pointera vers NULL (vu que l'insertion est faite dans une liste vide on utilise l'adresse du pointeur fin qui vaut NULL)
• les pointeurs debut et fin pointeront vers le nouvel élément
• la taille est mise à jour

La fonction

int insertion_dans_liste_vide (dl_Liste * liste, char *donnee){
  dl_Element *nouveau_element;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->precedent = liste->debut;
  nouveau_element->suivant = liste->fin;
  liste->debut = nouveau_element;
  liste->fin = nouveau_element;
  liste->taille++;
  return 0;
}

2. Insertion au début de la liste

Prototype de la fonction :

int ins_debut_liste (dl_Liste * liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur precedent du nouvel élément pointe vers NULL
• le pointeur suivant du nouvel élément pointe vers le 1er élément
• le pointeur precedent du 1er élément pointe vers le nouvel élément
• le pointeur debut pointe vers le nouvel élément
• le pointeur fin ne change pas
• la taille est incrémentée

La fonction

int ins_debut_liste (dl_Liste * liste, char *donnee){
  dl_Element *nouveau_element;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->precedent = NULL;
  nouveau_element->suivant = liste->debut;
  liste->debut->precedent = nouveau_element;
  liste->debut = nouveau_element;
  liste->taille++;
  return 0;
}

3. Insertion à la fin de la liste

Prototype de la fonction :

int ins_fin_liste (dl_Liste * liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointe vers NULL
• le pointeur precedent du nouvel élément pointe vers le dernier élément (c'est le pointeur fin qui contient pour l'instant son adresse
• le pointeur suivant du dernier élément va pointer vers le nouvel élément
• le pointeur fin pointe vers le nouvel élément
• le pointeur debut ne change pas
• la taille est incrémentée

La fonction

int ins_fin_liste (dl_Liste * liste, char *donnee){
  dl_Element *nouveau_element;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->suivant = NULL;
  nouveau_element->precedent = liste->fin;
  liste->fin->suivant = nouveau_element;
  liste->fin = nouveau_element;
  liste->taille++;
  return 0;
}

4. Insertion avant un élément de la liste

Prototype de la fonction :

int ins_avant (dl_Liste * liste, char *donnee, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

L'insertion s'effectuera avant une certaine position passée en argument à la fonction.
La position indiquée ne doit pas être ni le 1er ni le dernier élément. Dans ce cas il faut utiliser les fonctions d'insertion au début et/ou à la fin de la liste.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• choisir une position dans la liste (l'insertion se fera après la position choisie)
• le pointeur suivant du nouvel élément pointe vers l'élément courant.
• le pointeur precedent du nouvel élément pointe vers l'adresse sur la quelle pointe le pointeur precedent d'élément courant. (une explication un peu tordue avec l'espoir que l'image vous éclaira ;-)
• le pointeur suivant de l'élément qui précède l'élément courant pointera vers le nouveau élément
• le pointeur precedent d'élément courant pointe vers le nouvel élément
• le pointeurs fin ne change pas
• le pointeur debut change si et seulement la position choisie est la position1
• la taille est incrémentée d'une unité

La fonction

int ins_avant (dl_Liste * liste, char *donnee, int pos){
  int i;
  dl_Element *nouveau_element, *courant;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  courant = liste->debut;
  for (i = 1; i < pos; ++i)
    courant = courant->suivant;
  nouveau_element->suivant = courant;
  nouveau_element-> precedent = courant->precedent;
  if(courant->precedent == NULL)
    liste->debut = nouveau_element;
  else
    courant->precedent->suivant = nouveau_element;
  courant->precedent = nouveau_element;
  liste->taille++;
  return 0;
}

5. Insertion après un élément de la liste

Prototype de la fonction :

int ins_apres (dl_Liste * liste, char *donnee, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

L'insertion s'effectuera après une certaine position passée en argument à la fonction.
La position indiquée ne doit pas être le dernier élément. Dans ce cas il faut utiliser la fonction d'insertion à la fin de la liste.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• choisir une position dans la liste (l'insertion se fera après la position choisie)
• le pointeur suivant du nouvel élément pointe vers l'adresse sur la quelle pointe le pointeur suivant d'élément courant (voir l'image)
• le pointeur precedent du nouvel élément pointe vers l'élément courant.
• le pointeur precedent de l'élément qui succède l'élément courant pointera vers le nouveau élément
• le pointeur suivant d'élément courant pointe vers le nouvel élément
• le pointeurs debut ne change pas
• le pointeur fin change si et seulement la position choisie est la position du dernier élément (la taille de liste)
• la taille est incrémentée d'une unité

La fonction

int ins_apres (dl_Liste * liste, char *donnee, int pos){
  int i;
  dl_Element *nouveau_element, *courant;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  courant = liste->debut;
  for (i = 1; i < pos; ++i)
    courant = courant->suivant;
  nouveau_element->suivant = courant->suivant;
  nouveau_element->precedent = courant;
  if(courant->suivant == NULL)
    liste->fin = nouveau_element;
  else
    courant->suivant->precedent = nouveau_element;
  courant->suivant = nouveau_element;
  liste->taille++;
  return 0;
}

C. Suppression d'un élément dans la liste

Voici l'algorithme de suppression d'un élément de la liste :

• utilisation d'un pointeur temporaire pour sauvegarder l'adresse d'éléments à supprimer
• l'élément à supprimer peut se trouver dans n'importe quelle position dans la liste.

Par rapport aux listes simplement chaînées où la suppression ne peux pas être faite qu'après un élément désigné, les listes doublement chaînées sont plus maniables grâce aux 2 pointeurs qui permettent de garder une trace en arrière comme en avant.

• libérer la mémoire occupée par l'élément supprimé
• mettre à jour la taille de la liste

Pour supprimer un élément dans la liste il y a plusieurs situations :

• 1. Suppression au début de la liste
• 2. Suppression à la fin de la liste
• 3. Suppression avant un élément
• 4. Suppression après un élément
• 3. Suppression d'un élément

Toutefois, la suppression au début et à la fin de la liste doublement chaînées ainsi qu'avant ou après un élément revient à la suppression à la position 0 (zéro) ou à la position N (N = nombre d'éléments de la liste) ou ailleurs dans la liste.

Dans le cas des listes doublement chaînées la suppression à n'importe quelle position ne pose pas des problèmes grâce au pointeurs precedent et suivant, qui permettent de garder la liaison entre les éléments de la liste.
C'est la raison pour la quelle nous allons créer une seule fonction.

• si nous voulons supprimer l'élément au début de la liste nous choisirons la position zéro
• si nous voulons supprimer l'élément à la fin de la liste nous choisirons la position N (le nombre d'éléments)
• si nous désirons supprimer un élément quelconque alors on choisit sa position dans la liste

Suppression dans la liste

Prototype de la fonction :

int supp(dl_Liste *liste, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Nous distinguons plusieurs situations :

• suppression à la position 1 dans une liste avec un seul élément
• suppression à la position 1 dans une liste avec plusieurs éléments
• suppression à la dernière position (le dernier élément)
• suppression ailleurs dans la liste à une certaine position

La suppression dans une liste vide n'a pas de sens.

Étapes:

• la position choisie est 1 (le cas de suppression du 1er élément de la liste)
  • le pointeur supp_element contiendra l'adresse du 1er élément
  • le pointeur debut contiendra l'adresse contenue par le pointeur suivant du 1er élément que nous voulons supprimer (si ce pointeur vaut NULL alors nous mettons à jour le pointeur fin puisqu'on est dans le cas d'une liste avec un seul élément, sinon nous faisons pointer le pointeur precedent du 2ème élément vers NULL)

• la position choisie est égale avec le nombre d'éléments de la liste
  • le pointeur supp_element contiendra l'adresse du dernier élément
  • nous faisons pointer le pointeur suivant de l'avant dernier élément (c'est l'élément vers le quel pointe le pointeur <precedent> de dernier élément), vers NULL
  • nous mettons à jour le pointeur fin

• la position choisie est aléatoire dans la liste
  • le pointeur supp_element contiendra l'adresse de l'élément à supprimer
  • le pointeur suivant d'élément qui précède l'élément à supprimer pointe vers l'adresse contenu par le pointeur suivant d'élément à supprimer
  • le pointeur precedent d'élément qui succède l'élément à supprimer pointe vers l'adresse contenu par le pointeur precedent d'élément à supprimer.
  • la taille de la liste sera décrémentée d'un élément

La fonction

int supp(dl_Liste *liste, int pos){
  int i;
  dl_Element *supp_element,*courant;

  if(liste->taille == 0)
    return -1;

  if(pos == 1){ /* suppresion de 1er élément */
    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    if(liste->debut == NULL)
      liste->fin = NULL;
    else
      liste->debut->precedent == NULL;
  }else if(pos == liste->taille){ /* suppression du dernier élément */
    supp_element = liste->fin;
    liste->fin->precedent->suivant = NULL;
    liste->fin = liste->fin->precedent;
  }else { /* suppression ailleurs */
    courant = liste->debut;
      for(i=1;i<pos;++i)
        courant = courant->suivant;
    supp_element = courant;
    courant->precedent->suivant = courant->suivant;
    courant->suivant->precedent = courant->precedent;
  }
  free(supp_element->donnee);
  free(supp_element);
  liste->taille--;
  return 0;
}

D. Affichage de la liste

Pour afficher la liste entière nous pouvons nous positionner au début de la liste ou à la fin de la liste (le pointeur debut ou fin le permettra).
Ensuite en utilisant le pointeur suivant ou precedent de chaque élément la liste est parcourue du 1er vers le dernier élément ou du dernier vers le 1er élément.
La condition d'arrêt est donnée par le pointeur suivant du dernier élément qui vaut NULL dans le cas de la lecture du début vers la fin de liste, ou par le pointeur precedent du 1er élément qui vaut NULL, dans le cas d'une lecture de la fin vers le début de la liste.

Les fonctions

void affiche(dl_Liste *liste){ /* affichage en avançant */
  dl_Element *courant;
  courant = liste->debut; /* point du départ le 1er élément */
  printf("[ ");
  while(courant != NULL){
    printf("%s ",courant->donnee);
    courant = courant->suivant;
  }
  printf("]\n");
}

void affiche_inv(dl_Liste *liste){ /* affichage en reculant */
  dl_Element *courant;
  courant = liste->fin; /* point du départ le dernier élément */
  printf("[ ");
  while(courant != NULL){
    printf("%s : ",courant->donnee);
    courant = courant->precedent;
  }
  printf("]\n");
}

E.Destruction de la liste

Pour détruire la liste entière, j'ai utilisé la suppression à la position 1 tant que la taille est plus grande que zéro.

La fonction

void detruire(dl_Liste *liste){
  while(liste->taille > 0)
    supp(liste,1);
}

V. Exemple complet

dliste.h

/* ---------- dliste.h ----------- */
typedef struct dl_ElementListe{
  char *donnee;
  struct dl_ElementListe *precedent;
  struct dl_ElementListe *suivant;
} dl_Element;

typedef struct dl_ListeRepere{
  dl_Element *debut;
  dl_Element *fin;
  int taille;
} dl_Liste;

/* initialisation de la liste */
void initialisation (dl_Liste * liste);
dl_Element *alloc (dl_Element * nouveau_element);

/* INSERTION */
int ins_dans_liste_vide (dl_Liste * liste, char *donnee);
int ins_debut_liste (dl_Liste * liste, char *donnee);
int ins_fin_liste (dl_Liste * liste, char *donnee);
int ins_apres (dl_Liste * liste, char *donnee, int pos);
int ins_avant (dl_Liste * liste, char *donnee, int pos);


/* SUPPRESSION */
int supp(dl_Liste *liste, int pos);
void affiche (dl_Liste * liste);

/**************************/
void affiche_inv (dl_Liste * liste);
void detruire (dl_Liste * liste);
/* -------- FIN liste.h --------- */

dliste_function.h

/***************************\

 *     dliste_function.h    *
\***************************/
void initialisation (dl_Liste * liste){
  liste->debut = NULL;
  liste->fin = NULL;
  liste->taille = 0;
}

int insertion_dans_liste_vide (dl_Liste * liste, char *donnee){
  dl_Element *nouveau_element;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->precedent = NULL;
  nouveau_element->suivant = NULL;
  liste->debut = nouveau_element;
  liste->fin = nouveau_element;
  liste->taille++;
  return 0;
}

int ins_debut_liste (dl_Liste * liste, char *donnee){
  dl_Element *nouveau_element;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->precedent = NULL;
  nouveau_element->suivant = liste->debut;
  liste->debut->precedent = nouveau_element;
  liste->debut = nouveau_element;
  liste->taille++;
  return 0;
}

int ins_fin_liste (dl_Liste * liste, char *donnee){
  dl_Element *nouveau_element;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->suivant = NULL;
  nouveau_element->precedent = liste->fin;
  liste->fin->suivant = nouveau_element;
  liste->fin = nouveau_element;
  liste->taille++;
  return 0;
}

int ins_apres (dl_Liste * liste, char *donnee, int pos){
  int i;
  dl_Element *nouveau_element, *courant;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  courant = liste->debut;
  for (i = 1; i < pos; ++i)
    courant = courant->suivant;
  nouveau_element->suivant = courant->suivant;
  nouveau_element->precedent = courant;
  if(courant->suivant == NULL)
    liste->fin = nouveau_element;
  else
    courant->suivant->precedent = nouveau_element;
  courant->suivant = nouveau_element;
  liste->taille++;
  return 0;
}

int ins_avant (dl_Liste * liste, char *donnee, int pos){
  int i;
  dl_Element *nouveau_element, *courant;
  if ((nouveau_element = alloc (nouveau_element)) == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  courant = liste->debut;
  for (i = 1; i < pos; ++i)
    courant = courant->suivant;
  nouveau_element->suivant = courant;
  nouveau_element-> precedent = courant->precedent;
  if(courant->precedent == NULL)
    liste->debut = nouveau_element;
  else
    courant->precedent->suivant = nouveau_element;
  courant->precedent = nouveau_element;
  liste->taille++;
  return 0;
}

int supp(dl_Liste *liste, int pos){
  int i;
  dl_Element *supp_element,*courant;
  
  if(liste->taille == 0)
    return -1;

  if(pos == 1){ /* suppresion de 1er élément */
    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    if(liste->debut == NULL)
      liste->fin = NULL;
    else
      liste->debut->precedent == NULL;
  }else if(pos == liste->taille){ /* suppression du dernier élément */
    supp_element = liste->fin;
    liste->fin->precedent->suivant = NULL;
    liste->fin = liste->fin->precedent;
  }else { /* suppression ailleurs */
    courant = liste->debut;
    for(i=1;i<pos;++i)
	    courant = courant->suivant;
    supp_element = courant;
    courant->precedent->suivant = courant->suivant;
    courant->suivant->precedent = courant->precedent;
  }
  free(supp_element->donnee);
  free(supp_element);
  liste->taille--;
  return 0;
}

void detruire(dl_Liste *liste){
  while(liste->taille > 0)
    supp(liste,1);
}

dl_Element *alloc (dl_Element * nouveau_element){
  if ((nouveau_element = (dl_Element *) malloc (sizeof (dl_Element))) == NULL)
    return NULL;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return NULL;
  return nouveau_element;
}

int menu (dl_Liste *liste){
  int choix;
  if (liste->taille == 0){
    printf ("1. Ajout du 1er element\n");
    printf ("2. Quitter\n");
  }  else{
    printf ("1. Ajout au debut de la liste\n");
    printf ("2. Ajout a la fin de la liste\n");
    printf ("3. Ajout avant la position specifie\n");
    printf ("4. Ajout apres la position specifie\n");
    printf ("5. Suppression à la position specifie\n");
    printf ("6. Detruire la liste\n");
    printf ("7. Quitter\n");
  }
  printf ("\n\nFaites votre choix : ");
  scanf ("%d", &choix);
  getchar();
  if(liste->taille == 0 && choix == 2)
    choix = 7;
  return choix;
}
int supp(dl_Liste *liste, int pos);
void affiche(dl_Liste *liste){
	dl_Element *courant;
	courant = liste->debut;
	printf("[ ");
	while(courant != NULL){
		printf("%s ",courant->donnee);
		courant = courant->suivant;
	}
	printf("]\n");
}
void affiche_inv(dl_Liste *liste){
	dl_Element *courant;
	courant = liste->fin;
	while(courant != NULL){
		printf("%s : ",courant->donnee);
		courant = courant->precedent;
	}
	printf("\n");
}
/* -------- FIN dliste_function.h --------- */

dliste.c

/**********************\

 *     dliste.c        *
\**********************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dliste.h"
#include "dliste_function.h"

int main (void)
{

  int choix = 0,pos;
  char *donnee;
  donnee = malloc(50);
  dl_Liste *liste;
  dl_Element *pilote = NULL;
  liste = (dl_Liste *) malloc (sizeof(dl_Liste));

  initialisation(liste);

  while(choix != 7){
    choix = menu(liste);
    switch(choix){
      case 1:
             printf("Entrez un element : ");
	     scanf("%s",donnee);
	     getchar();
	     if(liste->taille == 0)
               insertion_dans_liste_vide(liste,donnee);
	     else
               ins_debut_liste (liste, donnee);
	     printf("%d elements: deb=%s,fin=%s ",
			     liste->taille,liste->debut->donnee,liste->fin->donnee);
	     affiche(liste);
	     break;
      case 2:
	     printf("Entrez un element : ");
	     scanf("%s",donnee);
	     getchar();
	     ins_fin_liste (liste, donnee);
	     printf("%d elements: deb=%s,fin=%s ",
			     liste->taille,liste->debut->donnee,liste->fin->donnee);
	     affiche(liste);
	     break;
      case 3:
	     if(liste->taille == 1){
               printf("Utiliser l'insertion au debut ou a la fin (Entree Menu : 1 ou 2)\n");
	       break;
	     }
	     printf("Entrez un element : ");
	     scanf("%s",donnee);
	     getchar();
	     do{
                 printf("Entrez la position : ");
		 scanf("%d",&pos);
	     }while (pos < 1 || pos > liste->taille);
	     getchar();
	     ins_avant(liste,donnee,pos);
	     printf("%d elements: deb=%s fin=%s ",
			     liste->taille,liste->debut->donnee,liste->fin->donnee);
	     affiche(liste);
	     break;
      case 4:
	     if(liste->taille == 1){
		     printf("Utiliser l'insertion au debut ou a la fin (Entree Menu : 1 ou 2)\n");
		     break;
	     }
	     printf("Entrez un element : ");
	     scanf("%s",donnee);
	     getchar();
	     do{
                 printf("Entrez la position : ");
		 scanf("%d",&pos);
	     }while (pos < 1 || pos > liste->taille);
	     getchar();
	     ins_apres(liste,donnee,pos);
	     printf("%d elements: deb=%s,fin=%s ",
			     liste->taille,liste->debut->donnee,liste->fin->donnee);
	     affiche(liste);
	     break;
      case 5:
	     do{
                 printf("Entrez la position : ");
		 scanf("%d",&pos);
	     }while (pos < 1 || pos > liste->taille);
	     getchar();
	     supp(liste,pos);
	     if(liste->taille != 0)
               printf("%d elements: deb=%s,fin=%s ",
			       liste->taille,liste->debut->donnee,liste->fin->donnee);
	     else
               printf("liste vide : %d elements",liste->taille);
	     affiche(liste);
	     break;
      case 6:
	     detruire(liste);
	     printf("la liste a ete detruite : %d elements\n",liste->taille);
	     break;
    }
  }
  return 0;
}
/* -------- FIN dliste.c --------- */

VI. Voir aussi

• les listes simplement chaînées
• les listes circulaires
• les piles
• les files

Lire la suite

Vérifier si un nombre entier est un nombre premier en C »

Définition nombre premier

Un nombre premier est un entier naturel, qui se divise seulement par 1 et lui-même.

Algorithme 1 : les diviseurs compris entre 2 et N-1 seront testés

• les diviseurs compris entre 2 et N-1 seront testés

/**************************\

 *  nombre_premier1.c     *
\**************************/

/* algorithme : teste tous les diviseurs */
#include <stdio.h>


int main (void)
{
  int i, nb, compter, test;
  test = compter = 0;
  printf ("Entrez un nombre entier : ");
  if (scanf ("%d", &nb) != 1)
    return -1;

  for (i = 2; i < nb; i++, compter++)
    if (nb % i == 0)
      test = 1;
  if (!test)
    printf ("%d nombre premier, nombre iterations = %d\n", nb, compter);
  else
    printf ("%d n'est pas nombre premier, nombre iterations = %d\n", nb,compter);
  return 0;
}

Algorithme 2 : les diviseurs pairs ne seront pas testés, la recherche se limitant aux diviseurs impairs

• les diviseurs pairs ne seront pas testés, la recherche se limitant aux diviseurs impairs

/**************************\

 *    nombre_premier2.c   *
\**************************/

/* algorithme : exclure les nombres pairs et

 *    teste tous les diviseurs */
#include <stdio.h>


int main (void)
{
  int i, nb, compter, test;
  test = compter = 0;
  printf ("Entrez un nombre entier : ");
  if (scanf ("%d", &nb) != 1)
    return -1;

  if (nb % 2 == 0)
          test = 1;
  else{
      for (i = 3 ; i < nb; i+=2, compter++)
        if (nb % i == 0)
          test = 1;
  }
  if (!test)
          printf ("%d nombre premier, nombre iterations = %d\n",
                          nb, compter);
  else
          printf ("%d n'est pas nombre premier, nombre iterations = %d\n",nb, compter);
  return 0;
}

Algorithme 3 : les diviseurs impairs jusqu'à la racine carrée du N seront testés

• les diviseurs impairs jusqu'à la racine carrée du N seront testés

/**************************\

 *    nombre_premier3.c   *
\**************************/

/* algorithme : exclure les nombres pairs et

 * teste tous les diviseurs jusqu'à la racine carrée */
#include <stdio.h>
#include <math.h>

int main (void)
{
  int i, nb, compter, test,limite;
  test = compter = 0;
  printf ("Entrez un nombre entier : ");
  if (scanf ("%d", &nb) != 1)
    return -1;
  limite = sqrt(nb) + 1;

  if (nb % 2 == 0)
          test = 1;
  else{
      for (i = 3 ; i < limite; i+=2, compter++)
        if (nb % i == 0)
          test = 1;
  }
  if (!test)
          printf ("%d nombre premier, nombre iterations = %d\n", nb, compter);
  else
          printf ("%d n'est pas nombre premier, nombre iterations = %d\n",nb, compter);
  return 0;
}

Algorithme4 : arrêt du programme quand un diviseur est trouvé

• arrêt du programme quand un diviseur est trouvé

/**************************\

 *    nombre_premier4.c   *
\**************************/

/* algorithme : exclure les nombres pairs et

 * teste tous les diviseurs jusqu'à la racine carrée
 * et sortie de la boucle au 1er diviseur trouvé */
#include <stdio.h>
#include <math.h>

int main (void)
{
  int i, nb, compter, test,limite;
  test = compter = 0;
  printf ("Entrez un nombre entier : ");
  if (scanf ("%d", &nb) != 1)
    return -1;
  limite = sqrt(nb) + 1;

  if (nb % 2 == 0)
          test = 1;
  else{
      for (i = 3 ; i < limite && ! test; i+=2, compter++)
        if (nb % i == 0)
          test = 1;
  }
  if (!test)
          printf ("%d nombre premier, nombre iterations = %d\n", nb, compter);
  else
          printf ("%d n'est pas nombre premier, nombre iterations = %d\n", nb, compter);
  return 0;
}

Lire la suite

Permuter deux variables sans utilisation d'une variable temp »

Utilisation de pointeurs

Le code

#include <stdio.h>
void change(int *,int*);

int main ()
{
  int a=2,b=5;
  printf("Avant : a=%d,b=%d\n",a,b);

  change(&a,&b);

  printf("Apres : a=%d,b=%d\n",a,b);
  return 0;
}

void change(int *a,int *b){

  *a += *b;
  *b = *a-*b;
  *a = *a-*b;
}

Le résultat

lami20j@debian:~/trash$ gcc permuter_var.c
lami20j@debian:~/trash$ ./a.out
Avant : a=2,b=5
Apres : a=5,b=2

Utilisation d'une macro

Code :

#include <stdio.h>
#define PERMUTER(x,y) x ^= y, y ^= x, x ^= y

int main ()
{
  int a=2,b=5;
  printf("Avant : a=%d,b=%d\n",a,b);

  PERMUTER(a,b);

  printf("Apres : a=%d,b=%d\n",a,b);
  return 0;
}

Le résultat

vlmath@debian:~$ gcc permuter_var.c
vlmath@debian:~$ ./a.out
Avant : a=2,b=5
Apres : a=5,b=2

Remarque
Le nom de la macro, ou de ses variables, peut naturellement être changé.

Lire la suite

Listes circulaires (Ring Buffer) »

Listes circulaires

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées
Les listes doublement chaînées

I. INTRODUCTION

Cette article a pour but la compréhension des listes circulaires.
L'implémentation en fonction des besoins et des performances vous appartient.

II. Définition

La liste circulaire est une sorte de liste simplement ou doublement chaînée, qui comporte une caractéristique supplémentaire pour le déplacement dans la liste, "elle n'a pas de fin".
Pour rendre la liste sans fin, le pointeur suivant du dernier élément pointera sur le 1er élément de la liste au lieu de la valeur NULL, que nous avons vu dans le cas des listes simplement et doublement chaînées.
Dans les listes circulaires, nous n'arriverons jamais à une position depuis laquelle nous ne pourrons plus nous déplacer.
En arrivant au dernier élément, le déplacement recommencera au premier élément. En bref, il s'agit d'une rotation.

III. La construction du prototype d'un élément de la liste

Pour définir un élément de la liste, le type struct sera utilisé.
L'élément de la liste contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur "suivant" permettra l'accès vers le prochain élément.

typedef struct ElementListe {
    char *donnee;
    struct ElementListe *suivant;
}Element;

Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.


Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition:

typedef struct ListeRepere {
    Element *debut;
    Element *fin;
    int taille;
}Liste;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.

Quelle que soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelle que soit l'opération effectuée sur la liste.

IV. Opérations sur les listes circulaires

A. Initialisation

Prototype de la fonction :

void initialisation (Liste *liste);

Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (Liste *liste){
    liste->debut = NULL;
    liste->fin = NULL;
    taille = 0;
}

B. Insertion d'un élément dans la liste

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
  • Cas particulier : dans une liste avec un seul élément, le 1er est en même temps le dernier.
  • mettre à jour la taille de la liste

1. Insertion dans une liste vide

Prototype de la fonction :

int ins_liste_circ_vide(Liste * liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

étapes :

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointera vers lui-même (c'est l'étape qui rend la liste circulaire)
• les pointeurs debut et fin pointeront vers le nouvel élément
• la taille est mise à jour

La fonction

/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
          == NULL)
      return -1;       
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
       return -1;
    strcpy (nouveau_element->donnee, donnee);

    nouveau_element->suivant = nouveau_element;
    liste->debut = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

2. Insertion dans une liste non vide

Prototype de la fonction :

int ins_liste_circ(Liste * liste, Element *courant, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

L'insertion s'effectuera à la fin de la liste.


étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointe vers l'adresse du premier élément (garder la liste circulaire)
• le pointeur debut ne change pas
• le pointeur fin pointe vers le nouvel élément
• la taille est incrémentée d'une unité

La fonction

/* insertion dans une liste non vide */
int ins_liste_circ(Liste * liste, Element *courant, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
            == NULL)
        return -1;       
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
        return -1;
    strcpy (nouveau_element->donnee, donnee);

    if(courant != liste->fin)
        return -1;
  
    nouveau_element->suivant = courant->suivant;
    courant->suivant = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

C. Suppression d'un élément dans la liste

Voici l'algorithme de suppression d'un élément de la liste :

• utilisation d'un pointeur temporaire pour sauvegarder l'adresse d'éléments à supprimer
• l'élément à supprimer se trouve après l'élément courant

Faire pointer le pointeur suivant de l'élément courant vers l'adresse du pointeur suivant de l'élément à supprimer

• libérer la mémoire occupée par l'élément supprimé
• mettre à jour la taille de la liste

Pour supprimer un élément dans la liste il y a plusieurs situations :

• 1. Suppression dans la liste
• 2. Suppression du dernier élément de la liste

1. Suppression au début de la liste

Prototype de la fonction:

int supp_list_circ(Liste *liste);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


étapes:

• le pointeur supp_elem contiendra l'adresse du 1er élément
• le pointeur debut pointera vers le 2ème élément
• le pointeur suivant du dernier élément pointera vers le 1er élément (qui était le 2ème avant la suppression)
• la taille de la liste sera décrémentée d'un élément

La fonction

/* suppression au début de la liste */
int supp_liste_circ(Liste * liste){
    if (liste->taille < 2)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    liste->fin->suivant = liste->debut;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

2. Suppression dans une liste avec un seul élément

Prototype de la fonction:

int supp_list_circ_unique(Liste *liste);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


étapes:

• le pointeur supp_elem contiendra l'adresse d'élément (la liste contient un seul élément)
• le pointeur debut pointera vers NULL
• le pointeur fin pointera vers NULL
• la taille de la liste sera décrémentée d'un élément

La fonction

/* suppression dans une liste avec un seul élément*/
int supp_liste_circ_unique(Liste *liste){
    if (liste->taille != 1)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = NULL;
    liste->fin = NULL;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

D. Affichage de la liste

Pour afficher la liste entière, il faut se positionner au début de la liste (le pointeur debut le permettra).
Ensuite, en utilisant le pointeur suivant de chaque élément, la liste est parcourue du 1er vers le dernier élément.
En comparaison avec les listes simplement et doublement chaînées, où la condition d'arrêt est donnée par le pointeur suivant du dernier élément, qui vaut NULL, pour la liste circulaire, il n'y a pas de point d'arrêt, à moins que vous n'en choisissiez un.

Voici deux variantes d'affichage :

• affichage de la liste (du 1er vers le dernier élément)
• affichage de la liste sans condition d'arrêt (à l'infini)

1. Affichage de la liste (du 1er vers le dernier élément)

Nous utiliserons la taille de la liste pour la condition d'arrêt.

La fonction

/* affichage de la liste */
void affiche (Liste * liste){
    Element *courant;
    courant = liste->debut;
    int i;
    for(i=0;i<liste->taille;++i){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

2. Affichage de la liste sans condition d'arrêt (à l'infini)

La fonction

/* parcourir la liste à l'infini*/
void affiche_infini (Liste * liste){
    Element *courant;
    courant = liste->debut;
    while (1){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

E. Destruction de la liste

Pour détruire la liste entière, j'ai utilisé la suppression au début de la liste tant que la taille est plus grande que 1, ensuite la suppression dans une liste avec un seul élément.

La fonction

/* detruire la liste */
void detruire (Liste * liste){
    while (liste->taille > 0){
        if(liste->taille > 1)
        supp_liste_circ (liste);
    else
        supp_liste_circ_unique(liste);
    }
}

V. Exemple complet

liste_circ.h

/* ---------- liste_circ.h ----------- */
typedef struct ElementListeCirc {
    char *donnee;
    struct ElementListeCirc *suivant;
} Element;

typedef struct ListeRepereCirc {
    Element *debut;
    Element *fin;
    int taille;
} Liste;

/* initialisation de la liste */
void initialisation (Liste * liste);

/* INSERTION */
/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee);
int ins_liste_circ(Liste * liste, Element *courant, char *donnee);

/* SUPPRESSION */
int supp_liste_circ (Liste * liste);
int supp_liste_circ_unique (Liste * liste);

int menu (Liste *liste);
void affiche (Liste * liste);
void affiche_infini (Liste * liste);
void detruire (Liste * liste);
/* -------- FIN liste_circ.h --------- */

liste_circ_function.h

/******************************\

    * liste_circ_function.h *
\******************************/
void initialisation (Liste * liste){
    liste->debut = NULL;
    liste->fin = NULL;
    liste->taille = 0;
}

/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
          == NULL)
      return -1;       
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
       return -1;
    strcpy (nouveau_element->donnee, donnee);

    nouveau_element->suivant = nouveau_element;
    liste->debut = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

/* insertion dans une liste non-vide */
int ins_liste_circ(Liste * liste, Element *courant, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
            == NULL)
        return -1;       
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
        return -1;
    strcpy (nouveau_element->donnee, donnee);

    if(courant != liste->fin)
        return -1;
  
    nouveau_element->suivant = courant->suivant;
    courant->suivant = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

/* suppression au début de la liste */
int supp_liste_circ(Liste * liste){
    if (liste->taille < 2)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    liste->fin->suivant = liste->debut;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

/* suppression dans une liste avec un seul élément*/
int supp_liste_circ_unique(Liste *liste){
    if (liste->taille != 1)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = NULL;
    liste->fin = NULL;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

/* affichage de la liste */
void affiche (Liste * liste){
    Element *courant;
    courant = liste->debut;
    int i;
    for(i=0;i<liste->taille;++i){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

/* parcourir la liste à l'infini*/
void affiche_infini (Liste * liste){
    Element *courant;
    courant = liste->debut;
    while (1){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

/* detruire la liste */
void detruire (Liste * liste){
    while (liste->taille > 0){
        if(liste->taille > 1)
        supp_liste_circ (liste);
    else
        supp_liste_circ_unique(liste);
    }
}

int menu (Liste *liste){
    int choix;     printf("********** MENU **********\n");
    if (liste->taille == 0){
        printf ("1. Ajout du 1er element\n");
        printf ("2. Quitter\n");
    }else {       
        printf ("1. Ajout d'un élément\n");
        printf ("2. Suppression au début (la liste doit avoir au moins 2 éléments)\n");
    printf ("3. Suppression dans une liste avec un seul élément\n");
        printf ("4. Affiche liste circulaire\n");
        printf ("5. Affiche liste circulaire [Ctrl-C] pour quitter le programme\n");
        printf ("6. Détruire la liste\n");
        printf ("7. Quitter\n");
    }
    printf ("\n\nFaites votre choix : ");
    scanf ("%d", &choix);
    getchar();
    if(liste->taille == 0 && choix == 2)
        choix = 7;
    return choix;
}
/* -------- FIN liste_circ_function --------- */

liste_circ.c

/**********************\

    * liste_circ.c *
\**********************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "liste_circ.h"
#include "liste_circ_function.h"

int main (void)
{
    char choix;
    char *nom;
    Liste *liste;
    Element *courant;


    if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL)
    return -1;
    if ((nom = (char *) malloc (50)) == NULL)
        return -1;
    courant = NULL;
    choix = 'o';

    initialisation (liste);

    while (choix != 7){
        choix = menu (liste);
        switch (choix){
            case 1:
                printf ("Entrez un element : ");
                scanf ("%s", nom);
                getchar ();
                if(liste->taille == 0)
                    ins_liste_circ_vide (liste,nom);
                else
                    ins_liste_circ (liste,liste->fin,nom);
                printf ("%d elements:deb=%s, fin=%s\n",
                                        liste->taille,
                                        liste->debut->donnee,
                                        liste->fin->donnee);
                affiche (liste);
                break;
            case 2:
                if(liste->taille < 2)
                    break;
                supp_liste_circ (liste);
                if (liste->taille != 0)
                    printf ("%d elements:deb=%s, fin=%s\n",
                                            liste->taille,
                                            liste->debut->donnee,
                                            liste->fin->donnee);
                affiche(liste);
                break;
            case 3:
                if(liste->taille != 1)
                    break;
                supp_liste_circ_unique(liste);
                printf("La liste est vide\n");
                break;
            case 4:
                affiche(liste);
                break;
            case 5:
                affiche_infini(liste);
                break;
            case 6:
                detruire (liste);
                printf ("la liste a ete detruite : %d elements\n", liste->taille);
                break;
        }
    }
    return 0;
}

VI. Voir aussi

• les listes simplement chaînées
• les listes doublement chaînées
• les piles
• les files

Lire la suite

Télécharger le contenu d'une page WEB distante »

Introduction

Il n'existe pas, dans la librairie standard, de fonction permettant de télécharger une page web, et même pour être plus général, de fonctions pour communiquer en utilisant le protocole HTTP.

Il n'existe finalement que deux manières:

• Utiliser les fonctions de communications bas niveau: les sockets pour reproduire le dialogue HTTP.
• Utiliser une librairie capable de faire ça toute seule, ce qui vous permettra de vous concentrer sur l'essentiel.

LibCurl est une de ces librairies qui supporte également beaucoup d'autres protocoles comme ftp, ldap etc... C'est également une librairie libre et portable (passe indifféremment sous Windows comme Unix par exemple).

Installation sous Linux (Ubuntu / Debian)

Ouvrez un shell puis tapez:

sudo apt-get install libcurl3 libcurl3-dev

Voilà, vous avez installé la librairie et ses fichiers d'en-têtes.

Installation sous Windows

Dev C++

Ceci a été testé avec la version 4.9.9.2 uniquement.

Avec l'IDE libre Dev C++, l'installation est plutôt simple, aussi je vous recommande ce logiciel dans notre exemple d'autant plus qu'il est gratuit et libre.
Nous allons installer d'abord la librairie zlib, dont dépend libcurl, puisque nous installerons libcurl ensuite.

Ouvrez donc Dev C++ et allez dans le menu Outils/Nouvelles versions Packages.
Dans le menu déroulant intitulé "Select devpack server" en haut de la petite fenêtre de gestion de package, sélectionnez devpacks.org puis cliquez sur le bouton "Check for updates".



Des noms de bibliothèques vont apparaître, cherchez "zlib" et sélectionnez la dernière version.

Cliquez sur "Download selected" et laissez vous guider par l'installeur.



Ensuite, dans la même liste, cherchez libcurl et vérifiez que la version contient la mention "no_ssl" puis sélectionnez-la et cliquez de nouveau sur "Download Selected" et idem, laissez-vous guider.



Et voilà, c'est installé :-)

Microsoft Visual C++

Explication en anglais pour installer avec Visual C++

Petite exploration des fonctions de libcurl

Maintenant, regardons de plus près comment utiliser cette librairie pour télécharger une page web.
Certaines des fonctions utiles sont détaillées ici.
Nous aurons besoin des fonctions suivantes:

• CURL *curl_easy_init( );

  Cette fonction est la première à appeler, elle initialise la session puis la stocke dans une variable de type CURL * qui est un type propre à la librairie, vous n'avez pas à vous en soucier.

• CURLcode curl_easy_setopt(CURL *handle, CURLoption option, parameter);

  Cette fonction est la plus délicate à utiliser. C'est ici que tout se passe en quelque sorte. Le premier argument est la session que vous avez initialisée. L'option et le parameter forment un couple de données qui forme un sens ensemble. C'est dans ce couple que vous configurez tout: l'url, la fonction à utiliser pour enregistrer le contenu téléchargé, le nom du fichier etc... Par exemple pour mettre l'url de la page à télécharger, option sera égal à CURLOPT_URL et parameter sera l'url du genre http://machin.com. On verra ça dans l'exemple. Mais il faut bien retenir que le type de parameter dépend fortement de l'option. On appele cette fonction autant de fois que l'on a des paramètres à passer.

• CURLcode curl_easy_perform(CURL * handle );

  Ça, c'est la fonction magique, elle exécute le téléchargement.

• void curl_easy_cleanup(CURL * handle );

  Ça, c'est une fonction qu'il vaut mieux ne pas oublier: elle libère les ressources utilisées durant la session que vous avez initialisée.

Allez on met en pratique!

Un exemple: télécharger la page d'accueil de CCM

On a besoin de télécharger la page d'accueil de CCM.
On enregistrera la page http://www.commentcamarche.net dans le fichier ./index_ccm.html

• Fichiers d'en-tête, obligatoires pour utiliser les fonctions et types de la libcurl et aussi pour la gestion de notre fichier

  #include <curl/curl.h>

  #include <stdio.h>

• Initialisation de la session

  CURL *session = curl_easy_init(); //Mouarf, trop facile

• On précise l'url qui nous intéresse

  curl_easy_setopt(session, CURLOPT_URL, "http://www.commentcamarche.net");

• On précise le nom de notre fichier destination qui recevra le contenu de la page

  FILE * fp = fopen("./index_ccm.html", "w"); //Création de notre fichier

  curl_easy_setopt(session,  CURLOPT_WRITEDATA, fp); //On balance notre pointeur de fichier comme destination 

• On précise la fonction qui gèrera l'écriture dans notre fichier. Peut être n'êtes-vous pas habitués à cela, il faut mettre un pointeur de fonction en paramètre de curl_easy_setopt. Comme ça, curl_easy_setopt utilisera cette fonction pointée pour écrire dans le fichier. La fonction en question doit respecter la même en-tête que la fonction standard fwrite:

  size_t  fwrite(const  void  *ptr,  size_t  size,  size_t  nmemb,  FILE  *stream);

  Vous pouvez donc créer une fonction d'écriture de votre choix et la mettre en paramètre de curl_easy_setopt tant qu'elle possède la même en-tête que fwrite. Mais sincèrement si vous ne voulez pas vous prendre la tête, utilisez fwrite qui est déjà toute prête:

  curl_easy_setopt(session,  CURLOPT_WRITEFUNCTION, fwrite);

• On a fait le plus dur si j'ose dire. Il ne reste plus qu'à lancer le téléchargement

  curl_easy_perform(session);

• Enfin, on libère nos ressources utilisées

  fclose(fp);

  curl_easy_cleanup(session);

Notre fichier source

Voici donc ce que donne notre exemple:

#include <curl/curl.h>
#include <stdio.h>

int main(int argc, char **argv)
{
	CURL *session = curl_easy_init(); 
	curl_easy_setopt(session, CURLOPT_URL, "http://www.commentcamarche.net");
	FILE * fp = fopen("./index_ccm.html", "w"); 
	curl_easy_setopt(session,  CURLOPT_WRITEDATA, fp); 
	curl_easy_setopt(session,  CURLOPT_WRITEFUNCTION, fwrite);
	curl_easy_perform(session);
	fclose(fp);
	curl_easy_cleanup(session);
	return 0;
}

Compilation avec gcc (Unix/Linux)

Maintenant on va compiler ça. On appellera notre fichier ccm.c
Pour compiler, il sera important de préciser que l'on utilise la libcurl à l'éditeur de lien, pour qu'il sache où trouver les fonctions de libcurl. On rajoutera donc l'option -lcurl:

gcc ccm.c -o ccm -lcurl

Et voilà, il n'y a plus qu'à lancer notre application:
./ccm

Compilation sous Windows

Dev C++

Testé avec la version 4.9.9.2, comme tout à l'heure pour l'installation.

Créez un nouveau projet d'application en mode console.
Dans votre main.c, collez le code du fichier source de la section précédente. A présent, notre but sera d'indiquer au compilateur et à l'éditeur de lien, les options nécessaires pour la création de notre exécutable.

• Compiler en mode statique. On va intégrer le code de la libcurl dans notre exécutable sans dépendre de la dll de libcurl. Ça s'appelle une compilation avec bibliothèque statique. C'est moins contraignant. Pour cela, on compilera en définissant la constante de macroprocesseur CURL_STATICLIB.
• Dépendances de librairies statiques et dll. Oui il en faut bien des dll, comme certaines de Windows par exemple. Nous aurons besoin de la libcurl (évidemment), de la dll de gestion des sockets (Ws2_32.dll), de la zlib (librairie de compression des données) et de winmm.dll.

Pour définir tout cela, allez dans Outils / Options du compilateur puis ajoutez la commande suivante pour le compilateur:

-DCURL_STATICLIB

et les commandes suivantes pour l'éditeur de liens:

-lcurl -lWs2_32 -lz -lWinmm

Cliquez sur OK puis sur l'icône "Tout reconstruire", et à priori, le tour est joué :-)

Microsoft Visual C++

Explication en anglais pour compiler avec Visual C++ (même document que pour l'installation)

Notes

Cette librairie est certes un peu magique mais il y a des limites:

• Vous ne téléchargerez que la page précisée, les fichiers dont dépend la page ne seront pas téléchargés (images, feuilles de style etc...). Si vous voulez tous les fichiers dont dépend une page, vous pouvez utiliser des programmes tout fait comme wget par exemple.
• Vous n'aurez que le code source finalisé de la page, vous n'aurez pas le code source PHP d'une page web par exemple

Compléments

• Site officiel (en)
• Tutorial (en)
• Les fonctions de libcurl (en)
• Des exemples pour utiliser libcurl (en)
• Libwww, une autre librairie qui fait la même chose (en)

Lire la suite

Les files en langage C »

Les files - Premier Entré Premier Sorti

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées
Les listes doublement chaînées

I. INTRODUCTION

Cette article a pour but la compréhension des files.
L'implémentation en fonction du besoin vous appartient.
Pour expliquer l'algorithme j'ai choisi d'utiliser une liste simplement chaînée. Donc la compréhension des listes chaînées est nécessaire.

II. Définition

La file est une structure de données, qui permet de stocker les données dans l'ordre FIFO (First In First Out) - en français Premier Entré Premier Sorti).
La récupération des données sera faite dans l'ordre d'insertion.

Pour l'implémentation j'ai choisi une liste simplement chaînée.
L'insertion dans la file se fera dans l'ordre normal, le 1er élément de la file sera le premier élément saisi, donc sa position est au début de la file.

III. La construction du prototype d'un élément de la file

Pour définir un élément de la file le type struct sera utilisé.
L'élément de la file contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur suivant permettra l'accès vers le prochain élément.

typedef struct ElementListe {
    char *donnee;
    struct ElementListe *suivant;
}Element;

Pour avoir le contrôle de la file, il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.


Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition:

typedef struct ListeRepere{
  Element *debut;
  Element *fin;
  int taille;
} File;

IV. Opérations sur les files

A. Initialisation

Prototype de la fonction :

void initialisation (File * suite);

Cette opération doit être faite avant toute autre opération sur la file.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (File * suite){
  suite->debut = NULL;
  suite->fin = NULL;
  suite->taille = 0;
}

B. Insertion d'un élément dans la file

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour le pointeur debut vers le 1er élément (le début de file)
• mettre à jour le pointeur fin (ça nous servira pour l'insertion vers la fin de la file)
• mettre à jour la taille de la file

Prototype de la fonction :

int enfiler (File * suite, Element * courant, char *donnee);

La 1ère image affiche le début de l'insertion, donc la liste a la taille 1 après l'insertion.



Dans la file, l'élément à récupérer c'est le 1er entré. Pour cela, l'insertion se fera toujours à la fin de la file. Il s'agit de l'ordre normal de l'insertion (1er, 2ème, 3ème ...... etc. ).



La fonction

int enfiler (File * suite, Element * courant, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);

  if(courant == NULL){
    if(suite->taille == 0)
      suite->fin = nouveau_element;
    nouveau_element->suivant = suite->debut;
    suite->debut = nouveau_element;
  }else {
    if(courant->suivant == NULL)
      suite->fin = nouveau_element;
    nouveau_element->suivant = courant->suivant;
    courant->suivant = nouveau_element;
  }
  suite->taille++;
  return 0;
}

C. Oter un élément de la file

Pour supprimer (ôter) l'élément de la file, il faut tout simplement supprimer l'élément vers lequel pointe le pointeur debut.
Cette opération ne permet pas de récupérer la donnée au début de la file (la première donnée), mais seulement de la supprimer.

Prototype de la fonction :

int de_filer (File * suite);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

étapes :

• le pointeur supp_elem contiendra l'adresse du 1er élément
• le pointeur debut pointera vers le 2ème élément (après la suppression du 1er élément, le 2ème sera au début de la file)
• la taille de la file sera décrémentée d'un élément

La fonction

int de_filer (File * suite){
  Element *supp_element;
  if (suite->taille == 0)
    return -1;
  supp_element = suite->debut;
  suite->debut = suite->debut->suivant;
  free (supp_element->donnee);
  free (supp_element);
  suite->taille--;
  return 0;
}

D. Affichage de la file

Pour afficher la file entière, il faut se positionner au début de la file (le pointeur debut le permettra).
Ensuite en utilisant le pointeur suivant de chaque élément, la file est parcourue du 1er vers le dernier élément.
La condition d'arrêt est donnée par la taille de la file.

La fonction

void affiche(File *suite){
  Element *courant;
  int i;
  courant = suite->debut;

  for(i=0;i<suite->taille;++i){
    printf(" %s ", courant->donnee);
    courant = courant->suivant;
  }
}

E. Récupération de la donnée au début de la file

Pour récupérer la donnée au début de la file sans la supprimer, j'ai utilisé une macro. La macro lit les données au début de la file en utilisant le pointeur debut.

#define file_donnee(suite) suite->debut->donnee

V. Exemple complet

file.h

/*********************\

 *      file.h       *
\*********************/
typedef struct ElementListe{
  char *donnee;
  struct ElementListe *suivant;
} Element;

typedef struct ListeRepere{
  Element *debut;
  Element *fin;
  int taille;
} File;

/* initialisation */
void initialisation (File * suite);

/* ENFILER*/
int enfiler (File * suite, Element * courant, char *donnee);

/* DE_FILER*/
int de_filer (File * suite);

/* FirstInFirstOut */
#define file_donnee(suite) suite->debut->donnee

/* Affiche la file */
void affiche(File *suite);

file_function.h

/***********************\

 * file_function.h     *
\***********************/

void initialisation (File * suite){
  suite->debut = NULL;
  suite->fin = NULL;
  suite->taille = 0;
}

/* enfiler (ajouter) un élément dans la file */
int enfiler (File * suite, Element * courant, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);

  if(courant == NULL){
    if(suite->taille == 0)
      suite->fin = nouveau_element;
    nouveau_element->suivant = suite->debut;
    suite->debut = nouveau_element;
  }else {
    if(courant->suivant == NULL)
      suite->fin = nouveau_element;
    nouveau_element->suivant = courant->suivant;
    courant->suivant = nouveau_element;
  }
  suite->taille++;
  return 0;
}

/* de_filer (supprimer) un élément de la file */
int de_filer (File * suite){
  Element *supp_element;
  if (suite->taille == 0)
    return -1;
  supp_element = suite->debut;
  suite->debut = suite->debut->suivant;
  free (supp_element->donnee);
  free (supp_element);
  suite->taille--;
  return 0;
}

/* affichage de la file */
void affiche(File *suite){
  Element *courant;
  int i;
  courant = suite->debut;

  for(i=0;i<suite->taille;++i){
    printf(" %s ", courant->donnee);
    courant = courant->suivant;
  }
}

file.c

/*********************\

 *      file.c       *
\*********************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "file.h"
#include "file_function.h"

int main ()
{
  File *suite;
  char *nom;
  if ((suite = (File *) malloc (sizeof (File))) == NULL)
    return -1;
  if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)
    return -1;
  initialisation (suite);

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  enfiler (suite, suite->fin, nom);
  printf ("La file (%d éléments)\n",suite->taille);
  printf("\nDébut de la FILE [ ");
  affiche (suite);      /*le premier entré sera affiché */
  printf(" ] Fin de la FILE\n\n");

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  enfiler (suite, suite->fin, nom);
  printf ("La file (%d éléments)\n",suite->taille);
  printf("\nDébut de la FILE [ ");
  affiche (suite);      /*le premier entré sera affiché */
  printf(" ] Fin de la FILE\n\n");

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  enfiler (suite, suite->fin, nom);
  printf ("La file (%d éléments)\n",suite->taille);
  printf("\nDébut de la FILE [ ");
  affiche (suite);      /*le premier entré sera affiché */
  printf(" ] Fin de la FILE\n\n");


  printf ("\nLe premier entré (FirstInFirstOut) [ %s ] sera supprimé",
                    file_donnee(suite));
  printf ("\nLe premier entré est supprime\n");
  de_filer (suite);              /* suppression de premier element entre */
  printf ("La file (%d éléments): \n",suite->taille);
  printf("\nDébut de la FILE [ ");
  affiche (suite);
  printf(" ] Fin de la FILE\n\n");

  return 0;
}

VI. Voir aussi

• les listes simplement chaînées
• les listes doublement chaînées
• les listes circulaires
• les piles

Lire la suite

Les piles en langage C »

Les piles

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées
Les listes doublement chaînées

I. INTRODUCTION

Cette article a pour but la compréhension des piles.
L'implémentation en fonction du besoin vous appartient.
Pour expliquer l'algorithme j'ai choisi d'utiliser une liste simplement chaînée. Donc la compréhension des listes chaînées est nécessaire.

II. Définition

La pile est une structure de données, qui permet de stocker les données dans l'ordre LIFO (Last In First Out) - en français Dernier Entré Premier Sorti).
La récupération des données sera faite dans l'ordre inverse de leur insertion.

Pour l'implémentation j'ai choisi une liste simplement chaînée, présentée sur la verticale.
L'insertion se faisant toujours au début de la liste, le 1er élément de la liste sera le dernier élément saisi, donc sa position est en haut de la pile.
Je n'ai pas utilisé un pointeur fin, comme je l'ai fait dans le cas des listes simplement chaînées, puisque le but ce n'est pas de traiter une liste chaînée, mais la pile.
Ce qui nous intéresse c'est que le dernier élément entré, sera le 1er élément récupéré.

III. La construction du prototype d'un élément de la pile

Pour définir un élément de la pile le type struct sera utilisé.
L'élément de la pile contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur suivant permettra l'accès vers le prochain élément.

typedef struct ElementListe {
    char *donnee;
    struct ElementListe *suivant;
}Element;

Pour permettre les opérations sur la pile, nous allons sauvegarder certains éléments :

• le premier élément
• le nombre d'éléments

Le 1er élément, qui se trouve en haut de la pile, nous permettra de réaliser l'opération de récupération des données situées en haut de la pile.


Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition :

typedef struct ListeRepere{
  Element *debut;
  int taille;
} Pile;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
La variable taille contient le nombre d'éléments.

Observation :
Nous n'utilisons pas cette fois un pointeur fin (voir les listes simplement chaînées), puisque nous n'en avons pas besoin, vu que nous travaillons qu'au début de la liste.

Quelque soit la position dans la liste, le pointeur debut pointe toujours vers le 1er élément, qui sera en haut de la pile.
Le champ taille contiendra le nombre d'éléments de la pile, quelque soit l'opération effectuée sur la pile.

IV. Opérations sur les piles

A. Initialisation

Prototype de la fonction :

void initialisation (Pile *tas);

Cette opération doit être faite avant toute autre opération sur la pile.
Elle initialise le pointeur debut avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (Pile * tas){
  tas->debut = NULL;
  tas->taille = 0;
}

B. Insertion d'un élément dans la pile

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour le pointeur debut vers le 1er élément (le haut de la pile)
• mettre à jour la taille de la pile

Prototype de la fonction :

int empiler (Pile *tas, char *donnee);

La 1ère image montre le début de l'insertion, donc la liste a la taille 1 après l'insertion. La caractéristique de la pile n'est pas très bien mise en évidence avec un seul élément, puisque c'est le seul à récupérer.



En revanche la 2ème image nous permet d'observer le comportement de la pile.
La chose qu'il faut retenir, c'est que l'insertion se fait toujours en haut de la pile (au début de la liste).



La fonction

/* empiler (ajouter) un élément dans la pile */
int empiler (Pile * tas, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->suivant = tas->debut;
  tas->debut = nouveau_element;
  tas->taille++;
}

C. Ôter un élément de la pile

Pour supprimer (ôter ou dépiler) l'élément de la pile, il faut tout simplement supprimer l'élément vers lequel pointe le pointeur debut.
Cette opération ne permet pas de récupérer la donnée en haut de la pile, mais seulement de la supprimer.

Prototype de la fonction :

int depiler (Pile *tas);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Les étapes :

• le pointeur supp_elem contiendra l'adresse du 1er élément
• le pointeur debut pointera vers le 2ème élément (après la suppression du 1er élément, le 2ème sera en haut de la pile)
• la taille de la pile sera décrémentée d'un élément

La fonction

int depiler (Pile * tas){
  Element *supp_element;
  if (tas->taille == 0)
    return -1;
  supp_element = tas->debut;
  tas->debut = tas->debut->suivant;
  free (supp_element->donnee);
  free (supp_element);
  tas->taille--;
  return 0;
}

D. Affichage de la pile

Pour afficher la pile entière, il faut se positionner au début de la pile (le pointeur debut le permettra).
Ensuite, en utilisant le pointeur suivant de chaque élément, la pile est parcourue du 1er vers le dernier élément.
La condition d'arrêt est donnée par la taille de la pile.

La fonction

/* affichage de la pile */
void affiche (Pile * tas){
  Element *courant;
  int i;
  courant = tas->debut;

  for(i=0;i<tas->taille;++i){
    printf("\t\t%s\n", courant->donnee);
    courant = courant->suivant;
  }
}

E. Récupération de la donnée en haut de la pile

Pour récupérer la donnée en haut de la pile sans la supprimer, j'ai utilisé une macro. La macro lit les données en haut de la pile en utilisant le pointeur debut.

#define pile_donnee(tas)  tas->debut->donnee

V. Exemple complet

pile.h

/*********************\

 *      pile.h       *
\*********************/
typedef struct ElementListe{
  char *donnee;
  struct ElementListe *suivant;
} Element;

typedef struct ListeRepere{
  Element *debut;
  int taille;
} Pile;


/* initialisation */
void initialisation (Pile *tas);

/* EMPILER*/
int empiler (Pile *tas, char *donnee);

/* DEPILER*/
int depiler (Pile *tas);

/* Affichage de élément en haut de la pile (LastInFirstOut) */
#define pile_donnee(tas)  tas->debut->donnee

/* Affiche la pile */
void affiche (Pile *tas);

pile_function.h

/***********************\

 * pile_function.h     *
\***********************/

void initialisation (Pile * tas){
  tas->debut = NULL;
  tas->taille = 0;
}

/* empiler (ajouter) un élément dans la pile */
int empiler (Pile * tas, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);
  nouveau_element->suivant = tas->debut;
  tas->debut = nouveau_element;
  tas->taille++;
}

/* depiler (supprimer un élément de la pile */
int depiler (Pile * tas){
  Element *supp_element;
  if (tas->taille == 0)
    return -1;
  supp_element = tas->debut;
  tas->debut = tas->debut->suivant;
  free (supp_element->donnee);
  free (supp_element);
  tas->taille--;
  return 0;
}

/* affichage de la pile */
void affiche (Pile * tas){
  Element *courant;
  int i;
  courant = tas->debut;

  for(i=0;i<tas->taille;++i){
    printf("\t\t%s\n", courant->donnee);
    courant = courant->suivant;
  }
}

pile.c

/*********************\

 *      pile.c       *
\*********************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "pile.h"
#include "pile_function.h"

int main ()
{
  Pile *tas;
  char *nom;
  if ((tas = (Pile *) malloc (sizeof (Pile))) == NULL)
    return -1;
  if ((nom = (char *) malloc (50 * sizeof (char))) == NULL)
    return -1;
  initialisation (tas);

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  empiler (tas, nom);
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  empiler (tas, nom);
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  printf ("Entrez un mot : ");
  scanf ("%s", nom);
  empiler (tas, nom);
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  printf ("\nLe dernier entré (LastInFirstOut) [ %s ] sera supprimé",
                  pile_donnee(tas));
  printf ("\nLe dernier entré est supprime\n");
  depiler (tas);              /* suppression de dernier element entre */
  printf ("La pile (%d éléments): \n",tas->taille);
  printf("\n********** Haut de la PILE **********\n");
  affiche(tas);
  printf("__________ Bas de la PILE __________\n\n");

  return 0;
}

VI. Voir aussi

• les listes simplement chaînées
• les listes doublement chaînées
• les listes circulaires
• les files

Lire la suite

Compiler un programme en C avec Dev C++ sous Vista »

Il est très probable que vous ayez des problèmes lors de la compilation d'une source C sous Vista avec Dev C++.

Solution rapide de secours: le compilateur g++

Voici une astuce pour Dev-Cpp :

• Aller dans "Outils" -> "Options du compilateur" puis cliquez sur l'onglet "Programmes".
• Remplacer "gcc.exe" se trouvant dans la première case par "g++.exe".

Solution plus adaptée

L'utilisation de g++ pour un code en C n'est pas forcement le plus adapté. Voici donc une deuxième astuce :

• 1. Télécharger le programme "codeblock" sur cette page .
• 2. Télécharger Mingw et l'installer.
• 3. Télécharger ce fichier et le decompresser dans "c:\mingw".
• 4. Installer codeblock
• 5. Codeblock va automatiquement trouver Gcc
• 6. A vos projets =D

Merci à icare-ares pour ces deux astuces.

Lire la suite

Que fait un fork() ? »

...ou le petit fork() illustré....

Introduction

Un fork est une fonctionnalité sous les systèmes Unix ou Linux qui permet de dupliquer un processus.
Pour expliquer son fonctionnement, on va partir d'un processus qu'on appellera avec affection "Le Papa". Ce processus va simplement se dupliquer et les deux processus (le père et le fils) afficheront chacun leur statut (père ou fils).

Lancement du père

Nous allons partir d'un processus père. Afin de bien déterminer les enjeux du fork, on va également observer ses descripteurs de fichiers, ou plutôt l'un des plus importants: celui du flux de sortie (stdout) c'est-à-dire l'écran. On va aussi lui mettre une petite variable globale qui servira plus tard pour l'affichage du statut du processus (père ou fils).

Voici à quoi va ressembler notre processus de départ:



La flèche rouge pointe vers la prochaine instruction à exécuter. Comme on a encore rien exécuté, on en est au début du main. On va donc exécuter les deux premières instructions:



On peut voir en rouge les instructions qui ont été exécutées, ainsi que les données qui ont été modifiées par la dernière instruction. Jusqu'ici tout va bien, on a changé la valeur de quisuisje pour lui attribuer l'identité du père. Passons à l'instruction suivante.

Le fork

La prochaine instruction est la plus délicate à comprendre, exécutons-la et regardons ce qui se passe.



Le père a appelé fork et il s'est dupliqué. Cela implique plusieurs choses:

• Un nouveau processus a été créé, il est considéré comme le fils du processus qui a appelé fork()
• Ce processus est une copie conforme de son père. D'ailleurs, la prochaine instruction à exécuter sera la même pour les deux : la condition if.
• La fonction fork() ne retourne pas la même chose pour les deux processus. Pour le fils, il retournera 0. Pour le père, il retournera le pid du fils (son numéro de processus).
• Cette duplication implique certaines choses concernant les variables et les descripteurs de fichiers. Nous allons y venir.

Passons à l'instruction suivante pour les deux.

Maîtriser le fil d'exécution du père et celui du fils

Les deux processus viennent de vérifier la condition if. Etant donné que chez le père, la variable pid est différente de 0, il continuera dans le else. Par contre, le fils entrera dans le bloc du if car, pour lui, pid est égal à 0.

Important: C'est donc ainsi qu'on maîtrise le fil d'exécution du père et celui du fils: en vérifiant la valeur de la variable pid qui est différente pour les deux.

On continue.

Les variables et les descripteurs de fichiers

Attention ici c'est un point à ne pas manquer!

• Le fils a changé la valeur de sa variable quisuisje. Ceci a changé la valeur de sa propre variable quisuisje, mais pas celle du père. Voici donc notre première conclusion: les variables du père et celles du fils sont totalement distinctes ; même si elles portent le même nom, il ne s'agit pas des mêmes variables. En revanche, vous aurez remarqué qu'au moment du fork, le fils avait hérité des valeurs de toutes les variables de son père.
• Le père vient de faire un printf et a donc écrit "Je suis Le pere" sur le flux de sortie standard (stdout). Donc, après cette écriture, le pointeur du fichier stdout a avancé de 15 caractères (la longueur de la phrase affichée). Avez-vous remarqué qu'il en était de même chez le fils? En effet, si le père et le fils ont des variables distinctes, en revanche, leur descripteurs de fichiers sont les mêmes. Donc, si l'un des deux processus modifie son pointeur de position dans un fichier, ça se répercutera également chez l'autre. Attention, cela ne vaut que pour les descripteurs de fichiers hérités durant le fork. Si le père ou le fils ouvre d'autres fichiers après le fork, ces descripteurs ne seront pas partagés entre eux deux. De même, si le fils ferme un descripteur de fichier hérité du père, le descripteur de fichier du père ne sera par contre pas fermé (même chose dans le sens inverse).

La synchronisation

• Côté fils: un printf a été fait, cette fois pour afficher "Je suis Le fils". Le pointeur de fichier a donc avancé de 15 chez le fils, ce qui se répercute chez le père.
• Côté père: le père a exécuté la fonction wait(). Cette fonction permet la synchronisation entre le père et tous ses fils. Cela signifie que le père va arrêter de s'exécuter (dans ce cas on dit qu'il dort) jusqu'à ce que son fils se termine complètement.

La fin

Le fils vient d'exécuter sa dernière instruction ; à présent, il n'existe plus. Pendant ce temps-là, le père était encore en attente, mais il va bientôt se réveiller puisque le fils est terminé. Enfin, le père se terminera lui aussi.

Notes et remerciements

L'image qui précède le sommaire est une modification d'une photographie originale produite par tanakawho.

Lire la suite

La compilation et les modules en C et en C++ »

Cet article a pour vocation d'introduire les notions de bases de la compilation en C et en C++ et de la programmation modulaire.

Il permet de mieux comprendre les messages d'erreur du compilateur. Les notions abordées ici sont indépendantes du fait que l'on utilise windows ou linux. Toutefois on se placera plutôt dans le cadre de linux afin de voir plus en détail tout se qui se passe lors de la compilation d'un programme C ou C++.

Introduction

De manière générale, un compilateur a pour objectif de convertir un fichier texte (contenant un code source) en un fichier binaire (par exemple un exécutable). Une fois l'exécutable construit, on le lance comme n'importe quel programme. Ce programme peut se lancer sans que l'on dispose du code source.

Un langage compilé (comme le C ou le C++) est à opposer à un langage interprété (par exemple un script shell) ou pseudo-interprété (par exemple un programme python).

Dans le cadre du C, la compilation va transformer le code C d'un programme en code natif, à savoir une suite d'instructions binaires directement compréhensibles par le processeur.

Installation d'un compilateur C et C++

Sous linux

On utilise gcc et g++ en général. Pour l'installer on passe par son gestionnaire de paquet habituel. Par exemple sous debian (ou sous une distribution basée sur debian) il suffit de taper en root ou avec un sudo :

aptitude update
aptitude safe-upgrade
aptitude install gcc g++

On peut également installer de la même façon un environnement de développement comme par exemple kdevelop (sous KDE) ou anjuta (sous gnome).

Sous windows

On peut utiliser dev-cpp ou code::blocks: deux environnements de développement libres qui reposent sur gcc et g++ :
www.bloodshed.net
www.codeblocks.org

Article connexe : ou trouver un compilateur c c

Les phases de compilation

La première étape consiste à écrire le code source en langage C ou C++ (fichiers .c et .h en C et .cpp et .hpp en C++). Ensuite on lance une compilation, par exemple avec gcc (en C) ou g++ (en C++). La compilation (au sens vague du terme) se déroule en trois grandes phases.

1) La précompilation (préprocesseur)

Le compilateur commence par appliquer chaque instruction passée au préprocesseur (toutes les lignes qui commencent par un #, dont les #define). Ces instructions sont en fait très simples car elles ne consistent en gros qu'à recopier ou supprimer des sections de codes sans chercher à les compiler. C'est de la substitution de texte, ni plus ni moins.

C'est notamment à ce moment là que les #define présents dans un fichier source (.c ou .cpp) ou dans un header (.h ou .hpp) sont remplacés par du code C/C++. À l'issue de cette étape, il n'y a donc plus, pour le compilateur, d'instructions commençant par un #.

2) La compilation

Ensuite, le compilateur compile chaque fichier source (.c et .cpp), c'est-à-dire qu'il crée un fichier binaire (.o) par fichier source, excepté pour le fichier contenant la fonction main. Cette phase constitue la compilation proprement dite.

Ces deux premières étapes sont assurées par cc lorsqu'on utilise gcc/g++. Enfin le compilateur passe au fichier contenant le main.

3) Le linkage

Enfin, le compilateur agrège chaque fichier .o avec les éventuels fichiers binaires des librairies qui sont utilisées (fichiers .a et .so sous linux, fichiers .dll et .lib sous windows).

- Une librairie dynamique (.dll et .so) n'est pas recopiée dans l'exécutable final (ce qui signifie que le programme est plus petit et bénéficiera des mises à jour de ladite librairie). En contrepartie, la librairie doit être présente sur le système sur lequel tourne le programme.

- Une librairie statique (.a) est recopiée dans l'exécutable final ce qui fait que celui-ci est complètement indépendant des librairies installées du le système sur lequel il sera recopié. En contrepartie, l'exécutable est plus gros, il ne bénéficie pas des mises à jour de cette librairie etc...

Le linker vérifie en particulier que chaque fonction appelée dans le programme n'est pas seulement déclarée (ceci est fait lors de la compilation) mais aussi implémentée (chose qu'il n'avait pas vérifié à ce stade). Il vérifie aussi qu'une fonction n'est pas implémentée dans plusieurs fichiers .o.

Cette phase, appelée aussi édition de lien, constitue la phase finale pour obtenir un exécutable (noté .exe sous windows, en général pas d'extension sous linux).

Cette étape est assurée par ld lorsqu'on utilise gcc/g++.

Warnings et erreurs

Évidemment, dans un environnement de développement, il suffit de cliquer sur "build" et ces trois phases se déroulent de manière transparente. Toutefois, il est important de les avoir en tête pour interpréter correctement les messages d'erreur ou de warning d'un compilateur lorsqu'il y en a.

Je rappelle qu'un warning signifie que le code est ambigu et que le code peut être interprété différemment d'un compilateur à l'autre, mais l'exécutable peut être créé.

A contrario, une erreur signifie que le code n'a pas pu être compilé complètement et que l'exécutable n'a pas pu être (re)créé. Si un code peut compiler avec des warnings et doit compiler sans erreurs, il vaut mieux essayer de coder de sorte à n'avoir ni erreur, ni warning.

Les grandes étapes pour écrire un programme en C ou en C++

Écrire le code source

Un simple bloc note peut suffire, par exemple on peut écrire dans le fichier plop.c :

#include <stdio.h>

int main(){
    printf("plop !\n");
    return 0;
}

Compiler

Ici je suis sous linux donc j'appelle directement gcc (-W et -Wall permettent d'afficher plus de messages pour vérifier si le code est propre, le -o plop.exe permet de dire que l'exécutable à créer doit s'appeler plop.exe) :

gcc -W -Wall -o plop.exe plop.c

Implicitement le compilateur fait les trois étapes que j'ai décrites juste avant.

1) Précompilation

/* Tout ce qui est défini par <stdio.h>, y compris printf() */

int main(){
    printf("plop !\n");
    return 0;
}

2) Compilation (il trouve bien le printf car celui-ci est déclaré dans <stdio.h>)
3) Édition de lien (il trouve bien le printf dans le binaire de la lib c). On peut d'ailleurs le vérifier sous linux avec ldd :

ldd plop.exe

.. qui donne :

        linux-gate.so.1 =>  (0xb7f2b000)
        libc.so.6 => /lib/i686/cmov/libc.so.6 (0xb7dbb000)
        /lib/ld-linux.so.2 (0xb7f2c000)

Sur la deuxième ligne on voit bien qu'il utilise la lib c. Puis il crée plop.exe. On vérifie en outre qu'il n'y a ni erreur, ni warning.

Exécution

Il ne reste plus qu'à le lancer :

./plop.exe

... ce qui donne comme espéré :

plop !

Si une erreur se produit à ce moment là (erreur de segmentation, pas assez de mémoire etc...) il faut souvent recourir à un debuggeur (par exemple gdb ou ddd), revoir le code source etc... Dans tous les cas, ce n'est pas un problème de compilation.

Article connexe : langage c c c erreur de segmentation

Attention, gros piège sous windows

Pour exécuter un programme sous windows, deux méthodes sont possibles.

Méthode 1 : On peut lancer un programme via les commandes ms-dos (en cliquant sur démarrer exécuter et en tapant "cmd"). On se place ensuite dans le bon répertoire avec la commande cd et on lance le programme. Dans ce cas tout se passera bien.

Méthode 2 : Si on lance le programme depuis l'explorateur, windows lance les commandes ms-dos, qui lance le programme, celui-ci se termine, rend la main aux commandes ms-dos, et windows ferme les commandes ms-dos. Concrètement on n'a alors rien le temps de voir. Il faut donc mettre une "pause" juste avant la fin du programme si on veut lancer ton exécutable de cette manière :

#include <stdio.h>

int main(){
    printf("plop !\n");

    getchar(); /* le programme n'avance plus tant qu'on appuie pas sur une touche */
    return 0;
}

Les erreurs classiques

Erreur de compilation

Supposons que mon code source oublie d'inclure le fichier <stdio.h> (dans lequel est déclarée la fonction printf), ou un ";", j'aurai alors un message d'erreur de compilation (syntax error, parse error...). Ce sont les erreurs les plus classiques.

Erreur de linkage

Ces erreurs sont plus subtiles, car elles ne concernent pas la syntaxe, mais la manière dont est structuré et compilé le programme. Elles sont faciles à reconnaître quand on utilise gcc ou g++ puisque les messages d'erreurs correspondant parlent de ld (le linker).

Premier exemple : mutlidéfinition

Une erreur de linkage peut survenir dès que l'on écrit le code d'un programme à l'aide de plusieurs fichiers. Nous allons à présent illustrer ce genre d'erreur.

Supposons que mon programme est écrit au travers de 3 fichiers : a.h, a.c, et main.c. Le header a.h est inclu par les deux fichiers source main.c et a.c. Le fichier main.c contient la fonction main().

1) Si je compile juste a.c, le fichier de contenant pas de main, il faut le préciser au compilateur (option -c dans gcc) sinon celui-ci ne sait pas comment créer un exécutable, vu qu'il n'y a pas de point de départ. C'est pourquoi le fichier contenant le main (pas d'option -c) et les autres fichiers sources se compilent différemment. En l'occurrence :

gcc -W -Wall -c a.c
gcc -W -Wall -o plop.exe main.c a.o

Les options -W et -Wall permettent d'afficher plus de messages de warning.
- La première commande construit a.o à partir de a.c.
- La seconde génère le binaire associé à main.c, l'assemble avec a.o, et produit ainsi un exécutable (plop.exe)

On voit tout de suite que si le programme comporte une erreur dans a.c, le compilateur déclenchera une erreur au moment de compiler a.c. Ceci provoquera des erreurs en cascade dans les autres fichiers. C'est pourquoi lorsqu'un programme ne compile pas, on commence par les premiers messages d'erreurs, on les résout, on recompile etc... jusqu'à ce que toutes les erreurs soient résolues.

2) Rappelons qu'en temps normal, on déclare la fonction dans le header (par exemple a.h) :

void plop();

... et qu'on l'implémente dans le fichier source (par exemple a.c) :

#include "a.h"
#include <stdio.h>

void plop(){
  printf("plop !\n");
}

Supposons à présent que j'implémente la fonction plop() dans a.h (c'est à dire que la fonction n'est pas juste déclarée dans a.h). En d'autre termes, le fichier a.h contient

#include <stdio.h>

void plop(){
  printf("plop !\n");
}

... et le fichier a.c contient par exemple :

#include "a.h"

void f(){
  plop();
}

Le fichier a.h est inclu par main.c et a.c. Ainsi le contenu de a.h est recopié dans a.c et dans main.c. Ainsi, ces deux fichiers sources disposeront chacun d'une implémentation de la fonction plop() (la même certes !), mais le compilateur ne saura pas laquelle prendre et déclenchera une erreur de multi définition au moment du linkage:

(mando@aldur) (~) $ gcc -W -Wall main.c a.o
a.o: In function `plop':
a.c:(.text+0x0): multiple definition of `plop'
/tmp/ccmRKAvQ.o:main.c:(.text+0x0): first defined here
collect2: ld returned 1 exit status

Ceci justifie pourquoi l'implémentation d'une fonction doit se faire en général dans un fichier source (.c ou .cpp) et non dans un header (.h et .hpp). On retiendra juste deux exceptions à cette règle en C++ : les fonctions inline et les fonctions templates (ou les méthodes d'une classe template). Pour plus de détails on pourra se référer à ces deux articles :
http://www.commentcamarche.net/faq/sujet 11194 les templates en c
http://www.commentcamarche.net/faq/sujet 11250 les inlines en c

Programmation modulaire : multi définitions, boucles d'inclusion...

Supposons que j'ai 3 fichiers : main.c et les fichiers a.h, et b.h. Supposons que a.h et b.h s'incluent mutuellement. Ces deux fichiers s'incluent mutuellement indéfiniment ! C'est là que le pré compilateur vient à notre secours, car on va pouvoir éviter que les #include ne se fassent indéfiniment en mettant dans a.h :

#ifndef A_H
#define A_H
#include "b.h"
/* Le contenu du header a.h */

#endif

et dans b.h :

#ifndef B_H
#define B_H
#include "a.h"
/* Le contenu du header b.h */

#endif

Que va-t'il se passer concrètement ? Le compilateur va commencer par un fichier (par exemple a.h). Comme à ce stade A_H n'est pas défini, il avance, puis il définit a.h et continue à lire le header a.h, en incluant b.h. À ce stade B_H n'est pas défini, donc de la même façon on rentre dans le header b.h et on active A_H.

On lit à présent le contenu de b.h qui veut inclure a.h. On rentre à nouveau dans a.h mais cette fois-ci, A_H est défini donc on ignore le contenu du header. On finit de lire le header b.h, ce qui résout le #include "b.h" que l'on était en train de traiter dans a.h. Puis on termine le header b.h.

Ce cas peut paraître tordu, mais il faut bien voir que lorsqu'un header est inclus plusieurs fois, des multidéfinitions peuvent apparaître (en particulier si des structures sont déclarées dans les headers). C'est pourquoi on met systématiquement ce mécanisme de verrou dans tous les headers.

Fonction déclarée ... mais pas trouvée

Si une fonction est déclarée, utilisée, mais pas implémentée, une erreur de linkage se produit également. Ceci survient typiquement dans deux cas :
- on a déclaré une fonction mais on ne l'a pas encore implémentée
- on veut utiliser une fonction d'une librairie, on a correctement inclu les headers correspondant, mais on a oublié de passer en paramètre du compilateur lesdites librairies.

Plus loin avec la compilation : makefile

Si un environnement de développement permet au travers d'un "nouveau projet" de gérer ton code de sorte à le compiler entièrement, tu te doutes qu'il doit compiler chaque fichier .c et assembler le tout. Lorsqu'on ne dispose pas d'environnement de développement, afin d'éviter de taper manuellement un "gcc" par fichier source, on fait un fichier "makefile" qui s'occupe de décrire comment construire l'exécutable.

En pratique, on est sensé en écrire un en plus de tes fichiers C/C++ afin que le code soit simple à compiler. En effet, si ce fichier est correctement écrit, il suffit de lancer le makefile pour construire intégralement le programme. Sous linux on tape alors simplement la commande :

make

Lire la suite

Les ressources en langage C/C++ »

-->

1. Principe

Les ressources peuvent souvent s'avérer utiles pour la version finale d'un programme, ou avant. Cela consiste à stocker des images, des fonds, des curseurs, des dll ou même un autre programme dans le programme lui même, dans le même dossier ou sous-dossiers.
Cela aura pour conséquence de rendre plus clair le dossier où se situe le programme, mais cela alourdira inévitablement l'exécutable.

 

2. Utilisation

2.1 Utilisation normale

Pour utiliser les ressources avec le langage C/C++, il faut créer un fichier d'extension ".rc", et le placer dans le même dossier que les autres fichiers du projet.

Exemple : contenu dossier "jeu" avec codeblocks :

• Fichiers sources
  • main.c
  • functions.c
• Fichiers headers
  • headers.h
  • globalesVar.h
• Fichier ressources
  • res.rc
• Autres
  • jeu.layout
  • jeu.depend
  • jeu.cdp

Le fichier se trouve donc dans le même dossier que les autres fichiers.
Dans un fichier ressource, il doit y avoir un seul fichier joint par ligne, et une ligne doit commencer par un numéro.

Exemple :

ICON "icone.ico"
RCDATA "autreProgramme.exe"

Attention : Si un fichier se trouve dans un sous-dossier, il faut indiquer ce sous-dossier :

1 ICON "icones/icone.ico"

 

2.2 Utilisation avec Qt

L'utilisation des ressources peut aussi être utile avec Qt, en C++. Ici, le principe n'est pas le même. Les ressources ne se trouveront pas dans un fichier avec pour extension ".rc", mais avec une extension ".qrc".
Il doit être indiqué au fichier ".pro" dans la partie #Input, de cette manière :

#input

RESOURCES += res.qrc

Voici la structure que doit avoir votre fichier ".qrc" :

<RCC>
          <qresource>
                    <file>icone.ico</file>
                    <file>saveIcone.ico</file>
                    <file>quitterIcone.ico</file>
          </qresource>
</RCC>

Cela se rapproche de la syntaxe du langage HTML. Les fichiers à intégrer se trouvent entre les balises "<file>" et "</file>".

 

3. Mots-clés

La liste des mots-clés des fichiers ressources se trouve sur le site de la msdn, ici .



Merci à ozox pour cette astuce.