Liste itérative en C

Version imprimable

Bonjour,

Je veux réaliser une liste itérative en C (je débute en C). Voici la structure LISTE:
Code:

1 2 3 4 5 6 7 /* Type LISTE*/ typedef struct { int capacite; int rang; char* tableau; } LISTE;
Voici maintenant l'interface des fonctions qui traitent une LISTE:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 /* Interface */ LISTE creer(int); void detruire(LISTE*); int nbElements(LISTE); int capacite(LISTE); short estVide(LISTE); short estPleine(LISTE); char* consulter(LISTE,int); int supprimer(LISTE,int); int supprimerPremier(LISTE,char*); int supprimerTous(LISTE,char); int modifier(LISTE,int,char*); int insererFin(LISTE,char*); int inserer(LISTE,int,char*);
Ma première question concerne la fonction creer:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /* Créer une liste vide, d'une capacité initiale de ci places; retourne NULL si la création a échouée. */ LISTE creer(int ci) { LISTE liste; /* Le premier élément de la liste sera de rang 0 */ liste.rang = 0; /* Allocation du tableau des éléments */ liste.tableau = (char*)malloc(sizeof(char) * ci); /* Test de création de la liste */ if(liste.tableau) { liste.capacite = ci; return liste; } return liste; }
Je ne sais pas comment faire pour retourner NULL quand la création a échouée. J'ai essayé:
return (LISTE)NULL;
return (LISTE)0;
return NULL;
return 0;
et rien ne marche. (j'utilise stdio.h pour NULL)

Autre question, ma fonction detruire est-elle correcte ?
Code:

1 2 3 4 5 6 7 8 9 10 /* Détruit la liste et la fait pointer sur NULL */ void detruire(LISTE* liste) { /* Libération de l'espace mémoire */ if(liste -> tableau) free(liste -> tableau); /* liste pointe sur NULL */ liste = NULL; }
Enfin, comment compter le nombre d'éléments dans une telle liste ?
Faut-il réserver un champ nbelements dans la structure ou faut-il parcourir le tableau des éléments avec un pointeur (je voulais suivre cette deuxième méthode mais je suis bloqué) ?
Code:

1 2 3 4 5 6 7 8 9 10 /* Retourne le nombre d'éléments contenus dans la liste */ int nbElements(LISTE liste) { auto int nb = 0; auto int* p; p = liste.tableau; ??? }
a+

26/11/2006, 15h09
kamouminator
Citation:
Envoyé par mathieumadrid

Bonjour,

Je veux réaliser une liste itérative en C (je débute en C). Voici la structure LISTE:

Code:

1 2 3 4 5 6 7 /* Type LISTE*/ typedef struct { int capacite; int rang; char* tableau; } LISTE;
pourquoi tu parles de liste ?

Code:

if(liste.tableau!=NULL)

moi je mettrai ca !

et qu'est ce que tu entends par:

Citation:

et rien ne marche.

as tu testé la valeure de retour de ta fonction ?

Citation:
Envoyé par mathieumadrid
Code:

1 2 3 4 5 6 7 8 9 10 /* Créer une liste vide, d'une capacité initiale de ci places; retourne NULL si la création a échouée. */ LISTE creer(int ci) { LISTE liste; [...] return liste; }
Retourner une structure n'est pas conseillée....
Il est préférable de retourner un pointeur sur une structure que tu auras allouer dynamiquement au préalable.
Et cela resoudra les quelques questions que tu te poses un peu plus loin.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 /* Créer une liste vide, d'une capacité initiale de ci places; retourne NULL si la création a échouée. */ LISTE *creer(int ci) { LISTE *liste; liste = malloc (sizeof *liste); [...] return liste; }

26/11/2006, 15h43
mathieumadrid

Pour répondre à kamouminator:
Je parle de LISTE car je veux faire une liste d'éléments en C. On pourra consulter cette liste avec un rang. Par exemple, le premier élément de ma liste se trouve au rang 0.
Sinon je pense que

Code:

if(liste.tableau!=NULL)

et

Code:

if(liste.tableau)

revient au même.
Enfin j'ai testé les 4 façons de renvoyer une LISTE nulle et ça me renvoie:

Code:

iterative.c:22: erreur: conversion vers un type non scalaire demand'ee

Pour répondre à crocodilex:
Moi aussi, je voulais renvoyer un pointeur sur une LISTE mais vu que c'est un projet imposé par des professeurs, je suis obligé de renvoyer une LISTE. Tu ne sais pas comment faire pour renvoyer une LISTE nulle ?
26/11/2006, 16h36
gl

Citation:

Envoyé par mathieumadrid

Moi aussi, je voulais renvoyer un pointeur sur une LISTE mais vu que c'est un projet imposé par des professeurs, je suis obligé de renvoyer une LISTE. Tu ne sais pas comment faire pour renvoyer une LISTE nulle ?

Tu ne peux pas renvoyer une structure NULL. Ce qu'il est par contre possible c'est de renvoyer une structure "vide", c'est a dire avec un contenu indiquant qu'il y a eu un probleme de creation, par exemple dans ton cas avec capacite=0 et tableau=NULL.

Par contre es-tu vraiment certains que tes professeurs ne veulent pas que tu renvoit un pointeur plutot qu'une liste ? Ca me semble assez bizarre comme contrainte.
26/11/2006, 17h16
mathieumadrid

Moi aussi, je pense qu'il faut renvoyer une liste nulle (ça doit être une erreur dans le sujet). Sinon, pour compter le nombre d'éléments, on peut compter avec un pointeur sur le tableau ou en introduisant un champ nbelements dans la structure LISTE ???
26/11/2006, 18h23
kamouminator
ta liste est en fait une chaine de caracteres,
alors pour compter tu compte jusqu'au caractere de fin de chaine '\0'
il faudrai bien entendu qu'a chaque fin de chaine tu trouve le '\0'
je te conceil de le faire juste apres le malloc: remplir tout ton tableau de '\0'
et ensuite lorsque tu le rempli par des caracteres, ne pas depasser ci (c'est bien la capacité ?) moins 1 : ci-1

ou alors, des le debut allouer ci+1 octets a ton tableau
le 1 etant pour le caractere de fin de chaine au cas ou tu rempli completement la capacité...
je sais pas si je suis clair....
Code:

1 2 for(i=0;liste.tableau[i]!='\0';i++){} \*une fois sorti de la boucle,i+1 sera ton nombre d'elements*\
mais tu peux aussi rajouter un element nbelements à ta structure...
26/11/2006, 19h03
crocodilex
Citation:
Envoyé par kamouminator

ta liste est en fait une chaine de caracteres,
alors pour compter tu compte jusqu'au caractere de fin de chaine '\0'
il faudrai bien entendu qu'a chaque fin de chaine tu trouve le '\0'
je te conceil de le faire juste apres le malloc: remplir tout ton tableau de '\0'
et ensuite lorsque tu le rempli par des caracteres, ne pas depasser ci (c'est bien la capacité ?) moins 1 : ci-1

ou alors, des le debut allouer ci+1 octets a ton tableau
le 1 etant pour le caractere de fin de chaine au cas ou tu rempli completement la capacité...
je sais pas si je suis clair....

Code:

1 2 for(i=0;liste.tableau[i]!='\0';i++){} \*une fois sorti de la boucle,i+1 sera ton nombre d'elements*\

mais tu peux aussi rajouter un element nbelements à ta structure...
Comment tu vois que c'est une chaine de caractère ?
Le P.O n'a pas parlé de chaine de caractère, à moins que j'ai mal lu...
26/11/2006, 19h05
mathieumadrid

en fait, c'est une liste d'ELEMENT. Un ELEMENT est une structure que l'utilisateur définiera quand il voudra utiliser une LISTE. Il faudra qu'il caste par (char*) pour pouvoir utiliser les fonctions. Il ne faut donc pas voir ça comme des chaînes de caractères. Comment compter alors ?
26/11/2006, 19h13
crocodilex

Citation:

Envoyé par mathieumadrid

en fait, c'est une liste d'ELEMENT. Un ELEMENT est une structure que l'utilisateur définiera quand il voudra utiliser une LISTE. Il faudra qu'il caste par (char*) pour pouvoir utiliser les fonctions. Il ne faut donc pas voir ça comme des chaînes de caractères. Comment compter alors ?

Je n'ai pas bien saisie ton problème....
Le membre "capacite" de ta structure contient le nombre d'objet alloué (cf ta fonction creer() ).
Donc où est le problème ?
26/11/2006, 19h16
kamouminator

Citation:

Envoyé par crocodilex

Comment tu vois que c'est une chaine de caractère ?
Le P.O n'a pas parlé de chaine de caractère, à moins que j'ai mal lu...

bah a cause du char * tableau...
meme si c'etait pas une chaine de caractere, ca aurais pu etre une solution pour marquer la fin...
mais apperement c'est pas ca qu'il cherche a faire...
26/11/2006, 19h17
kamouminator

Citation:

Envoyé par crocodilex

Je n'ai pas bien saisie ton problème....
Le membre "capacite" de ta structure contient le nombre d'objet alloué (cf ta fonction creer() ).
Donc où est le problème ?

nan ! capacité c'est le nombre d'elements qu'elle peut contenir !
le nombre d'lements peut etre inferieure a la capacité du tableau...enfin, je crois
26/11/2006, 19h20
crocodilex

Citation:

Envoyé par kamouminator

bah a cause du char * tableau...
meme si c'etait pas une chaine de caractere, ca aurais pu etre une solution pour marquer la fin...
mais apperement c'est pas ca qu'il cherche a faire...

Son tableau peut contenir n'importe quoi. L'octet 0 peut en faire partie.
A lui de nous dire ce qu'il veut faire exactement, jusqu'à présent je n'ai pas bien compris.
26/11/2006, 19h21
kamouminator

oui oui, j'y avais pas pensé ! ^^
26/11/2006, 19h22
crocodilex

Citation:

Envoyé par kamouminator

nan ! capacité c'est le nombre d'elements qu'elle peut contenir !
le nombre d'lements peut etre inferieure a la capacité du tableau...enfin, je crois

En effet, on peut voir ça ainsi. Là tu as sans doute raison...
26/11/2006, 19h25
kamouminator

Citation:

Envoyé par mathieumadrid

en fait, c'est une liste d'ELEMENT. Un ELEMENT est une structure que l'utilisateur définiera quand il voudra utiliser une LISTE. Il faudra qu'il caste par (char*) pour pouvoir utiliser les fonctions. Il ne faut donc pas voir ça comme des chaînes de caractères. Comment compter alors ?

j'ai pas bien compris ce que doit contenir ton tableau !
il doi contenir des char ou LISTE ?

En fait, mon tableau doit contenir des éléments quelconques. Vu que je crée une bibliothèque .a, c'est à l'utilisateur de définir ces propres éléments (int, float, ...). On ne sait pas à l'avance ce que va mettre l'utilisateur dans LISTE.
Sinon voici mes fonctions modifiées grâces à vos réponses:

Code:

1
2
3
4
5
6
7
8
/* Type LISTE*/
typedef struct
{
	int capacite;
	int nbelements;
	int rang;
	char* tableau;
} LISTE;

Code:

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
/* Créer une liste vide, d'une capacité initiale de ci places;
   retourne NULL si la création a échouée. */
LISTE* creer(int ci)
{
	LISTE* liste;
 
	/* Allocation de la structure LISTE */
	liste = (LISTE*)malloc(sizeof(LISTE));
 
	/* Le premier élément de la liste sera de rang 0 */
	liste -> rang = 0;
 
	/* Allocation du tableau des éléments */
	liste -> tableau = (char*)malloc(sizeof(char) * ci);
 
	/* Test de création de la liste */
	if(liste -> tableau)
	{
		liste -> capacite = ci;
		return liste;
	}
 
	return NULL;
}
 
/* Détruit la liste et la fait pointer sur NULL. */
void detruire(LISTE* liste)
{
	/* Libération de l'espace mémoire */
	if(liste -> tableau)
	{
		free(liste -> tableau);
		if(liste)
			free(liste);
	}
 
	/* liste pointe sur NULL */
	liste = NULL;
}
 
/* Retourne le nombre d'éléments contenus dans la liste. */
int nbElements(LISTE liste)
{
	return liste.nbelements;
}
 
/* Retourne la capacité de stockage de la liste. */
int capacite(LISTE liste)
{
	return liste.capacite;
}
 
/* Retourne une valeur différente de 0 quand la liste est vide, 0 sinon. */
short estVide(LISTE liste)
{
	return (liste.nbelements == 0);
}
 
/* Retourne une valeur différente de 0 quand la liste est pleine, 0 sinon. */
short estPleine(LISTE liste)
{
	return (liste.nbelements == liste.capacite);
}
 
/* Retourne l'adresse de l'élément de rang i de la liste, NULL si l'élément n'existe pas. */
char* consulter(LISTE liste, int i)
{
	return &(liste.tableau[i]);
}

26/11/2006, 19h55
kamouminator

si tu rajoute un element nbelements a ta structure,
il suffi de l'incrementer a chaque fois que tu ajoute quelque chose au tableau
et le decrementer a chaque fois que tu suprime un element du tableau
en faisant bien attention a la limite ci
26/11/2006, 19h59
mathieumadrid

oui, c'est pour ça que je voulais introduire nbelements dans la structure. Mais est-ce possible de faire autrement en parcourant le tableau par exemple (avec un pointeur) ?
26/11/2006, 20h00
kamouminator

et je pense qu'un probleme va se poser si tu utilise un tableau de char !
tu ne pourra pas y mettre de float ou d'int...
26/11/2006, 20h02
kamouminator

Citation:

Envoyé par mathieumadrid

oui, c'est pour ça que je voulais introduire nbelements dans la structure. Mais est-ce possible de faire autrement en parcourant le tableau par exemple (avec un pointeur) ?

et bien il faudra une valeur que l'utilisateur ne rentrera jamais !tu la met dans la case apres ton dernier element.
et quand en parcourant ton tableau tu tombe dessus, tu arretes de compter...mais ca me parrait difficile, vu que tu n'a aucune idée de ce que l'utilisateur peut entrer...
26/11/2006, 20h15
kamouminator

c'est dans l'ennoncer qu'on te demande un tableau de char ?

Salut,

Que penserais tu d'une structure beaucoup plus simple, et de travailler, effectivement, avec une liste simpelent chainée :question:
Un truc du genre de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
typedef struct SValeur
{
    /* à remplire avec les bons éléments, dépendemment des besoins */
}Val;
/* Les noeud de la liste */
typedef struct SNoeud
{
   /* qui contiennent chacun une valeur */
   Val Valeur;
   /*et un pointeur vers l'élément suivant */
   struct SNoeud *Suivant;
}Noeud;

La récursivité peut venir bien à point pour certaines fonctions, entre autre:
pour savoir le nombre de noeuds présents dans la liste

Code:

1
2
3
4
5
6
7
 
int CompteNoeud( Noeud *actuel)
{
    if(actuel->Suivant==NULL)
        return 0;
    return CompteNoeud(actuel->Suivant)+1;
}

Pour la création d'un nombre donné de noeuds

Code:

1
2
3
4
5
6
7
8
9
10
 
Noeud* Init(int combien)
{
    Noeud* nouveau=malloc(sizeof(Noeud));
    if(combien==0)
        nouveau->Suivant=NULL
    else
        nouveau->Suivant=Init(combien-1);
    return nouveau;
}

pour la libération de la mémoire allouée à toute la liste

Code:

1
2
3
4
5
6
7
8
 
void Libere(Noeud* actuel)
{
    if(actuel->Suivant!=NULL)
        Libere(actuel->Suivant;
    actuel->Suivant=NULL;
    free(actuel);
}

Pour obtenir un pointeur sur les valeurs

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Val* GetValeurs(Noeud* actuel, int index)
{
    Val* retour;
    if(index==0)
        retour=&(actuel->Valeur);
    else
    {
        if(actuel->Suivant==NULL)
        {
            retour=NULL;
            printf("indice hors limites\n");
        }
        else
            retour=GetValeur(actuel->Suivant, index);
    }
    return retour;
}

Pour l'insertion à n'importe quel position de la liste

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/*renverra le nouvel élément inséré */
Noeud* InserePos(Noeud* actuel, Val valeur, int index)
{
    Noeud *Retour;
    if(index==0)
    {
        Retour=malloc(sizeof(Noeud));
        Retour->Suivant=actuel->Suivant;
        Retour->Valeur=valeur;
        if(actuel!= NULL)
            actuel->Suivant=Retour;
    }
    else
    {
        Retour=InserPos(actuel->Suivant, valeur, index-1)
        if(actuel->Suivant==NULL)
            actuel->Suivant=Retour;
    }
    return Retour;
}

Pour définir les valeurs

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void SetVal(Noeud* actuel, Val valeur, int index)
{
    if(index==0)
        actuel->Valeur=valeur;
    else
    {
        if(actuel->Suivant==NULL)
            printf("index hors limites");
        else
            SetVal(actuel->Suivant, valeur, index-1);
    }
}

Voire, si tu dispose dans ta structure "Val" de la possibilité de tester si c'est vide, pour compter le nombre d'éléments remplis (symbolisé ici par le test actuel->Val.rempli==0)

Code:

1
2
3
4
5
6
7
 
int CompteRemplis(Noeud *actuel)
{
   if(actuel->Val.rempli==0 || actuel->Suivant==NULL)
       return 0;
   return CompteRemplis(actuel->Suivant)+1
}

Avec tout cela, je crois que tu as les principales fonctions qui te seront nécessaires (peut etre à renommer quand meme ;))