Discussion :

[WAI_T]

bonsoir,

j'ai implémenté un code pour la recherche de boucle à partir d'un fichier texte. il il compile correctement, mais la fonction detectloop ne fonctionne pas correctement, il parait.

est ce qu'il ya une erreur de typage? Pourriez vous svp me donner un coup de main!

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
#include <iostream>
#include <string>
#include <fstream>
#include <cstdlib> 
 
using namespace std;
 
/* Link list node */
struct node
{
  string data;
  struct node* next;
};
void push(node** head_ref, string new_data)
{
  /* allocate node */
struct node* new_node = new struct node;
// with C struct node* new_node=(struct node*) malloc(sizeof(struct node));
  /* put in the data  */
  new_node->data  = new_data;
  /* link the old list off the new node */
  new_node->next = (*head_ref);
 
  /* move the head to point to the new node */
  (*head_ref)    = new_node;
} 
int detectloop(struct node *list)
{
struct node *p = list, *q = list;
//p=q=head;
do{
p=p->next->next;
q=q->next;
}while (p!=q or p!=NULL);
if (p==q) { printf("Found Loop"); return 1;
}else printf("No Loop Found"); return 0;
}
 
/* Drier program to test above function*/
int main()
{
  /* Start with the empty list */
  struct node* head = NULL;
ifstream fichier("test.txt", ios::in);  // open text.txt
        if(fichier)  // if opened
        {
                string ligne;
        while(getline(fichier, ligne))  // while it is possible to put in ligne
        {
                //int nmb = atoi(ligne.c_str());
		push(&head, ligne);  
                // printf("%n",head);              
		cout << ligne << endl;  // show
        }
                fichier.close();
        }
        else
               // cerr << "Impossible d'ouvrir le fichier !" << endl;
 detectloop(head);
 
 getchar();
}

voici le contenu de test.txt qui contient une boucle: répétion d'une meme séquence:

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
2
2
6
7
6
6
8
5
8
2
7
6
6
7
6
6
8
5
8
2
7
6
6
7
6
6
8
5
8
2
7

[3DArchi]

Salut,
Utilises std::vector pour injecter tes données et des itérateurs pour parcourir ta séquence. Dans le code que tu nous proposes tu utilises inutilement des pointeurs avec une structure de liste maison et conséquence inévitable => bugs + erreur (tes conditions while ne permettent pas la sortie sans un déréférencement invalide).

[WAI_T]

merci pour ta réponse.
j'ai pensé à utiliser les listes car j'aurai un grand flux de données à traiter ( des milliards) et je pensais que les listes consomment moins de mémoire que les tableaux..
sinon, le programme ne fait ni des bugs ni erreurs mais les résultats ne sont pas complets..
je n'ai pas utilisé des vecteurs avant ( plus précisément, c'est les premières appli que je fais en c++).. donc, je cherche à optimiser du temps!

[3DArchi]

sinon, le programme ne fait ni des bugs ni erreurs mais les résultats ne sont pas complets..

ce sont les pointeurs qui sont comparés, donc p sera toujours différent de q. Et si le nombre d'item est pair, alors p finira par taper dans une zone mémoire invalide. J'appelle cela erreur et bug

Tu n'as peut être pas besoin de garder tous les éléments dans un std::vector mais tu as peut être besoin de deux itérateurs sur tes séquences. Le même flux ne peut être traversé deux fois avec un itérateur. Tu peux éventuellement gérer une fenêtre d'écart entre tes deux itérateurs.

[WAI_T]

ok.. je comprends mieux pour les pointeurs

pourrais tu stp me donner un element de plus pour corriger cette erreur?

[WAI_T]

j'ai fais cet essai ( ajout d'un pointeur de référence) :

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
int detectloop(struct node* list)
{
struct node *p1 = list, *p2 = list, *l=list;
/* Test trivial no-loop and trivial loop */
     if (l == NULL)
        {
	// No loop, uninitialised list 
	printf("No loop\n");
	}
 
	if (l->next == l)
	{
	// Trivial loop 
	printf("Loop detected\n");
	return 0;
	}
	p1 = l;
	p2 = l->next;
 
	while (p2 != NULL && p1 != p2)
	{
	// Increment p1 once, p2 twice
	p1 = p1->next;
	p2 = p2->next;
	if (p2 != NULL)
	p2 = p2->next;
	}
	if (p2 == NULL)
	{
	// We got to the end of the list
	printf ("No loop\n");
	}
	else
	{
	// p1 == p2, and the p2 "lapped" the p1
	// in the loop
	printf ("Loop detected\n");
	}
	return 0;}

mais tjrs pas de résultats visibles!