Discussion :

[benjiprog]

Bonjour,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#define LG 10
 
struct element{               /*Déclaration de la structure*/
       char nom[LG+1];
       int age;
       struct element *suivant;  /*Pointeur sur l'élément suivant*/
       };
 
void creation (struct element * *);  /*Prototype des fonctions*/
void affiche (struct element *);    
 
int main (void)
{
    struct element *fiche;
 
    creation(&fiche);      
    affiche(fiche);
 
    getch ();
    return (0);
}
 
            /*********Fonction de création de liste chainée**********/
void creation (struct element * *adr) 
{
     char nom[LG+1];
     int age;
     struct element *courant;  
 
     printf ("Entrer un nom vide pour terminer\n\n");
     *adr=NULL;              
     while (1)                
     {
         printf ("Nom :");
         gets(nom);
         if (!strlen(nom)) break;        
         printf ("Age :");
         scanf ("%d",&age);
         getchar();
         courant=(struct element *)malloc (sizeof(struct element)); /*réservation mémoire*/
         strcpy(courant->nom,nom);  
         courant->age=age;          
         courant->suivant=*adr;     
         *adr=courant;                 
     }
}
 
           /*******Fonction d'affichage de la liste chainée******/
void affiche (struct element *point)
{
     printf ("\n\tNOM\tAGE\n\n");
     while (point)      
     {
         printf ("%12s",point->nom);      
         printf ("%7d\n",point->age);     
         point=point->suivant;    
     }
}

Ce programme de liste chainée marche mais il m'affiche les noms et age dans l'ordre inverse dans lequel je les aient saisie et moi j'aimerais les afficher dans l'ordre dans lequel je les aient saisie j'ai déjà essayé mais je n'y suis pas arriver je solicite votre aide merci d'avance.

[bigquick]

Salut,

Après un coup d'oeil rapide, on dirait que tu fais un ajout en tête de liste, et que tu les affiche en parcourant ta liste dans l'ordre... Comme ils sont stockés dans l'ordre inverse de la saisie (le dernier ajouté est en 1ère position), ils s'affichent "à l'envers".

Il faudrait donc que tu fasse un ajout en fin de liste, ou que tu les affiche à reculons ...

note: tu as 3 solutions qui me viennent à l'esprit:

- ajout en fin de liste en re-parcourant toute la liste à chaque fois -> pas top
- ajout en fin de liste en gardant un pointeur vers le dernier -> pas mal
- affichage à reculons -> pas top, car difficile à lire (et puis c'est bizarre de stocker à l'envers, puis de lire à l'envers histoire d'afficher dans l'ordre)

Donc d'après moi le mieux serait de stoquer un pointeur vers le dernier élément pour faire des ajouts en fin de liste rapides !
Voilà, si quelqu'un d'autre à des idées ....

[diogene]

bigquick propose :

- ajout en fin de liste en gardant un pointeur vers le dernier -> pas mal

C'est sans doute le plus efficace et le plus rapide à mettre en oeuvre pour l'implantation d'une file. Il suffit de définir une structure comportant un pointeur sur la tête et un pointeur sur la queue. La précaution à ne pas omettre est de mettre les deux à NULL lorsqu'on vide la file et à positionner les deux pointeurs lors de l'insertion dans une file vide

[benjiprog]

D'accord mais qu'est ce que vous appeler exactement un "ajout"?Sinon merci j'essaierais votre solution dés que je pourrais.

[Emmanuel Delahaye]

D'accord mais qu'est ce que vous appeler exactement un "ajout"?Sinon merci j'essaierais votre solution dés que je pourrais.

Par défaut, une liste est vide (contrairement à un tableau) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

struct node *p_list = NULL;

Ajouter un élément consiste à créer ce élément

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

struct node *p_elem = malloc (sizeof *p_elem);

initialise les membres 'intelligement', notamment

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p_elem->p_next = NULL;

et ensuite de lier cet élément à la liste existante. Si elle est vide, c'est simple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p_list = p_elem;

Ensuite, l'ajout se fera en tête

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
p_elem->p_next = p_list;
p_list = p_elem;

ou en queue (c'est un choix).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p_last->p_next = p_elem;

L'ajout en queue est chronologique...

(et je ne parle pas de l'insersion triée...)

[Jedai]

On peut aussi implémenter facilement une file comme une liste chainée simple circulaire, ce qui permet d'économiser un pointeur (ce dont on se contrefout, mais c'est joli ).

--
Jedaï

[Emmanuel Delahaye]

On peut aussi implémenter facilement une file comme une liste chainée simple circulaire, ce qui permet d'économiser un pointeur (ce dont on se contrefout, mais c'est joli ).

Sauf qu'on a un peu du mal à savoir où est la fin... (à moins d'utiliser une donnée spéciale...)

