Discussion :

[mido1951]

Bonjour,

je voulais savoir si j'utilise une liste chainée ou enregistrement ?
Pour moi je veux bien utiliser les enregistrements mais ils m'ont dis d'utiliser les listes chainées donc si c'est possible je peux votre avis sur ça.

Merci.

[ternel]

Si tu te poses la question, c'est qu'il n'y a pas de réponse universelle.
Il nous faut donc un contexte, pourrais-tu nous exposer le tien?

Au passage, qu'appelles-tu un enregistrement?

[mido1951]

Si tu te poses la question, c'est qu'il n'y a pas de réponse universelle.
Il nous faut donc un contexte, pourrais-tu nous exposer le tien?

Au passage, qu'appelles-tu un enregistrement?

Un enregistrelent est une structure de données. la declaration comme la declaration d'une liste chainée mais pas de pointeur.
en fait, moi je veux stocker dans un tableau des position et chaque position a ses proriétés (par exemple).
donc le TABLEAU sera composé de deux colonnes (index, position) et dans la colonne position j'ai plusieurs valeurs: [pos1,num1],[pos2,num2],...
donc pour une ligne de mon tableau j'ai index1, [pos1,num1],[pos2,num2],... donx ici je voulais savoir est pour [pos1,num1],[pos2,num2] est j'utilise une liste chainée ou une structure sans pointer sur l'élément suivant?
je voulais avoir des avis des experts.
Merci

[Médinoc]

Ben ça dépend de ce que tu en fais.

• Si tu fais de la lecture pure avec besoin de recherche rapide (recherche dichotomique etc.) tu utilises un tableau.
• Si tu fais un truc qui est modifié de nombreuses fois durant l'exécution du code, une liste chaînée sera plus appropriée.

[ternel]

Le tableau et la liste chainée sont deux techniques pour répondre à un besoin commun: disposer d'une séquence de choses.
Il y a plusieurs différences entre ces deux techniques, et l'une d'elle est fondamentale:
un tableau est de taille constante, une liste chainée est de taille variable.

Il y a deux variantes principales de chainage: le chainage externe et le chainage dit intrusif.
supposons que je veuille une séquence de points.

avec un chainage intrusif (le plus classiquement utilisé en C), on aurait quelque chose comme:

Code :

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

1
2
3
4
struct point {
    int x, y;
    struct point* suivant;
};

Avec un chainage externe, par contre, on aurait deux structure: une chaine, et un point

Code :

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

1
2
3
4
5
6
7
8
struct point {
    int x, y;
};
 
struct chainon_point {
    struct point *p;
    struct chainon_point *suivant;
};

L'intéret de seconde solution est de pouvoir placer le même point dans plusieurs chaines.

Dans ton cas, si tu sais combien tu auras d'éléments à lister, préfère le tableau. Si tu connais un maximum tu peux aussi tenter le tableau.
Si ta séquence n'est pas vraiment bornée, tu n'as d'autre choix que la liste chainée

[mido1951]

Le tableau et la liste chainée sont deux techniques pour répondre à un besoin commun: disposer d'une séquence de choses.
Il y a plusieurs différences entre ces deux techniques, et l'une d'elle est fondamentale:
un tableau est de taille constante, une liste chainée est de taille variable.

Il y a deux variantes principales de chainage: le chainage externe et le chainage dit intrusif.
supposons que je veuille une séquence de points.

avec un chainage intrusif (le plus classiquement utilisé en C), on aurait quelque chose comme:

Code :

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

1
2
3
4
struct point {
    int x, y;
    struct point* suivant;
};

Avec un chainage externe, par contre, on aurait deux structure: une chaine, et un point

Code :

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

1
2
3
4
5
6
7
8
struct point {
    int x, y;
};
 
struct chainon_point {
    struct point *p;
    struct chainon_point *suivant;
};

L'intéret de seconde solution est de pouvoir placer le même point dans plusieurs chaines.

Dans ton cas, si tu sais combien tu auras d'éléments à lister, préfère le tableau. Si tu connais un maximum tu peux aussi tenter le tableau.
Si ta séquence n'est pas vraiment bornée, tu n'as d'autre choix que la liste chainée

