Bonjour,

Voila je viens de rentré dans la chapitre des PILE.

Je suis des cours, en C, sur youtube. Et voila que je tombe sur cette structure pour faire une PILE :

1)

/* Définition d'une Pile */
typedef struct StackElement
{
  int value;
  struct StackElement *next;
}StackElement, *Stack;

Cette structure me paraissait ambigue, je suis partie dans le cours d'openclassroom et voila que je tombe sur cette structure :

1)

typedefstruct Element Element;

structElement{
  int nombre;
  Element* suivant;
};

typedefstruct Pile Pile;
struct Pile
{
  Element*premier;
};

Questions:

-Quel est la différence entre les deux méthodes pour construire une PILE ?

- Pour les deux strucutre (1 et 2),  comment s'explique le fait de typé un pointeur dans une structure qui porte le même nom de la strucutre ?

- 2) comment se fait-il que la structure peut avoir deux noms ? et à quoi pourra servir le deuxieme ? 

StackElement, *Stack;

Merci d'avance pour vos réponse

1) Je n'ai pas compris quand tu parles de maillon. Tu peux reformuler ton explication.

2)on peut avoir deux noms de la structure et utiliser l'un ou l'autre

1) Tu ne sais pas ce qu'est une pile ? Ce que j'appelle un maillon, c'est un objet (variable) du type de la structure pourquoi maillon car ils sont chaînés comme les maillons d'une chaîne via le pointeur next. Un autre lien sur les piles, si ça peux t'aider : https://chgi.developpez.com/pile/

2) Oui, 2, 3, 50... mais bon c'est pas vraiment utile. commence avec 1 ça devrait largement te suffire. Il ne faut pas vouloir tout manger en même temps.

comment s'explique le fait de typé un pointeur dans une structure qui porte le même nom de la strucutre ?

Le C permet la déclaration de types incomplets, c'est à dire des déclarations qui comprennent un identifiant pour un type d'objet (typiquement des struct, union voire des tableaux). à charge pour le programme de fournir plus tard la déclaration complète du type si le type doit être utilisé pour y stocker quelque chose ou en relation avec une opération qui nécessite de pouvoir en déterminer la taille.

Le typedef compliquant un peu les choses, prenons un exemple simple de déclaration de struct sans typedef.

Par exemple :

struct liste;
  
int main() {
    return 0;
}

est un programme C valable. De même :

struct liste * pliste;

int main() {
    return 0;
}

En effet, pour définir un pointeur sur un type, tu n'as pas besoin de connaître la taille du type à ce stade, le pointeur occupera en mémoire la taille gérée par la plateforme et l'implémentation du C pour les adresses mémoires, qui sera la même taille pour toutes les adresses (adressage 32 bits ou 64 bits).

Cette particularité permet de définir des struct qui contiennent des références à des pointeurs sur elles-mêmes.

struct liste;
struct liste {
    int valeur;
    struct liste * suivant;
};

int main() {
    return 0;
}

Dans ton exemple 2, tu as quelque chose qui ressemble à cela, et qui, de plus, déclare un alias de type (typedef).

Les déclaration du type incomplet dans ton exemple 2 prélable à la déclaration de la struct est juste utile pour définir l'alias avec le typedef qui permet de raccourcir ce que tu as à taper dans la déclaration complète qui suit. Dans l'exemple ci-dessus, d'ailleurs, la ligne 1 peut être omise car dans notre cas nous n’utilisons pas de typedef, et ceci suffit :

struct liste {
    int valeur;
    struct liste * suivant;
};

int main() {
    return 0;
}

Les déclaration de types incomplets ont d'autres utilités. Par exemple, en le plaçant dans un header (un .h) et en plaçant la déclaration du type complet dans l'implémentation (.c), tu vas pouvoir masquer le type réel de ta struct aux utilisateurs du module. Tu crées un type opaque à l'utilisateur, qui n'a pas besoin d'en connaître les détails, car il est utilisé en interne par le module. C'est une technique courante qui permet d'encapsuler les données. Mais... c'est une autre histoire.

Si tu comprends déjà ce qui est plus haut, cela sera bien.

-
Edité par Dlks 1 avril 2021 à 20:20:59

Hello,

il y plusieurs choses à comprendre :

• la structure de donnée abstraite PILE ;
• la structure de donnée abstraite LISTE ;
• comment une implémentation de LISTE peut permettre d'implémenter PILE ;
• comment implémenter LISTE en C.

En général quand un débutant entend le mot liste il pense immédiatement à un code comme celui que tu peux montrer en exemple. Il est néanmoins beaucoup plus simple dans un premier temps d'implémenter une pile avec juste un simple tableau … 

Le premier truc important est de définir l'interface. Par exemple pour manipuler une pile tu as besoin au minimum de quoi :

• créer une pile vide ;
• détruire une pile précédemment créée ;
• vérifier si elle est vide ou non ;
• obtenir la tête de la pile ;
• dépiler ;
• empiler une valeur.

