Discussion :

[scarabee10]

Bonsoir,
Je travaille en ce moment sur un sujet qui traite d'une implémentation assez spéciale des chaînes de caractères en liste chaînée (appelée lstring). Une chaîne structurée en liste est en fait une liste chaînée de tableaux de caractères terminés par '\0'. On alloue les tableaux dynamiquement pour contenir exactement exactement le nombre de caractères nécessaires. On représente une chaîne vide par une liste vide et non par un élément qui contiendrait un tableau représentant la chaîne vide "".
Il est demandé d'implémenter des procédures d'initialisation, affichage, destruction, obtention de la taille, ajout d'une chaîne de caractères classique à la fin d'une lstring, obtention d'un caractère à partir de son indice, recherche d'un motif de caractères....
J'ai pour ma part des soucis avec l'ajout d'une string et l'obtention de la taille d'une lstring.
Ci-dessous mon fichier d'en-tête:

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
#ifndef LSTRING__H
#define LSTRING__H
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct Cellule{
    char *chaine;
    struct Cellule *suivante;
} Cellule;
 
typedef Cellule *lstring;
 
bool initialiser(lstring *lstr, const char src[]);
/* Initialiser une lstring à partir d'une chaine ou d'un pointeur NULL */
 
bool est_vide(lstring lstr);
/* Tester si une lstring est vide */
 
void afficher(lstring lstr);
/* Afficher une lstring (avec un retour à la ligne à la fin) */
 
void detruire(lstring *lstr);
/* Detruire une lstring */
 
size_t taille(lstring lstr);
/* Obtenir la taille d'une lstring */
 
bool ajouter(lstring *lstr, const char src[]);
/* Ajouter une chaîne de caractères classique à la fin d'une lstring */
 
char obtenir(lstring lstr, size_t indice);
/*  Obtenir un caractère dans une lstring à partir de son indice */
 
bool motif(lstring lstr, const char s[]);
/* Chercher si un motif est présent dans une lstring */
 
bool supprimer(lstring *lstr, size_t inf, size_t max);
/* Supprimer une sous-partie d'une lstring comprise entre deux indices */
 
#endif

Ma procédure d'initialisation:

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
bool initialiser(lstring *lstr, const char src[]){
    if (src==NULL || strcmp(src,"")==0){
	*lstr=NULL;
	return true;
    } else{
	(*lstr)=malloc(sizeof(**lstr));
	if (*lstr){
	    (*lstr)->chaine=malloc((strlen(src)+1)*sizeof(char));
	    if ((*lstr)->chaine){
		strcpy((*lstr)->chaine, src);
		return true;
	    } else{
		free(*lstr);
		(*lstr)=NULL;
		fprintf(stderr, "Mémoire insuffisante\n");
		return false;
	    }
	}else{
	    fprintf(stderr, "Mémoire insuffisante\n");
	    return false;
	}
    }
}

Ma procédure taille:

Code :

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

1
2
3
4
5
6
7
8
9
size_t taille(lstring lstr){
    size_t resultat=0;
    Cellule *curseur=lstr;
    while (curseur!=NULL){
	resultat+= strlen(curseur->chaine);
	curseur=curseur->suivante;
    }
    return resultat;
}

La procédure qui permet d'obtenir un caractère suivant son indice dans la lstring:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
char obtenir(lstring lstr, size_t indice){
    /* A optimiser */
    //assert(indice<taille(lstr));
    Cellule *curseur=lstr;
    size_t taille_cumule=strlen(curseur->chaine);
    while (curseur!=NULL && indice>=taille_cumule){
	curseur=curseur->suivante;
	taille_cumule+=strlen(curseur->chaine);
    }
    return curseur->chaine[strlen(curseur->chaine)-(taille_cumule-indice)];
}

Et ma procédure d'ajout qui pose à priori des soucis dans mon code:

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
bool ajouter(lstring *lstr, const char src[]){
    if (src!=NULL || strcmp(src,"")==0)
	/* Si la liste est vide, on ne fait rien! */
	return true;
    else{
	Cellule *curseur=*lstr;
	while(curseur->suivante!=NULL){
	    curseur=curseur->suivante;
	}
	Cellule *nouvelle=malloc(sizeof(*nouvelle));
	if (nouvelle){
	    nouvelle->chaine=malloc(sizeof(char)*strlen(src));
	    if (nouvelle->chaine){
		strcpy(nouvelle->chaine,src);
		nouvelle->suivante=NULL;
		curseur->suivante=nouvelle;
		return true;
	    }else{
		fprintf(stderr,"Mémoire insuffisante\n");
		return false;
	    }
	}else{
	    fprintf(stderr,"Mémoire insuffisante\n");
	    return false;
	}
    }
}

