algorithme liste circulaire

**youkisall** · 11/10/2008, 22h12

Bonjour.
Je veux de l'aide s'il vous plaît , j'ai fait quelques recherches dans les tutos et FAQ mais j'ai pas avancé.

Je veux écrire un algo qui parcourt une liste circulaire de n éléments (n étant pair) et de la diviser en 2 listes circulaires de x et y éléments tels que x = y.

Je veux juste la logique (en c ou n importe quel langage) je ne suis pas encore programmeur, c est juste la théorie (logique) qui m'intéresse.

j ai fais le code suivant pour parcourir ma liste circulaire :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
Element *courant;
    courant = liste->debut;
    int i;
    int k;
    for(i=0;i<liste->taille;++i){
    liste->debut = liste->suivant;
    n++;
   }
     k = n/2;

**Trap D** · 11/10/2008, 22h25

Petite question : pourquoi comptes-tu la longueur de la liste puisque tu connais la taille ???
Pourquoi n'utilises-tu pas courant dans ta boucle ?
D'autre part, si tu fais en C liste->debut = liste->suivant; tu perds pratiquement toute ta liste !

**dot-_-net** · 12/10/2008, 20h15

for(i=0;i<liste->taille;++i){
J’ai pas comprit i<liste->taille
Peux tu nous donner la structure de ta liste circulaire ?

**dot-_-net** · 12/10/2008, 20h18

Envoyé par Trap D

D'autre part, si tu fais en C liste->debut = liste->suivant; tu perds pratiquement toute ta liste !

C’est une liste circulaire il va rien perdre si il perd la position du début de la liste

**Trap D** · 12/10/2008, 20h40

Ça dépend un peu de son type de donées j'ai l'impression, mais je pense quand même qu'il y aura des éléments de perdus, on est dans une boucle.

**dot-_-net** · 12/10/2008, 20h50

Envoyé par Trap D

Sauf que c'est dans la boucle ...

Il peux même mètre une boucle infini il va rien perdre car ça va toujours circulaire

**Trap D** · 13/10/2008, 10h29

mouaih, c'est le liste->debut = liste->suivant sans définition de structure qui me perturbe

**Zavonen** · 13/10/2008, 23h51

Si cela peut t'être utile voici une implémentation en C d'une file circulaire d'entiers:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <stdio.h>
#include <stdlib.h>
 
typedef struct
{ int taille;
  int index;
  int contenu;
  int* base;
}FileCirc;
 
void InitCirc ( FileCirc * pfc, int S)
{ pfc->taille=S;
  pfc->index=0 ;
  pfc->contenu=0;
  pfc->base= (int *)malloc(S*sizeof(int));
}
 
void Destruct (FileCirc * pfc)
{free (pfc->base);}
 
void Store(FileCirc * pfc, int n)
{ int storindex;
	if(pfc->contenu==pfc->taille) {printf ("Impossible: File pleine"); return;}
 else
	{storindex= (pfc->index + pfc->contenu)%pfc->taille;
     *(pfc->base+storindex)=n;
	 pfc->contenu++;
	}
 
}
 
int Retrieve (FileCirc * pfc)
{ 	int result;
	if(pfc->contenu==0) {printf("Impossible: Pile vide"); return 0;}
  else
  { result=*(pfc->base+pfc->index);
    pfc->contenu--;
    pfc->index ++;
	if (pfc->index==pfc->taille) pfc->index=0;
  }
  return result;
}
 
void Empile (int n, FileCirc * pfc)
{ while (n)
{ Store(pfc, n%10);
n=n/10;}
}
 
int Depile( FileCirc * pfc)
{ int i;
   int p=1;
   int result=0;
   int m=pfc->contenu;
   for(i=1; i<pfc->contenu; i++) p*=10;
   for(i=0;i<m;i++)
   {result += Retrieve(pfc)*p;
   p/=10;}
   return result;
}
 
FileCirc FC;
 
int palindrome (int n)
{ int u= n;
 int v;
 Empile (u,&FC);
 v=Depile(&FC);
 return (u==v);
}
 
void ListeTout (FileCirc * pfc)
{ int indexcourant= pfc->index;
   int i;
   for (i=0; i<pfc->contenu; i++)
   { printf("\n%d", *(pfc->base+indexcourant));
     indexcourant++;
	 if (indexcourant== pfc->taille) indexcourant=0;
   }
}
 
void Ecrit ( FileCirc * pfc)
{ FILE * fp;
  fp= fopen("test", "wb");
  fwrite(pfc,sizeof(FileCirc),1,fp);
  fwrite(pfc->base,sizeof(int),pfc->taille,fp);
  fclose(fp);
}
 
void Lit(FileCirc * pfc)
{ FILE *fp;
  fp=fopen("test", "rb");
  fread(pfc, sizeof(FileCirc),1,fp);
  pfc->base=(int *) malloc(pfc->taille*sizeof(int));
  fread(pfc->base, sizeof(int), pfc->taille,fp);
  fclose(fp);
}
 
void main()
 
{
// test du mécanisme
 
/*InitCirc (&FC, 3);
	Store (&FC,1);
Store (&FC,2);
Store (&FC,3);
Store (&FC,4); // provoque l'ereur
m=Retrieve(&FC);
printf("%d\n",m);
m=Retrieve(&FC);
printf("%d\n",m);
Store(&FC,4);
m=Retrieve(&FC);
printf("%d\n",m);
m=Retrieve(&FC);
printf("%d\n",m);
//Pour provoquer l'erreur
m=Retrieve(&FC);
printf("%d\n",m);
Store (&FC,5);
Store (&FC,6);
Store (&FC,7);
Store (&FC,8); // provoque l'erreur
m=Retrieve(&FC);
printf("%d\n",m);
*/
// test d'Empile
/*
int m;
InitCirc (&FC, 10);
Empile(123,&FC);
m=Retrieve(&FC);
printf("%d\n",m);
m=Retrieve(&FC);
printf("%d\n",m);
m=Retrieve(&FC);
printf("%d\n",m);
*/
// test Depile
/*int m;
Empile(123,&FC);
m=Depile(&FC);
printf("%d\n",m);
*/
 
	// test palindrome
/*
int m;InitCirc (&FC, 10);
m=palindrome(123);
printf("%d\n",m);
m=palindrome(121);
printf("%d\n",m);
m=palindrome(1221);
printf("%d\n",m);
*/
	// test Listetout
/*
	InitCirc (&FC, 3);
	Store (&FC,1);
Store (&FC,2);
Store (&FC,3);
Retrieve(&FC);
Store (&FC,4);
 
ListeTout(&FC);
*/
InitCirc (&FC, 3);
Store (&FC,1);
Store (&FC,2);
Store (&FC,3);
Ecrit(&FC);
InitCirc(&FC,10);
ListeTout(&FC);
Destruct(&FC);
Lit(&FC);
ListeTout(&FC);
}

**nonpoluant** · 14/10/2008, 10h22

Une question me semble importante :
Ta liste elle est doublement chainée ou pas?

**Rakken** · 14/10/2008, 17h16

Déjà, quand on a une liste circulaire (et les listes chainées en général) on n'a à priori pas à l'avance sa taille. Donc pour le parcours, on prend l'élément qu'on a déjà, on le duplique, et on fait des ->next jusqu'a ce qu'on retombe sur l'élément qu'on a sauvegardé.

Après pour ton problème précis, sachant que ta liste est nécessairement avec un nombre pair d'élément, je ferai une boucle, avec deux pointeurs : 'pParcours', qui avance de deux en deux, et 'pMilieu', un autre en même temps qui avance un par un. Lorsque le pointeur 'pParcours' est retombé sur pDebut (le pointeur de début, cf ce que j'ai dit juste au dessus sur le parcours d'une liste circulaire), tu te retrouves avec 'pMilieu' qui est justement au milieu. A ce stade, tu n'a plus qu'a dire que pParcours->next = pMilieu->next, comme ca tu as une boucle avec la fin, et pMilieu->next = pDebut, comme ça tu as une boucle avec le début.

**SpiceGuid** · 14/10/2008, 17h33

Première étape, récupérer toutes les cellules d'indice impair (la liste commence à l'indice i=0) :

