débutant besoin d'orientation

**josef24** · 20/09/2007, 14h13

Salut les amis

Je suis un nouveau et débutant en C

Je veux savoir ou puis-je étudier ses chapitres

les files et les piles
les arbres
les listes chainées

Et grand merci

**Thierry Chappuis** · 20/09/2007, 14h34

Dans n'importe quel bouquin d'algo. Sinon sur developpez:

Pour les files et les piles:
http://nicolasj.developpez.com/articles/file/
http://nicolasj.developpez.com/articles/file/

Pour les listes chainées:
http://nicolasj.developpez.com/articles/listesimple/
http://nicolasj.developpez.com/articles/listedouble/
http://chgi.developpez.com/pile/

Pour les arbres:
http://rperrot.developpez.com/articl...ctures/arbres/

Thierry

**Franck.H** · 20/09/2007, 14h36

Salut et bienvenue sur les forums de developpez.com

Pour les piles/files/listes : http://nicolasj.developpez.com/#LI
Pour les arbres tu as : http://rperrot.developpez.com/articl...ctures/arbres/

Sinon d'autres liens :
Le site de la rubrique où tu peux avoir accés à tout ce qui touche au C: http://c.developpez.com/ et pour t'aider à prendre quelques points repères pour débuter: http://franckh.developpez.com/articl...-debuter-en-c/

En fait tout est sur le site, après il suffit de chercher... bonne lecture

[Edit]...grillaide

...[/Edit]

**josef24** · 20/09/2007, 23h35

merci beaucoup les amis

**josef24** · 24/09/2007, 14h15

et pour bien comprendre avec quoi dois-je commencer en premier
les files
ou
les piles
ou
les listes chainées
ou
les arbres
?

**Franck.H** · 24/09/2007, 14h18

En générale on utilise les Listes chaînées comme introduction aux structures de données donc commence par ca, ce sera déjà très bien le jour où tu maîtrise ce point là

**Emmanuel Delahaye** · 24/09/2007, 14h33

Envoyé par josef24

et pour bien comprendre avec quoi dois-je commencer en premier
les files
ou
les piles
ou
les listes chainées
ou
les arbres
?

Je conseille :

les listes chainées
les piles
les files
les arbres

**josef24** · 24/09/2007, 19h09

merci bcp les amis

**josef24** · 25/09/2007, 01h36

je veux savoir est ce que mon niveau me permet d'attaquer les liste chaînées avec l'explication de http://nicolasj.developpez.com/
car j'ai trouvé des difficulté
par exemple cette fonction

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
sll_s *sll_new (void)
{
sll_s *p_sll = malloc (sizeof *p_sll);
if (p_sll)
{
item_s *p_l = malloc (sizeof *p_l);
if (p_l)
{
p_l->data = NULL;
p_l->next = NULL;
p_sll->p_start = p_l;
p_sll->list = NULL;
}
else
{
fprintf (stderr, "Memoire insufisante\n");
exit (EXIT_FAILURE);
}
}
else
{
fprintf (stderr, "Memoire insufisante\n");
exit (EXIT_FAILURE);
}
return p_sll;
}
III-D - Insertion d'un élément

**Thierry Chappuis** · 25/09/2007, 08h15

Quelles sont tes difficultés? Qu'est-ce que tu ne comprends pas?

Thierry

**josef24** · 25/09/2007, 22h45

J’ai pas compris le fonctionnement de la fonction précédente
Et aussi ses structures

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct item
{
struct item *next;
void *data;
} item_s;
 
 
typedef struct item
{
struct item *next;
void *data;
} item_s;

L’auteur n'explique pas trop et rentre directement au vif du sujet alors que moi le débutant c'est difficile

**Emmanuel Delahaye** · 25/09/2007, 22h54

Envoyé par josef24

J’ai pas compris le fonctionnement de la fonction précédente
Et aussi ses structures

Code :

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

1
2
3
4
5
6
 
typedef struct item
{
struct item *next;
void *data;
} item_s;

L’auteur n'explique pas trop et rentre directement au vif du sujet alors que moi le débutant c'est difficile

Tu as compris ce qu'était une liste chainée ?

http://emmanuel-delahaye.developpez....s_chainees.htm

**Thierry Chappuis** · 26/09/2007, 01h35

Le type item_s:

Code :

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

1
2
3
4
5
typedef struct item
{
   struct item *next;
   void *data;
} item_s;

représente un noeud ou un maillon de la chaine. Chaque noeud contient une donnée (dont l'adresse est ici rangée dans le pointeur générique data) et un pointeur sur le noeud suivant dans la liste (c'est le principe d'une liste chainée: chaque maillon de la chaine pointe sur l'élément suivant).

Jusque là c'est OK?

La structure sll_s (signifie list chainée simple ou liste simplement chaînée) représente la liste en elle-même. Cette structure facilite la gestion des opérations implantées par la liste chainée:

Code :

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

1
2
3
4
5
typedef struct sll
{
   item_s *p_start;
   item_s *list;
} sll_s;

p_start pointe sur un élément sentinelle qui se trouve au début de la liste, tandis que list pointe sur l'élément courant.