Pour résumer cette dernière procédure. Si la liste n'est pas vide (autrement on ne fait rien), je déclare un pointeur sur cellule (curseur) qui me permettra de parcourir la liste jusqu'à la dernière cellule, arrivée à celle-ci, j'alloue une nouvelle cellule pointée par "nouvelle" où je copie la chaîne à ajouter. Je relie finalement cette nouvelle cellule à la précédente, pointée par curseur, et je boucle la liste par NULL.
Là où ça marche pas c'est dans mes tests. Je déclare une lstring avec un seul élément "abc", je rajoute une autre chaîne "defg" en utilisant ma procédure ajouter mais la taille renvoyé avec la procédure correspondante est toujours égale à 3 (p-e le problème vient-il de ce SP!).
Egalement, quand j'essaie d'obtenir le caractère d'indice 3 (i.e: 'd') j'ai une segmentation fault.
Au final, le problème peut venir de n'importe où.

Merci d'éclairer ma lanterne.
Cordialement,

[plumedesiles]

Je viens de tester ton code

Dans Ajouter ce n'est pas src!NULL mais src==NULL

De plus c'est la liste que tu veux savoir si elle est vide donc il faudrait corriger en *lstr==NULL, ca irait aussi

[scarabee10]

Je viens de tester ton code

Dans Ajouter ce n'est pas src!NULL mais src==NULL

De plus c'est la liste que tu veux savoir si elle est vide donc il faudrait corriger en *lstr==NULL, ca irait aussi

- Merci c'était bien src==NULL.
- Non c'est bien src que je veux tester, si elle est vide, pas la peine de créer une nouvelle cellule, on ne fait rien.

En modifiant l'erreur, la taille est toujours égale à 3 après rajout de la chaîne "defg". Cependant, j'ai constaté une erreur que je n'avais pas encore remarqué: la commande "putchar(obtenir(s,2));" provoque une erreur de segmentation, alors que le caractère d'indice 2 est censé être 'c'. Donc la procédure "obtenir" couak aussi. Décidemment...

[plumedesiles]

Normal il faut que tu inverses les deux lignes dans le while car tu peux te ramasser un pointeur NULL sans l'avoir tester

[diogene]

- Dans la fonction initialiser() :
le champ suivante n'est pas initialisé :

Code :

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

1
2
3
4
5
6
7
8
....
if ((*lstr)->chaine)
{
  strcpy((*lstr)->chaine, src);
  (*lstr)->suivante  = NULL ; //<-------
  return true;
}
....

- Dans les fonctions taille(), obtenir() et ajouter(), une écriture dangereuse qui pourra conduire à des problèmes plus tard :

Code :

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

