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
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
A voir également:
- Un programme séparant une liste chainée en deux
- Liste déroulante excel - Guide
- Deux comptes whatsapp - Guide
- Liste déroulante en cascade - Guide
- Programme demarrage windows 10 - Guide
- Deux ecran pc - Guide
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
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.
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.
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
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;
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)->val=p->val;
(*demi1)->nxt=NULL;
d1=*demi1;
printf("demi1=[");affichage(*demi1);
p=p->nxt;
if(p!=NULL){
(*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;
}
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;
}
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
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.
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.
21 mai 2015 à 16:27
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();
}
23 mai 2015 à 18:42
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. :-)