Un programme séparant une liste chainée en deux

Fermé
nedercosmos Messages postés 4 Date d'inscription jeudi 21 mai 2015 Statut Membre Dernière intervention 15 novembre 2017 - 21 mai 2015 à 03:06
nedercosmos Messages postés 4 Date d'inscription jeudi 21 mai 2015 Statut Membre Dernière intervention 15 novembre 2017 - 5 janv. 2016 à 12:49
Bonjour les amis , je fais des études à distances en informatiques et notre enseignant nous a donné un devoir à faire en c dont l'une des questions est :

Soit la structure lliste définit comme suit :
#include <stdlib.h>

typedef struct element
{
int val;
struct element*nxt;
} element;
typedef element* llist;

3. Proposer ensuite un algorithme séparant une liste en deux. Etant donné une liste en entrée, un élément sur deux va dans la première liste et un élément sur deux va dans la deuxième liste.

" sachant que la 1 ère et la 2 ème question consistent à faire une fonction qui fusionne deux listes et une autre qui insère une valeur dans une liste trié. "


s'il vous plait que quelqu'un m'explique l'objectif de la question et me propose une solution avec explication de la démarche .
A voir également:

2 réponses

Alchimic Messages postés 60 Date d'inscription lundi 9 juillet 2012 Statut Membre Dernière intervention 15 février 2016 21
21 mai 2015 à 07:37
Bonjour, d'après la façon dont est posée la question je dirais que le but est le suivant :
Imaginons une liste nommée L0 triée passée en paramètre dont les éléments sont nommés Rn avec par exemple la propriété Rn<R(n+1) pour tout n.
On a :
L0 = R0->R1->R2->R3->R4->R5->R6 ...
La question demande de séparer en deux la liste avec 1 élément sur 2 dans la première liste et le suivant dans la seconde. On aura donc deux listes en sortie L1 et L2:
L1 = R0->R2->R4->R6 ...
et
L2 = R1->R3->R5-> ....
Les deux listes sont toujours triées (par la loi de composition) :
si Rn<R(n+1)<R(n+2) alors Rn<R(n+2)
Pour construire un tel algorithme, le plus simple est d'utiliser un compteur à incrémenter en parcourant la liste et d'appliquer un modulo 2 sur ce compteur.
Voici un pseudo code :

Si (compteur modulo 2=0)
On met l'élément de la chaine dans L1
Sinon
On met l'élément de la chaine dans L2

Il ne s'agit pas de la solution la plus optimale mais la plus simple selon moi.
Je vous laisse le soin de convertir ce principe en code. :-)
Espérant avoir répondu à vote question, n'hésitez pas à demander s'il y a des incompréhensions.
0
nedercosmos Messages postés 4 Date d'inscription jeudi 21 mai 2015 Statut Membre Dernière intervention 15 novembre 2017
21 mai 2015 à 16:27
je vous remercie Alchimic de votre prompte réponse.C'est très bien éxpliqué.
J'ai traduit ce que vous avez dit en un programme c qui fait une création d'une liste, la séparation dont on parle, et enfin l'affichage. Pas d'erreur de compilation signalé sauf que il y a une erreur d'Exécution (message qui dit que le l'exécutable cesse de fonctionner ) après le remplissage de la liste parent ,sachant que j'utilise l'éditeur dev c++ 4.9.9.2
s'il vous plait faites moi un petit look sur le programme et guidez moi vers les fautes et les problèmes présentes.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct element
{
int val;
element*nxt;
}element;
typedef element* list;

void creer(list l ,int taille) //créer une liste
{
list tete,p; int i;
tete=(list)malloc(sizeof(element));
printf("donnez l'element numero 1 : ");
scanf("%d",&tete->val);
tete->nxt=NULL;
l=tete;
for(i=1;i<taille;i++)
{
p=(list)malloc(sizeof(element));
printf("donnez l'element numero %d : ",i+1);
scanf("%d",&p->val);
p->nxt=NULL;
l->nxt=p;
l=p;
}
l=tete;
}


