Algorithme liste circulaire
Fermé
youkisall
Messages postés
20
Date d'inscription
lundi 12 novembre 2007
Statut
Membre
Dernière intervention
5 juin 2011
-
11 oct. 2008 à 22:13
MetaHack Messages postés 14 Date d'inscription jeudi 17 juillet 2008 Statut Membre Dernière intervention 14 septembre 2010 - 12 juin 2009 à 01:49
MetaHack Messages postés 14 Date d'inscription jeudi 17 juillet 2008 Statut Membre Dernière intervention 14 septembre 2010 - 12 juin 2009 à 01:49
A voir également:
- Liste circulaire algorithme
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Liste de diffusion whatsapp - Guide
- Gertrude a préparé la liste des affaires à prendre pour l'excursion. juliette a modifié cette liste en utilisant le mode suivi des modifications proposé par le traitement de texte. - Guide
- Liste site streaming illégal - Accueil - Services en ligne
2 réponses
MetaHack
Messages postés
14
Date d'inscription
jeudi 17 juillet 2008
Statut
Membre
Dernière intervention
14 septembre 2010
32
12 juin 2009 à 01:49
12 juin 2009 à 01:49
Bonjour , le 11 octobre 2008 :D
voila je vous propose une solution qui consiste à réaliser une fonction qui reçoit l'adresse d'une liste et divise cette liste en deux sous listes, en utilisant une autre fonction qui calcule la taille d'une liste simple circulaire:
cette fonction retourne l'adresse de la 1ere sous liste;
et l'adresse de la 2eme sous liste , c'est l'adresse de la liste initiale càd l'adresse reçu en paramètre voila un exemple pour mieux comprendre:
L1=diviser_2(&lst);
printf("\n\n\n les éléments de la première liste : "); afficher(L1);
printf("\n\n la taille de la première liste est : %d",lenght(L1));
printf("\n\n\n les éléments de la deuxième liste : "); afficher(lst);
printf("\n\n la taille de la deuxième liste est : %d",lenght(lst));
lst : c'est la liste qu'on veut diviser.
diviser_2(&lst); divise la liste en deux , et retourne l'adresse de la 1ere sous liste.
L1 : c'est l'adresse de la 1ere liste.
lst : maintenant lst contient l'adresse de la 2eme liste
lst : 1->2->3->4->5->6
diviser_2(&lst);
L1 : 1->2->3
lst : 4->5->6
liste diviser_2(liste *L)
{int taille=lenght(*L);// la taille de la liste
int NbrL1=0; // une variable qui calcule à chaque fois le nombre d'élément de la 1ere sous liste
liste parcourir = *L , adr_L1 = *L , sauv;
if(parcourir)// tester d'abord si la liste n'est pas vide
{while(parcourir = parcourir->suiv , NbrL1++ , NbrL1 < (taille/2) );
adr_L1 = parcourir; // l'adresse de la 1ere liste
sauv = parcourir->suiv; // si on sauvegarde pas cette adresse on risque de la perdre en découpant
parcourir->suiv = (*L)->suiv ;// on fait le chainage de la 1ere sous liste
(*L)->suiv = sauv; // on relie l'ancienne liste avec le nouveau élément
}
return adr_L1;
}
NB : si on fait pas le test if(parcourir) càd if(parcourir != NULL)
si jamais la liste est vide càd lst=NULL alors parcourir = NULL, donc si on fait pas ce test alors on va passé à la boucle while , après lors de l'exécution de parcourir = parcourir->suiv le programme s'arrête ERREUR car parcourir == NULL donc parcourir->suiv n'a pas de sens .
pour la fonction qui retourne la taille d'une liste circulaire :
int lenght(liste lst)
{liste p=lst; int l=0;
if(p)while(p=p->suiv,l++,p!=lst);
return l;
}
pour tester cette fonction voila un programme :
prog.cpp
//****************** Ouadie Boussaid 2°IIR3 EMSI****************************
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
typedef int typeElem;
typedef struct noeud
{ typeElem val;
struct noeud *suiv;
};
typedef struct noeud* liste;
liste remplir()
{liste L=NULL,;
struct noeud *nouv,*der=NULL;
typeElem val;
printf("\n donner les valeurs de la liste (0 pour sortir) : ");
scanf("%d",&val);
if(val){
nouv=(noeud*)malloc(sizeof(struct noeud));
L=nouv;
der=nouv;
nouv->val=val;
nouv->suiv=L;
while(scanf("%d",&val), val!=0
&& ( nouv=(noeud*)malloc(sizeof(struct noeud)) ))
{
nouv->val=val;
nouv->suiv=L;
der->suiv=nouv;
der=nouv;
}}
return der;
}
int lenght(liste lst)
{liste p=lst; int l=0;
if(p)while(p=p->suiv,l++,p!=lst);
return l;
}
liste diviser_2(liste *L)
{int taille=lenght(*L);// la taille de la liste
int NbrL1=0; // une variable qui calcule à chaque fois le nombre d'élément de la 1ere sous liste
liste parcourir = *L , adr_L1 = *L , sauv;
if(parcourir)// tester d'abord si la liste n'est pas vide
{while(parcourir = parcourir->suiv , NbrL1++ , NbrL1 < (taille/2) );
adr_L1 = parcourir; // l'adresse de la 1ere liste
sauv = parcourir->suiv; // si on sauvegarde pas cette adresse on risque de la perdre en découpant
parcourir->suiv = (*L)->suiv ;// on fait le chainage de la 1ere sous liste
(*L)->suiv = sauv; // on relie l'ancienne liste avec le nouveau élément
}
return adr_L1;
}
void afficher(liste lst)
{liste p=lst;
if(p)while(p=p->suiv,printf("%d->",p->val),p!=lst);
}
main()
{liste lst,L1; int x;
lst=remplir();
printf("\n les éléments de la liste : ");
afficher(lst);
printf("\n\n la taille de la liste est : %d",lenght(lst));
L1=diviser_2(&lst);
printf("\n\n\n les éléments de la première liste : ");
afficher(L1);
printf("\n\n la taille de la première liste est : %d",lenght(L1));
printf("\n\n\n les éléments de la première liste : ");
afficher(lst);
printf("\n\n la taille de la première liste est : %d",lenght(lst));
getch(); }
///********************************************
voila je vous propose une solution qui consiste à réaliser une fonction qui reçoit l'adresse d'une liste et divise cette liste en deux sous listes, en utilisant une autre fonction qui calcule la taille d'une liste simple circulaire:
cette fonction retourne l'adresse de la 1ere sous liste;
et l'adresse de la 2eme sous liste , c'est l'adresse de la liste initiale càd l'adresse reçu en paramètre voila un exemple pour mieux comprendre:
L1=diviser_2(&lst);
printf("\n\n\n les éléments de la première liste : "); afficher(L1);
printf("\n\n la taille de la première liste est : %d",lenght(L1));
printf("\n\n\n les éléments de la deuxième liste : "); afficher(lst);
printf("\n\n la taille de la deuxième liste est : %d",lenght(lst));
lst : c'est la liste qu'on veut diviser.
diviser_2(&lst); divise la liste en deux , et retourne l'adresse de la 1ere sous liste.
L1 : c'est l'adresse de la 1ere liste.
lst : maintenant lst contient l'adresse de la 2eme liste
lst : 1->2->3->4->5->6
diviser_2(&lst);
L1 : 1->2->3
lst : 4->5->6
liste diviser_2(liste *L)
{int taille=lenght(*L);// la taille de la liste
int NbrL1=0; // une variable qui calcule à chaque fois le nombre d'élément de la 1ere sous liste
liste parcourir = *L , adr_L1 = *L , sauv;
if(parcourir)// tester d'abord si la liste n'est pas vide
{while(parcourir = parcourir->suiv , NbrL1++ , NbrL1 < (taille/2) );
adr_L1 = parcourir; // l'adresse de la 1ere liste
sauv = parcourir->suiv; // si on sauvegarde pas cette adresse on risque de la perdre en découpant
parcourir->suiv = (*L)->suiv ;// on fait le chainage de la 1ere sous liste
(*L)->suiv = sauv; // on relie l'ancienne liste avec le nouveau élément
}
return adr_L1;
}
NB : si on fait pas le test if(parcourir) càd if(parcourir != NULL)
si jamais la liste est vide càd lst=NULL alors parcourir = NULL, donc si on fait pas ce test alors on va passé à la boucle while , après lors de l'exécution de parcourir = parcourir->suiv le programme s'arrête ERREUR car parcourir == NULL donc parcourir->suiv n'a pas de sens .
pour la fonction qui retourne la taille d'une liste circulaire :
int lenght(liste lst)
{liste p=lst; int l=0;
if(p)while(p=p->suiv,l++,p!=lst);
return l;
}
pour tester cette fonction voila un programme :
prog.cpp
//****************** Ouadie Boussaid 2°IIR3 EMSI****************************
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
typedef int typeElem;
typedef struct noeud
{ typeElem val;
struct noeud *suiv;
};
typedef struct noeud* liste;
liste remplir()
{liste L=NULL,;
struct noeud *nouv,*der=NULL;
typeElem val;
printf("\n donner les valeurs de la liste (0 pour sortir) : ");
scanf("%d",&val);
if(val){
nouv=(noeud*)malloc(sizeof(struct noeud));
L=nouv;
der=nouv;
nouv->val=val;
nouv->suiv=L;
while(scanf("%d",&val), val!=0
&& ( nouv=(noeud*)malloc(sizeof(struct noeud)) ))
{
nouv->val=val;
nouv->suiv=L;
der->suiv=nouv;
der=nouv;
}}
return der;
}
int lenght(liste lst)
{liste p=lst; int l=0;
if(p)while(p=p->suiv,l++,p!=lst);
return l;
}
liste diviser_2(liste *L)
{int taille=lenght(*L);// la taille de la liste
int NbrL1=0; // une variable qui calcule à chaque fois le nombre d'élément de la 1ere sous liste
liste parcourir = *L , adr_L1 = *L , sauv;
if(parcourir)// tester d'abord si la liste n'est pas vide
{while(parcourir = parcourir->suiv , NbrL1++ , NbrL1 < (taille/2) );
adr_L1 = parcourir; // l'adresse de la 1ere liste
sauv = parcourir->suiv; // si on sauvegarde pas cette adresse on risque de la perdre en découpant
parcourir->suiv = (*L)->suiv ;// on fait le chainage de la 1ere sous liste
(*L)->suiv = sauv; // on relie l'ancienne liste avec le nouveau élément
}
return adr_L1;
}
void afficher(liste lst)
{liste p=lst;
if(p)while(p=p->suiv,printf("%d->",p->val),p!=lst);
}
main()
{liste lst,L1; int x;
lst=remplir();
printf("\n les éléments de la liste : ");
afficher(lst);
printf("\n\n la taille de la liste est : %d",lenght(lst));
L1=diviser_2(&lst);
printf("\n\n\n les éléments de la première liste : ");
afficher(L1);
printf("\n\n la taille de la première liste est : %d",lenght(L1));
printf("\n\n\n les éléments de la première liste : ");
afficher(lst);
printf("\n\n la taille de la première liste est : %d",lenght(lst));
getch(); }
///********************************************
Posotaz
Messages postés
489
Date d'inscription
samedi 23 juin 2007
Statut
Membre
Dernière intervention
19 juin 2011
225
12 oct. 2008 à 03:04
12 oct. 2008 à 03:04
Salut,
Si tu sais créer une liste circulaire et tu sais la parcourir, tu devrais pouvoir résoudre ton exercice sans difficultés. Donc voici la théorie : http://www.commentcamarche.net/faq/sujet 8225 listes circulaires qui t'aidera à comprendre comment créer et parcourir une liste circulaire (en C).
Si tu dois diviser une liste circulaire en deux, je suppose que si tu as une liste initiale telle que :
1 -> 2 -> 3 -> 4 -> 5 -> 6 --> 1....
tu dois obtenir quelque chose comme :
1 -> 2 -> 3 --> 1
et
4 -> 5 -> 6 --> 4
(on a bien deux listes circulaires de x et y éléments éclatés depuis la liste initiale tels que x(3) = y(3)
Donc, en théorie tu devrais déjà commencer par créer deux nouvelles listes circulaires vides. Ensuite il faudrait parcourir la liste circulaire initiale jusqu'à taille_liste/2 et mettre ces valeurs dans une des nouvelles listes circulaires. Et pareil pour la deuxième moitié. Tu ne fais rien d'autre que parcourir une liste circulaire et créer une liste circulaire réduite... Bon courage !
Si tu sais créer une liste circulaire et tu sais la parcourir, tu devrais pouvoir résoudre ton exercice sans difficultés. Donc voici la théorie : http://www.commentcamarche.net/faq/sujet 8225 listes circulaires qui t'aidera à comprendre comment créer et parcourir une liste circulaire (en C).
Si tu dois diviser une liste circulaire en deux, je suppose que si tu as une liste initiale telle que :
1 -> 2 -> 3 -> 4 -> 5 -> 6 --> 1....
tu dois obtenir quelque chose comme :
1 -> 2 -> 3 --> 1
et
4 -> 5 -> 6 --> 4
(on a bien deux listes circulaires de x et y éléments éclatés depuis la liste initiale tels que x(3) = y(3)
Donc, en théorie tu devrais déjà commencer par créer deux nouvelles listes circulaires vides. Ensuite il faudrait parcourir la liste circulaire initiale jusqu'à taille_liste/2 et mettre ces valeurs dans une des nouvelles listes circulaires. Et pareil pour la deuxième moitié. Tu ne fais rien d'autre que parcourir une liste circulaire et créer une liste circulaire réduite... Bon courage !
