C'est un exemple d'utilisation des tableaux et des pointeurs.
A mon avis, celui qui comprend ce source et est capable de faire un programmme similaire a compris le principal sur les pointeurs en C et est, au moins virtuellement, un bon programmeur C.
Ce programme vient d'une réponse que j'ai faite sur le
forum usenet fr.comp.lang.c.
Le but est de créer à partir d'un tableau d'ints que nous appellerons
tableau d'origine, un tableau, que nous appellerons tableau résultat,
des indices dans le tableau d'origine triés sur les valeurs du tableau
d'origine correspondant à ces indices.
Oui, moi aussi il a fallu qu'on me répète la question...
Supposons que le tableau d'origine soit :
5 2 6 4
le tableau résultat sera :
1 3 0 2
(Rappelons que l'indice d'un premier élément est 0 en C, 1 celui
du second etc.
Dans le tableau résultat, 1 est l'indice dans le tableau d'origine
de la valeur la plus petite, ici 2, 3 est l'indice de la valeur
immédiatement supérieure, ici 4, etc.
Le code est sur-commenté, je suis d'habitude moins verbeux,
je ne mets guère de commentaires qu'en début de certaines fonctions,
peu dans le code, le plus souvent à droite de la définition des variables.
Ici c'est dans un but didactique que j'en mets.
Il se passera d'autres commentaires.
Le code comprend le header indsort.h contenant la definition (signature) de la fonction, indsort.c contenant sa déclaration, et un programme testind.c servant à tester le tout.
Le header indsort.h :
#ifndef __INDSORT_H__ #define __INDSORT_H__ #include <stdlib.h> // renvoie les indices de 0 à nmemb - 1 dans pind // ptab : adresse de la table d'origine // pind : adresse de la table résultat (allouée par l'appelant) // nmemb : nombre d'éléments (de chacune des 2 tables) void indsort(const int * ptab, int * pind, int nmemb); #endif
Les fonctions indsort.c :
#include <stdlib.h>
#include <stdio.h>
#include "indsort.h"
// qsort callback
static int
compar(const void * p1, const void * p2) {
return (**((int **) p1) - **((int **) p2));
}
void
indsort(const int * ptab, int * pind, int nmemb) {
int * pt; // pour parcouri ptab
int * pi; // pour parcourir pind
int ** paddr; // tableau des adresses des elements de ptab
int ** pa; // pour parcourir paddr
// alloue le tableau d'adresses des elements
paddr = malloc(nmemb * sizeof(*paddr));
if (paddr == NULL) {
fprintf(stderr, "Allocation mémoire impossible.");
abort();
}
// initialise les addresses
pt = (int *)ptab + nmemb;
for (pa = paddr + nmemb; pa-- > paddr; *pa = --pt);
// trie les adresses.
qsort(paddr, nmemb, sizeof(*paddr), compar);
// construit indices à partir des adresses
pi = pind + nmemb;
for (pa = paddr + nmemb; pa-- > paddr; *(--pi) = *pa - ptab);
// libère le tableau d'adresses
free(paddr);
}
Le programme de test testind.c :
#include <stdlib.h>
#include <stdio.h>
#include "indsort.h"
int
main(int argc, char **argv)
{
int argn; // nombre d'arguments (sans le nom du programme)
int * tab; // table d'origine
int * ind; // table résultat des indices dans tab
int * pi; // pour parcourir tab et ind
char **p; // pour parcourir argv
// alloue les tables en même temps
argn = argc - 1;
tab = malloc(2*(argn * sizeof(*tab)));
if (tab == NULL) {
fprintf(stderr, "Allocation mémoire impossible.");
abort();
}
ind = tab + argn; // on partage l'allocation en 2
// construit la table d'origine
for (pi = tab, p = argv + 1; argn--;) {
*(pi++) = atoi(*(p++));
}
// remplit la table résultat par indsort()
argn = argc - 1;
indsort(tab, ind, argn);
// affiche les résultats
for (pi = ind; pi < ind + argn; pi++) {
printf("%d ", *pi);
}
printf("\n");
// libère inutilement la mémoire allouée
free(tab);
// retourne si on ne s'est pas planté avant
return(EXIT_SUCCESS);
}
Faisons un petit script pour compiler le tout :
#!/bin/sh gcc -W -Wall -c -o indsort.o indsort.c gcc -W -Wall -c -o testind.o testind.c gcc -o testind indsort.o testind.o
compilons et testons :
pat@harpo:~/test/indsort$ ./compile.sh pat@harpo:~/test/indsort$ ./testind 12 2 5 25 32 8 1 2 5 0 3 4