Ubuntu-fr

zephyre123

Question de compréhension sur une pile en langage C[RESOLU]

Bonjour,

Voici le code ci dessous, je me suis inspiré d'une vidéo de Jason champagne que l'on peut trouver ici , https://www.youtube.com/watch?v=zERZNLu … j&index=17

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

StackElement* new_stack(void)
{
	return NULL;
}

/*------------------------------------------------*/

Bool is_empty_stack(StackElement *stack)
{
	if (stack == NULL)
		return true;
	else
		return false;

}

/*------------------------------------------------*/

StackElement* push_stack(StackElement* stack, int x)
{
	StackElement* nouvelElement = malloc(sizeof(*nouvelElement));
	if (nouvelElement == NULL)
	{
		fprintf(stderr, "problement allocation dynamique de mémoire\n");
		exit(EXIT_FAILURE);
	}

	nouvelElement -> value = x;
	nouvelElement -> suivant = stack;

	return nouvelElement;

}

/*------------------------------------------------*/

StackElement* clear_stack(StackElement* stack)
{
	if (is_empty_stack(stack))
		return new_stack();

	StackElement* elementTemporaire = stack -> suivant;

	free(stack);

	return clear_stack(elementTemporaire);
}

/*------------------------------------------------*/

void affichage_pile(StackElement *stack)
{
	if (is_empty_stack(stack))
		printf("Aucun element à affihcher la pile est vide\n");

	else
	{
		while (!(is_empty_stack(stack)))
		{
			printf("[%d]\n", stack -> value);
			stack = stack -> suivant;
		}
	}
}
/*------------------------------------------------*/

StackElement* pop_stack(StackElement *stack)
{
	if (is_empty_stack(stack))
		return new_stack();

	StackElement* elementTemporaire = stack -> suivant;
	free(stack);

	return elementTemporaire;
}

/*------------------------------------------------*/

int lenght_stack(StackElement *stack)
{
	int lenght = 0;

	while (!is_empty_stack(stack))
	{
		lenght++;
		stack = stack -> suivant;
	}

	return lenght;
}

/*------------------------------------------------*/

int top_stack(StackElement *stack)
{
	if (is_empty_stack(stack))
		return -1;
	else
		return stack -> value;
}

/*------------------------------------------------*/

Voici ce que je ne comprends pas pourquoi les fonctions push, pop, on retourne un pointeur.
Il part ou ce pointeur ?
Et pourquoi on ne le récupère jamais et pourtant ça fonctionne à croire que c'est magique.
Pouvez vous m'aider svp.
S'il y a un truc dans la mémoire qui se fait pouvez vous me faire un dessin dans un hébergeur d'image par exemple ici https://pix.toile-libre.org/
Je suis désolé mais j'ai vraiment besoins d'un dessin pour comprendre ce qui se passe dans la mémoire.

Dernière modification par zephyre123 (Le 01/04/2020, à 18:46)

kevlar

Re : Question de compréhension sur une pile en langage C[RESOLU]

Bonsoir.
L'auteur appelle çà une pile, il n'a jamais du faire d'assembleur AMHA.
Ce programme ressemble beaucoup plus à une liste chaînée, par exemple aux GList fournies par la Glib sous Linux.
Cela retourne donc logiquement un pointeur sur l'élément de la liste.
Mon conseil : lire la littérature sur les listes chaînées, et çà ira tout seul.

zephyre123

Re : Question de compréhension sur une pile en langage C[RESOLU]

C'est grosso modo le même code source qu'il y a sur openclassroom
Mais j'ai compris ce que tu voulais dire.

Dernière modification par zephyre123 (Le 31/03/2020, à 18:29)

kevlar

Re : Question de compréhension sur une pile en langage C[RESOLU]

Parfait !
Une liste chaînée est en fait une structure, qui contient des données (data) et un pointeur sur l'élément ancètre et/ou l'élément sucesseur, selon que ce soit une liste doublement chaînée ou simplement chaînée.
J'utilise la même technique que- ci-dessus dans deux de mes applis pour gérer la fonction "undo" (annulation) ; par nostaligie, j'ai des fonctions pop et push, mais çà reste des listes chaînées, pas de vraies piles pour moi.
Bonne suite en programmation !

Zakhar

Re : Question de compréhension sur une pile en langage C[RESOLU]

Oui mais "fonctionnellement" c'est une pile, ou si vous voulez du LIFO (Last In First Out).

Après que la pile soit implémentée en liste chaînée, en hash, en stack, c'est de l'implémentation.

Ce qui est fait fonctionnellement une "pile" est qu'on empile et on dépile : par le dessus. Il faut imaginer qu'on a un stock d'assiettes, quand on range les assiettes on les met en haut de la pile, et quand on a besoin d'assiettes on les prend également au dessus de la pile, car l'assiette qu'on prend n'a strictement aucune importance (on suppose toutes les assiettes identiques).

A contrario, dans une "file d'attente" on ne veut pas faire ça. Quand un nouveau client arrive il se met "à la queue", et quand on sert un client, on sert "le début" de la file. Là on a plutôt "fonctionnellement" une liste puisque l'ordre d'arrivée est important. C'est alors du FIFO (First In First out).
Dans les deux cas on peut implémenter avec une liste chaînée, mais pour le FIFO le double chaînage est plus pratique car la file a "deux bouts", l'endroit où on empile, et l'endroit où on dépile, contrairement au LIFO.

Dernière modification par Zakhar (Le 01/04/2020, à 21:33)

---

"A computer is like air conditioning: it becomes useless when you open windows." (Linus Torvald)