listes chainées

[dadabouin]

Bonjour,

Je précise tout d'abord que je travaille en c, sur compilateur visual studio, sous windows 7.
Je travaille sur les listes chainées, mon but ici est de réaliser une fonction permettant d'inverser une liste sans passer par une liste temporaire. Voici ,le code:

typedef struct Cell Cell;

typedef Cell* LcListe;

struct Cell
{
	int donnee;
	struct Cell* next;
};

LcListe retourne_liste_en_place(LcListe head)
{
	LcListe prev = NULL, cur = head, next = NULL;

	while (cur)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	
	return prev;
}

Sauf que cette fonction ne me renvoie que le premier élément de la liste. En remplacant le while par un for pour voir, le programme crash dès la deuxième itération. Je ne comprends pas pourquoi ca ne fonctionne pas...

Merci d'avance de votre aide bienvenue!
-----

[Jack]

Sauf que cette fonction ne me renvoie que le premier élément de la liste

1er élément de l'ancienne ou de la nouvelle liste?

Il me semble que tout est correct en tout cas. On peut voir le programme de test?

[dadabouin]

Déjà merci pour cette réponse rapide!

Le premier élément de l'ancienne liste.
Voilà le main, ya d'autres fonctions avant qui marchent, ca pose pas de souci:

int main()
{
	/*Création d'une liste*/
	maListe = initListe(10);
	printf("** afficheListe() ** \n[ ");
	afficheListe(maListe);
	printf(" ]\n");

	/*Insertion En tête*/
	maListe = insertionEnTete(maListe, 17);
	printf("** afficheListe() ** \n[ ");
	afficheListe(maListe);
	printf(" ]\n");

	/*Insertion En Queue*/
	maListe = insertionEnQueue(maListe, 6);
	printf("** afficheListe() ** \n[ ");
	afficheListe(maListe);
	printf(" ]\n");

	/*Moyenne de la liste */
	printf("Moyenne(Liste) = %.2f\n", moyenne(maListe));

	/*Supprimer un element */
	maListe = supprimerElement(maListe, 9);
	printf("** afficheListe() ** \n[ ");
	afficheListe(maListe);
	printf(" ]\n");

	/*Copier une liste vers une autre liste dans l'odre inverse */
	retourne_liste_copie(maListe);
	printf("** afficheListe() ** \n[ ");
	afficheListe(retourne_liste_copie(maListe));
	printf(" ]\n");

	system("pause");
	return 0;
}

[Jack]

je veux bien tester, mais il me faut le code des autres fonctions, au moins l'insertion en tête.

PS: pas la peine, elle n'est pas bien compliquée

[A voir en vidéo sur Futura]

[dadabouin]

Voici le code complet :

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



LcListe initListe(int nb)
{
	LcListe curr, head;
	int i;
	head = NULL;

	for (i = 0; i<nb; i++)
	{
		curr = (LcListe)malloc(sizeof(Cell));
		curr->donnee = rand() % 100 + 1;
		curr->next = head;
		head = curr;
	}
	return head;
}

LcListe insertionEnTete(LcListe head, int valeur)
{
	LcListe curr;
	curr = (LcListe)malloc(sizeof(Cell));
	curr->donnee = valeur;
	curr->next = head;
	return curr;
}


LcListe insertionEnQueue(LcListe head, int valeur)
{
	LcListe curr = head, add = (LcListe)malloc(sizeof(Cell));
	add->donnee = valeur;
	add->next = NULL;
	while (curr->next != NULL)
	{
		curr = curr->next;
	}

	curr->next = add;
	return head;
}

void afficheListe(LcListe head)
{
	LcListe curr = head;
	while (curr != NULL)
	{
		printf("%d ", curr->donnee);
		curr = curr->next;
	}
}

float moyenne(LcListe head)
{
	LcListe curr = head; float somme = 0; int i = 0;
	while (curr != NULL)
	{
		i++;
		somme = somme + curr->donnee;
		curr = curr->next;
	}
	return somme / i;
}

