Bonjour, je souhaite implémenter une pile à l'aide d'une liste chainée. J'ai déjà implémenté une liste chainée : 

typedef struct List *PList;

struct List {
  D element;
  struct List *next;
};

/* Pre-condition : list is non-empty */
static void setNext(PList, PList);

/*Pre-condition : list is non-empty */
static void setElement(PList, D);

PList emptyList() {
  return NULL;
}

PList getNext(PList list) {
  return list->next;
}

void setNext(PList list, PList p) {
  list->next = p;
}

D getElement(PList list) {
  return list->element;
}

void setElement(PList list, D x) {
  list->element = x;
}

bool isEmptyList(PList list) {
  return list == NULL;
}

PList addAtTheBeginning(PList list, D x) {
  PList p = malloc(sizeof(struct List));
  if (p == NULL) {
    fprintf(stderr, "Error: addAtTheBeginning: malloc");
    exit(1);
  }
  setElement(p, x);
  setNext(p, list);
  return p;
}

  J'ai commencé à faire ces fonctions mais je ne suis pas sur si quelqu'un peut m'expliquer 

Stack emptyStack() {
return NULL;
}
 
D getTop(Stack s) {
return s->array[s->top];
}
 
void push(Stack s, D x) {
s->array[++s->top] = x;
}
 
void pop(Stack s) {
s->top--;
}
 
bool isEmptyStack(Stack s) {
return s->top == -1;
}

Je ne sais pas quoi mettre en typedef j'ai l'impression que j'ai pas utilisé finalement ma liste 

Tu veux faire de ta liste chaînée une pile, il suffit de lui rajouter une fonction qui retire et retourne le dernier élément entrée.

PS : tu ne devrais pas utiliser un type pointeur pour représenter ta liste, c'est source de complications et ça ne facilite pas la lecture. 

rouIoude a écrit:

Tu veux faire de ta liste chaînée une pile, il suffit de lui rajouter une fonction qui retire et retourne le dernier élément entrée.

PS : tu ne devrais pas utiliser un type pointeur pour représenter ta liste, c'est source de complications et ça ne facilite pas la lecture. 

===>  Je ne veux pas rajouter une fonction à ma liste car après je vais implémenter avec un tableau et je je ferai un seul tri (une fonction qui trie la pile que ce soit celle implémentée avec une liste chainée ou avec un tableau)

-
Edité par ManaMana2 19 janvier 2022 à 17:56:14

Trier une pile ? Mais ce n'est plus une pile alors !

Donc si tu ne veux pas rajouter de fonction à ta liste, du va devoir faire ta pile à partir de zéro ! Surtout qu'a priori, elle comporte des champs qui ne sont pas dans ta liste.