void separer(list l,list demi1,list demi2) //diviser une liste en deux
{ list p=l; list d1,d2,k; int i=1;

/*creer la tête de la premiere moitié (demi1) de la liste parent :*/
demi1=(list)malloc(sizeof(element));
demi1->val=p->val;
demi1->nxt=NULL;
p=p->nxt;
i++;
/*creer la tête de la 2 ème moitié (demi2) de la liste parent */
demi2=(list)malloc(sizeof(element));
demi2->val=p->val;
demi2->nxt=NULL;
p=p->nxt;
i++;

d1=demi1; d2=demi2;

while(p!=NULL)
{ if((i%2)!=0)
{
/*créer un nouveau élément de la liste (demi1) pour y mètre la valeur de P n°: i (impaire)*/
k=(list)malloc(sizeof(element));
k->val=p->val;
k->nxt=NULL;
d1->nxt=k;
d1=k;
p=p->nxt;
i++;
}
else
{
/*créer un nouveau élément de la liste demi2 pour y mètre la valeur de P n°: i (paire) */
k=(list)malloc(sizeof(element));
k->val=p->val;
k->nxt=NULL;
d2->nxt=k;
d2=k;
p=p->nxt;
i++;
}
}
}
void affichage(list l) //affiche une liste
{
list p;
p=l;
while(p!=NULL)
{
printf("%d -->",p->val);
p=p->nxt;
}

}

/*programme principal*/
int main(void)

{ list l,demi1,demi2; int taille=5;

creer(l,taille);
separer(l,demi1,demi2);
printf("la liste parent est :\n");
affichage(l);
printf("la 1 ere moitié est :\n");
affichage(demi1);
printf("la 2eme moitié est :\n");
affichage(demi2);
getch();
}
0
Alchimic Messages postés 60 Date d'inscription lundi 9 juillet 2012 Statut Membre Dernière intervention 15 février 2016 21 > nedercosmos Messages postés 4 Date d'inscription jeudi 21 mai 2015 Statut Membre Dernière intervention 15 novembre 2017
23 mai 2015 à 18:42
A première vue, je pense que le soucis vient du fait que dans "creer" vous donnez au pointeur " l " l'adresse de "p" dans la boucle for, par cela, le pointeur " l " est redirigé à chaque tour de boucle.
Je travaille sur un débogage du programme que je posterais dès qu'il sera fonctionnel si cela vous convient.

PS : attention avec les pointeurs, prenez garde à allouer la mémoire avant de déplacer le pointeur sur l'élément nouvellement créé. Descendre sur un pointeur NULL puis l'initialiser avec malloc provoque une rupture du chaînage. :-)
0
Alchimic Messages postés 60 Date d'inscription lundi 9 juillet 2012 Statut Membre Dernière intervention 15 février 2016 21
25 mai 2015 à 11:42
Voici une version de votre devoir, j'ai recodé vos fonctions en les renommant "creer2" et "separer2". Je vous invite à bien relire les modifications apportées.
Voici un lien qui devrait pouvoir vous éclairer sur l'utilisation de pointeurs en C (la réponse de : mathematician1975) :
https://stackoverflow.com/questions/13431108/changing-address-contained-by-pointer-using-function

Votre code modifié ci-dessous :

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

typedef struct element{
int val;
struct element *nxt;
}element;

typedef element* list;

void affichage(list l){ //affiche une liste
element *p;
p=l;
if(p!=NULL){
while(p->nxt!=NULL){
printf("%d-->",p->val);
p=p->nxt;
}
printf("%d]\n",p->val);
}
else
printf("]\n");
}

void creer(list l ,int taille) //créer une liste
{
list tete,p; int i;
tete=(list)malloc(sizeof(element));
printf("donnez l'element numero 0 : ");
scanf("%d",&tete->val);
tete->nxt=NULL;
l=tete;
for(i=0;i<taille-1;i++)
{
p=(list)malloc(sizeof(element));
printf("donnez l'element numero %d : ",i+1);
scanf("%d",&p->val);
p->nxt=NULL;
l->nxt=p;
l=p;
}
l=tete;
}