t_stack *stack_new(void);
void stack_delete(t_stack *);

int stack_peek(t_stack *);
bool stack_is_empty(t_stack *);
t_stack_status stack_pop(t_stack *);
t_stack_status stack_push(t_stack *, int);

Ensuite pour l'implémentation réelle tu as le choix entre différentes techniques, mais si on part sur un simple tableau, quelque chose comme :

#define STACK_MAXSIZE (10000)

typedef struct {
    size_t size;
    int data[STACK_MAXSIZE];
} t_stack;

typedef enum {
    STACK_OK,
    STACK_ERROR,
    STACK_OVERFLOW,
    STACK_UNDERFLOW
} t_stack_status;

pourrait convenir.

Il faut bien séparer dans ta tête ce qu'est une pile, comment on la manipule, à quoi elle peut servir, quelle sont ses performances minimales … de comment on implémente une pile en C.

D'après ce que je comprend, IbBk suit le cours d'OC sur les piles et a trouvé des choses sur YouTube.
Le cours d'OC utilise des listes chaînées.
@White Crow:
Je suis néanmoins d'accord avec ton approche sur les fonctions de base pour gérer une pile.

PierrotLeFou a écrit:

@White Crow:
Je suis néanmoins d'accord avec ton approche sur les fonctions de base pour gérer une pile.

Ah ben oui, merci 😀

C'est un peu la base …

Donc si j'ai bien compris:

La strucutre de la pile :

struct liste;
struct liste {
    int valeur;
    struct liste * suivant;
};

Est une structure récursive. Ai-je bien compris la stru de la pile ?

Bah tu as une idée sur comment implémenter une pile en C en utilisant une liste simplement chaînée implémentée avec des pointeurs (oui je sais c'est long à écrire).

L'idée en programmation procédurale et structurée (oui c'est un peu ancien comme concept, mais beaucoup de concepts le sont ^_^), c'est non seulement de définir une structure de données (sdd, type en C si tu veux) mais également les primitives (fonction en C si tu veux) qui manipulent les données.

La panacée en plus c'est d'isoler l'implémentation par les primitives. On ne peut modifier les données qu'en passant par tes fonctions, jamais d'accès direct aux données.

C'est pour cela qu'on divise tout en programmation modulaire.

Dans le header4 (le .h), tu auras un type incomplet (non défini, juste déclaré) avec les prototypes des primitives →

typedef struct stack t_stack;

t_stack *stack_new(void);
void stack_delete(t_stack *);
 
int stack_peek(t_stack *);
bool stack_is_empty(t_stack *);
t_stack_status stack_pop(t_stack *);
t_stack_status stack_push(t_stack *, int);

et l'implémentation des primitives avec la déclaration du type dans le source associé.

S'il faut vraiment retenir une chose c'est qu'une pile c'est une structure de donnée qui permet de manipuler des données en les empilant, les dépilant, et en interrogeant la pile si elle contient ou non des éléments. C'est tout. Uniquement ce qu'on voit avec les primitives. Basta. Les primitives ont en général des complexités temporelles constantes (au moins en temps amorti) et spatiales linéaires.

Avoir le réflexe, pile ⇒ pointeur est typique du programmeur C qui n'a que peu de connaissances en algo. Mais ça s'arrange Bon, faut dire qu'on voit souvent ce genre de structure dans le chapitre consacré aux pointeurs …

Un truc pas cool, c'est que tu parle de pile, mais tu montres un source avec «liste» … On pourra t'en dire plus quand tu nous exhiberas tes primitives.

IbBk a écrit:

Est une structure récursive. Ai-je bien compris la structure de la pile ?

Je ne sais pas si le terme est le bon, mais ce qu'il faut comprendre, c'est surtout son fonctionnement !

White Crow a écrit:

Avoir le réflexe, pile ⇒ pointeur est typique du programmeur C qui n'a que peu de connaissances en algo. Mais ça s'arrange Bon, faut dire qu'on voit souvent ce genre de structure dans le chapitre consacré aux pointeurs …

C'est quand même un bon exercice pour s'apprendre à manipuler les pointeurs !

rouloude a écrit:

IWhite Crow a écrit:

Avoir le réflexe, pile ⇒ pointeur est typique du programmeur C qui n'a que peu de connaissances en algo. Mais ça s'arrange Bon, faut dire qu'on voit souvent ce genre de structure dans le chapitre consacré aux pointeurs …

C'est quand même un bon exercice pour s'apprendre à manipuler les pointeurs !

Oui, clairement. C'est juste que je déplore que bon nombre de dèv C n'en viennent plus qu'à penser ce genre de structure qu'en terme de pointeurs. C'est un peu similaire au fait que bon nombre de dèv pensent que les structures C sont les structures de données et vice-versa, en en oubliant que les données doivent être manipulées.