Bonjour à tous !
 
Dans le cadre de mes études je dois réaliser un projet passionnant mais assez complexe et je bloque sur certains points. La lecture peut vous paraitre un peu longue mais lisez ce topic et vous verre comme ce projet est intéressant . Je ne poste donc pas un message pour que l'on me donne une solution, mais plutôt dans l'optique d'obtenir des conseils avisés des membres de ce forum. Je vais vous expliquer à quoi consiste ce projet et après on attaquera avec les problèmes.
 
Alors le but est simple, le programme se fait en ligne de commande et l'user définit en entrée le réseau et donne une phrase qui traversera ce dernier. Celle ci entrera dans le premier bloc d'effet et le résultats de tout les effets appliqué au mot sortira dans le dernier bloc définie. Mais il peut y avoir des cas où la sortie de 2 blocs (1 et 2) se connectent à l'entrée d'un 3eme. Dans ce cas là l'entrée du 3ème sera la concaténation des sortie des bloc 1 et 2. OUI mais la concaténation est faite en fonction de l'ordre où les connections avec le bloc 3 ont été faite. C'est à dire si on connecte 1->3 puis 2->3 alors l'entrée du bloc 3 sera "sortieBloc1 + sortieBloc2".
 
Voilà pour la description du fonctionnement du réseau. Maintenant un petit point sur sa création.
 
Dans le terminal, chaque fois que l'user commence une ligne par "bloc" alors un nouveau bloc est ajouté dans le réseau. chaque ligne commençant par "connexion" va connecté deux bloc entre eux. Enfin la ligne commençant par "run" envoie le reste de la ligne dans le 1er bloc du réseau et lance le programme.
 
 
Regardons maintenant la définition d'un bloc :
 
bloc <nom> <effet>
 
On dispose de 4 effets
 
- repeat : la sortie est l'entrée concaténé à elle même. Ex : on a en entrée "hey" en sortie on aura "heyhey"
 
- retard : la sortie est le l'entrée du bloc précédent (celui connecté en premier) suivi de l'entrée du bloc actuel. Par exemple si le bloc N-1 est le bloc repeat de l'exemple au dessus on alors alors : hey heyhey"
 
- sens : la sortie est l'entrée inversée. Ex : entrée "hey" sortie "yeh"
 
- rien : la sortie est la même que l'entrée
 
Ensuite pour les connexion on procède de la façon suivante :
 
connexion <bloc1> <bloc2>
 
Bien évidemment on ne peut connecté que des blocs déjà définis.
 
Voilà pour ce qui en est de la description du projet...
 
Je poste une image et un exemple du fonctionnement attendu, ça sera plus simple à se représenter
 
 
 

 
 
 
Voilà vous voyez que ça peut vite devenir un joyeux bordel tout ça.
 
Maintenant il est temps de vous exposer mon problème et c'est là où un mage de l'algo est demandé.
 