[Jedai]

Le but d'une file initialement n'est pas d'être traversée, mais comme de toute façon on conserve l'adresse de l'élément à partir duquel on débute le parcours, on peut toujours savoir si on est revenu à son point de départ.
Exemple d'implémentation d'une telle file : (ayez un peu d'indulgence, je commence à peine le C)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
/* my_str_queue :
 * a lib who provide a queue of strings
 */
 
#ifndef H_MY_CHAR_QUEUE
#define H_MY_CHAR_QUEUE
 
typedef struct node {
	char *ent;
	struct node *next;
} NODE;
 
typedef struct {
	int elem;
	NODE *first;
} QUEUE;
 
typedef QUEUE *P_QUEUE;
typedef NODE *P_NODE;
 
// Create a new queue with the content as first element
P_QUEUE new( char *content );
 
int is_empty( P_QUEUE my_queue );
 
void push( P_QUEUE my_queue, char *content );
 
// Be careful, this function returns NULL if the list is empty
char *pop( P_QUEUE my_queue );
 
// Don't forget to clean the mess
void delete( P_QUEUE my_queue );
 
#endif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
/* my_str_queue :
 * a lib who provide a queue of strings
 */
#include <stdlib.h>
#include <stddef.h>
 
#include "inc/my_char_queue.h"
 
 
// Create a new queue with the content as first element
P_QUEUE new( char *content ){
	P_NODE fstnode = (P_NODE) malloc( sizeof(NODE) );
	fstnode->ent = content;
	fstnode->next = fstnode;
	P_QUEUE my_queue = (P_QUEUE) malloc( sizeof(QUEUE) );
	my_queue->elem = 1;
	my_queue->first = fstnode;
	return my_queue;
}
 
int is_empty( P_QUEUE my_queue ){
	if( my_queue->elem == 0) return 1;
	else return 0;
}
 
void push( P_QUEUE my_queue, char *content ){
	if( is_empty(my_queue) ){
		my_queue->elem = 1;
		P_NODE fstnode = (P_NODE) malloc( sizeof(NODE) );
		fstnode->ent = content;
		fstnode->next = fstnode;
		my_queue->first = fstnode;
	} else {
		my_queue->elem++;
		P_NODE newnode = (P_NODE) malloc( sizeof(NODE) );
		newnode->ent = content;
		newnode->next = my_queue->first->next;
		my_queue->first->next = newnode;
		my_queue->first = newnode;
	}
}
 
// Be careful, this function returns NULL if the list is empty
char *pop( P_QUEUE my_queue ){
	if( is_empty(my_queue) ){
		return NULL;
	} else {
		my_queue->elem--;
		P_NODE fstnode = my_queue->first;
		P_NODE lastnode = fstnode->next;
		if( my_queue->elem == 0 ){
			my_queue->first = NULL;
		} else {
			fstnode->next = lastnode->next;
		}
		char *content = lastnode->ent;
		free(lastnode);
		return content;
	}
}
 
void delete( P_QUEUE my_queue ){
	int elem = my_queue->elem;
	for( ; elem ; elem--){
		pop(my_queue);
	}
	free(my_queue);
}

(C'est juste un code pour montrer l'algo, il n'y a aucune optimisation et je ne teste même pas si mes mallocs ont réussi)

--
Jedaï

[benjiprog]

Excuser-moi je suis débutant et j'ai du mal a comprendre la méthode que vous m'avez donné.

[Emmanuel Delahaye]

Excuser-moi je suis débutant et j'ai du mal a comprendre la méthode que vous m'avez donné.

Et on est censé répondre quoi à çà ?

[benjiprog]

Il faut que je mette un pointeur qui pointe sur l'element suivant et un pointeur qui pointe sur l'élement précédant seulement je ne vois pas comment faire pour qu'il pointe sur l'élement précédant et ensuite comment afficher les listes dans le même ordre que la saisie.

[Emmanuel Delahaye]

Il faut que je mette un pointeur qui pointe sur l'element suivant et un pointeur qui pointe sur l'élement précédant seulement je ne vois pas comment faire pour qu'il pointe sur l'élement précédant et ensuite comment afficher les listes dans le même ordre que la saisie.

On t'a demandé de faire une liste doublement chainée ?

Avec une liste simple ça donne ça :

1. liste vide: head->NIL
2. Ajout de A : head->A->NIL
3. Ajout de B : head->A->B->NIL
4. Ajout de C : head->A->B->C->NIL

Avec une liste double :

1. liste vide: head->NIL
2. Ajout de A: head->A->NIL et NIL<-A
3. Ajout de B: head->A->B->NIL et NIL<-A<-B
4. Ajout de C: head->A->B->C->NIL et NIL<-A<-B<-C

Il faut une structure avec 2 pointeurs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
struct node
{
   struct node *p_prev;
   struct node *p_next;
   ... data...
};

A toi de créer les bons liens (initialiser les pointeurs comme il faut).

[benjiprog]

Avec une liste simple ça donne ça :

1. liste vide: head->NIL
2. Ajout de A : head->A->NIL
3. Ajout de B : head->A->B->NIL
4. Ajout de C : head->A->B->C->NIL

Voilà avec une liste simple mais ce que je n'arrive pas a réaliser c'est ajouter chaque nouvel élement en fin de liste afin que le parcour de la liste se fasse dans le même ordre dans lequel j'ai introduit mes données.
par exemple si je fournit 3 prénom anne en 1er franck en 2ème et jean en 3ème j'aimerais que mon programme me les affiches dans cet ordre :
anne
franck
jean

[Emmanuel Delahaye]

mais ce que je n'arrive pas a réaliser c'est ajouter chaque nouvel élement en fin de liste

Et on est censé deviner ton code ou tu as l'intention de le poster un jour ?

[benjiprog]

Et on est censé deviner ton code ou tu as l'intention de le poster un jour ?

Je l'ai déjà posté en tout début mais bon le revoilà :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#define LG 10
 
struct element{               /*Déclaration de la structure*/
       char nom[LG+1];
       int age;
       struct element *suivant;  /*Pointeur sur l'élément suivant*/
       };
 
void creation (struct element * *);  /*Prototype des fonctions*/
void affiche (struct element *);    
 
int main (void)
{
    struct element *fiche;
 
    creation(&fiche);      
    affiche(fiche);
 
    getch ();
    return (0);
}
 
            /*********Fonction de création de liste chainée**********/
void creation (struct element * *adr) 
{
     char nom[LG+1];
     int age;
     struct element *courant;   /*Pointeur pour l'échange de valeur et réservation mémoire*/
 
     printf ("Entrer un nom vide pour terminer\n\n");
     *adr=NULL;                /*Initialisation du tout début de liste*/
     while (1)                     
    {
         printf ("Nom :");
         gets(nom);
         if (!strlen(nom)) break;        /*Sortie de boucle si nom vide*/
         printf ("Age :");
         scanf ("%d",&age);
         getchar();
         courant=(struct element *)malloc (sizeof(struct element)); /*réservation mémoire*/
         strcpy(courant->nom,nom);  
         courant->age=age;          
         courant->suivant=*adr;       
         *adr=courant;                 
     }
}
 
           /*******Fonction d'affichage de la liste chainée******/
void affiche (struct element *point)
{
     printf ("\n\tNOM\tAGE\n\n");
     while (point)       
     {
         printf ("%12s",point->nom);     
         printf ("%7d\n",point->age);      
         point=point->suivant;      
     }
}

[Emmanuel Delahaye]

Et on est censé deviner ton code ou tu as l'intention de le poster un jour ?

Je l'ai déjà posté en tout début mais bon le revoilà :

Et tu n'as rien modifié depuis ? Ca sert à quoi les explications ?

Pour ajouter un élément, il faut parcourir la liste jusqu'au dernier élément,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
p := head
WHILE  p.next <> NIL
   p := p.next
WHILE END

et 'accocher' le nouvel élément au dernier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p.next := new.

Evidemment, new.next vaut NIL...

[Jedai]

Il est tout de même préférable de maintenir un pointeur sur le dernier élément pour s'éviter de reparcourir l'ensemble de la liste à chaque ajout ! (ou alors utiliser la méthode que j'ai présentée dans mon code, que tu pourrais d'ailleurs réutiliser facilement pour t'éviter des soucis).

--
Jedaï

[Emmanuel Delahaye]

Il est tout de même préférable de maintenir un pointeur sur le dernier élément pour s'éviter de reparcourir l'ensemble de la liste à chaque ajout ! (ou alors utiliser la méthode que j'ai présentée dans mon code, que tu pourrais d'ailleurs réutiliser facilement pour t'éviter des soucis).

Oui, mais je pense que pour saisir l'utilité du pointeur de fin, il faut s'être un peu cassé les dents sur le parcours...

Allons-y étapes par étapes...

[benjiprog]

Il faut que je change dans ma fonction d'affichage ou de création?

[benjiprog]

Si j'ai bien compris il faut que j'affecte l'adresse de mon nouvel élement (nom) au dernier (pointeur suivant) non?