/* Programme de recherche dans un tableau d'une liste chaînée 
   de blocs de tailles variables pour trouver les entrées d'un nombre ID spécifié,
   et retourne la moyenne des valeurs de toutes ces entrées. C*/
         
#include <stdio.h>
#ifdef __TURBOC__
#include <alloc.h>
#else
#include <malloc.h>
#endif

void main(void);
void exit(int);
unsigned int FindIDAverage(unsigned int, struct BlockHeader *);

/* Structure de départ de chaque bloc de taille variable */
struct BlockHeader {
   struct BlockHeader *NextBlock; /* pointeur sur le prochain bloc, ou NULL
                                     si c'est le dernier bloc de la
                                     liste chaînée */
   unsigned int BlockCount;       /* le nombre d'entrées DataElement 
                                     dans le bloc */
};

/* Structure qui contient un élément du tableau que nous recherchons */
struct DataElement {
   unsigned int ID;     /* nombre ID de l'entrée du tableau */
   unsigned int Value;  /* valeur de l'entrée */
};

void main(void) {
   int i,j;
   unsigned int IDToFind;
   struct BlockHeader *BaseArrayBlockPointer,*WorkingBlockPointer;
   struct DataElement *WorkingDataPointer;
   struct BlockHeader **LastBlockPointer;

   printf("nombre ID pour lequel vous souhaitez trouver la moyenne: ");
   scanf("%d",&IDToFind);

   /* Construit un tableau sur 5 blocs pour le test */
   /* Fixe la liste chaînée à BaseArrayBlockPointer */
   LastBlockPointer = &BaseArrayBlockPointer;
   /* Crée 5 blocs de diverses tailles */
   for (i = 1; i < 6; i++) {
      /* Essaie de récupérer de la mémoire pour le prochain bloc */
      if ((WorkingBlockPointer =
            (struct BlockHeader *) malloc(sizeof(struct BlockHeader) +
            sizeof(struct DataElement) * i * 10)) == NULL) {
         exit(1);
      }
      /* Détermine le nombre d'éléments de données du bloc */
      WorkingBlockPointer->BlockCount = i * 10;
      /* Ajoute le nouveau bloc à la chaîne */
      *LastBlockPointer = WorkingBlockPointer;
      /* Pointe sur le premier champ de données */
      WorkingDataPointer =
            (struct DataElement *) ((char *)WorkingBlockPointer +
            sizeof(struct BlockHeader));
      /* Remplit les champs avec les ID et les valeurs */
      for (j = 0; j < (i * 10); j++, WorkingDataPointer++) {
         WorkingDataPointer->ID = j;
         WorkingDataPointer->Value = i * 1000 + j;
      }
      /* Mémorise le lien entre le bloc et le suivant */
      LastBlockPointer = &WorkingBlockPointer->NextBlock;
   }
   /* Positionne le pointeur de bloc suivant le précédent à  NULL pour indiquer
      qu'il n'y a plus d'autres blocs */
   WorkingBlockPointer->NextBlock = NULL;

   printf("Moyenne de tous éléments avec ID %d: %u\n",
         IDToFind, FindIDAverage(IDToFind, BaseArrayBlockPointer));
   exit(0);
}

/* Recherche dans le tableau des entrées DataElement de la
   liste chaînée de blocs de tailles diverses commençant par le bloc 
   pointé par BlockPointer pour trouver toutes les entrées dont les ID correspondent
   à SearchedForID, et retourne la moyenne des entrées. Si aucune correspondance n'est 
   trouvée, retourne zéro */
unsigned int FindIDAverage(unsigned int SearchedForID,
      struct BlockHeader *BlockPointer)
{
   struct DataElement *DataPointer;
   unsigned int IDMatchSum;
   unsigned int IDMatchCount;
   unsigned int WorkingBlockCount;

   IDMatchCount = IDMatchSum = 0;
   /* Parcourt tous les blocs jusqu'à trouver le dernier 
      (celui dont le pointeur sur le suivant est à NULL ) */
   do {
      /* Pointe sur la première entrée DataElement du bloc */
      DataPointer =
            (struct DataElement *) ((char *)BlockPointer +
            sizeof(struct BlockHeader));
      /* Recherche toutes les entrées DataElement du bloc
         et additionne les données qui correspondent à l'ID recherché */
      for (WorkingBlockCount=0;
            WorkingBlockCount<BlockPointer->BlockCount;
            WorkingBlockCount++, DataPointer++) {
         /* Si l'ID correspond, additionnez dans la moyenne et incrémentez la valeur
            du compteur de correspondance */
         if (DataPointer->ID == SearchedForID) {
            IDMatchCount++;
            IDMatchSum += DataPointer->Value;
         }
      }
   /* Pointe sur le prochain bloc, et continue tant que le pointeur
     n'est pas NULL */
   } while ((BlockPointer = BlockPointer->NextBlock) != NULL);

   /* Calcule la moyenne de toutes les correspondances */
   if (IDMatchCount == 0)
      return(0);            /* évite la division par 0 */
   else
      return(IDMatchSum / IDMatchCount);
}