Tri des indices d'un tableau.

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
keywords : langage C, snippet, pointeurs, tableau, exemple
OSI Certified Open Source Software