Code Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let rec filter_odd_nth l =
  match l with
  | []  -> []
  | [a] -> []
  | a::b::l -> b::filter_odd_nth l

Deuxième étape, récupérer toutes les cellules d'indice pair, il suffit de prendre la cellule d'indice i=0 et de lui ajouter les cellules impaires dans la liste d'indices i-1 :

Code Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let filter_even_nth l =
  match l with
  | []   -> []
  | a::l -> a::filter_odd_nth l

Remarque: que la liste soit circulaire (ou pas) ne change rien à l'algo, ça n'est que de l'implémentation.

**henderson** · 16/10/2008, 00h09

Salut !

Il y a aussi l'illusion de la circularité sur un simple tableau (ou un objet liste) avec un index qui, lui, est géré de manière circulaire.
Ca peut paraître plus compliqué (à cause du modulo) ... mais dans ce cas précis, le tableau est scindé en deux implicitement :
- soit à l'aide de deux calculs d'index qui vont permettre d'accéder à la partie haute ou à la partie basse du tableau sans avoir besoin de faire défiler tout ce petit monde pour trouver le n/2ième élément.
- soit avec l'autre solution qui consiste à récupérer les éléments pairs et les éléments impairs !
Comme chacun le sait, le cas de figure révé, c'est lorsque n est 2^^x ce qui permet d'appliquer un simple masque i = i & (n-1) pour assurer la circularité.

Ceci dit ... c'est l'usage qu'on en fait qui est important (du comment et pourquoi on implémente d'une manière et pas d'une autre ) !

A plus !

**henderson** · 16/10/2008, 16h04

Salut !

Sinon, pour la partogénèse :

On donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
// sous entenu une déclaration de ce type
struct jObj;
// points d'ancrage des boucles
jObj *Ring1;  
jObj *Ring2;
// connu d'avance ou à calculer sur Ring1 le moment venu
int Nb;

Donc notre paramécie (une simple liste liée et bouclée : dernier->suivant = premier) va devoir exécuter :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
int last1 = (Nb/2)-1;
int last2 = Nb-1;
 
jObj *Obj = Ring1;
int i=0;
do{
    if(i == last1)
        {
        //On tient le début de Ring2
        Ring2 = Obj->Next;
        //On boucle Ring1
        Obj->Next = Ring1;
        }
    else
        {
        if(i == last2)
            {
            //On tient la fin de Ring2 et on boucle
            Obj->Next = Ring2;
            // -> en fait ... c'est terminé ici  
            }
        }
    i++;
    Obj = Obj->Next;
  }while(Obj != Ring1);

Rien n'a été perdu !

A plus !

algorithme liste circulaire

Algorithmes et structures de données

Discussions similaires

Partager

Partager