Le langage C

Base de donnée: Table de hachage (suite)



Par :

Guilhem de Wailly (gdw@erian-concept.com)



Résumé

Dans cette série d'articles, nous présentons le langage C. Il ne s'agit pas de réécrire les ouvrages de référence donnés en annexe, mais de donner, au travers du C, une méthode de programmation basée sur la notion d'interface.

Au fur et à mesure de notre progression, nous décrirons les éléments indispensables du langage et conduirons le lecteur à consulter les ouvrages de références. Le but poursuivi est clairement de parvenir à construire des programmes de manière segmentée.

Ce mois-ci, nous allons nous continuer à nous intéresser aux tables de hachage réalisées en C. Nous avons déjà pu aborder ce sujet avec le langage Scheme dans le numéro 6 de Linux Magazine. Cette réalisation permettra de réaliser de petites bases de données.

Cette description sera aussi le prétexte pour aborder certains points nouveaux du langage C.

Remerciement

De nombreux lecteurs m'ont contacté par email pour signaler certaines erreurs ou améliorations des bibliothèques décrites dans les numéros précédents.

Je n'ai malheureusement pas eu beaucoup de temps pour leur répondre et je les prie de m'en excuser.

Je les remercie vivement de leur intérêt et de leurs encouragements.

Description

Ce mois-ci, nous allons terminer la réalisation de la bibliothèque pour créer une table de hachage. Cette présentation commencée il y a deux numéros est aussi le prétexte pour aborder l'arithmétique des pointeurs, les entrées / sorties en C et la manipulation des données.

Les tables de hachage sont des structures très utilisées pour réaliser de petites bases de données. En effet, elles sont assez faciles à réaliser tout en restant assez efficaces. Les tables de hachage restent utilisables jusqu'à 500 000 enregistrements ; au-delà, on utilisera des structures plus complexes comme les b-arbres.

Le principe des tables de hachages est d'associer un identificateur à une donnée dans une structure, en permettant de retrouver la donnée rapidement, en connaissant l'identificateur. Elles sont réalisées à l'aide d'un tableau de taille fixe contenant des listes associant les identificateurs et les données.

Par rapport à l'article traitant des listes à double chainage où les données étaient stockées par leur pointeur, cette bibliothèque duplique le contenu de la donnée dans la table. Cela ralenti un peu les traitements, mais permet de sauver la table sur le disque.

Les sources de la bibliothèque sont disponibles à l'adresse:

http://www.erian-concept.com/pub/hash.tgz

La dernière fois, nous avons présenté l'interface de la bibliothèque et la manière de l'utiliser. Ce mois-ci, nous allons réaliser le corps de la bibliothèque. Rappelons le contenu de cette interface.

Interface

Nous avons donc :

#ifndef ___HASH_H
#define ___HASH_H

/* TYPES DE DONNEES */
/* Table de hachage */
typedef struct Hash * Hash;

/* codes de retour */
typedef enum {
  HASH_OK,         /* pas d'erreur */
  HASH_ERREUR,     /* erreur indéfinie */
  HASH_DOUBLON,    /* existe déjà */
  HASH_INTROUVABLE /* n'existe pas */
} HashStatus;

/* PROTOTYPES DES FONCTIONS */
Hash       hash_cree    (int    taille_table,
                         int    taille_ident);
HashStatus hash_detruit (Hash   hash_table);
HashStatus hash_ajoute  (Hash   hash_table,
                         char * identificateur,
                         void * donnee,
                         int    taille_donnee);
HashStatus hash_enleve  (Hash   hash_table,
                         char * identificateur);
int        hash_taille  (Hash   hash_table,
                         char * identificateur);
HashStatus hash_donne   (Hash   hash_table,
                         char * identificateur,
                         void * donnee,
                         int  * taille_donnee);
HashStatus hash_tous    (Hash   hash_table,
                         void * paramètre,
                         int (* proc) (void * parametre,
                                       char * identificateur,
                                       void * donnee,
                                       int    taille_donnee));
HashStatus hash_sauve   (Hash   hash_table,
                         char * fichier);
Hash       hash_charge  (char * fichier);

#endif /* ___HASH_H */

Le lecteur se référera au numéro précédent traitant de ce sujet pour obtenir plus d'explications.

Réalisation

L'interface de la bibliothèque est notre guide pour mener sa réalisation.

Types de données

