Problemes de C/C++/Java/whatever

Ben j’avais bon alors…
Le seul problème avec ma méthode c’est qu’on pouvait pas repartir directement du début de la liste, il fallait remonter de proche en proche. Mais sinon, j’utilisais les mêmes ressources supplémentaires (c’est-à-dire un pointeur vers l’élément courant et un pointeur vers l’élément précédent), et je répondais au problème posé en respectant les contraintes. Mais bon.

C’est rigolo quand même cet usage du xor :wink:

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; }; [/quote] 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;

}
[/quote]Et voila :wink: 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 :stuck_out_tongue: :mad: :mad:

[quote]Oui tu triches :stuck_out_tongue:
C est pas ca, ton truc il prend plus de place que prevu…[/quote]
Ben la contrainte de depart c’etait : « sans prendre plus de place en memoire pour un element »
La la structure element reste la meme, il y a juste 2 malheureux pointeurs en plus dans le programme principal. En plus, 2 pointeurs par rapport a une liste de plusieurs miliers d’elements, ca pese pas lourd… Rhaaa, vous etes exigeants :wink:

[quote]Cybernoid >
Tu sais, l’opérateur « -> » existe :pleure:[/quote]
Ha oui, ca me rappelle vaguement quelque chose :slight_smile:
Mais bon, je suis pas informaticien, deja rien que pour comprendre ce que c’etait une liste chainee j’ai eu du mal…

Serait-il possible de coder propre lorsque nous présentons du code, de façon à s’enrichir mutuellement des différentes expériences que nous pouvons avoir ?

Cybernoid >
Tu sais, l’opérateur « -> » existe :wink:

Pour moi codage « propre » == nommage des symboles, alignement, préfixage, définition de blocs bien indentés…

NB : Pour l’alignement on peut utiliser le « ALT 255 »

Sinon, je n’ai toujours pas d’idée sur la question qui nous est posée. Grmmbll…

Euh… je comprends pas trop.

une liste simplement chaînée, ça existe.
une liste doublement chaînée, ça existe aussi.

dans la structure, en plus d’avoir un élément suivant, on a un élément précédent.

si le suivant est NULL, on regarde le précédent…

J’ai l’impression d’avoir loupé l’intrigue là :wink:

EDIT: j’avais effectivement loupé l’intrigue.

Je vote que c’est pas possible.

[Edité le 23/10/2002 par hurlosaure]

Oui tu triches :smiley:
C est pas ca, ton truc il prend plus de place que prevu…

Sinon pour le gars plus haut qui dit qu’il faut pas struc, ben en fait il le faut parce que ya pas le typedef (enfin si on parle toujours de C :smiley: ).

Et enfin, pour le gars encore plus haut qui y croit pas, ben si c est possible :smiley:
C’est clair que c est pas super intuitif comme ca, mais c est malin…Et ca marche.

Hop hop, les cellules grises la, allez on mijote :wink:

J’ai une solution un peu batarde mais je tente quand même:

on garde la même structure pour tous les éléments de la liste chaînée, mais on rajoute juste deux pointeurs vers un élément en plus.

element* precedent; // pointeur vers l’element precedent
element* en_cours; // pointeur vers l’element en cours
element* buffer; // buffer :wink:

Pour passer de l’élément i à l’élément i+1, on fait:
buffer=precedent;
precedent=en_cours;
en_cours=(*en_cours).le_suivant;
(*precedent).le_suivant=buffer;

Et pour revenir en arrière:
buffer=(*precedent).le_suivant;
(*precedent).le_suivant=en_cours;
en_cours=precedent;
precedent=buffer;

Voilà. Bon d’accord, je triche un peu en utilisant 2 pointeurs supplémentaires, mais la taille d’un élément de la liste reste la même. Et puis on peut pas parcourir la liste à partir du début du coup…

[quote]struct element {
void* element_contenu
struct element* le_suivant
}[/quote]Moi j’appelle pas ça du pseudo code, j’appele ça du C :-p
Bon, faudrait virer le 2ème struct pour être nickel et que ça passe sur un compilo, mais bon :smiley:

Sinon pour l’algo, je vois pas trop, là, mais j’ai pas trop réfléchi non plus, faut dire…

C’est un sujet que j’ai eu en entretien. Et je pouvais pas lui soutenir que c’etait con son truc, c’etait pas possible :smiley: Bon je precise le pb et je viendrai poster la solution.

Un liste chainee c’est une structure qui contient, en pseudo code, un truc du genre:

struct element {
void* element_contenu
struct element* le_suivant
}

on est tous d’accord. Avec ca on peut passer au suivant en allant la ou pointe le pointeur le_suivant. Si la liste est cyclique et qu’on veut le precedent il faut faire tout le tour, si elle est pas cyclique il faut tout refaire la liste et aller a l’index-1. C’est bad.

Maintenant la question c’est sans prendre plus de place en memoire pour un element comment rendre possible le fait de parcourir la liste en avant ou en arriere, sans changer le nombre d’instruction necessaire quel que soit le sens.

Je precise que avec cette solution la liste ne peut pas etre circulaire.

