Liste ou non ?

voici un pseudo code de ce que je veux faire :

tab contient un premier couple (a0,b0)
while (il y a des couples à traiter dans tab) {
(a,b)=premier couple de tab
tab = enleve(tab,a,b) /* enlève le couple (a,b) à la liste de couple à traiter */
resultat=proc(a,b);
if (resultat==quelquechose) {
(a1,b1)=fonction1(a,b)
(a2,b2)=fonction2(a,b)
tab = ajoute(tab,a1,b1) /* ajoute le couple (a1,b1) à la liste de couple à traiter */
tab = ajoute(tab,a2,b2) /* ajoute le couple (a2,b2) à la liste de couple à traiter */
}
}

Vous l'aurez compris, tab est la liste de couples à traiter. Ma question est : de quel type doit être tab ? une liste chaînée, une chaine de caractère, un tableau, ...
En effet, je dois pouvoir faire indépendamment les deux actions suivantes :
- ajouter un couple (a,b) à la liste de couples à traiter
- extraire le premier couple de la liste et le supprimer de la liste


Des idées ?

Merci

perso, je te conseillerai une petite liste chainée... c'est un peu plus long a mettre en place mais ça devrai mieux marcher... apres tout dépend du nombre de manipulation que tu as a faire, ça peux devenir trop long avec une liste chainée.

mais bon vu comme c'est présenté une liste chainée de classe d'éléement ça me semble bien

voir un arbre...

Une liste chaînée avec un pointeur vers la tête et un pointeur vers le dernière élément si tu ajoutes en fin de liste. Ça s'appelle en fait une file !

oui et?

et quoi ?

je pense pas que de limiter l'acces a la chaine par deux pointeurs ( donc une liste) soit bien utile dans ce cas la...car il dois inclure des valeur pas obligatoirement en tête ou queu non?

Merci pour vos réponses.

Pour plus de précision, il importe peu que j'ajoute en début ou en fin de chaine : il faut juste que je puisse ajouter facilement (et rapidement surtout) et extraire un couple en le prenant toujours à la même place (le premier ou le dernier).

Actuellement, j'ai une solution où tab est une chaine de caractères et j'ajoute et enlève des bouts de chaines, deux couples correspondant à deux sous-chaines séparées par des espaces. Cela fonctionne très bien mais je pense qu'il y a moyen de faire plus propre et surtout plus rapide (car c'est là le point essentiel de ma question).

comme on te l'a dit, le plus simple dans ce cas-là est une liste chaînée, dont tu ne gardes que le premier et dernier élément en variables. Et tu auras 2 fonctions :

ajouter ( FIN_OU_DEBUT )
enlever ( FIN_OU_DEBUT )

Salut,

Citation:

---

Envoyé par Trap D

Une liste chaînée avec un pointeur vers la tête et un pointeur vers le dernière élément si tu ajoutes en fin de liste. Ça s'appelle en fait une file !

---

Ah, non, pas forcément...

Le nombre et la position des pointeurs maintenu pour la gestion d'une structure dynamique n'a rien à voir avec le terme à utiliser pour "définir" cette structure...

Les termes "piles", "files" et "listes (doublement/simplement) chainées" fournissent des précisions sur la manière dont les éléments sont insérés/supprimés dans la structure, et sur la manière d'y accéder:

• pile: système LIFO (ou FILO, je ne sais jamais :oops:) - le premier rentré est le dernier sorti
• file: système FIFO - le premier rentré est le premier sorti
• liste: "aléatoire" - on peut ajouter, retirer ou accéder à un élément n'importe où dans la liste

Le fait de maintenir ou non un pointeur sur le début et/ou sur la fin de la structure n'est qu'une décision purement arbitraire de la part du programmeur, et influera sur les performances de la structure, non sur son usage ;)

Tu peux tres bien avoir une file avec un seul pointeur maintenu (mais tu devra parcourrir toute la file pour ajouter un élément), et avoir une liste avec deux pointeurs (ou plus) maintenu...

La seule exception est peut etre la pile, pour laquelle maintenir un pointeur sur la fin de la pile n'a que peu de sens ;)

Encore merci pour vos réponses.

J'ai opté pour une pile avec un seul pointeur vers l'élément en haut de la pile. Du coup, quand j'ajoute un élément, je le mets en haut de la pile et quand j'en suprime un, je prend celui du haut de la pile.

Ca fonctionne très bien.