un array tout con? (offset + ints consécutifs)
le monsieur a dit une liste chaînée B)
Alors je ne vois que le XOR comme MadGnome.
Mais il faut donc 2 adresses d’elems consécutifs pour démarrer. (comme le dit Drealmer)
Voilà après fouille j’ai retrouvé la réponse de Glop à cette question:
[quote]Bon je poste la solution alors ? C’est ca ?
Ok … ok …
La solution consiste a utiliser un XOR binaire (en math le + entoure ou en C le ^) et a combiner le pointeur vers l’element suivant et le pointer vers l’element precedent en un seul pointeur « voisin ».
Cela fonctionne parceque le XOR est non destructif dans le sens ou, si on a A et B et C ou C=A XOR B, on peut faire un nouveau XOR entre n’importe lesquelle des deux valeurs pour retrouver la troisieme. Si C = A XOR B, alors A = B XOR C et B = A XOR C. On peut noter que XOR est commuatatif, cad que A XOR B = B XOR A.
Donc … si on traduit toute ces maths dans du code on peut stocker chaque noeud de la liste chainee sous la forme suivante, et toujours avec un seul pointeur :
(je prend une liste chainee d’entiers pour l’exemple)
struct ListNode {
ListNode * voisin; /* voison= suivant^ precedent */
int payload;
};
Avec les regles du XOR ci dessus, si on a un noeud et qu’on connait le pointeur « prev », on peut avoir le suivant en faisant:
suivant = precedent ^ listNode.voisin;
Aux extremites bien sur NULL est utilise pour terminer la list. Donc en chopant un cote ou l’autre on peut parcourir la liste dans un sens ou dans l’autre sans operations supplementaires et sans occuper plus de place en memoire qu’un seul pointeur.
Donc que donne le code pour parcourir est le suivant:
ListNode *debut;
ListNode *suivant, *precedent, *courant;
courant = debut;
precedent = NULL;
while(courant != NULL)
{
suivant = courant->voisin ^ precedent;
/* ON FAIT LE TRAVAIL SUR L’ELEMENT */
precedent = courant;
courant = suivant;
}
Et voila B) Ca marche, un seul pointeur et on peut faire dans n’importe quel sens. On peut facilement faire une classe avec une liste chainee et des fonction Precedent() et Suivant(). Au pire si on change de sens, on chope le suivant, et ca nous donne le precedent pour repartir dans l’autre sens, une seule operation, on ne fait pas tout le tour.
C’etait pas impossible B) 
:D[/quote]
C’est fort comme solution, perso si je l’avais pas lu une fois, impossible de trouver.
Pfff, pas marrant si tu poste la solution, surtout que j’étais plus ou moins sur la voie.
Maintenant, fais les procédures d’insertions et d’effacement dans la liste B)
Huhu grilled B) pas drole je me souvenais pas avoir posté la reponse. Ca m’evite de la retaper, c’est deja ca.
ya des gens qui t’ont deja trouvé la reponse en entretien ? serieux…
Les gars si vous ouvrez un topic “casse-têtes” de programmation avec des réponses protégées par des antispoil, vous avez d’ores et déjà un candidat à la chute des rares neuronnes présents dans ma tête ^^
J’ai jamais eut qqn de suffisament hargneux en prog pour devoir aller taper dans ce genre de choses. En general on reste dans le beaucoup plus simple et c’est largement suffisant pour coller la majoritee des gens. L’important c’est de poser un probleme que tu sais faire par coeur voire que tu sais pas forcement resoudre, pour voir comment tu reflechis. Ca en general ca tient plus du « rigolons ensemble si il reste du temps », mais c’est sympa.
Le probleme de cette solution c’est que si t’as pas 2 elements consecutifs, tu peux plus du tout naviguer dans la liste.
C’est pas un probleme c’est la maniere dont ca marche.