Heuu oui là je ne vois pas… à moins de jouer avec des offsets (sur 16 bits) et stocker offset_next et offset_previous sur un 32 bits mais qu’en bien même, ça ne peut pas être la règle générale…

Envoie la réponse Glop (j’ai peur d’être déçu).
:cool:

bon… j’insiste…

s’il s’agit VRAIMENT d’une liste chainée, avec 1 seul pointeur par element, c’est impossible (non mais ! enfin… sauf si triche en lisant le sujet bizarrement)

PAR CONTRE, s’il s’agit d’un truc qui doit offrir les memes fonctionnalités qu’une liste chainée, avec des performances moindre pour les fonctions : suivant, inserer, supprimer (quand on connait déjà le precedent) mais meilleures pour les fonctions : rechercher, precedent

AVEC, un seul pointeur pour referencer un element (attention, chaque element peut contenir 2 pointeurs, mais certains ne pointerons sur rien, et donc au global y’aura qu’un pointeur par element)

ALORS ca existe, ca s’appelle un Arbre (arbre binaire, notamment, c’est le plus simple)

C’est compliqué à gérer, ca demande une fonction de tri (quand tu recherche ton element dans ton arbre, il faut que tu le designe par quelque chose que tu peux trier… sinon l’arbre ne marchera pas)

[EDIT]
Oui, je suis borné, et alors ?
[/EDIT]

[Edité le 22/10/2002 par urdle]

Non c’est pas impossible et non tu fais pas le tour sans le dire. Si c’etait aussi debile que ca ou qu’il n’y avait pas de solution j’aurais pas pose la question je suis pas debile :wink:

[Edité le 22/10/2002 par GloP]

facile… tu fais tout le tour, mais tu le dis pas… (tu fais une fonction “next” et une fonction “previous”, le gars qui utilise tes fonctions n’a pas à savoir ce qui se passe)
sinon, c’est impossible, à moins que ta liste n’ai que 2 elements…

sinon y’a les arbres, mais c’est plus chaud… et c’est pas forcement ce que tu cherche

d’autres questions ?

ouais sinon pour les question, il me parait important que les questions soient précises, et que si elles sont vagues, qu’on ne donne en reponse que des indices, des pistes à suivre…

genre (j’prend un cas bateau de tp)
A : “faut faire un programme qui calcule x^y (^ exposant, x et y entiers)”
B : “decompose : x^y = xxxxx (y fois); c’est la methode simple et qui marche, mais lente.”
A : “et la rapide ? parceque c’est pas ca que le prof veux voir”
B : “decompose y en puissance de deux y=((y1*2+y2)*2+y3)*2+y4…”

s’il ca lui suffit, nickel, sinon on lui demande de chercher un peu. Si ca ne l’avance pas parceque c’est deja l’indication que donnait le prof, il avait qu’à etre plus précis. (Le but est pas de faire son tp)

pour ceux qui poseraient des questions qui ne sont pas des sujets de tp, qu’ils le disent, le soucis est different, et on pourra eventuellement donner des reponses plus indicatives (mais soyez honnete, par pitié)

[Edité le 21/10/2002 par urdle]

Vous voulez un pb a la con ? Comment faire une linked list a double sens (cad une list ou on peut passer a l’element suivant ou a l’element precedent directement, sans faire tout le tour) en utilisant un seul pointeur?

Go!

:smiley:

Merde je n’avais pas vu ce thread… UP.
J’aimerai bien voir ça aussi :D. Qui sera le premier ?

Très bonne idée.
Cela dit un pblm par semaine ca fait peut etre court non ?
Enfin, c’est vrai que j’ai 47 heures de boulot par semaine, donc niveau temps pour moi ce sera chaud.
Vivement que ca commence !

:remouk

Tranquille ! Je suis aussi d’accord pour le vendredi car pour l’instant, j’ai du mal à aller sur internet à l’IUT (problème de serveur Wind…:-.

Pour info, je débute en C/C++ mais je maitrise déjà très bien le Java (et le Cobol, non pas frapper).

moi j aime cette idee en plus cette année je risque d avoir super besoin d aide alors ouvrons la taverne de l Alog je dis !!!
KOUby qui dit OUI !!!

[quote name=‹ ZGoblin › date=’ 22 Sep 2002, 08:13’]Tranquille ! Je suis aussi d’accord pour le vendredi car pour l’instant, j’ai du mal à aller sur internet à l’IUT (problème de serveur Wind…:P.

Pour info, je débute en C/C++ mais je maitrise déjà très bien le Java (et le Cobol, non pas frapper).
[right][post=« 77872 »]<{POST_SNAPBACK}>[/post][/right][/quote]

:stuck_out_tongue:
ÉH EH faudrait retravailler la dessus :stuck_out_tongue:

Qq’un a un truc qui traine la moi je suis out pour penser a un truc mais sinon ca serait bon :stuck_out_tongue:

Koubiak

Alors koubiak ? on reveil l’esprit des anciens ? on fait de le thread decede ?

Cela dit, l’idee me semble toujours super interessante, mais j’ai pas une minute a moi avant… hmmm… 2012 ou un truc… donc si quelqu’un veux proposer des trucs je suis preneurs, et je modererais, a la pelle !