Discussion :

[BrahimLamri]

Salut tout le monde ,

J'ai un problème avec un exercice qui me demande de définir une structure de données contiguë pour représenter une liste bidirectionnelle afin de réaliser quelque fonction et procédure tel que : ajouter un élément lire un élément , trier la liste ... etc .
quelqu'un peut m'expliquer le principe de cet exercice et peut me donner quelques indices


Merci

[AdmChiMay]

Bonsoir,

Je suppose que tu veux parler d'un RECORD ? Et que donc que tu les as vus en cours ?
Puis-je aussi supposer que tu as vus les pointeurs (avec les "^") en cours ? Et comment les utiliser ?

Parce qu'une liste, c'est d'une part des paquets avec des informations à stocker, et d'autre part dans chaque paquet, un (ou des) pointeur(s) vers un (des) autre(s) paquet(s).
Donc :

• ton paquet c'est un RECORD,
• ta liste d'informations / de données, c'est toi qui décide des variables que tu y stockes,
• dans une liste uni-directionnelle, il faut un pointeur vers le suivant,
• dans une liste bi-directionnelle, il faut aussi un pointeur vers le précédent.

Bon, il est fortement préférable de savoir où est la tête de liste, et souvent utile de savoir où est la fin de la liste. Ce qui veut dire stocker ces deux informations (des pointeurs, forcément) dans deux variables, éventuellement regroupées au sein d'un autre type de RECORD.

Vois-tu une manière de t'organiser avec cela ?

[BrahimLamri]

Le problème ce n'est pas le RECORD ou les pointeurs , je connais bien ces notions , le problème c'est comment je peux représenter un liste (une structure de donnée dynamique ) , dans une structures de donnée statique contiguë ( un Tableau ) ?

[AdmChiMay]

Donc, si je comprends bien, tes record (ou autre) sont stockés dans un tableau ? Et ce tableau, on essaye de ne pas le triturer ?

Si c'est tableau, alors il a des indices (p.ex. de 1 à max).
Rien ne t'empêche d'avoir un autre tableau (de 1 à max), qui contient des entiers, lesquels représentent les indices dans le tableau de données d'origine ? Bref, ton second tableau sert de "pointeurs", d'indirection. C'est généralement le cas lorsque les données d'origine sont grosses et qu'on essaye de ne pas les bouger sans raison valable. Et tu passes par le second tableau pour avoir le côté dynamique (c'est toi qui programme le dynamisme).

Exemple :

• Données : tableau Data[1..max]. Ok, il est statique.
• Nombre d'éléments dans le tableau (et donc dans la liste) : n tel que 1<= n <= max
• Ta liste : un autre tableau "Liste", contenant une liste de trois entiers pos (indice dans Data de ton paquet), succ (indice dans Data du paquet suivant), pred (indice dans Data du paquet précédent). Soit tes entiers sont dans un record, soit ils ont chacun leur ligne dans le tableau. Je prends par exemple cette seconde option, donc 1 pour pos, 2 pour succ, 3 pour pred. Soit quelque chose du type Liste[1..max][1..3]

D'où :

• Liste[1,1] : indice dans Data du paquet de tête de la liste.
• Liste[1,3] = 0 et Liste[n,2] = 0, forcément, n'est-ce pas ?
• Data(Liste(1,1))^.truc : l'information truc du premier élément de la liste
• Liste[n,1] : indice du dernier élément de ta liste :
• Data(Liste(i,1)) : iè élément de la liste
• Data(Liste(i,1))^.truc : la donnée truc du iè élément de la liste
• Data(Liste(i,2)) : le successeur du iè élément
• Data(Liste(i,3)) : le prédécesseur du iè élément

Après, tu gères ta liste via le tableau Liste[][]. C'est dans ce tableau que tu bouges, décales, insère, etc. Mais ton premier élément de liste est toujours à Liste[1,...] et le dernier à Liste[n,...].

Cela correspond-il mieux ?
En fait, il n'y a plus de pointeur, c'est toi qui gère le "pointage" (je devrai plutôt dire le référencement) via un autre tableau.