void creer2(list *l, int taille){
if(taille>0){
element *p;
int i;
  • l=malloc(sizeof(element));

printf("donnez l'element numero 1 : ");
scanf("%d",&(*l)->val);
(*l)->nxt=NULL;
p=*l;
printf("l=[");affichage(*l);
for(i=2;i<taille+1;++i){
p->nxt=malloc(sizeof(element));
printf("donnez l'element numero %d : ",i);
scanf("%d",&p->nxt->val);
p=p->nxt;
p->nxt=NULL;
printf("l=[");affichage(*l);
}
}
else
l=NULL;
printf("Liste crée\n");
}

void separer(list l,list demi1,list demi2) //diviser une liste en deux
{ list p=l; list d1,d2,k; int i=1;

/*creer la tête de la premiere moitié (demi1) de la liste parent :*/
demi1=malloc(sizeof(element));
demi1->val=p->val;
demi1->nxt=NULL;
p=p->nxt;
i++;
/*creer la tête de la 2 ème moitié (demi2) de la liste parent */
demi2=(list)malloc(sizeof(element));
demi2->val=p->val;
demi2->nxt=NULL;
p=p->nxt;
i++;

d1=demi1; d2=demi2;

while(p!=NULL)
{ if((i%2)!=0)
{
/*créer un nouveau élément de la liste (demi1) pour y mètre la valeur de P n°: i (impaire)*/
k=(list)malloc(sizeof(element));
k->val=p->val;
k->nxt=NULL;
d1->nxt=k;
d1=k;
p=p->nxt;
i++;
}
else
{
/*créer un nouveau élément de la liste demi2 pour y mètre la valeur de P n°: i (paire) */
k=(list)malloc(sizeof(element));
k->val=p->val;
k->nxt=NULL;
d2->nxt=k;
d2=k;
p=p->nxt;
i++;
}
}
}

void separer2(list l,list *demi1,list *demi2){ //diviser une liste en deux
element *p=l, *d1,*d2;
int i=2;
//il faut traiter la tête de list indépendamment de ses éléments
if(p!=NULL){
  • demi1=malloc(sizeof(element));

(*demi1)->val=p->val;
(*demi1)->nxt=NULL;
d1=*demi1;
printf("demi1=[");affichage(*demi1);
p=p->nxt;
if(p!=NULL){
  • demi2=(list)malloc(sizeof(element));

(*demi2)->val=p->val;
(*demi2)->nxt=NULL;
d2=*demi2;
printf("demi2=[");affichage(*demi2);
p=p->nxt;
while(p!=NULL){
if(i%2==0){
d1->nxt=(element*)malloc(sizeof(element));
d1->nxt->val=p->val;
d1=d1->nxt;
d1->nxt=NULL;
printf("demi1=[");affichage(*demi1);
}
else{
d2->nxt=(element*)malloc(sizeof(element));
d2->nxt->val=p->val;
d2=d2->nxt;
d2->nxt=NULL;
printf("demi2=[");affichage(*demi2);
}
p=p->nxt;
++i;
}
}
else
demi2=NULL;
}
else{
demi1=NULL;
demi2=NULL;
}
printf("sous-listes crées\n");
}

/*programme principal*/
int main(void) {
list l=NULL,demi1=NULL,demi2=NULL; int taille=0;
printf("entrez la taille de la liste principale l : ");
scanf("%d",&taille);
creer2(&l,taille);
printf("l=[");affichage(l);
printf("separation en deux sous liste demi1 et demi2 :\n");
separer2(l,&demi1,&demi2);
printf("la liste parent est :\nl=[");
affichage(l);
printf("la 1 ere moitié est :\ndemi1=[");
affichage(demi1);
printf("la 2eme moitié est :\ndemi2=[");
affichage(demi2);
//getch();
return 0;
}
0
nedercosmos Messages postés 4 Date d'inscription jeudi 21 mai 2015 Statut Membre Dernière intervention 15 novembre 2017
5 janv. 2016 à 12:49
un grand merci pour votre aide Alchimic. Je n'ai pas accédé a ce compte depuis la date de 21 mai 2015.En fait j'ai cru ne pas avoir de réponses.
Je vais tester ce code comme même bien que le devoir est passé voire l'année universitaire.
je suis maintenant seul (enfin que je sent) face à une autre dure année universitaire et d'autres problèmes avec autres langages de programmations.
Encore merci pour votre coopération.
0