procèdure insertion en fin de liste

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: sandrine_guillerme

Bonjour tout le monde,

Petit souci .. je bloque .. (oué je bosse l'info, ce sont les voeux de Dominique en m temps )

bref,

j'aimerais écrire un programme en algo pr inserer un élèment en fin de liste, (oui les listes chaînées quoi )

je commence,

structure élém_liste
{
donnée: t // type à définir auparavant
lien: pointeur sur élém_liste
}
p : pointeur sur élèm_liste

// C'est à partir de cette fonction que je ne comprends pas le raisonnement..

fonction dernier (E liste : pointeur):pointeur
// la fonction prend en entrèe une liste d'accord, et retrourne un pointeur .. oui mais pourquoi !!! on pourrait bien se débrouiller sinon ? non ..?
{
tant que ( liste -> lien != NUL) faire
liste <- liste -> lien // je ne comprends pas trop ce que ça veut dire mais si ça veut dire un passage à l'élèment suivant on pourrait faire p->lien<- liste
retourner liste

}

Je vous prie de m'éxpliquer ça déjà .. après peut être j'aurais pas besoin de mettre la suite, je le comprendrais peut être,
et merci d'utiliser les termes les plus simples possible ..

Cordialement..


Posted by: Joker62

Et bien la fonction retourne un pointeur sur le dernier élément de la liste.
En gros ça retourne l'adresse mémoire du dernier élément.

Et donc la boucle c'est en gros :

Tant qu'on est pas arrivé au dernier,
Alors on avance le pointeur au suivant.

Les pointeurs c'est délicats j'avoue.


Posted by: sandrine_guillerme

Salut joker,

Oui Délicat, délicat,

tant pis je mes la suite ,

procedure insert_fin (E/S liste: pointeur , E: val :t)
{
der , p : pointeur
si (liste = NUL ) alors
insert_debut ( liste, val)
// ok

sinon

der <- dernier(liste) // je comprends pas ça .. !
p<- allouer élèm_list
p->lien <- NUL
der -> lien <- p
}
}
tu comprends ça toi joker?


Posted by: Joker62

Désolé pour le retard :D

Donc der pointe vers l'adresse du dernier élément de Liste
C'est comme si on avait mit une grosse flêche vers la dernière case en faite :

Donc on après on alloue un peu d'espace mémoire pour le pointeur qu'on va ajouter à la fin ( ie : p )

Et on dit que der -> lien = p

Donc on vient de créer un lien de la dernière case vers p, ce qui veut dire que p est le dernière.

Le fait qu'on récupère le pointeur vers le dernier permet un accés direct à la mémoire, on ne peut pas récupéré une structure car déjà impossible dans certain langage, et si c'est possible, on en reçoit une copie, donc quand on la modifie, ça changera rien à l'originale.

Tandis que là, on s'attaque à la source du problème, à l'adresse mémoire carrément ! c'est sympa les pointeurs en fait ;)


Posted by: sandrine_guillerme

Ay, :s

J'ai pas tout capté là ..
récapitulons,

je sais que si on point sur liste (début) on utlilise, la procèdure insérer au début (qui est largement plus facile d'ailleurs)

mais si non on fait :

der <- dernier(liste)
p<- allouer élèm_list
p->lien <- NUL
der -> lien <- p


pourquoi pointer sur NUL ?? et après passer à l'élèment suivant rrrrrrr .. m'énerve ça ..


Posted by: Joker62

Allez on refait la procédure en français :)

Donc on veut insérer à la fin d'une liste, un nouvel élément.

Si la liste est vide, alors, ajouter à la fin, c'est la même chose qu'ajouter au début...
Si elle est pas vide, c'est différent.

Pour ajouter un dernier élément, on doit d'abord récupéré l'adresse du dernier élément, et oui l'adresse :D
Donc on la récupère avec la fonction que tu as proposé:
On a

Der = Dernier(liste);