PS : Ta liste à beaucoup de fonctions (c'est bien de faire des fonctions), mais n'en a t'elle pas un peu trop ?

Moi non plus je ne comprend pas: une pile triée?
Pour faire une pile avec une liste chaînée, tu as besoin de 3 fonctions:
+ créer la liste (descripteur de liste)
+ fonction qqui ajoute (push)
+ fonction qui retire (pop)
Et en bonus, une fonction qui fait un free sur les éléments réservés par malloc.
Ça se fait une fonction qui ajoute les éléments dans une liste chaînées en les maintenant dans l'ordre, mais je n'appelle pas ça une pile.

edit:

+ une fonction qui vérifie si la pile est vide.

-
Edité par PierrotLeFou 19 janvier 2022 à 18:39:02

Les fonctions Puch (empiler) et pop (dépiler) c'est ce que j'ai essayé de faire mais c'est encore flou pour moi. Je veux faire le lien avec ma liste chainée et la pile que je souhaite implémenter avec cette liste

ManaMana2 a écrit:

Je veux faire le lien avec ma liste chainée et la pile que je souhaite implémenter avec cette liste

Faire le lien entre une liste chaînée et une pile ça veux dire quoi pour toi ?

Ta liste n'a pas de fonction pour soutirer un élément et tu ne veux pas en faire une ! Donc ce n'est pas possible d'en faire une pile !

Pour moi le mieux, c'est de faire une pile sans utiliser ta liste.

Sur ta liste la fonction addAtTheBeginning pourrait être utilisé comme fonction push, mais il te faut une fonction pop.

Mais bon, pour que tu ai des réponses pertinente, il faut décrire précisément ce que tu veux faire !

Pour bien gérer une liste chaînée, ça te prend deux structures:
+ le descripteur de liste (ou tête de liste)
+ les maillons de cette liste.
Ici, tu n'as qu'une structure.
Dans les fonctions, on passe comme argument le descripteur de liste et ce qu'il faut d'autre s'il y a lieu:
typedef struct Item Item;
struct Item {
    type data;   // type peut être plusieurs choses (int, float, double, ...).
    Item *next;
};
typedef struct Pile Pile;
struct Pile {
    Item *first;
    int length;
};

Il faut d'abord créer la liste:

Pile *creerPile();

Par exemple pour le push:
void push(Pile *pile, type item);   // ou *item si c'est un élément complexe réservé par malloc.
type pop(Pile *pile);
bool isempty(Pile *pile);
void destroy(Pile *pile);

-
Edité par PierrotLeFou 19 janvier 2022 à 19:28:15

Tu peux me montrer comment utiliser addAtTheBeginning comme push 

rouIoude a écrit:

ManaMana2 a écrit:

Je veux faire le lien avec ma liste chainée et la pile que je souhaite implémenter avec cette liste

Faire le lien entre une liste chaînée et une pile ça veux dire quoi pour toi ?

Ta liste n'a pas de fonction pour soutirer un élément et tu ne veux pas en faire une ! Donc ce n'est pas possible d'en faire une pile !

Pour moi le mieux, c'est de faire une pile sans utiliser ta liste.

Sur ta liste la fonction addAtTheBeginning pourrait être utilisé comme fonction push, mais il te faut une fonction pop.

Mais bon, pour que tu ai des réponses pertinente, il faut décrire précisément ce que tu veux faire !

ManaMana2 a écrit:

Tu peux me montrer comment utiliser addAtTheBeginning comme push 

Tu n'as rien à changer, tu peux l'utiliser tel quel est.

Push ajoute un élément à la liste.

addAtTheBeginning fait la même chose.

-
Edité par rouIoude 19 janvier 2022 à 19:35:30

Bonjour,

quitte à faire quelque chose, autant faire quelque chose de propre

Une pile c'est une structure de donnée abstraite, les primitives que l'on définit usuellement sont au minimum :

• create : pour créer une pile vide ;
• top : pour accéder à la valeur en tête de pile ;
• push : pour empiler une valeur ;
• pop : pour dépiler la pile ;
• is_empty : pour vérifier si la pile est vide.

Ici je prends le parti de de ne pas renvoyer une valeur par pop, la valeur en tête pouvant être lue via top. Il faudra sans doute aussi penser à définir une fonction de libération (toujours en C). Comme le C ne gère pas la généricité aisément je prendrai l'exemple (plutôt classique) d'une pile d'entiers.

Une api possible pour une pile d'entiers en C peut être :

typedef struct int_stack;

struct int_stack *int_stack_create(void);
void int_stack_delete(struct int_stack *);

int int_stack_top(struct int_stack *);
void int_stack_push(struct int_stack *, int);
void int_stack_pop(struct int_stack *);

bool int_stack_is_empty(struct int_stack *);

Tu peux imaginer avoir d'autres fonctions comme une qui te renvoie le nombre d'éléments présents dans la pile = sa longueur, ou une autre qui renvoie sa capacité si elle est limitée, voire une qui la clone ou  encore une qui la trie …

Tu peux aussi imaginer une api dont chaque fonction renverrai un code d'erreur qui te permettrait de gérer plus facilement les erreur d'over/under flow au niveau supérieur …

Si tu décides d'implémenter une liste non plus d'entiers mais de pointeurs sur qqch alors il te faudra décider qui sera propriétaire des données pointées (transfert de propriété vs copie des données) …

Ensuite que tu l'implémentes en utilisant une liste chaînée ou un tableau peu importe.

Une implémentation utilisant une liste chaînée ou non d'entiers pourrait être par exemple :

struct int_stack {
    size_t length;
    struct int_list *int_list;
};

struct int_stack *int_stack_create(void) {
    struct int_stack *new=malloc(sizeof *new);
    if (new) {
        *new = (struct int_stack) {
                   .length=0,
                   .int_list = int_list_create(),
               };
        if (new->int_list) {
            return new;
        } else {
            free(new);
            return NULL;
        }
    } else {
        return NULL;
    }
}

void int_stack_delete(struct int_stack *is) {
    if (is) {
        int_list_destroy(is->int_list);
        free(is);
    }
}

int int_stack_top(struct int_stack *is) {
    assert(is && is->length!=0);
    return int_list_head(is->int_list);
}

void int_stack_push(struct int_stack *is, int value) {
    assert(is);
    int_list_prepend(is->int_list, value);
    is->length++;
}

void int_stack_pop(struct int_stack *is) {
    assert(is && is->length>0);
    int_list_remove_first(is->int_list);
    is->length--;
}

bool int_stack_is_empty(struct int_stack *is)
{
    assert(is);
    return is->length==0;
}

Et là tu vois que tu n'as pas à te soucier de l'implémentation de ta liste … tant qu'elle est correcte.

Bon il y a pas mal de partis pris dans le code montré (disclaimer : il a été fait en mode quick and dirty).

Même si c'est très chiant, tu peux même implémenter un tri en n'utilisant que les fonctions définies ci-dessus sans jamais à avoir à te soucier de l'implémentation de ta pile.

-
Edité par White Crow 19 janvier 2022 à 23:32:58

Merci pour ton aide.

Possible de faire en gardant les memes prototypes que j'ai mis et sans passer par create stack 

Je veux implémenter avec stack s ==> une pile s

Stack emptyStack() {
return NULL;
}
  
D getTop(Stack s) {
return s->array[s->top];
}
  
void push(Stack s, D x) {
s->array[++s->top] = x;
}
  
void pop(Stack s) {
s->top--;
}
  
bool isEmptyStack(Stack s) {
return s->top == -1;
}

White Crow a écrit:

Bonjour,

quitte à faire quelque chose, autant faire quelque chose de propre

Une pile c'est une structure de donnée abstraite, les primitives que l'on définit usuellement sont au minimum :

• create : pour créer une pile vide ;
• top : pour accéder à la valeur en tête de pile ;
• push : pour empiler une valeur ;
• pop : pour dépiler la pile ;
• is_empty : pour vérifier si la pile est vide.

Ici je prends le parti de de ne pas renvoyer une valeur par pop, la valeur en tête pouvant être lue via top. Il faudra sans doute aussi penser à définir une fonction de libération (toujours en C). Comme le C ne gère pas la généricité aisément je prendrai l'exemple (plutôt classique) d'une pile d'entiers.

Une api possible pour une pile d'entiers en C peut être :

typedef struct int_stack;

struct int_stack *int_stack_create(void);
void int_stack_delete(struct int_stack *);

int int_stack_top(struct int_stack *);
void int_stack_push(struct int_stack *, int);
void int_stack_pop(struct int_stack *);

bool int_stack_is_empty(struct int_stack *);

Tu peux imaginer avoir d'autres fonctions comme une qui te renvoie le nombre d'éléments présents dans la pile = sa longueur, ou une autre qui renvoie sa capacité si elle est limitée, voire une qui la clone ou  encore une qui la trie …

Tu peux aussi imaginer une api dont chaque fonction renverrai un code d'erreur qui te permettrait de gérer plus facilement les erreur d'over/under flow au niveau supérieur …

Si tu décides d'implémenter une liste non plus d'entiers mais de pointeurs sur qqch alors il te faudra décider qui sera propriétaire des données pointées (transfert de propriété vs copie des données) …

Ensuite que tu l'implémentes en utilisant une liste chaînée ou un tableau peu importe.

Une implémentation utilisant une liste chaînée ou non d'entiers pourrait être par exemple :

struct int_stack {
    size_t length;
    struct int_list *int_list;
};

struct int_stack *int_stack_create(void) {
    struct int_stack *new=malloc(sizeof *new);
    if (new) {
        *new = (struct int_stack) {
                   .length=0,
                   .int_list = int_list_create(),
               };
        if (new->int_list) {
            return new;
        } else {
            free(new);
            return NULL;
        }
    } else {
        return NULL;
    }
}

void int_stack_delete(struct int_stack *is) {
    if (is) {
        int_list_destroy(is->int_list);
        free(is);
    }
}

int int_stack_top(struct int_stack *is) {
    assert(is && is->length!=0);
    return int_list_head(is->int_list);
}

void int_stack_push(struct int_stack *is, int value) {
    assert(is);
    int_list_prepend(is->int_list, value);
    is->length++;
}

void int_stack_pop(struct int_stack *is) {
    assert(is && is->length>0);
    int_list_remove_first(is->int_list);
    is->length--;
}

bool int_stack_is_empty(struct int_stack *is)
{
    assert(is);
    return is->length==0;
}

Et là tu vois que tu n'as pas à te soucier de l'implémentation de ta liste … tant qu'elle est correcte.

Bon il y a pas mal de partis pris dans le code montré (disclaimer : il a été fait en mode quick and dirty).

Même si c'est très chiant, tu peux même implémenter un tri en n'utilisant que les fonctions définies ci-dessus sans jamais à avoir à te soucier de l'implémentation de ta pile.

-
Edité par White Crow il y a environ 8 heures

-
Edité par ManaMana2 20 janvier 2022 à 8:31:46

Arrêtes de mettre en copie les posts à chaque fois que tu réponds !

Ton code de pile, n'a rien à voir avec le code de ta liste puisqu'il est basé sur un tableau ! Il ne faut pas tout mélanger, sinon on y comprend plus rien !

A priori ta fonction qui crée la pile, c'est : emptyStack mais tu devrais le savoir puisque c'est ton code ! Mais il va bien falloir que le pointeur pointe sur quelque chose de valide !

Tu devrais poster la structure Stack, car on ne connait la nature de ton tableau array (il est créé sur le tas ou la pile ?)

Quand tu ajoutes un élément avec push, il faut t'assurer que tu ne sort pas du tableau, sinon ça va planter à un moment ou à un autre !

PS : tu fais des fonctions de liste de pile, mais je ne vois à aucun moment un code qui les manipules ? Tu ne les testes donc jamais ?