Listes chainées (djgpp)
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é ;-)
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
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
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.