Note d'édition : j'ai mis des "()" et pas des "[]", car que ce soit en écriture normale ou en mode code, j'ai un passage à la ligne systématique entre le mot Data et "[" ! ! !

[Roland Chastain]

Bonsoir ! On pourrait peut-être remplacer l'adresse dans la mémoire par l'adresse dans le tableau, c'est-à-dire par l'index du paquet suivant ou précédent. Au lieu du pointeur, on utilise un nombre entier qui exprime un index. Personnellement, c'est comme ça que je l'ai compris.

P.-S. Je n'avais pas vu la réponse d'AdmChiMay.

[BrahimLamri]

Est-ce que je peux utiliser un seul tableau ( un type record ) qui contient la donnée , et deux autres variable de type integer , une pour le suivant , et l'autre pour le précédent ?
Et si je déclare un tableau [1..100] , comment je peux insérer une donnée dans la case 'N' donné par l'utilisateur
sans écraser la donnée dans la case 'N' ? j'ai essayer de décaler les cases du tableau vers la fin , mais cela m'oblige à chaque fois de déclarer un tableau plus grand p.ex: [1..101] !

[AdmChiMay]

Ok, tu pars sur une autre piste.
Première réponse : mais tu fais comme tu veux ! Du moment que tu n'oublies aucune information…

Suggestion : prends des pièces, des sucres, n'importe quoi, et simules à la main ce qu'il faut faire.
Ensuite, même chose avec les deux super-méga-outils qu'on a pas encore fait mieux : papier+crayon.

Par contre, fais très attention à ce que tu écris, à ta manière de formuler. Parce que "un tableau de type record", je ne comprends pas. Mais, un tableau de (contenant des) records, là oui.

Tes integers pour suivant/précédent, sont-elles dans le record ?
- si oui : ok, tu as un tableau à une dimension de records,
- si non : ok, mais tu dois avoir (par exemple) deux lignes supplémentaires à ton tableau; et ne pas oublier qu'un élément de liste c'est 3 cases du tableau.

Ton tableau fait [1..100] ? Déclares donc la constante max = 100, et ton tableau fait [1..max].
Tu veux insérer un élément ? Il faut que tu connaisses à tout instant la longueur que fait déjà ta liste, par exemple avec une variable entière LongueurListe. Et forcément, tu dois toujours vérifier que LongueurListe > 0 si tu veux enlever un élément, et que LongueurListe < max si tu veux en ajouter.

Maintenant, on suppose qu'il y a de la place dans le tableau. Tu veux insérer un élément à la Nème place de la liste.

* Si ton tableau contient les éléments dans le bon ordre, il suffit de décaler (recopier) d'un cran vers le bout du tableau les éléments de N à LongueurListe, et d'insérer le nouveau à N.
*Si tu gères les indices suivant et prédécesseur, c'est que les éléments de ta liste sont bien dans le désordre dans le tableau, non ? Donc que tu dois savoir à quelle indice est le premier élément de la liste (donc avoir une variable pour cela) ? Et cet indice n'est pas forcément 1, car tu ne sais pas ce qu'a déjà subi ta liste.Tu as deux manières de gérer ton tableau : en faisant beaucoup de déplacements/recopies, ou pas.

* Cas avec beaucoup de recopies. Si tu veux que ton tableau ne contienne pas de "trous", il faut à chaque modification tasser tous les éléments :

- si tu enlèves un élément, il faut tout tasser vers le début du tableau,
- si tu ajoutes un élément, tu le rajoutes au bout de ce qui existe.

* Cas en limitant les déplacements/recopies :

- si tu enlèves un élément, tu mets simplement à jours les champs suivant précédent de ceux qui l'encadrent; voir par précaution (ou pour être utile plus tard quand tu chercheras de la place) tu mets ses champs à jour.
- si tu ajoutes un élément, tu cherches la première place libre, tu l'y mets, et tu mets à jour les champs suivant/précédent pour lui et ceux qui l'encadrent.

Voilà, tout "bêtement".