Listes chainées (djgpp)

Soyez le premier à donner votre avis sur cette source.

Vue 5 854 fois - Téléchargée 160 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 121 Date d'inscription mercredi 26 octobre 2005 Statut Membre Dernière intervention 14 mars 2009 1
6 août 2006 à 21:09
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
26 déc. 2002 à 12:03
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 8
16 nov. 2002 à 18:42
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
15 nov. 2002 à 21:24
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
15 nov. 2002 à 19:53
Kaid: Merci pour le listing de la libération de la liste ;-)
@+
Afficher les 11 commentaires

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.