Jusque là, as-tu des questions?

Thierry

**josef24** · 27/09/2007, 20h07

Merci pour le site Emmanuel
Cher Thierry quand tu dit que *next est un pointeur sur le noeud suivant dans la liste, tu peux me donner un exemple de modification des champs du suivant maillon car j'ai pas bien compris théoriquement cette structure dans structure .
Et je vx savoir est ce que item_s; sll_s sont des nom standard

**Emmanuel Delahaye** · 27/09/2007, 23h28

Envoyé par josef24

Et je vx savoir est ce que item_s; sll_s sont des nom standard

Pas du tout. Ce sont des noms 'applicatifs' (donnés par le programmeur).

**Thierry Chappuis** · 28/09/2007, 01h15

Envoyé par josef24

Merci pour le site Emmanuel
Cher Thierry quand tu dit que *next est un pointeur sur le noeud suivant dans la liste, tu peux me donner un exemple de modification des champs du suivant maillon car j'ai pas bien compris théoriquement cette structure dans structure .
Et je vx savoir est ce que item_s; sll_s sont des nom standard

Voici une implantation très schématique et explicite d'une liste chainée. J'ai essayer d'exposer le mécanisme de fonctionnement de la manière la plus simple possible et j'espère que cela t'aidera à comprendre les principes sous-jacent à cette structure de donnée:

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <stdlib.h>
 
/*-tc- cette structure définit un maillon de la chaine */
struct Noeud
{
    int valeur;
    struct Noeud *p_suivant;
};
 
int main(void)
{
 
    int compteur = 0;
    struct Noeud *p = NULL;
    struct Noeud *p_liste = NULL;
 
 
    /* 1.Définition des maillons de la chaine --------------------------------*/
 
    /*-tc- Nous allons créer ici explicitement 4 maillons de type struct Noeud*/
    struct Noeud maillon_1 =
    {
        1, NULL
    };
    struct Noeud maillon_2 =
    {
        2, NULL
    };
    struct Noeud maillon_3 =
    {
        3, NULL
    };
    struct Noeud maillon_4 =
    {
        4, NULL
    };
 
    /* 2. chainage des maillons de la liste ----------------------------------*/
 
    /*-tc- Pour obtenir une liste chainee, il faut relier les maillons entre
      eux. On aura donc maillon_1 pointe sur maillon_2, maillon_2 pointe sur
      maillon_3, maillon_3 pointe sur maillon_4 et maillon_4 pointe sur NULL (ce
      qui indique que c'est le dernier maillon de la chaine */
 
    /*-tc- concretement, voila comment cela se passe. On fait pointer maillon_1
       sur maillon_2 */
    p_list = &maillon_1;
    maillon_1.p_suivant = &maillon_2;
    /*-tc- On fait pointer maillon_2 sur maillon_3 */
    maillon_2.p_suivant = &maillon_3;
    /*-tc- et ainsi de suite... */
    maillon_3.p_suivant = &maillon_4;
 
 
    /* 3. Modification de la valeur d'un maillon ------------------------------*/
 
    /*-tc- pour accéder à une valeur contenue dans une liste chainee, on est
      obligé de parcourir la liste. Imaginons que nous voulons modifier la valeur
      de maillon_3 sans passer par l'intermédiaire de la variable maillon_3 */
 
    /* On parcours la liste depuis maillon_1 jusqu'au maillon_3 */
    for (p = p_list; p != NULL && compteur < 2; p = p->p_suivant)
    {
        compteur++;
    }
    /* On modifie la valeur de maillon_3 */
    p->valeur = 40;
 
    /* 4. Parcours de liste pour afficher les donnees de chaque noeud --------*/
 
    /*-tc- enfin on parcours toute la liste pour afficher chaque valeur */
    for (p = p_list; p != NULL; p = p->p_suivant)
    {
        printf("%d ", p->valeur);
    }
    printf("\n");
 
    /* 4. Ajout d'un nouveau maillon a la liste chainee ----------------------*/
 
    /*-tc- Le grand avantage d'une liste chainee est de permettre d'ajouter
       tres facilement un nouveau maillon */
 
    {
        /*-tc- soit un maillon supplementaire */
        struct Noeud nouveau_maillon =
        {
            100, NULL
        };
 
        /*-tc- pour l'inserer dans la liste entre maillon_3 et maillon_4, il faut
          parcourir la liste jusqu'au 3e element */
        for (compteur = 0, p = p_list; p != NULL && compteur < 2; p = p->p_suivant)
        {
            compteur++;
        }
        /*-tc- On veut faire pointer nouveau_maillon sur maillon_4 */
        nouveau_maillon.p_suivant = p->p_suivant;
        /*-tc maillon_3 doit pour sa part pointer sur nouveau_maillon */
        p->p_suivant = &nouveau_maillon;
    }
 
    /* 5. On affiche la liste complete ---------------------------------------*/
 
    /*-tc- enfin on parcours toute la liste pour afficher chaque valeur */
    for (p = p_list; p != NULL; p = p->p_suivant)
    {
        printf("%d ", p->valeur);
    }
    printf("\n");
 
    return EXIT_SUCCESS;
}