1
2
3
4
size_t taille(lstring lstr)
{
...
    Cellule *curseur=lstr;

lstr, du type lstring, est converti en cellule *. C'est vrai pour le moment puisque lstring est bien le type Cellule *. Mais si on a défini un type lstring, c'est bien pour différencier les deux types. D'ailleurs, on peut trouver avantageux de modifier ultérieurement le type lstring par exemple pour lui ajouter un pointeur sur la dernière cellule ce qui facilitera les concaténations, ou modifier le type Cellule pour lui ajouter la longueur de la chaine stockée ce qui évitera les strlen() à répétition qui vont pénaliser grandement les performances.

-Dans ajouter(), outre le src==NULL déjà signalé, la quantité allouée est incorrecte :

Code :

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

nouvelle->chaine=malloc(strlen(src)+1);

Pouquoi si la liste est vide, ne fait-on rien ? On devrait mettre la chaine dans la liste !
Je pense qu'il y a une ambiguïté sur les rôles de initialiser() et ajouter() puisque initialiser() ajoute une chaine (à une liste vide) lorsque ajouter() est incapable de le faire dans ce cas.
ajouter() devrait être capable de placer une chaine dans une liste vide. Alors, initialiser() doit créer une nouvelle liste vide, c'est son rôle essentiel, et si on spécifie une chaine pour initialiser la liste alors la fonction initialiser() appelle ajouter() pour faire l'opération.

- Pour la fonction obtenir(), aucune vérification n'est faite pour s'assurer que l'indice est dans une plage correcte. Réfléchir à ce problème.

[scarabee10]

- Dans la fonction initialiser() :
le champ suivante n'est pas initialisé :

Code :

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

1
2
3
4
5
6
7
8
....
if ((*lstr)->chaine)
{
  strcpy((*lstr)->chaine, src);
  (*lstr)->suivante  = NULL ; //<-------
  return true;
}
....

C'est corrigé.

- Dans les fonctions taille(), obtenir() et ajouter(), une écriture dangereuse qui pourra conduire à des problèmes plus tard :

Code :

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

1
2
3
4
size_t taille(lstring lstr)
{
...
    Cellule *curseur=lstr;

lstr, du type lstring, est converti en cellule *. C'est vrai pour le moment puisque lstring est bien le type Cellule *. Mais si on a défini un type lstring, c'est bien pour différencier les deux types. D'ailleurs, on peut trouver avantageux de modifier ultérieurement le type lstring par exemple pour lui ajouter un pointeur sur la dernière cellule ce qui facilitera les concaténations, ou modifier le type Cellule pour lui ajouter la longueur de la chaine stockée ce qui évitera les strlen() à répétition qui vont pénaliser grandement les performances.

Ça rejoint ce que mon prof nous a raconté en cours. Instinctivement, l'utilité du curseur n'était pour moi que de pointer vers une cellule. Cependant, dans le sujet le type lstring n'est pas modifié plus tard, mais cela reste toutefois plus robuste de différencier une lstring d'un pointeur vers cellule.

-Dans ajouter(), outre le src==NULL déjà signalé, la quantité allouée est incorrecte :

Code :

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

nouvelle->chaine=malloc(strlen(src)+1);

Corrigé.

Pouquoi si la liste est vide, ne fait-on rien ? On devrait mettre la chaine dans la liste !

Faute de frappe: "Si la chaîne est vide, on ne fait rien". Pas la peine d'allouer une nouvelle cellule.

Je pense qu'il y a une ambiguïté sur les rôles de initialiser() et ajouter() puisque initialiser() ajoute une chaine (à une liste vide) lorsque ajouter() est incapable de le faire dans ce cas.
ajouter() devrait être capable de placer une chaine dans une liste vide. Alors, initialiser() doit créer une nouvelle liste vide, c'est son rôle essentiel, et si on spécifie une chaine pour initialiser la liste alors la fonction initialiser() appelle ajouter() pour faire l'opération.

Initialiser ne doit pas pouvoir créer une nouvelle liste, mais placer une chaîne dans une liste à peine déclarée.

Code :

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

1
2
3
4
5
 lstring s;
/* Tests basiques */
initialiser(&s, "abc");
assert(!est_vide(s));
assert(taille(s)==3);

Ajouter rajoute une chaîne à une liste déjà définie (lstr==NULL étant une définition comme les autres).

- Pour la fonction obtenir(), aucune vérification n'est faite pour s'assurer que l'indice est dans une plage correcte. Réfléchir à ce problème.

J'ai rajouté un assert(indice<taille(lstr)) en début de fonction.

-------
J'ai modifié ma fonction obtenir en mettant un do-while au lieu d'un while.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char obtenir(lstring lstr, size_t indice){
    /* A optimiser */
    assert(indice<taille(lstr));
    assert(!est_vide(lstr));
    lstring curseur=lstr;
    lstring buffer;
    size_t taille_cumule=0;
    do{
	taille_cumule+=strlen(curseur->chaine);
        buffer=curseur;
	curseur=curseur->suivante;
    }while (curseur!=NULL && indice>=taille_cumule);
    return buffer->chaine[strlen(buffer->chaine)-(taille_cumule-indice)];
}

C'est peut-être un peu redondant, mais ça marche. J'ai passé un bon quart d'heure à faire des schémas de structure sur papier ainsi que l'évolution de la pile mémoire pour me rendre à l'évidence que le problème ne vient pas de là.
Là avec mes assert, après avoir ajouté la chaîne "defg", il n'essaie même pas d'obtenir le caractère 'd' puisque la taille reste égale à 3 et l'assert l'en n'empêche donc.
Je rappelle que les appels obtenir(s,'0'), obtenir(s,'1') et obtenir(s,'2') renvoient bien 'a', 'b' et 'c'. Ma chaîne initiale étant "abc".

Idem pour la fonction ajouter, l'analyse sur papier n'a révélé à priori aucun soucis dans le code.

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
bool ajouter(lstring *lstr, const char src[]){
    if (src==NULL || strcmp(src,"")==0)
	/* Si la chaîne est vide, on ne fait rien! */
	return true;
    else{
	lstring curseur=*lstr;
	while(curseur->suivante!=NULL){
	    curseur=curseur->suivante;
	}
	Cellule* nouvelle=malloc(sizeof(*nouvelle));
	if (nouvelle){
	    nouvelle->chaine=malloc(sizeof(char)*(strlen(src)+1));
	    if (nouvelle->chaine){
		strcpy(nouvelle->chaine,src);
		nouvelle->suivante=NULL;
		curseur->suivante=nouvelle;
		return true;
	    }else{
		fprintf(stderr,"Mémoire insuffisante\n");
		return false;
	    }
	}else{
	    fprintf(stderr,"Mémoire insuffisante\n");
	    return false;
	}
    }
}

Idem en fin pour la fonction taille:

Code :

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

1
2
3
4
5
6
7
8
9
size_t taille(lstring lstr){
    size_t resultat=0;
    lstring curseur=lstr;
    while (curseur!=NULL){
	resultat+= strlen(curseur->chaine);
	curseur=curseur->suivante;
    }
    return resultat;
}

Retour au point de départ donc (ou presque). La source du problème peut-être n'importe où. J'ai tout passé au peigne fin et ça m'énerve.

Cordialement.