Nous commençons donc par défnir les types de données déclarés dans l'interface, ainsi que les types de données ``privés'' au fichier de réalisation :

#define ___HASH_C


/* ENTETES */

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


/* DEFINITION DES TYPES DE DONNEE */

/* cellule */
typedef struct Cellule * Cellule;

typedef struct Cellule {
  /* La cellule suivante dans la liste */
 Cellule suivante;
  /* L'identificateur de la callule */
 char * identificateur;
  /* La taille de la donnée pointée par la callule */
 int taille_donnee;
  /* Le pointeur vers la donnée */
 void * donnee;
} _Cellule;

/* table de hashage */
typedef struct Hash {
  /* Nombre de listes de cellules de la table */
 int taille_table;
  /* Taille des identificateurs */
 int taille_identificateur;
  /* Tableau de listes de cellule */
 Cellule * table;
} _Hash;

Le type de donnée Cellule n'est pas visible depuis l'extérieur de ce fichier. Chaque entrée d'une table de hachage sera rangée dans une cellule qui contient un pointeur vers la cellule suivante (la table de hachage est une liste de cellules), d'un pointeur vers l'identificateur de la cellule, la taille de la donnée associée à la cellule et enfin un pointeur vers la donnée. Nous verrons qu'une astuce dans la gestion de la mémoire nous permettra d'appeler la fonction d'allocation qu'une seule fois pour la cellule, son identificateur et sa donnée. Nous remarquons aussi que le mot Cellule doit être défini avant son utilisation à l'intérieur de la structure (champs suivante), sans quoi le compilateur provoquerait une erreur.

Nous trouvons ensuite la définition du type de donnée publique struct Hash déclaré dans hash.h. C'est une structure de donnée contenant la taille de la table de listes de cellules, la taille des identificateurs et la liste de cellules déclarée comme un pointeur vers une cellule.

Fonctions locales

Dans tous les programmes en C que nous avons écrits dans ces colones, les fonctions étaient ``visibles'' dans tous les fichiers. En effet, si dans un fichier a.c nous écrivons:

int fonction (int argument) {
  /* corps de la fonction */
}

nous définissons une fonction fonction. Cette fonction est connue du compilateur dans tout le texte qui suit sa définition. Nous avons appris que si nous voulons utiliser cette fonction dans un autre fichier, mettons b.c, nous devons la déclarer avec :

int fonction (int);

De cette manière, le compilateur ``connaît'' le prototype de la fonction fonction et il est capable de vérifier la validité des appels qui y sont fait.

Mais cela semble ne concerner que le compilateur : en effet, si nous omettons la déclaration dans b.c, nous pouvons quand même appeler la fonction fonction. Plus encore, nous pouvons l'appeler avec des arguments de types différents, comme un caractère, ou un réel. On peut même l'appeler avec plusieurs arguments : le compilateur ne bronche pas ! La raison est que comme il ne connaît pas la fonction fonction (pas de déclaration), il ne peut rien vérifier. Bien qu'inconnue dans le deuxième fichier, la fonction fonction reste utilisable et la fabrication du binaire peut se faire sans erreur. On en déduit que fonction est visible dans tous les fichiers composant le binaire.

Sans autres spécifications, toute variable et toute fonction C sont visibles dans tous les fichiers sources qui composent le programme. Pour pouvoir les utiliser, il faut déclarer les fonctions (prototype) et déclarer les variables en rajoutant le mot clef extern devant la déclaration.

Ainsi, on a le fichier a.c :

/* Variable globale */
int variable;

/* Fonction globales */
int fonction (int argument) {
 return (variable + argument);
}

et le fichier b.c :

/* Variable externe */
extern int variable;

/* Fonction externe */
int fonction (int);

void main (void) {
  variable = 123;
 fonction (456);
}

La fabrication du binaire ne provoque pas d'erreur. Nous aurions aussi pu déclarer la fonction par :

extern int fonction (int);

Le fait que les variables et les fonctions sont par défaut partagées par tous les fichiers d'un projet est gênant. Le premier problème est les confits de noms que cela peut entraîner : en effet, tous les noms globaux (fonction et variables globales) doivent être uniques dans un projet. Par exemple, si nous définissons une fonction nommée fonction dans le fichier b.c ci-dessus, la fabrication du binaire provoquera une erreur. Le second problème inhérent du premier est qu'il est nécessaire de placer un préfix devant tous les noms globaux pour préserver leur unicité,c'est compliqué et lourd à gérer.

