Discussion :

[monrow]

Bonsoir,

J'ai un petit souci dans une procédure, je vous présente le problème.

On travaille ici avec le type Liste des listes simplement chaînées de caractères défini par:

Code :

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

1
2
3
4
5
6
7
 
   type Cellule;
   type Liste is access Cellule ;
   type Cellule is record
      Val : Character ;
      Suiv : Liste;
   end record;

On doit écrire une procédure Extrait, qui retire d'une liste L, une sous-liste correspondant à une certaine chaîne non vide S.

Code :

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

procedure Extrait(L: in out Liste ; S:String) ;

On utilisera la procédure:

Code :

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

1
2
 
procedure Liberer is new Ada.Unchecked_Deallocation(Cellule,Liste) ;

Exemple:

On suppose L=[a,b,a,t,o,t,o,t,o,r,o]
Extrait(L,"totor");
L=[a,b,a,t,o,o]
Extrait(L,"oo");
L=[a,b,a,t]
Extrait(L,"aa");
L=[a,b,a,t]
Extrait(L,"a");
L=[b,a,t]
Extrait(L,"bat");
L=[]

Voilà à quoi j'ai pensé :

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
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
 
   procedure Extrait(L: in out Liste ; S:String) is
 
      Cour , Tete , Queue , Aux: Liste ;
      B : Boolean;
      K:Integer;
 
   begin
      Cour := L ;
      Tete := null;
      Queue := null;
      B := True ;
      K:=S'First;
 
      while Cour /= null loop
         Aux := Cour;
         while Cour.Val = S(K) loop
            if B then
               Tete:=Cour;
               B:=False;
            end if;
            if K/=S'Last then
               if Cour.Suiv = null then
                  exit ;
               end if;
               K:=K+1;
               Cour:=Cour.Suiv ;
            else
               Queue:=Cour;
               exit;
            end if;
         end loop;
 
         if Queue /= null then
            Cour:=null;
         else
            Cour:=Aux.Suiv;
            K:=S'First;
            Tete:=null;
            B:=True;
         end if;
         Liberer(Cour);
      end loop;
 
 
      if Queue /= null then
         Cour := L;
         while Cour.Suiv /= Tete loop 
            Cour := Cour.Suiv;
         end loop;
         if Queue.Suiv /= null then
            Cour.Suiv := Queue.Suiv;
            Queue.Suiv:=null;
         else
            if Tete /= L then
               Cour.Suiv := null;
            else
               L:=null;
            end if;
         end if;
         Liberer(Cour);
         Liberer(Tete);
         Liberer(Queue);
      end if;
   end;

En fait, la tête et la queue c'est pour délimiter la chaîne de caractères si elle a été trouvée, pour l'éliminer après.

Merci d'avance.

[PRomu@ld]

En fait, tu ne nous précises pas ton problème (et il faut bien dire que je n'ai pas envie d'aller dans ton code pour comprendre où peut être le problème).

Mais algorithmiquement parlant, je pense qu'il faut découper la fonction en deux fonctions : identification de la sous liste (tu passes tes deux listes en paramètre et elle te retourne un pointeur vers le début de la sous chaîne si elle existe) et suppression de la sous liste.

[monrow]

Mais algorithmiquement parlant, je pense qu'il faut découper la fonction en deux fonctions : identification de la sous liste (tu passes tes deux listes en paramètre et elle te retourne un pointeur vers le début de la sous chaîne si elle existe) et suppression de la sous liste.

Voilà donc mon algorithme est divisé en deux aussi :

La première partie est :
Ici, je mets plutôt deux pointeurs Tete et Queue qui délimitent le début et la fin de la chaine de caractères si elle est présente, sinon les deux sont nuls.

Avec une boucle while, je parcours alors d'un pointeur Cour la liste chaînée. Tant qu'on n'est pas arrivé à la fin (où Cour deviendra null), on stocke la valeur de Cour dans un pointeur auxiliaire Aux (on va l'utiliser après dans le cas où on trouve juste le début de la chaine mais pas totalement).
Après on analyse ce pointeur Cour.
Avec une boucle while, si Cour.Val et S(K) (K ici est S'First), alors:

On a un traitement de début, pour définir la tête, et cela on utilisant un booléen B qui devient False dès qu'on attribue à Tete sa valeur.

Après on distingue deux cas, soit on est arrivé à S'Last soit non.

Si on n'est toujours pas arrivé à S'Last, on voit si Cour.Suiv = null, dans ce cas, on est sûr que S n'existe pas dans la liste, je sors de la boucle while avec exit. Si Cour.Suiv n'est pas null, alors on incrémente K, et on met Cour à Cour.Suiv.

Si on est arrivé à S'Last, on met alors Queue à Cour, et on sort avec exit.

A la sortie de cette petite boucle, on fait une petite vérification:

Si Queue n'est pas à null (i.e. S existe), on met Cour à null pour sortir tout de suite de la grande boucle while.
Sinon, c'est que S n'existe pas, et là Cour prend la valeur Aux.Suiv comme si rien n'était, et on réinitialise le tout : K à S'First, Tete à null et B à True.

On voit déjà s'il y a un problème dans cette partie puis on termine.

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
27
28
29
30
31
32
33
34
35
36
 
      Cour := L ;
      Tete := null;
      Queue := null;
      B := True ;
      K:=S'First;
 
      while Cour /= null loop
         Aux := Cour;
         while Cour.Val = S(K) loop
            if B then
               Tete:=Cour;
               B:=False;
            end if;
            if K/=S'Last then
               if Cour.Suiv = null then
                  exit ;
               end if;
               K:=K+1;
               Cour:=Cour.Suiv ;
            else
               Queue:=Cour;
               exit;
            end if;
         end loop;
 
         if Queue /= null then
            Cour:=null;
         else
            Cour:=Aux.Suiv;
            K:=S'First;
            Tete:=null;
            B:=True;
         end if;
         Liberer(Cour);
      end loop;

Merci d'avoir pris le temps pour m'aider.