Maintenant, que l'on sait que Der pointe sur le dernier élément de la liste, il suffit de lui ajouter un élément p.
Donc on a déclarer un pointeur p.
Mais il ne pointe nul part...
Donc bon ça sert un peu à rien...
On lui alloue alors une zone dans la mémoire.

On vient de créer une zone dans la mémoire, et p pointe sur cette zone.
P sera le nouveau dernier.
On sait qu'après le dernier, y'a plus rien du tout donc

p -> Lien = NULL; Pouf c'est la fin :)

On a déjà fait une bonne partie du travail, il manque juste le lien entre der et p
Parce que oui, l'ordi y'est pas super intelligent, il sait pas trop qu'on est entrain de faire une liste.

Donc der -> lien = p
Ce qui veut dire, la case après der c'est p.

Alors attention, ne surtout pas croire, que toutes les cases se suivent en mémoires, rien de tout ça, c'est pour ça qu'il faut utiliser les liens.

Pour compléter voici un petit dessin tout beau :D
http://img150.imageshack.us/my.php?...93810003zy8.jpg

NDLR : je vais au dodo, j'espère t'as compris un peu mieux (k)


Posted by: sandrine_guillerme

Alors là , je peux te dire que tu mérite un grand merci,

Je comprends vite mais il faut m'expliquer longtemps ..


merci joker,

Mais j'ai pas fini encore , si tu veux t'en dormir dis le, moi je reste encore !
J'ai un paquet de questions, et pour l'instant ze révise, je commence à aimer l'info grace à toi mon vieux ;)


Posted by: Joker62

Lol ben vas y alors continue donc les questions :)
J'reste core un tit peu :)


Posted by: sandrine_guillerme

Non non zy va zy va, y a pas de problème,

Tu les trouveras au meme endroit demain,

enfin taleur lol ..


Bah bonne nuit, et merci JoKer ..

merci beaucoup ..


Posted by: Joker62

Comme tu veux lol :)
Poste à volonté :D
J'aime bien ça moi les listes :D
J'avais toujours 3 TD d'avance :$

Bonne nuit à toi aussi :)


Posted by: sandrine_guillerme

Va Falloir que je bosse ça à fond la réccursivité, piles files, méthodes itératives, ..


pour tout dire, je commence à aimer ça, finalement vous avez raison, y a bien des maths qui se cachent derrière, enfin bon, je vais aller voir tout ça .. !

Bonne nuit .. ! (il se fait tard mais bon .. )


Posted by: Dominique Lefebvre

Citation:
Posté par sandrine_guillerme
Va Falloir que je bosse ça à fond la réccursivité, piles files, méthodes itératives, ..


pour tout dire, je commence à aimer ça, finalement vous avez raison, y a bien des maths qui se cachent derrière, enfin bon, je vais aller voir tout ça .. !

Bonne nuit .. ! (il se fait tard mais bon .. )


Un moyen simple de construire les algos de gestion de chaîne et de liste est de se demander ce que tu ferais pour ajouter un maillon sur une chaîne avec une extrémité fixée à un mure et l'autre extrémité libre. Les cas à imaginer : ajouter un maillon en début de chaîne, au milieu de la chaîne et en fin de chaîne.

PS : le reste c'est de la tambouille informatique, qui dépend pour beaucoup du langage que tu utilises..


Posted by: sandrine_guillerme

Oki Dom ,


je ferais ça ..

Merci..


Posted by: sandrine_guillerme

Oui, je reviens à mon paquet de question ..

Quelqu'un peut me donner une idée comment construit t on une liste bidirectionnelle ?

bon là c'est vrai, ce que je sais c'est l'insertion au début de la liste et en fin de liste, mais doit t on imaginer une liste circulaire .. même pas ..

Enfin je sais pas ..

Help ..


Posted by: Joker62

Hey bien dans la structure
tu rajoutes deux membres :

LienDroit : pointeur
LienGauche : pointeur

Ensuite il suffit juste de bien comprendre le système.
Comme pour la chaîne de maillon comme disait Dominique.


Posted by: sandrine_guillerme

Oki En effet .. je chercherais un exercice d'application, si je le trouve ce serait génial ..




Merci










-