Heureusement, le langage C permet de maintenir une définition locale au fichier qui la contient. Cela se fait simplement en plaçant le mot clef static devant la définition. Si la fichier a.c devient :

/* Variable globale */
static int variable;

/* Fonction globales */
static int fonction (int argument) {
 return (variable + argument);
}

la compilation de a.c et b.c provoquera des erreurs (et sans doute des messages d'avertissements).

Les variables statiques ne peuvent être initialisées que par des valeurs que le compilateur peut calculer lui-même comme des constantes, ou des opérations arithmétiques ou booléennes sur des constantes. Les variables statiques non initialisées sont initialisées par défaut à zéro.

Le langage C a même prévu d'autoriser la définition d'une variable statique à l'intérieur d'une fonction :

int compteur () {
 static int n = 0;

  return (++n);
}

Dans cette écriture, la variable n n'est visible que dans le corps de la fonction compteur, sous sa définition. De plus, elle garde sa valeur entre chaque appel à la fonction compteur. Si nous supprimons le mot clef static, n vaudra toujours zero, et donc la valeur retournée sera toujours 1.

Dans le cadre du projet, nous définissons une fonction locale :

/* FONCTION LOCALES */

/* Calcule l'index dans la table de la
 * liste de cellules pour l'identificateur
 * donné en argument.
*/
static int _calcul_index (int taille_table,
                         char * identificateur) {
int somme = 0;

/* Vérification des arguments. */
assert (taille_table);
assert (identificateur);

/* Ajouter les valeurs ASCII de tous les
* caractères de l'identificateur.
*/
while (* identificateur) {
somme += (int) * identificateur;
identificateur ++;
}
/* Retourner la somme des valeurs ASCII modulo
* la taille de la table.
*/
return (somme % taille_table);
}

Etant donnée une chaîne de caractères représentant l'identificateur et la taille de la table, fixée une fois pour toute lors de sa création, cette fonction retourne l'index de la liste de cellule correspondante. Cet index est obtenu en calculant la somme des valeurs ASCII des caractères de l'identificateur jusqu'à ce que la valeur nulle soit rencontrée et en calculant le modulo de la somme ainsi trouvée.

Nous rappelons qu'une chaîne de caractère est en C, un tableau de caractères dont le dernier est le caractère nul. On appelle souvent cette forme de codage l'ASCIIZ.

Nous trouvons aussi une nouvelle écriture appelée cast. Le cast permet de convertir explicitement le type d'une valeur. Il s'écrit en plaçant le nouveau type entre parenthèses devant l'expression à convertir. Ici, nous souhaitons convertir le caractère * identificateur en entier ; pour cela, nous plaçons (int) devant.

Le compilateur est capable d'effectuer des casts implicites. Par exemple l'écriture :

int a = 4 + 1.234;

est castée par le compilateur en :

int a = (int) ((float) 4 + 1.234);

Dans ce genre de cast, le compilateur tente de convertir les données dans le type de plus haut niveau des opérandes, puis le résultat dans le type attendu.

En général, préciser explicitement les conversions facilite la maintenance des programmes car elle indique explicitement que le programmeur a conscience des différences de type.

Création d'une table

Une table de hachage est une structure de donnée contenant différents champs. Cette structure est allouée dynamiquement par sa fonction de création :

/* Création d'une hash table vide. */
Hash hash_cree (int taille_table,
int taille_identificateur) {
Hash hash_table;

/* Vérification des arguments. */
assert (taille_identificateur > 0);
assert (taille_table > 0);

/* Création de la table. */
hash_table = malloc (sizeof (_Hash));
if (! hash_table) return (0);

/* Initialisation de la table. */
hash_table->taille_table = taille_table;
hash_table->taille_identificateur
     = taille_identificateur;
hash_table->table = calloc (taille_table,
sizeof (Cellule));
if (! hash_table->table) {
free (hash_table);
return (0);
}
return (hash_table);
}

Cette fonction ne présente pas de difficultés. La seule chose que nous n'avons pas vue est la fonction calloc. Elle prend deux arguments, un nombre d'éléments et la taille de chaque élément. Elle alloue dynamiquement un espace mémoire capable d'accueillir un tel tableau, l'initialise à zéro et retourne l'adresse de ce tableau, ou zéro si le tableau ne peut pas être alloué. La fonction calloc pourrait être définie par :

void * calloc (int n, int i) {
  void * adresse = malloc (n * i);

  if (adresse) memset (adresse, 0, n * i);
  return (adresse);
}

Notons que la structure aurait pu comporter un nombre magique permettant de renforcer le contrôle des arguments.

Destruction d'une table

La fonction de destruction d'une table se contente de libérer les zones de mémoire allouées dans la fonction de création :

/* Destruction d'une table. */
HashStatus hash_detruit (Hash hash_table) {
/* Vérification des arguments. */
assert (hash_table);

/* Désallocation de la table. */
free (hash_table->table);
free (hash_table);

return (HASH_OK);
}

Ajout d'un élément

La fonction d'ajout d'un élément ajoute une cellule reliant l'identificateur et la donnée à la liste de cellule de la table donnée par un index calculé en fonction de l'identificateur. A priori, cette fonction doit réaliser trois allocations, une pour la cellule, une pour l'identificateur et une pour la donnée. Nous l'avons optimisé de manière à ne réaliser qu'une seule allocation :

/* Ajoute une entrée dans la hash table.
 * La taille de la donne est variable. La
 * longueur de l'identificateur est fixée
 * à la création de la table.
*/
HashStatus hash_ajoute (Hash hash_table,
char * identificateur,
void * donnee,
int taille_donnee) {
Cellule cellule;
int index;

/* Vérifications des arguments .
* Actif que lorsque la macro NDEBUG
   * n'est pas définie.
*/
assert (hash_table);
assert (identificateur);
assert ( strlen (identificateur)
<= hash_table->taille_identificateur);
assert (donnee);
assert (taille_donnee > 0);

if (hash_taille (hash_table, identificateur) > 0)
return (HASH_DOUBLON);

/* Création d'une cellule. */
cellule = malloc ( sizeof (_Cellule)
+ hash_table->taille_identificateur
+ 1
+ taille_donnee);
if (! cellule) return (HASH_ERREUR);

/* Initialisation de la cellule.
* Le format des cellule est le suivant:
*
* CELLULE
* +-----------------+
* | suivante -------|----->...
* | identificateur -|--
* | taille_donnee | |
* | donnee ---------|--|--
* |.................| | |
* | |<- |
* | IDENTIFICATEUR | |
* | | |
* |.................| |
* | |<----
* | |
* | DONNEE |
* | |
* | |
* +-----------------+
*
   */
cellule->identificateur = ((char *) cellule)
 + sizeof (_Cellule);
cellule->taille_donnee = taille_donnee;
cellule->donnee = ((char *) cellule)
+ sizeof (_Cellule)
+ hash_table->taille_identificateur
+ 1;
strcpy (cellule->identificateur, identificateur);
memcpy (cellule->donnee, donnee, taille_donnee);

/* Ajout de la cellule dans la table. */
index = _calcul_index (hash_table->taille_table,
identificateur);
cellule->suivante = hash_table->table[index];
if (hash_table->table[index]) {
hash_table->table[index]->suivante = cellule;
  }
else {
hash_table->table[index] = cellule;
  }
return (HASH_OK);
}

Le principe utilisé pour réduire le nombre d'allocation est d'allouer une cellule dont la taille dépasse la taille de la structure ; ensuite, nous initialisons les pointeurs de la structure vers la zone supplémentaire. Pour obtenir l'adresse des zones supplémentaires, nous convertissons par un cast l'adresse de la cellule en adresse vers des caractères. Dans le cas de l'identificateur, nous additionnons à cette adresse la taille de la structure. Dans le cas de la donnée, nous additionnons cette adresse à la taille de la structure et la longueur de l'identificateur plus un (ne pas oublier le zéro qui termine les chaînes de caractères).

Il ne nous reste qu'à remplir les deux zones pointées par leur valeur. Dans le cas de l'identificateur, nous utilisons la fonction standard strcpy (destination, source) qui recopie la chaîne ASCIIZ source à l'adresse destination. Dans le cas de la zone, nous utilisons la fonction standard memcpy (destination, source, nombe) qui recopie nombre octets de source vers destination.

Par la suite, nous intégrons la nouvelle cellule dans la liste des cellules de la table correspondantes à l'index calculé à partir de l'identificateur.

En utilisant cette technique, nous réduisons considérablement le nombre d'allocations nécessaires à la création d'une cellule, ce qui se traduit immédiatement par un gain significatif en performances et réduit la fragmentation de la mémoire.

Le langage C est l'un des seuls langages de haut niveau permettant d'effectuer ce genre de manipulations. Bien entendu, ce gain de liberté se traduit par une augmentation des risques d'erreurs, comme c'est souvent le cas : plus le langage laisse de liberté au programmeur, plus celui-ci doit avoir une attitude responsable et programmer ``proprement''. On retrouve un peu cela avec des langages permissifs comme le langage Scheme.

Taille d'un élément

Cette fonction retourne la taille de la donnée associée à l'identificateur passé en argument ; pour cela, elle effectue une recherche dans la hash-table. Par convention, si l'identificateur n'est pas trouvé, elle retourne -1 :

/* Retourne la taille d'une cellule. */
int hash_taille (Hash hash_table,
char * identificateur) {
Cellule cellule;
int index;

/* Vérification des arguments. */
assert (hash_table);
assert (identificateur);

/* Calcule de l'index */
index = _calcul_index (hash_table->taille_table,
identificateur);
cellule = hash_table->table[index];

/* Pour toutes les cellules de la liste. */
while (cellule) {
/* Si les identificateurs sont identiques,
* bingo!
*/
if (! strcmp (identificateur,
cellule->identificateur)) {
return (cellule->taille_donnee);
}
/* Sinon, continuer... */
cellule = cellule->suivante;
}
return (-1);
}

La recherche commence par le calcul de l'index correspondant à l'identificateur. Cela nous permet d'obtenir l'adresse de la première cellule de la table. Tant que l'adresse n'est pas nulle, nous comparons l'identificateur donné en argument et l'identificateur de la cellule avec la fonction standard strcmp. Cette fonction retourne zéro si les deux chaînes de caractères ASCIIZ sont identiques : dans ce cas, on retourne la taille de la donnée. Dans le cas contraire, on continue les tests avec la cellule suivante.

Cette fonction pourra être utilisée par l'utilisateur de la bibliothèque pour allouer exactement l'espace en mémoire capable d'accueillir la donnée, avant d'invoquer la fonction suivante.

Récupération d'un élément

La fonction de récupération des données fonctionne un peu comme la fonction précédente. On lui donne en argument une hash table, un identificateur, un pointeur vers une zone capable d'accueillir la donnée et un pointeur sur un entier qui contiendra la taille de la donnée. Le pointeur sur la donnée et le pointeur sur la taille peuvent, par convention, être nuls ; dans ce cas ils seront ignorés.

Elle est bâtie autour d'une boucle recherchant la cellule ayant même identificateur que celui donné en argument :

/* Retourne le contenu d'une cellule. */
HashStatus hash_donne (Hash hash_table,
char * identificateur,
void * donnee,
int * taille_donnee) {
Cellule cellule;
int index;

/* Vérification des arguments. */
assert (hash_table);
assert (identificateur);

/* Calcul de l'index. */
index = _calcul_index (hash_table->taille_table,
identificateur);
cellule = hash_table->table[index];

/* Pour toutes les cellules. */
while (cellule) {
/* Si les identificateurs sont identiques,
* Jackpot!
*/
if (! strcmp (identificateur,
cellule->identificateur)) {
/* Retourner à l'utilisateur ce qui
       * désire.
       */
if (taille_donnee) {
* taille_donnee = cellule->taille_donnee;
}
if (donnee) {
memcpy (donnee,
cellule->donnee,
cellule->taille_donnee);
}
return (HASH_OK);
}
/* Sinon, continuer ... */
cellule = cellule->suivante;
}
return (HASH_INTROUVABLE);
}

Suppression d'un élément

La fonction suivante supprime de la table une association identificateur-donnée :

/* Suppression d'une cellule. */
HashStatus hash_enleve (Hash hash_table,
char * identificateur) {
Cellule cellule, precedente;
int index;

/* Vérification des arguments. */
assert (hash_table);
assert (identificateur);

/* Calcule de l'index. */
index = _calcul_index (hash_table->taille_table,
identificateur);

/* Parcours de la liste de cellules. */
cellule = hash_table->table[index];
precedente = 0;
while (cellule) {
/* Comparaison des identificateurs. */
if (! strcmp (identificateur,
cellule->identificateur)) {
/* Mise à jour des liens. */
if (precedente) {
precedente->suivante = cellule->suivante;
}
else {
hash_table->table[index] = cellule->suivante;
}
/* Destruction de la cellule. */
free (cellule);
return (HASH_OK);
}
/* Sinon, continuer ... */
precedente = cellule;
cellule = cellule->suivante;
}
return (HASH_INTROUVABLE);
}

Cette fonction commence par rechercher la cellule à supprimer. Par rapport aux fonctions de recherche vues précédemment, elle maintient un pointeur vers la cellule précédente qui sera utilisé pour mettre à jour la liste de cellules correspondantes : s'il existe une cellule précédente, son lien de chaînage est modifié ; sinon, la table est mise à jour.

Parcourt de tous les éléments

Cette fonction permet d'appeler une fonction passée en argument avec toutes les cellules de la table. Par convention, si cette fonction retourne une valeur nulle, le parcours est interrompu et une erreur est retournée :

/* Applique à toutes les cellules la fonction
 * passée en argument.
*/
HashStatus hash_tous
            (Hash hash_table,
void * parametre,
int (* proc) (void * parametre,
char * identificateur,
void * donnee,
int taille_donnee)) {
int index;

/* Vérification des arguments. */
assert (hash_table);
assert (proc);

/* Pour toutes les listes de la table. */
for (index = 0;
index < hash_table->taille_table;
index++) {
Cellule cellule = hash_table->table[index];

/* Pour toutes les cellules de la liste. */
while (cellule) {
/* Appliquer la fonction. Par convention,
       * si elle retourne zéro, interrompre le
       * parcours.
*/
if (! proc (parametre,
cellule->identificateur,
cellule->donnee,
cellule->taille_donnee)) {
return (HASH_ERREUR);
}
/* Sinon, continuer */
cellule = cellule->suivante;
}
}
return (HASH_OK);
}

La seule difficulté potentielle est la déclaration de l'argument concernant la fonction. Cela s'écrit comme le prototype d'une fonction, en plaçant le nom de la fonction entre parenthèses avec une étoile devant : cela indique ``pointeur sur fonction''. Dans l'absolu, on devrait invoquer cette fonction passée en argument avec (* proc) (...), mais le compilateur comprend tout à fait proc (...). Le langage C ne considère pas les fonctions comme des objets comme les autres (appelés objets de première classe) ; elles ont droit à un traitement spécial dans le compilateur, ce qui explique ces incohérences mineures. Il y a d'autres endroits où le langage C présente certaines incohérences et nous les mettrons en évidences lorsque nous les rencontrerons. Le lecteur pourra comparer le langage C et le langage Scheme ou tous les objets sont de première classe, ce qui présente une cohérence hors du commun.

Le paramètre passé à la fonction de parcours permet à l'utilisateur d'éviter d'utiliser des variables globales pour garder un état lors du parcours. Nous le mettrons en évidence la prochaine fois, lorsque nous parlerons des fonctions d'entrée/sorties sur disque pemettant de sauver et lire une table de hachage sur disque.

Critique

Notre bibliothèque présente certaines caractéristiques intéressantes, comme la possibilité de ranger des données de toutes tailles. Nous pourrions l'étendre en permettant aux identificateurs d'avoir eux aussi une taille variable, non limitée à une valeur maximale, comme c'est le cas actuellement.

De plus, la table de hachage demeure totalement en mémoire, ce qui permet des traitements rapides, mais la limite en taille. Nous pourrions concevoir un algorithme permettant de ne charger en mémoire qu'une seule partie de la table. De cette manière, nous pourrions manipuler des tables beaucoup plus grandes.

L'auteur

Guilhem de Wailly, directeur de la société Erian Concept, partenaire NetUltra (www.netultra.net) et Getek (www.getek.fr).

Votre interlocuteur Linux !

Support, formations, configurations, administration, développements Linux.

http://www.erian-concept.com

Références

Langage C - norme ANSI : bon ouvrage de référence
Ph. DRIX
Masson

Programmer en C++: une bonne référence
S.C. DEWHURST et K.T. STARK
Masson

Le Langage C: la bible!
B.W. KERNIGHAN et D.M. RITCHIE
Masson

gcc: compilateur C du GNU, et tous les outils de développement
http://www.gnu.org

Kdevel: un environnement KDE de programmation C
http://samuel.cs.uni-potsdam.de/~smeier/kdevelop_new/index.html