Dans la pratique, on interagit avec une liste en utilisant des fonctions telles que liste_ajouter(), liste_creer(), liste_detruire(), liste_trier(), etc. Une fois qu'on a compris le principe général, il est très facile de programmer ces fonctions afin d'obtenir ce qu'un appelle un type abstrait de donnée. Le tutoriel que tu as entre les mains t'accompagne dans la création d'un certain nombre de ces fonctions dédiées à la manipulation des listes chainees.

Thierry

**josef24** · 28/09/2007, 20h07

Merci Thierry...mais j'ai quelque question
Pourquoi ça

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
  /* 3. Modification de la valeur d'un maillon ------------------------------*/
 
    /*-tc- pour accéder à une valeur contenue dans une liste chainee, on est
      obligé de parcourir la liste. Imaginons que nous voulons modifier la valeur
      de maillon_3 sans passer par l'intermédiaire de la variable maillon_3 */
 
    /* On parcours la liste depuis maillon_1 jusqu'au maillon_3 */
    for (p = &maillon_1; p != NULL && compteur < 2; p = p->p_suivant)
    {
        compteur++;
    }

Pourquoi passer par ça avant de modifier

Et ici

Code :

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

    for (p = &maillon_1; p != NULL; p = p->p_suivant)

Pour p = p->p_suivant est que le compilateur va savoir automatiquement le p-suivant et va le accrementer automatiquement car on définit pas quel p-suivant ? Pour le maillon 2 ou 3 ou 4 ?

**Thierry Chappuis** · 29/09/2007, 00h43

Envoyé par josef24

Pour p = p->p_suivant est que le compilateur va savoir automatiquement le p-suivant et va le accrementer automatiquement car on définit pas quel p-suivant ? Pour le maillon 2 ou 3 ou 4 ?

C'est ici que se fait le chainage:

Code :

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

1
2
3
4
5
6
 
maillon_1.p_suivant = &maillon_2;
/*-tc- On fait pointer maillon_2 sur maillon_3 */
maillon_2.p_suivant = &maillon_3;
/*-tc- et ainsi de suite... */
maillon_3.p_suivant = &maillon_4;

mailon_1.p_suivant contient l'adresse de maillon_2. maillon_2.p_suivant contient l'adresse de maillon_3 et ainsi de suite. Il est donc possible de parcourir la liste chainee en partant du premier maillon (maillon_1) de la manière suivante:

Code :

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

1
2
3
4
5
 
for (p = &maillon_1; p != NULL; p = p->p_suivant)
{
    /* ... */
}

L'expression p = p->p_suivant permet de passer d'un maillon à l'autre de la liste. Sachant que le champ p_suivant du dernier maillon de la chaine (ici: maillon_4) vaut NULL, on sait qu'on a atteint la fin de la liste chainee lorsque p == NULL.

Le concept de fonctionnement d'une liste chainee est très important à saisir, car on retrouvera des mécanismes similaires dans l'implantations des arbres, des graphes, voir même des tables de hachage. Par ailleurs les files et les piles sont souvent implantées à base de listes chainées. N'hésite donc pas à poser toutes les questions que tu veux.

Il existe également un autre tuto sur developpez.com, si cela peut t'aider à mieux comprendre le principe sous-jacent à l'implantation de cette structure de donnée: http://chgi.developpez.com/pile/

Thierry

**josef24** · 29/09/2007, 01h36

merci Thierry
Mais quand j'ai fais comme ça a ton code

Code :

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

1
2
3
4
5
6
// for (p = &maillon_1; p != NULL && compteur < 2; p = p->p_suivant)
    //{
       // compteur++;
    //}
    /* On modifie la valeur de maillon_3 */
    maillon_3.valeur = 40;

j'ai obtenu les mêmes résultat !!! donc on est pas obligé de parcourir la liste

et si la liste chaîne contient une taille grand plus que 4 par ex 100... je crois que se code sera très long

Code :

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

1
2
3
4
5
    maillon_1.p_suivant = &maillon_2;
    /*-tc- On fait pointer maillon_2 sur maillon_3 */
    maillon_2.p_suivant = &maillon_3;
    /*-tc- et ainsi de suite... */
    maillon_3.p_suivant = &maillon_4;

il y a pas une autre façon du chaînage ?

**Thierry Chappuis** · 29/09/2007, 02h44

Envoyé par josef24

Code :

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

1
2
3
 
    /* On modifie la valeur de maillon_3 */
    maillon_3.valeur = 40;

j'ai obtenu les mêmes résultat !!! donc on est pas obligé de parcourir la liste

J'avais ajouté le commentaire suivant:

Code :

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

1
2
3
/*-tc- pour accéder à une valeur contenue dans une liste chainee, on est
      obligé de parcourir la liste. Imaginons que nous voulons modifier la valeur
      de maillon_3 sans passer par l'intermédiaire de la variable maillon_3 */

C'était évidemment pour t'expliquer le principe... Je ne code pas une liste chainée comme cela.

Thierry

débutant besoin d'orientation

C

Discussions similaires

Partager

Partager