Liste chainée, Arbre binaire

Bonjour,

Dans le cadre d'un projet d’école, je dois réalisé une application basé sur la saisie prédictive (T9).

La contrainte imposé est de ne pas utilisé les Api.

Et donc je vois pas comment je pourrais réécrire une arraylist et comment faire un arbre binaire pour chargé ma liste de mots.

Merci.

As-tu réfléchis précisément à comment tu vas réaliser ton programme ?
Quelles structures de données tu vas utiliser, quelles algorithmes sont à utiliser? Y-a-t-il une interface utilisateur particulière ?

Si oui, tu peux alors réfléchir au développement. Ne pas utiliser java.util.* ne devrait pas être un problème pour toi, s'il ne s'agit que d'utiliser des tableaux ou un arbre. Pas besoin de refaire une "ArrayList" comme celle qui existe déjà, pareil pour l'arbre. Tu peux utiliser les tableaux et créer tes propres classes qui serviront à la place (pour un projet d'école ça devrait faire l'affaire). Une ArrayList, dans le fond c'est rien d'autre qu'un tableau qui s'agrandit automatiquement selon le besoin, et un arbre, un classe qui encapsule d'autres objets de la même classe.

Citation:

---

Envoyé par Climoo

As-tu réfléchis précisément à comment tu vas réaliser ton programme ?
Quelles structures de données tu vas utiliser, quelles algorithmes sont à utiliser? Y-a-t-il une interface utilisateur particulière ?

Si oui, tu peux alors réfléchir au développement. Ne pas utiliser java.util.* ne devrait pas être un problème pour toi, s'il ne s'agit que d'utiliser des tableaux ou un arbre. Pas besoin de refaire une "ArrayList" comme celle qui existe déjà, pareil pour l'arbre. Tu peux utiliser les tableaux et créer tes propres classes qui serviront à la place (pour un projet d'école ça devrait faire l'affaire). Une ArrayList, dans le fond c'est rien d'autre qu'un tableau qui s'agrandit automatiquement selon le besoin, et un arbre, un classe qui encapsule d'autres objets de la même classe.

---

Merci de m'avoir répondu.
Non, je n'y ai pas encore réfléchi car je suis bloqué par ce soucis.
Que veux tu dire par, Quelles structures de données.
J'ai déjà fait l'interface sous swing.

La représentation du dico se fera à l’aide d’un arbre (n-aire).
Le parcours dans l’arbre est déterminé par le préfixe du mot.
A chaque suite numérique, correspond un noeud, atteint en parcourant l'arbre depuis la racine et en suivant, dans l'ordre, les liens annotés par les valeurs numériques de la suite.Chaque noeud de l'arbre, si ce n'est le noeud racine, corrrespond donc à une suite numérique. Chaque noeud permet
d'accéder aux noeuds obtenu en complétant la suite actuelle par un nouveau chiffre.
Afin de permettre un parcours de l'arbre, chaque noeud doit donner accès à ses fils, sur base de la valeur numérique associée au lien. Chaque noeud doit donc contenir un pointeur, annoté par un chiffre de 2 à 9, vers ses noeuds fils.
Une liste chaînée permettrait, au prix d'une perte de l'accès direct, d'économiser la place mémoire
pour tous les (nombreux) noeuds fils absents.
De plus, donc, chaque noeud doit contenir la liste des mots associés. Cette liste sera représentée de
façon dynamique par une liste chaînée.

Héhé, ça devient intéressant...
Pas tout compris à ce que tu disais à propos de la structure d'arbre dont tu parles, mais je retiens que :
Tu dois créer un arbre n-naire.

• A chaque noeud de l'arbre se trouve un ensemble de données diverses.
• Tu dois être pouvoir parcourir ton arbre à partir d'une valeur entre 1 et 9, la touche du téléphone vraisemblablement.

Voici quelques petits bouts de code, volontairement très basique et que tu ne manqueras pas d'enrichir selon tes besoins, qui pourront t'aider à démarrer.

Une liste générique (simulacre de ArrayList)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public class MaListe<T> {   private static final int DEFAULT_SIZE = 9;   private Object[] liste;   private int size;   public MaListe() { this.size = 0; this.liste = new Object[DEFAULT_SIZE]; }   public void add(T element) { assurerTaille(this.size + 1); liste[this.size] = element; this.size++; }   public T get(int index) { if (index >= 0 || index < this.size) { return (T)liste[index]; } return null; }   private void assurerTaille(int tailleVoulue) { if (this.size < tailleVoulue) { Object[] nouvelleListe = new Object[tailleVoulue]; for(int i = 0; i < this.size ; i++) { nouvelleListe[i] = this.liste[i]; } this.liste = nouvelleListe; } } }

---

Tu peux aussi partir sur une liste chainée si tu veux, mais c'est un peu plus dur à faire.

Et un arbre n-aire

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