merci pour ta reponse.
pour moi je ne connais pas la longueur de mon tableau mais je connais sa plus longue taille mais je pense les listes chainées permettent de gangner en mémoire parceque si j'utilise les enregistrements et je fixe une taille MAX peut etre que je perds en mémoire puisque je ne vais pas remplir toutes les cases à MAX.
qu'est ce que vous pensez?

[Sve@r]

merci pour ta reponse.
pour moi je ne connais pas la longueur de mon tableau mais je connais sa plus longue taille mais je pense les listes chainées permettent de gangner en mémoire parceque si j'utilise les enregistrements et je fixe une taille MAX peut etre que je perds en mémoire puisque je ne vais pas remplir toutes les cases à MAX.
qu'est ce que vous pensez?

Bonjour

Encore une fois ça dépend du contexte. Si MAX est de l'ordre de 100, ou 1000, ou 10000, ou même 100000 ça n'a pas d'importance (encore que ça dépende aussi de la taille de ta structure). Si MAX est de l'ordre du million ou milliard, ça peut jouer. Mais même si MAX était à 1 milliard mais que tu stockes effectivement 999 999 999 éléments ben alors ça ne jouerait plus (parce qu'avec un tableau ou une liste chainée ça reste 999 999 999 et que perdre "1" avec un tableau ne compte pas).

Ceci dit, leternel a écrit qu'un tableau était de taille constante mais il a oublié de préciser qu'il pouvait être aussi alloué dynamiquement (malloc) puis agrandi par la suite (realloc). Tu peux alors très bien définir un MAX à 1000 et allouer donc 1000 éléments d'un coup, puis dès que tu arrives au 1001° élément tu réalloues 1000 de plus. Et etc.
Ca peut se faire très facilement dans un algo de ce type

Code c :

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
#define MAX         (1000)
typedef struct {
	struct s_ton_element *tab;
	struct s_ton_element *tmp;
	size_t nb;
	size_t max;
} t_alloc;
 
t_alloc data;
data.tab=NULL;
data.tmp=NULL;
data.nb=0;
data.max=0;
 
while (je lis un élément à stocker)
{
	// Si on a atteint le max éléments stockés (ce qui arrivera aussi la première fois vu que nb et max sont égaux à 0)
	if (data.nb == data.max)
	{
		// On réalloue MAX de plus - Dans le cas où le pointeur à réallouer est NULL, realloc se comporte comme malloc
		data.max+=MAX;
		data.tmp=realloc(data.tab, data.max * sizeof(struct s_ton_element));
 
		// Vérification allocation échouée
		if (data.tmp == NULL)
		{
			// Dans ce cas, on ne peut plus rien faire - On nettoie donc ce qui avait été éventuellement alloué précédemment et on quitte
			free(data.tab);
			return valeur_specifique_indiquant_echec;
		}
 
		// L'allocation/réallocation a réussie, on la recopie dans la bonne zone
		data.tab=data.tmp;
	}
 
	// Quoi qu'il arrive, ici on a forcément la place de stocker notre élément
	data.tab[data.nb]=element_a_stocker;
 
	// On a stocké un élément de plus
	data.nb++;  // on peut regrouper les deux lignes en data.tab[data.nb++]=element_a_stocker;
}

Tu peux le dérouler dans tous les sens, tu auras toujours la place pour stocker tout ce que tu lis. Et sur un ordi avec beaucoup de mémoire tu peux tailler MAX en très large, mais si tu es restreint tu le tailles à 1.

Bien entendu ça a un inconvénient (toute solution possède toujours des avantages et des inconvénients) c'est que contrairement à la liste (où l'allocation est facile car tu alloues à chaque fois un élément qui sera alloué n'importe où il y a de la place pour un élément), le malloc/realloc doit toujours allouer la zone demandée en un seul bloc contigû (pour qu'on puisse l'utiliser comme un tableau) et que s'il n'a plus de place là où il se trouve pour répondre à la demande, il devra déplacer tout ce qui a déjà été alloué dans une zone plus large. Ce qui peut alors prendre du temps.