LISTES CHAINÉES (DJGPP)

//#######################################################################
//Dans ce programme, nous allons apprendre ? utiliser les
//listes chain?es. Nous cr?erons donc les fonctions permettant
//de les manipuler facilement.
//By CoBr@84, tous droits r?serv?s.
//#######################################################################

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

//#################### On d?fini quelques constantes ####################
#define TRUE 1
#define FALSE 0



//#################### D?claration des structures ####################
//Tout d'abord, nous d?finisson la structure Node qui repr?sente
//un noeud contenant une valeur et un pointeur vers le prochain
//noeud. Si le pointeur vaut NULL, cela signifie qu'il n'y a
//plus de noeud apr?s celui-ci.
struct cNode{
        struct cNode *pNext; //Le pointeur vers le prochain noeud
        unsigned int Value; //La valeur du noeud
};



//Nous avons besoin d'une t?te de liste afin de mieux nous
//rep?rer.
struct cHead{
        struct cNode *pFirst; //Pointeur vers le premier noeud
};



//#################### D?claration des prototypes ####################

//Ajoute une valeur ? la fin de la liste
void Add(struct cHead *Header,int Value);

//Cr?? un nouveau Header
struct cHead *CreateHeader(void);

//Cr?? un nouveau node
struct cNode *CreateNode(void);
                                             
//Lib?re un Header
void FreeHeader(struct cHead *Header);

//Lib?re un noeud
void FreeNode(struct cNode *Node);

//Renvoie le dernier noeud de la liste, NULL si aucun
struct cNode *GetLastNode(struct cHead *Header);



//#################### Impl?mentation des fonctions ####################

struct cHead *CreateHeader(void)
{
        struct cHead *pHeader;
        pHeader= (struct cHead *) malloc(sizeof(pHeader));

        pHeader->pFirst=NULL;
        return pHeader;
};

struct cNode *CreateNode(void)
{
        struct cNode *pNode;
        pNode= (struct cNode *) malloc(sizeof(pNode));

        pNode->Value=0;
        pNode->pNext=NULL;
        return pNode;
}

void FreeHeader(struct cHead *Header)
{
        //On lib?re le pointeur du header
        free (Header);
};


void FreeNode (struct cNode *Node)
{
        //On lib?re le pointeur
        free (Node);
};

struct cNode *GetLastNode(struct cHead *Header)
{
        if (Header->pFirst==NULL)
        {
                //Aucun node, cela ne sert ? rien de continuer
                return NULL;
        }
        else
        {
                //On pointe vers le dernier noeud
                struct cNode *tNode;
                tNode=Header->pFirst;

                while (tNode->pNext)
                {
                        tNode=tNode->pNext;
                }
                return tNode;
        }


};


void Add(struct cHead *Header, int Value)
{
        struct cNode *pNode=CreateNode();
        pNode->Value=Value;
        
        //La liste ne contient aucun noeud, on ajoute
        //donc le premier au Header
        if(Header->pFirst==NULL)
        {
                Header->pFirst=pNode;
        }
        else
        {
                //On recherche le dernier noeud
                //Et on lui ajoute le nouveau noeud
                struct cNode *LastNode=GetLastNode(Header);
                LastNode->pNext=pNode;
        }
};



