Listes chainées (djgpp)

Soyez le premier à donner votre avis sur cette source.

Vue 5 527 fois - Téléchargée 147 fois

Description

Ce programme montre comment mettre en place des listes chainées dans vos algos. Le code est simple et efficace, cependant, il n'est pas optimisé ;-)

Source / Exemple :


//#######################################################################
//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;
};

Conclusion :


Je suis en train d'améliorer cette source et je mettrai les dernières versions en lignes dès que possible.
-Mises à jour:
-Le 15/11/2002: Ajout de la fonctionnalité "Clear" qui permet d'affacer la liste. (merci à Kaid ;-)
Pour toute remarque / suggestion: ipone.jeremy@wanadoo.fr

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

spidermario
Messages postés
130
Date d'inscription
mercredi 26 octobre 2005
Statut
Membre
Dernière intervention
14 mars 2009
-
Au lieu de
#define TRUE 1
#define FALSE 0
Tu peux mettre
enum BOOL
{
FALSE,TRUE
};
Mais de toutes façons, ça ne te servira pas, je n'ai pas vu une seule utilisation de TRUE ou de FALSE dans ton programme...
cs_Xs
Messages postés
368
Date d'inscription
mercredi 14 novembre 2001
Statut
Membre
Dernière intervention
1 septembre 2008
-
Merci ! grace a ce code+ explications + refonte en C++ par vieuxLion, j'ai enfin compris lutilité et surtout la maniére de les utiliser (c'est sur, c'est pas dur de faire la class/struct, mais fo savoir l'utiliser apres).
cs_vieuxLion
Messages postés
455
Date d'inscription
samedi 26 octobre 2002
Statut
Membre
Dernière intervention
6 avril 2004
7 -
c'est un bon source. Compliments
pour des idées d'amélioration :
mettre en cache le nombre d'éléments, proposer une fonction de recherche, utiliser C++ pour les new/delete + la protection des variables + la simplification de l'interface par rapport à l'implémentation + la généricité ... etc...
voila ma version en C++
http://www.cppfrance.com/article.aspx?Val=1104
cobra84
Messages postés
42
Date d'inscription
dimanche 26 août 2001
Statut
Membre
Dernière intervention
13 août 2007
-
Voila, j'ai mis à jour la source... On peut maintenant effacer la liste!
@+
cobra84
Messages postés
42
Date d'inscription
dimanche 26 août 2001
Statut
Membre
Dernière intervention
13 août 2007
-
Kaid: Merci pour le listing de la libération de la liste ;-)
@+

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.