LcListe supprimerElement(LcListe head, int n)
{
	LcListe curr = head, aux = head, aux2 = head; int j = 0;

	for (j = 0; j<n - 2; j++)
	{
		curr = curr->next;
		aux = aux->next;
	}

	aux = aux->next;
	aux2 = aux;
	aux = aux->next;
	curr->next = aux;
	free(aux2);

	return head;
}

LcListe retourne_liste_copie(LcListe head)
{
	LcListe h = NULL;
	while (head)
	{
		h = insertionEnTete(h, head->donnee);
		head = head->next;
	}
	return h;
}

Merci d'y mettre autant de bonne volonté, je m'en étonne encore Oo merci

[Jack]

Je viens de tester. Comme prévu l'inversion de la liste s'effectue correctement.

Qu'est ce qui te fait dire que ça ne fonctionne pas? Quel est ton test?

[Jack]

Nos messages se sont croisés. Ce que j'ai testé, c'est retourne_liste_en_place.

[dadabouin]

Sapristi!

Je comprends pas pourquoi ca veut pas...

Si je fais juste ca :

	/*Création d'une liste*/
	maListe = initListe(10);
	printf("** afficheListe() ** \n[ ");
	afficheListe(maListe);
	printf(" ]\n");

	/*Copier une liste dans la liste elle meme dans l'odre inverse */
	retourne_liste_en_place(maListe);
	printf("** afficheListe() ** \n[ ");
	afficheListe(retourne_liste_en_place(maListe));
	printf(" ]\n");

ca crash, comme si le programme bouclait.

J'ai pas pensé, voilà les entêtes, on sait jamais :

/****************************Fichier de spécification
Contient les définitions de constantes et les prototypes de fonctions
**************************/

#ifndef LISTE_H
#define LISTE_H

/**brief      Définition de la nature des éléments de la liste
*              Ici ce sont des pointeurs d entiers.
*/

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

/**
*  \typedef    Cell
*  \brief      Définition du type des Cellules qui composent les listes
*/
typedef struct Cell Cell;
/**
*  \struct     Cell
*  \brief      Définition de la structure d'une Cell
*/
struct Cell
{
	/**         L'information enregistrée dans la cellule*/
	int donnee;
	/**         Le pointeur sur la cellule suivante              */
	struct Cell* next;
};

typedef Cell* LcListe;

LcListe initListe(int nb);
LcListe insertionEnTete(LcListe head, int valeur);
LcListe insertionEnQueue(LcListe head, int valeur);
void afficheListe(LcListe head);
float moyenne(LcListe head);
LcListe supprimerElement(LcListe head, int n);
LcListe retourne_liste_copie(LcListe head);
LcListe retourne_liste_en_place(LcListe head);
LcListe insertion_iterat(LcListe head);
LcListe insertion_recur(LcListe head);
LcListe decoupe(LcListe head);
LcListe fusion(LcListe head1, LcListe head2);
LcListe tri(LcListe head);

#endif

[Jack]

Voici ce que j'ai essayé. ca affiche bien 12 8 5 , puis 5 8 12 après inversion

#include <iostream>

typedef struct Cell Cell;


typedef Cell* LcListe;


struct Cell
{
	int donnee;
	struct Cell* next;
};


LcListe insertionEnTete(LcListe l, int data){
	LcListe temp = new Cell;
	temp->donnee = data;
	temp->next = l;
	return temp;
}


LcListe retourne_liste_en_place(LcListe head)
{
	LcListe prev = NULL, cur = head, next = NULL;


	while (cur)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}


	return prev;
}


void afficheListe(LcListe l){
	while (l != NULL){
		std::cout << l->donnee << "  ";
		l = l->next;
	}
	std::cout << std::endl;
}


int main(){
	LcListe maListe = NULL;
	maListe = insertionEnTete(maListe, 5);
	maListe = insertionEnTete(maListe, 8);
	maListe = insertionEnTete(maListe, 12);
	afficheListe(maListe);
	maListe = retourne_liste_en_place(maListe);
	afficheListe(maListe);


	return 0;
}

PS: je dois partir. Je ne serai pas de retour avant la toute fin de soirée. Bon courage.

[dadabouin]

Ok effectivement ca fonctionne...Merci beaucoup pour cette aide rapide, efficace et généreuse, ça fait plaisir!

Bonne continuation!