Implémentation des listes doublement chaînées par tableaux !
Fermé
dx3d
Messages postés
68
Date d'inscription
dimanche 6 septembre 2009
Statut
Membre
Dernière intervention
19 juillet 2017
-
9 mai 2014 à 18:33
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 10 mai 2014 à 21:33
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 10 mai 2014 à 21:33
A voir également:
- Listes doublement chainees en c
- Liste déroulante en cascade - Guide
- Gertrude a préparé la liste des affaires à prendre pour l'excursion. juliette a modifié cette liste en utilisant le mode suivi des modifications proposé par le traitement de texte. - Guide
- Créer des listes déroulantes excel - Guide
- Supprimer les photos en double sur pc - Guide
- Comment mettre sa liste d'amis en privé sur facebook - Guide
4 réponses
jerome9359
Messages postés
693
Date d'inscription
mercredi 4 février 2009
Statut
Membre
Dernière intervention
10 juin 2019
159
9 mai 2014 à 18:41
9 mai 2014 à 18:41
oui c'est possible mais ça va être dur d'ajouter ou d'enlever des éléments de la liste... Le tableau en C est de taille fixe. Il Faut utiliser des structure de donné
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 842
10 mai 2014 à 00:34
10 mai 2014 à 00:34
Bonjour,
Au pire, tu peux utiliser de l'allocation dynamique. Tu peux réallouer la zone avec realloc().
Mais bon, cela ne s'appelle pas implémenter une liste doublement chaînée ;-))).
Cdlt,
Au pire, tu peux utiliser de l'allocation dynamique. Tu peux réallouer la zone avec realloc().
Mais bon, cela ne s'appelle pas implémenter une liste doublement chaînée ;-))).
Cdlt,
dx3d
Messages postés
68
Date d'inscription
dimanche 6 septembre 2009
Statut
Membre
Dernière intervention
19 juillet 2017
10 mai 2014 à 16:28
10 mai 2014 à 16:28
@fiddy : Donc déjà désolé pour le manque d'information que j'ai donné, donc pour mieux m'expliquer :
Dans notre TP on nous dit qu'on ne dispose pas de pointeur qu'on va devoir simuler les pointeurs par des indices dans des tableaux. On nous demande donc de proposer une implémentation des listes doublement chainées par tableaux multiples. et par la suite en nous inspirant du fait que les objets sont stockés de façon contigüe dans la plupart des langages de programmation et qu'un pointeur dans un tel objet est l'adresse du premier mot de proposer une autre implémentation en utilisant un tableau unique.
Et ce n'est que dans l'exercice suivant qu'on nous demande de crée des fonctions d'allocation et de libération de mémoire.
Donc déjà je m'étais dis que pour le tableau unique, avec des fonctions suivant/precedent je pourrais le parcourir pareil que pour une liste doublement chainées :
suivant -> si l'indice du tableau i < sizeof(tab)-1, on retourne tab[i+1] sinon on retourne tab[0]
precedent -> si l'indice du tableau i>0, on retourne tab[i-1] sinon on retourne tab[sizeof(tab)-1]
mais je ne vois pas vraiment pourquoi utiliser plusieurs tableaux du coup ( ou plutôt je n'en vois pas l'utilité ... )
Est ce que je me goure ou est ce qu'il me manque un truc? Tout avis est le bienvenu, si besoin je peux link le TP si mes explications ne sont pas claire ! :)
Dans notre TP on nous dit qu'on ne dispose pas de pointeur qu'on va devoir simuler les pointeurs par des indices dans des tableaux. On nous demande donc de proposer une implémentation des listes doublement chainées par tableaux multiples. et par la suite en nous inspirant du fait que les objets sont stockés de façon contigüe dans la plupart des langages de programmation et qu'un pointeur dans un tel objet est l'adresse du premier mot de proposer une autre implémentation en utilisant un tableau unique.
Et ce n'est que dans l'exercice suivant qu'on nous demande de crée des fonctions d'allocation et de libération de mémoire.
Donc déjà je m'étais dis que pour le tableau unique, avec des fonctions suivant/precedent je pourrais le parcourir pareil que pour une liste doublement chainées :
suivant -> si l'indice du tableau i < sizeof(tab)-1, on retourne tab[i+1] sinon on retourne tab[0]
precedent -> si l'indice du tableau i>0, on retourne tab[i-1] sinon on retourne tab[sizeof(tab)-1]
mais je ne vois pas vraiment pourquoi utiliser plusieurs tableaux du coup ( ou plutôt je n'en vois pas l'utilité ... )
Est ce que je me goure ou est ce qu'il me manque un truc? Tout avis est le bienvenu, si besoin je peux link le TP si mes explications ne sont pas claire ! :)
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 842
10 mai 2014 à 21:04
10 mai 2014 à 21:04
suivant -> si l'indice du tableau i < sizeof(tab)-1, on retourne tab[i+1] sinon on retourne tab[0]
Ce n'est pas i<sizeof(tab)-1 qu'il faut tester, mais i<sizeof(tab)/sizeof(*tab) - 1 (pour info les parenthèses sont facultatives).
De même pour précédent.
Sinon pour l'utilisation de multiples tableaux, c'est peut-être lorsque le tableau est plein. Non ?
Ce n'est pas i<sizeof(tab)-1 qu'il faut tester, mais i<sizeof(tab)/sizeof(*tab) - 1 (pour info les parenthèses sont facultatives).
De même pour précédent.
Sinon pour l'utilisation de multiples tableaux, c'est peut-être lorsque le tableau est plein. Non ?
dx3d
Messages postés
68
Date d'inscription
dimanche 6 septembre 2009
Statut
Membre
Dernière intervention
19 juillet 2017
10 mai 2014 à 21:19
10 mai 2014 à 21:19
J'ai pensé pour les tableaux multiple à faire :
En gros on prend une valeur de départ ici c'est 2, donc on commence avec
tabVAL[2]=15, on voit l'indice dans la tabIND associé et on trouve que tabIND[2]=6, donc l'élément suivant sera tabVAL[6]=11, et ainsi de suite, donc je me retrouve bien avec ma fonction suivant qui renvoie l'élément suivant de la liste ( c'est un peu bordélique à la lecture mais bon ça marche et la boucle marche bien, une fois qu'il passe tous les éléments il revient bien à l'élément de départ et ça continue, je suis entrain de faire la fonction precedent maintenant.
Et sinon pour la correction que tu m'as donné, ça risque d'être compliqué vu que je n'ai pas le droit aux pointeurs. (Notre prof est sadique ... )
int suivant(int VAL[], int IND[],int depart){
int i ;
printf("Valeur actuel : %d",VAL[depart]);
i = IND[depart];
depart=i;
printf("\nProchain indice : %d\n",depart);
return depart;
}
int main(){
int tabVAL[8]={1,4,15,31,23,6,11,3};
int tabIND[8]={7,5,6,0,2,3,1,4};
int start = 2;
start=suivant(tabVAL, tabIND, start);
start=suivant(tabVAL, tabIND, start);
}
En gros on prend une valeur de départ ici c'est 2, donc on commence avec
tabVAL[2]=15, on voit l'indice dans la tabIND associé et on trouve que tabIND[2]=6, donc l'élément suivant sera tabVAL[6]=11, et ainsi de suite, donc je me retrouve bien avec ma fonction suivant qui renvoie l'élément suivant de la liste ( c'est un peu bordélique à la lecture mais bon ça marche et la boucle marche bien, une fois qu'il passe tous les éléments il revient bien à l'élément de départ et ça continue, je suis entrain de faire la fonction precedent maintenant.
Et sinon pour la correction que tu m'as donné, ça risque d'être compliqué vu que je n'ai pas le droit aux pointeurs. (Notre prof est sadique ... )
fiddy
Messages postés
11069
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
23 avril 2022
1 842
10 mai 2014 à 21:33
10 mai 2014 à 21:33
Par contre, je ne comprends pas pourquoi tu utilises tabIND ? Tu ne peux pas dire simplement que l'élément suivant est i+1 ?
Et sinon pour la correction que tu m'as donné, ça risque d'être compliqué vu que je n'ai pas le droit aux pointeurs.
Hum. Dès lors que tu fais tab[i], tu utilises un pointeur sans le savoir. tab[i] est l'équivalent de *(tab+5)... Le prof ne veut pas d'allocations dynamiques je pense. Enfin si l'étoile te gêne, tu peux utiliser : sizeof tab / sizeof tab[0] ;-)
Et sinon pour la correction que tu m'as donné, ça risque d'être compliqué vu que je n'ai pas le droit aux pointeurs.
Hum. Dès lors que tu fais tab[i], tu utilises un pointeur sans le savoir. tab[i] est l'équivalent de *(tab+5)... Le prof ne veut pas d'allocations dynamiques je pense. Enfin si l'étoile te gêne, tu peux utiliser : sizeof tab / sizeof tab[0] ;-)