Mon problème est donc algorithmique et non "technique". Je me demande comment mettre en place tout ça de la manière la plus efficace (afin d'éviter de 1h pour avoir un résultat dans des cas complexes). Mon idée était la suivante :
 
- bloc sera une structure de type "bloc" avec { char nom, char type_effet, char input, char output, bloc tab_Priorite }
 
- Lorsque l'user rentre les blocs qu'il veut on les ajoute dans un tableau de façon dynamique.
 
- Le réseau final sera sous forme d'une liste, ainsi à la fin on aura notre mot/phrase et on parcourra cette liste pour voir les effets à appliquer dessus.
 
- On aurait pu s'arrêter ici si le programme ne permettait pas de créer des entrée provenant de différents bloc. Pour régler ce problème j'avais comme idée de créer des listes de tableau !! Je m'explique, on fait une 1ere connexion aucun des bloc R et S n'a de connexion, là pas de problème on a la liste circulaire " R -> S ", cette liste sera la Liste Principale dite liste 1 car c'est la première. Après on fait la connexion entre R et N, on voit que R est dans la liste principale mais pas N, on crée une 2eme file "R -> N" dite liste 2. Le but de cette liste est aussi de vérifier à la fin si tout les blocs seront connectés et ainsi n'avoir qu'UNE sortie.On se retrouve donc avec 2 listes. Ensuite on veut connecter S - N. S est dans une liste, et la destination N aussi. On prends la liste où se trouve la destination N, on parcours la liste jusqu'à N, on calcule le input de S et on remplit le tableau de la structure de N avec en première ligne le bloc S. On supprime la liste 2 "R-S". Et ainsi de suite.
 
A la fin pour calculer le résultat de la sortie du bloc N on n'aura qu'à se placer à la fin de la liste, c'est à dire en N.
 
Si N n'a pas de tableau alors la résultat sera juste le input dont on applique l'effet de N.
 
Si N a un tableau alors le résultat sera la concaténation de l'input de N avec les i N.tab_priorite.outuput de N.
 
M'avez vous suivi ? Je vous montre encore une fois en image ce que ça donnerait :
 
 

 
 
 
Voilà ce que donnerait pour l'organisation du réseau en gros ! Vu qu'on calcule entre chaque étape les entrées/sortie de chaque bloc à la fin on n'a qu'à lire le résultat avec le dernier élément de la liste.
 
Qu'en pensez ? Voyez vous une méthode plus efficace / rapide ???
 
Votre aide me sera d'un TRÈS GRAND SECOURS car je me sens un peu perdu ...

Salut

Ton probleme n'est pas bien complique, mais comme d'hab c'est les cas limites qui vont poser probleme.
Quelques questions de base:
- y a-t-il toujours une entree unique dans ton reseau? Je suppose que oui vu que de toutes facons, meme si ce n'est pas le cas, on peut le forcer silencieusement en introduisant de force un bloc "noop" a l'entree du reseau.
- ton reseau peut-il contenir des boucles? Je suppose que non sinon il ne s'arrete jamais d'apres ta description, mais du coup la question est: est-ce que tu dois detecter quand l'utilisateur rentre une boucle et l'empecher? Ou alors tu laisses faire et ton programme soit crashe ou renvoie un resultat faux (s'il est mal foutu) on ne s'arrete jamais (s'il est bien foutu)?
- en dehors des boucles, dois-tu verifier le reseau avant de le lancer? Par exemple, si l'utilisateur est un petit malin et rentre un reseau avec plusieurs sorties, ou rentre des blocs isoles (sans aucun lien), ou avec seulement un lien sortant?

Bon maintenant, tes histoires de liste. Je pense que j'ai compris ce que tu veux faire mais honnetement, ca va etre ingerable tres vite.

Je pense que t'as deux options "simples".

Si tu connais et peux utiliser la programmation orientee objet, c'est probablement la solution la plus simple a comprendre. Tu te definis un objet Bloc avec:
    - en variables:
        - le type (defini a la creation - tu peux faire une classe principale et une sous-classe pour chaque type si tu veux faire le malin, sinon utilises juste une seule classe avec une variable pour definir le type, peu importe)
        - l'entree (initialisee vide)
        - le nombre d'entrees (demarre a 0 et augmente a chaque fois que tu ajoutes un lien qui finit sur ce bloc)
        - le nombre d'entrees recues (demarre a 0 et augmente a chaque fois que tu recois une entree)
        - une liste d'autres Blocs representant les sorties (demarre vide et ajoute un Bloc a chaque fois que tu ajoutes un lien qui part de ce bloc)
    - en fonctions:
        - declaration d'un lien qui se finit sur le Bloc (+1 au nombre d'entrees)
        - declaration d'un lien partant du bloc (ajout du bloc suivant a la liste des sorties - c'est aussi probablement le meilleur endroit pour detecter la creation d'une boucle, grace par exemple a une fonction dediee de ton object Bloc)
        - reception d'une entree (ajoute l'entree (+ transformation specifique au type) a la variable d'entree, et augmente le compte d'entrees recues, et si ce compte vaut le nombre d'entrees, alors transmet "l'entree finale et tranformee" (i.e la sortie) a tous les Blocs de la liste de sortie)
Apres dans ta classe principale:
    - tu te declares une Map de <Nom de Bloc> -> <Bloc> histoire de pouvoir facilement stocker/recuperer/modifier les Blocs pendant la phase d'initialisation
    - une fois la commande "run" lancee, tu parcours tous les Blocs de ta Map pour verifications: y a-t-il un seul bloc sans entree (le bloc de depart) et un seul sans sortie (le bloc d'arrivee)? Si non, empeche le depart et decrit le probleme a l'utilisateur
    - si le reseau est valide, tu auras recupere les blocs de depart et d'arrivee pendant ton check dans des variables preparees pour, et tu n'as plus qu'a envoyer l'entree dans celui de depart et a recuperer la sortie dans celui d'arrivee.

La deuxieme option, si tu connais pas ou ne veut pas faire d'objet, est de faire la meme en programmation "classique". Utilises des tableaux ou des listes etc pour stocker tes variables, liaisons, tout ce beau monde. L'idee generale de fonctionnement peut rester la meme que pour l'approche objet mais ca sera un peu plus casse-couilles a mettre en place.

Hope this helps
A+

Edit: j'ai oublie les priorites... mais bon c'est pas la mort a gerer non plus. Transforme ton "entree" en une liste d'entrees dans ton objet Bloc et au moment ou les liens sont fait, assigne et retiens le bloc d'origine et sa priorite, puis sers t'en a chaque entree recue (ajoute le nom du bloc dans la fonction d'entree pour savoir qui t'envoies quelque chose) et au moment de restituer la sortie (pour concatener les entrees dans le bon ordre)

Alors un grand MERCI lasnoufle !
 
Il se trouve que j'ai réfléchi à l'algo entre temps car j'ai vite vu que ce que je proposais pouvait devenir ingérable comme tu l'as précisais d'ailleurs. Il se trouve que l'ago que j'ai maintennt est similaire à celui que tu as proposé. Avant de te le montrer je vais répondre à tes questions.  
 
 

 
Oui il y a toujours qu'une seule entrée. Je comptais mettre une erreur si l'user mettait plusieurs entrées mais ton idée du "noop" est très astucieuse !
 

 
Non le réseau ne doit PAS contenir de boucle. D'ailleurs si j'en trouve dans le le réseau de l'utilisateur je marque une erreur.
 

 
Oui il y a toutes ces vérification, si je détecte un problème l'user refait le réseau. Oui on ne joue pas au petit malin avec moi !  
 
 
Je vais maintenant te parler de mon algo. Je le coderai en C, car je n'ai pas de notion en POO, enfin si je connais un peu le Java mais avec la date de rendu je n'ai pas le temps d'apprendre le c++ (mais je compte le faire dans les semaines à venir   )
 
Les bloc ont la structure suivante :

 
- je regarde toutes les lignes commençant pas "bloc". A chaque nouveau bloc, je l'ajoute à un tableau (tabBloc) qui contiendra tout les blocs.
- je regarde toutes les lignes commençant pas "connexion". Et je rempli "listeInput", "output" et "strOutput".
  Pour "listeInput" chaque fois que ce que le bloc est en deuxième argument de "connexion" je rajoute à la liste le bloc en premier argument de "connexion". Et j'ai aussi la priorité des blocs si j'ai besoin de faire un concaténation.  
  Pour "output" si ce bloc est une fois en premier argument de "connexion" alors output = 1.
   
- Pour "strOutput" une fois que j'ai lu toutes les lignes "connexion" et que j'ai la phrase de l'user je commence à remplir en me plaçant au bloc d'entrée (celui avec "listeInput" vide). Et je me déplace dans mon tabBloc de case en case, à chaque case je regarde si le bloc.listIn.strOutput est différent de null, si c'est le cas avec tt les blocs de la liste alors je peux remplir le le "strOutput" du bloc où je me trouve. Je parcours mon tableau en boucle tant que tout les "strOutput" ne sont pas différents de NULL.
 
- Pour le résultat de sorti je n'ai qu'à me placer à la case où j'ai "Output = 0" et je prends le "strOutput".
 
Voici une image qui illustre le tableau final :
 

 
 
Voilà c'est à peu près la même chose que ce que tu avais dis je pense, mais avec des variables un peu différentes.

Plus qu'un tableau, j'aurais bien vu une variante des listes doublement chaînées, la variante étant que les pointeurs "précédent" et "suivant" sont en fait des tableaux listant les blocs d'avan ou d'après le bloc courant.
 
http://www.commentcamarche.net/faq [...] nt-chainee

 
 
Merci pour ton aide. Mais en quoi cette variante liste doublement chaînée serait mieux qu'un tableau ? Car il n'y a pas vraiment "d'ordre" dans le réseau, ça dépend des envies de l'user.
 
Pour moi une liste à l'avantage de pouvoir rajouter et supprimer des éléments au milieu de cette dernière mais ici l'user ne peut pas supprimer de bloc donc le tableau restera fixe. De plus un tableau est moins coûteux en mémoire et plus rapide  d'accès non ?

Il me semble qu'une liste est plus rapide à parcourir (dans le cas d'un réseau comme le tiens où y'a plusieurs liaisons entre noeuds et qu'ils ne sont pas ordonnés) car t'as accès directement aux cellules suivantes ou précédentes.
 
Après, c'est vrai qu'une liste est plus facile pour les insertions/suppressions.

En fait je viens de trouver une solution beaucoup plus simple. C'est l'arbre N-aire ! Je ne connaissais pas du tout et c'est en parlant avec quelqu'un que j'ai découvert ça. En fait ce type d'algo s'adapte parfaitement à mon projet.  
 
Mais je ne trouve pas grand chose sur le net, connaitriez vous un site avec un cours détaillé sur ces arbres ? Je ne trouve que des morceaux de code par ci par là...

L'auto-complétion est un arbre N-aire : http://fr.wikipedia.org/wiki/Arbre_de_compl%C3%A9tion