//#################### Fonction Main ####################
main (int NbArgs, char *Args[])
{

        //D?claration / initialisation variables
        struct cNode *Listing=CreateNode();
        struct cNode *BufferNode=CreateNode();
        char Choix[32];//Buffer du choix utilisateur
        int Buffer;    //Buffer d?cimal
        clock_t Timer;  //Notre chronom?tre
        int i;         //Compteur de boucle
        unsigned int min;       //Minimum
        unsigned int max;       //Maximum
        struct cHead *Header = CreateHeader();

        
        printf("Tapez 'help' pour obtenir de l'aide.\n");

        //Boucle des messages
        do
        {
                printf(">");
                scanf("%s",&Choix);

                if (strcmp(Choix,"help")==0)
                {
                    //AFFICHAGE DE L'AIDE
                    printf("\nCoBr@84 All rights reserved ;-)\n");
                    printf("----- Liste des commandes -----\n");
                    printf("Commande\t Description:\n");
                    printf("add\t\t Ajouter une valeur\n");
                    printf("list\t\t Lister\n");
                    printf("help\t\t Aide\n");
                    printf("ext\t\t Affiche les extremums\n");
                    printf("count\t\t Affiche le nombre de noeuds\n");
                    printf("clear\t\t Efface la liste\n");
                    printf("fill\t\t Remplir la liste automatiquement\n");
                    printf("bye\t\t Quitter\n");
                    printf("----- Contact -----\n");
                    printf("ipone.jeremy@wanadoo.fr\n\n");
                }
                else if(strcmp(Choix,"list")==0)
                {
                
                    //LISTING
                    if (Header->pFirst==NULL)
                    {//Liste vide
                     printf("Aucune donn?e.\n");
                    }
                    else
                    {
                        printf("Index\t\tAdresse\t\tValeur\t\tTemps d'acc?s:\n");
                        Listing=Header->pFirst;

                        Timer=clock();
                        i=1;
                        while (Listing)
                        {
                         printf("%u\t\t%X\t\t%d\t%u ms\n",i,&(*Listing),Listing->Value,clock()-Timer);

                                //On v?rifie qu'il y a un autre noeud
                                //apr?s celui-ci
                                if (Listing->pNext){
                                    Listing=Listing->pNext;
                                    i++;
                                }
                                else{ //Sinon, on d?fini un pointeur nul
                                    Listing=NULL;
                                }
                         };
                         FreeNode(Listing);
                         Buffer=clock()-Timer;
                         printf("Listing de %d noeuds effectu? en %d ms.\n",i,Buffer);
                    }
                }
                else if (strcmp(Choix,"add")==0)
                {
                    printf("valeur>");
                    scanf("%d",&Buffer);
                    Add(Header,Buffer);
                }
                else if (strcmp(Choix,"fill")==0)
                {
                    printf("longueur>");
                    scanf("%d",&Buffer);
                    printf("filling...");
                    for (i=0;i<Buffer;i++)
                    {
                       Add(Header,rand());
                    }
                    printf("\tOk\n");

                }
                else if (strcmp(Choix,"ext")==0)
                {
                    //Affiche les extremums
                    Listing=Header->pFirst;

                        Timer=clock();
                        //initialisation des variables:
                        max=0; //Valeur min pour un int unsigned
                        min=4294967265; //Valeur max pour un int unsigned
                        i=1;
                        while (Listing)
                        {

                                //On v?rifie qu'il y a un autre noeud
                                //apr?s celui-ci
                                if (Listing->pNext){
                                    //On regarde la valeur pour voir
                                    //s'il s'agit d'un maximum ou d'un
                                    //minimum
                                    if (Listing->Value<min){
                                       min=Listing->Value;}
                                       
                                    if (Listing->Value>max){
                                       max=Listing->Value;}
                                       
                                    Listing=Listing->pNext;
                                    i++;
                                }
                                else{ //Sinon, on d?fini un pointeur nul
                                    Listing=NULL;
                                }
                         };
                         
                         FreeNode(Listing);
                         Buffer=clock()-Timer;
                         printf("Maximum: %d \t Minimum: %d\n",max,min);
                         printf("Parcour de %d noeuds effectu? en %d ms.\n",i,Buffer);
                }
                else if(strcmp(Choix,"count")==0)
                {
                        //Affichage du nombre de noeuds
                        Listing=Header->pFirst;

                        Timer=clock();
                        i=1;
                        while (Listing)
                        {

                                //On v?rifie qu'il y a un autre noeud
                                //apr?s celui-ci
                                if (Listing->pNext){
                                    Listing=Listing->pNext;
                                    i++;//Un noeud supplementaire
                                }
                                else{ //Sinon, on d?fini un pointeur nul
                                    Listing=NULL;
                                }
                         };
                         
                         FreeNode(Listing);
                         Buffer=clock()-Timer;
                         printf("Nombre de noeuds: %d\n",i);
                         printf("Parcour  effectu? en %d ms.\n",Buffer);
                }
                else if(strcmp(Choix,"clear")==0)
                {
                    //On efface la liste
                    FreeNode(Listing);
                    BufferNode=Header->pFirst;

                    while(BufferNode)
                    {
                        Listing=BufferNode->pNext;
                        FreeNode(BufferNode);
                        BufferNode=Listing;
                    }
                    
                    FreeHeader(Header);
                    
                    Header=CreateHeader();
                    printf("Liste effac?e.)\n");

                }
                else
                {
                    //CHOIX INCORRECT!
                    printf ("Commande inconnue\n");
                }

                
        }while (strcmp(Choix,"bye"));
        
        printf("Bye!\n");
        FreeHeader(Header);

        return 0;
};