public class MonArbre<T> {   private T valeur;   private MaListe<MonArbre<T>> enfants;   public MonArbre(T valeur) { this.enfants = new MaListe<MonArbre<T>>(); this.valeur = valeur; }   public T getValeur() { return this.valeur; }   public MonArbre<T> getChild(int index) { return enfants.get(index); }   public MonArbre<T> getChildNumero(int numero_entre1_et_9) { // Celle là, ce sera à toi de l'écrire, elle est particulière à ce que tu viens de faire. return null; } }

---

J'ai pas essayé de compiler mon code, alors je te garantis pas, mais l'idée est là.

Il te reste à définir ce que tu vas mettre dans tes listes ou tes arbres, et à réfléchir au parcours de ton arbre. Réfléchis bien aux algorithmes avant, c'est primordiale, on se lance pas dans du code, si on ne sait pas où ça va nous mener.

Hésite pas à reposter ici quand tu auras quelque chose, ou si tu as des bugs... :)

Bonjour,

Le prof nous a donné un petit bout de code pour nous aidez.
J'essaye de traduire ce code en java, est comme je n'ai jamais fait de Delphi je suis perdu.

Est ce quelqu'un pourrait bien m'aider.

Merci

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Type TElem = String[25]; TListe = ^Cell;   Cell = Record info : TElem; svt : Tliste; End;   TArbre = ^Noeud;   Tableau = Array['2'..'9'] Of TArbre;   Noeud = Record fils : Tableau; mots : TListe;   End;

---

Mais je ne pense pas que tu ai besoin de tout cela pour réaliser ce que tu demande (mise à part l'arrayList).

Je ne pense pas que tu ai besoin de développer quelque chose de générique( <T>), tu traite avec des nœuds où chaque nœud représente un valeur.

Code:

---

1 2 3 4 5 6

public class NodeForCompletion{ private char value; private boolean isLast; private String prefixe; private List<NodeForCompletion> childs = new ArrayList<NodeForCompletion>(); }

---

Par exemple, tu va avoir le noeud "A" qui sera :

Code:

---

1 2 3

value = "A"; isLast = true; childs = //Une belles liste d'enfant;

---

Pour le retour des mots possible :

Code:

---

1 2 3 4 5 6 7 8 9 10

public List<String> getPosibleWord(){ List<String> toReturn = new ArrayList<String>(); for(NodeForCompletion achildren :childs ){ toReturn.addAll(achildren.getPosibleWord()); } if(isLast){ toReturn.add(prefixe+value); } return toReturn; }

---

Note préfixe et value peuvent directement stocké ensemble.


Pour la méthode de création, c'est le même principe.

Cordialement,
Patrick Kolodziejczyk.

Crie du Cœur :

Citation:

---

La contrainte imposé est de ne pas utilisé les Api.

---

Tu dira à ton professeur que ce qu'il demande est d'un stupidité...
Soit tu utilise java et tu utilise l'API standard et donc :
GO : TreeNode
TreeModel
Soit tu ne l'utilise pas, mais tu veux faire la même chose. Sauf que tu refait le code interne aux méthodes.

Si on te demande de refaire la classe ArrayList<T>, tu me donne le nom de ton professeur !

(L'API standard est là pour être utiliser... Et c'est STANDARD.)

Citation:

---

Envoyé par kolodz

Crie du Cœur :

Tu dira à ton professeur que ce qu'il demande est d'un stupidité...
Soit tu utilise java et tu utilise l'API standard et donc :
GO : TreeNode
TreeModel
Soit tu ne l'utilise pas, mais tu veux faire la même chose. Sauf que tu refait le code interne aux méthodes.

Si on te demande de refaire la classe ArrayList<T>, tu me donne le nom de ton professeur !

(L'API standard est là pour être utiliser... Et c'est STANDARD.)

---

Ça a l'air d'être un cours en rapport avec les structures de données courantes en informatique.
Dans ce cas-là, c'est normal de chercher à refaire soi-même ces structures pour comprendre véritablement comment ça marche. Les ingénieurs info y sont tous passés, et si quelqu'un ne saurait pas les refaire (assez vite) dans un environnement où elles n'existent pas déjà, pour moi c'est pas un ingénieur info.

Bon, par contre, Java me semble pas le meilleur langage pour aborder le sujet, c'est sûr.

A ce niveau, j'aurai demandé à mes élevées de faire une classe implémentant l'interface...

Citation:

---

One stone, Two Brids...

---

Citation:

---

Envoyé par kolodz

A ce niveau, j'aurai demandé à mes élevées de faire une classe implémentant l'interface...

---

Les interfaces Java en question imposent bien plus de fonctionnalités qu'on en proposerait pour un simple exercice. Bon, il reste possible de leur faire toutes lancer UnsupportedOperationException, mais ça va jeter la confusion.

De plus, comprendre les structures de données, et comprendre l'implémentation d'interface, sont deux cours différents.