J'aurais besoin d'aide pour vérifier que mon implémentation des listes chainées fonctionne correctement.
Pour le moment, je n'ai créé que des listes chainées d'entiers (int) et il y a possibilité d'initialiser cette liste soit avec un entier, soit avec un tableau d'entiers, et aussi d'ajouter des éléments en fin de liste après sa création.
Merci d'avance pour votre aide
Voici, dans l'ordre, mon header et mon code source:
liste_chainee.h :
#ifndef LISTE_CHAINEE_H_INCLUDED
#define LISTE_CHAINEE_H_INCLUDED
typedef struct Element Element;
struct Element
{
int nombre;
Element *suivant;
};
typedef struct IntList IntList;
struct IntList
{
Element *premier;
int len;
};
IntList *initintlist(int nombre);
IntList *inittablist(int *tableau);
void appendint(IntList *liste, int nombre);
#endif // LISTE_CHAINEE_H_INCLUDED
liste_chainee.c :
#include <stdio.h>
#include <stdlib.h>
#include "liste_chainee.h"
IntList *initintlist(int nombre)
{
/* L'espace memoire necessaire est alloue*/
IntList *liste = malloc(sizeof(*liste));
Element *element = malloc(sizeof(*element));
if (liste == NULL || element == NULL)
{
exit(EXIT_FAILURE);
}
/* Creation d'une liste chainee a 1 element,
contenant le nombre passe en parametre
*/
element->nombre = nombre;
element->suivant = NULL;
liste->premier = element;
liste->len = 1;
return liste;
}
IntList *inittablist(int *tableau)
{
/* L'espace memoire necessaire est alloue*/
IntList *liste = malloc(sizeof(*liste));
Element *element = malloc(sizeof(*element));
if (liste == NULL || element == NULL)
{
exit(EXIT_FAILURE);
}
/* Ajoute succesivement les elements du tableau passe
en parametre a la liste chainee en utilisant la
fonction (void appendint(IntList *liste, int nombre))
definie apres
*/
element->nombre = tableau[0];
element->suivant = NULL;
liste->premier = element;
liste->len = 1;
int n = sizeof(tableau) / sizeof(tableau[0]);
for (int i = 1; i<n; i++)
{
appendint(liste, tableau[i]);
}
return liste;
}
void appendint(IntList *liste, int nombre)
{
/* Grace a la boucle while, on cherche le
dernier element de la liste chainee
*/
Element *element = liste->premier;
while (element->suivant != NULL)
{
element = element->suivant;
}
/* On alloue l'espace necessaire pour le nouvel element */
Element *nouveau = malloc(sizeof(*nouveau));
if (nouveau == NULL)
{
exit(EXIT_FAILURE);
}
/* Initialisation du nouvel element et
mise a jour de la taille de la liste
*/
element->suivant = nouveau;
element->nombre = nombre;
liste->len++;
}
Je n'ai pas testé ton code (l'as-tu fait ?), mais dans ta fonction IntList *inittablist(int *tableau)tu dois passer la taille du tableau, c'est à dire le nombre d'éléments qu'il comporte, car lorsque le tableau est passé en paramètre dans une fonction, ce qui est passé c'est en fait l'adresse mémoire du premier élément et pas réellement un type tableau. Autrement, la fonction n'est pas capable de déterminer cela toute seule et la seule chose que tu vas faire en faisant int n = sizeof(tableau) / sizeof(tableau[0]); dans cette fonction c'est diviser le nombre de bytes occupés en mémoire par une adresse mémoire par la taille en bytes d'un int.
il y a beaucoup de choses à dire concernant ton code.
Concernant «le code»
Voici les messages du compilo après avoir ajouté un include sur ton header … :
$ gcc -Wall -Wextra -fanalyzer -c liste_chainee.c
liste_chainee.c: In function ‘inittablist’:
liste_chainee.c:50:40: warning: division ‘sizeof (int *) / sizeof (int)’ does not compute the number of array elements [-Wsizeof-pointer-div]
50 | for (int i = 1; i<(sizeof(tableau) / sizeof(int)); i++))
| ^
liste_chainee.c:28:27: note: first ‘sizeof’ operand was declared here
28 | IntList *inittablist(int *tableau)
| ~~~~~^~~~~~~
liste_chainee.c:50:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘long unsigned int’ [-Wsign-compare]
50 | for (int i = 1; i<(sizeof(tableau) / sizeof(int)); i++))
| ^
liste_chainee.c:50:60: error: expected statement before ‘)’ token
50 | for (int i = 1; i<(sizeof(tableau) / sizeof(int)); i++))
| ^
liste_chainee.c:52:34: error: ‘i’ undeclared (first use in this function)
52 | appendint(liste, tableau[i]);
| ^
liste_chainee.c:52:34: note: each undeclared identifier is reported only once for each function it appears in
Si on supprime la parenthèse surnuméraire il reste un message important qui te rappelle qu'il est impossible de connaître le nombre d'élément d'un tableau si tu fournis uniquement un pointeur sur le premier élément (erreur classique de débutant).
Donc : il faut commencer par lire ce que ton compilo raconte et tenir compte de ses remarques.
Ensuite je pourrais rajouter :
heu … la liste vide ? tu l'as complètement zappée ?
nommage : si tu implémentes une structure de données, il est toujours préférable de préfixer tes primitives d'accès. Par exemple tu pourrais utiliser le préfixe intlist_ pour tout ce qui concerne des fonctions dédiées aux IntList. Ton API serait plus claire ainsi :
#ifndef LISTE_CHAINEE_H_INCLUDED
#define LISTE_CHAINEE_H_INCLUDED
typedef struct Element Element;
struct Element
{
int nombre;
Element *suivant;
};
typedef struct IntList IntList;
struct IntList
{
Element *premier;
int len;
};
IntList *intlist_init(int nombre);
IntList *intlist_init_from_array(int *tableau);
void intlist_append(IntList *liste, int nombre);
#endif // LISTE_CHAINEE_H_INCLUDED
ton API serait sans doute à revoir un peu. Par exemple, pourquoi ne pas avoir de constructeur qui renvoie une liste vide ?
#ifndef LISTE_CHAINEE_H_INCLUDED
#define LISTE_CHAINEE_H_INCLUDED
typedef struct Element Element;
struct Element
{
int value;
Element *next;
};
typedef struct IntList IntList;
struct IntList
{
Element *premier;
int len;
};
IntList *intlist_init(void);
IntList *intlist_init_from_int(int value);
IntList *intlist_init_from_array(size_t size, int array[size]);
void intlist_append(IntList *list, int value);
#endif // LISTE_CHAINEE_H_INCLUDED
ton API serait sans doute à revoir un peu. Par exemple, pourquoi ne pas avoir de constructeur qui renvoie une liste vide ?
tu remarqueras que dans cette version j'ai également corrigé l'initialisation à partir d'un tableau, et nettoyé le mélange franglais.
Il y a beaucoup de duplication de code !!!! surtout en ce qui concerne la gestion des maillons. Il faudra refactorer cela et le placer dans un module séparé. Par exemple un couple intlist_element.h/intlist_element.c avec comme API :
#pragma once
typedef struct intlist_element intlist_element_t;
intlist_element_t *intlist_element_new(int value);
intlist_element_t *intlist_element_full(int value, intlist_element_t *next);
int intlist_element_get_value(intlist_element_t *elem);
intlist_element_t *intlist_element_get_next(intlist_element_t *elem);
void intlist_element_set_value(intlist_element_t *elem, int value);
void intlist_element_set_next(intlist_element_t *elem, intlist_element_t *next);
Ici j'ai remplacé les include guards traditionnels par un plus moderne «#pragma once» de même effet. Si tu as besoin de créer un maillon tu as ce qu'il faut et c'est centralisé à un seul endroit = maintenance, debug et évolution facilités ;
…
Il y a d'autres remarques mais je vais déjà te laisser réagir à celles-ci.
Une petite remarque sans importance... Plutôt que :
IntList *inittablist(int *tableau);
je préfère :
IntList *inittablist(int tableau[]);
Oui, c'est équivalent. Mais équivalent pour l'ordinateur. L'être humain qui lit ces lignes voit deux choses qui ont un sens différent : un pointeur, un tableau. Voyant le tableau, il risque plus facilement de se dire « oups, j'ai oublié de transmettre la taille du tableau ».
Je pense que c'est une erreur que d'initialiser une liste en lui fournissant une ou des valeurs à insérer dès le départ. La fonction d'initialisation "initialise" une liste vide. Ça te prend également une fonction qui va afficher les éléments de ta liste. Pour ce qui est d'ajouter des éléments, il y a plusieurs possibilités: + ajouter au début (la plus facile) + ajouter à la fin + ajouter à une position + ajouter avant ou après une valeur (liste ordonnée)
Les trois premières pourraient appeler la même fonction.
Exemple:
insert(liste, valeur, 0) ajoute au début
insert(liste, valeur, -1) ajoute à la fin
insert(liste, valeur, position) on vérifie que la position est correcte d'après le descripteur de liste Pour ajouter tous les éléments d'un tableau, il faut appeler la fonction d'ajout appropriée au lieu de dupliquer le code. Cela évitera certaines erreurs. Si ça ne marche pas, on regarde à un seul endroit.
Il faut réduire le plus possible le nombre d'endroits où tu appelles malloc. Et il y aura les fonctions de suppressions correspondantes. Ou la modification d'un élément dans la liste.
Et chercher un élément dans la liste et retourner soit sa position soit sa valeur.
Quoi faire si l'élément n'est pas dans la liste ?
- Edité par PierrotLeFou 12 avril 2022 à 19:05:12
Le Tout est souvent plus grand que la somme de ses parties.
Minimaliste : on fournit un ensemble d'opérations les plus simples possible, qui suffisent (en les combinant) à tout faire
Utilitaire : on fournit des opérations qui permettent de faire d'un seul coup les opérations les plus courantes dans un programme (par exemple ajouter le contenu d'une liste à la fin d'une autre)
Si on vise la seconde approche, il faut mieux avoir écrit pas mal d'applications pour voir ce qui sera vraiment pratique à l'usage. Et aussi savoir où s'arrêter.
Ce qui est généralement rentable de faire est de suivre le principe KISS → keep it simple, stupid ← de manière non naïve.
Il vaut mieux avoir quelque chose de simple et fonctionnel qu'avoir tout un tas de possibilités non utilisées souvent buguées qui deviennent inutilisables. Cela permet aussi d'avoir une API évolutive sans être disruptive.
Je ne présenterai pas mon code ici (parce qu'il n'est pas présentable ...) J'ai quelques fonctions de base pour soutenir les autres: getArea qui demande de la mémoire avec malloc setList qui initialise une liste vide getNode qui initialise un noeud ckRange pour les accès par position Et les autres: insert qui insère par position (comme j'avais décrit) sorting qi insère en ordre search qui retourne la position correspondante à une valeur obtain qui retourne la valeur correspondant à une position delete qui élimine une valeur putout qui élimine une position change qui remplace une valeur par une autre modify qui remplace la valeur à une position reverse qui inverse l'ordre de la chaîne. display qui affiche une liste
Mes fonctions sont toutes très semblable mais trop différentes pour admettre une primitive commune. Je les trouve tout de même assez simples. Avec ça, on peut copier un tableau dans une liste ou recopier une liste dans une autre. On peut faire une fonction pop en combinant search/obtain avec delete/putout, mais ça n'est pas tout à fait efficace.
- Edité par PierrotLeFou 13 avril 2022 à 14:51:27
Le Tout est souvent plus grand que la somme de ses parties.
Implémentation des listes chainées
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.