Discussion :

[startout]

Bonjour,


Je suis actuellement en train de préparer un document de synthèse sur les structures de données.
C'est ma façon de faire pour apprendre.
Dans un premier temps, j'essaye de lister toutes les structures de données

Je vais mettre ci-dessous une liste de structure de données, si vous pouviez m'indiquer si j'en ai oublié ou si j'ai fait des erreurs. Je vous en remercie grandement.

Structure Séquentielle
1°) Tableaux
2°) Fichier Séquentiel
3°) Liste chainée (Doublement chainée, circulaire, etc...)
4°) Pile et File

Structure Arborescente
1°) Arbre binaire
2°) Arbre N-aires
3°) Arbres H-équilibrés
4°) Arbres balancés.

Autres
1°) Le hachage (est-ce vraiment une structure de donnée ?)

Je vous remercie par avance de vos réponses.

[millie]

3°) Liste chainée (Doublement chainée, circulaire, etc...)

Pourquoi ne pas parler des listes en général. Et seulement après parler d'implémentation.

J'aurais personnellement fait comme ça (mais c'est personnel) :

Pour la partie : structure séquencielle

Type abstrait :

Type ensemble
Type tableau
Type structure
Type pile
Type file
Type liste

Edit Par contre, la définition d'un type Fichier est une bonne idée

Implémentation :

Les implémentations possibles (bon, il y a un problème qui est que le type ensemble peut s'implémenter par un tas, qui n'a pas encore été précisé)

par exemple la liste est implémentable par une liste chaînée
une pile peut être implementée par une liste ou par un tableau.


Mais c'est cool Bon courage

[Jean-Marc.Bourguet]

Si j'ai bonne mémoire, la description des différentes structures de données dans wikipedia n'est pas mauvaise.

[startout]

Effectivement tu as raison. Je confonds description de la structure de donnée et implémentation.
Donc le type pile je ne vais pas le mettre dans les structures de donnée puisque comme tu le dis, ce type peut-être implanté en tableau ou en liste chainé.

Pour les liste je vais parler des listes en général et pas la façon de les implémenter.

Par contre, je ne vois pas ce qu'est le type ensemble ?

Pour Jean-Marc.Bourguet,

Oui c'est fort possible que wikipédia donne une trés bonne définition des différentes structures de données mais je souhaite me pencher dessus et y réflechir (c'est de cette façon que j'apprends) plutôt que de lire un texte pondu par quelqu'un (façon passif). cela n'empêche que je peux m'y inspirer comme même


Je vais essayer de travailler dessus.
A+ tard.

[millie]

Donc le type pile je ne vais pas le mettre dans les structures de donnée puisque comme tu le dis, ce type peut-être implanté en tableau ou en liste chainé.

Il peut, mais c'est un type abstrait de donnée. Tu peux le définir comme tel.
(par exemple : regarde le dernier post de : http://www.developpez.net/forums/sho...d.php?t=193046)

[startout]

Voilà un premier jet :


Ensemble quelconque
Ajouter
O(1) commentaire -> ajout en début ou fin de liste suivant la structure

Recherche commentaire -> On peut imaginer un algo améliorant la recherche en déplaçant l'élément trouvé en le rapprochant de la tête de liste.
Au mieux O(1)
Au pire O(n)
En moy O(n/2)

Liste contigue (trié)
Ajouter et supprimer commentaire -> Gourmand en déplacement
Au mieux O(1) commentaire -> en fin de liste
Au pire O(n) commentaire -> en début de liste
En moy O(n/2)

Recherche (dichotomique)
O(log2n)

Arbre binaire
Ajouter commentaire -> deux possibilités. A la racine ou aux feuilles.
Que ce soit à la racine ou arbre même complexité.
En moy O(PCE(A))
Au pire O(h(A))

Suppression
En moy O(PC(A))
Au pire O(h(A))


Voilà pour le moment. Je n'ai pas encore terminé et il faut que je décrive ce qu'est PC(A), h(A) etc...

Je vous donnerais la suite plus.
Si vous avez des remarques

A +

[millie]

Ensemble quelconque
Ajouter
O(1) commentaire -> ajout en début ou fin de liste suivant la structure

Je ne suis pas d'accord, un ensemble n'admet pas deux même éléments...

Ici, Ajouter({1,2,3},1) va renvoyer {1,1,2,3} alors que ça ne devrait pas.

Pour l'ensemble :

Au mieux O(1)
Au pire O(n)
En moy O(n/2)

Il y a des implémentations plus efficaces (notamment en utilisant un tas, l'ensemble est trié et permet d'effectuer une recherche de manière plus rapide).

Cela dit, c'est plus complexe à mettre en oeuvre, ça dépend des performances que tu souhaites avoir.

[khayyam90]

dans les structures de données fortement utilisées, on retrouve aussi les graphes et les versions triées des structures déjà citées ici.
de plus tu peux t'inspirer de la liste des conteneurs de base de la STL c++

[Matthieu Brucher]

Pour la liste, je ne suis pas sûr d'être d'accord pour la complexité... Pour est-ce pire d'insérer en début qu'à la fin ? Pourquoi est-ce coûteux en déplacements ??