× Aidez la recherche contre le COVID-19 avec votre ordi ! Rejoignez l'équipe PC Astuces Folding@home
 > Tous les forums > Forum Autres langages
 Langage C : tableaux, listes chainéesSujet résolu
Ajouter un message à la discussion
Page : [1] 
Page 1 sur 1
Malcolm
  Posté le 14/11/2006 @ 11:08 
Aller en bas de la page 
Astucien

Hello

juste une question qui pourrait, de prime abord, paraitre rapide ... Mais discutable.

entre le tableau et la liste chainée, lequel s'exécute le plus rapidement ? Pour quel type d'utilisation ?

le tableau peut être lu sépentiellement par ses index, la liste chainée par les pointeurs sur les éléments suivants (j'inclue la liste doublement chainée pour le principe), mais comme le tableau n'est pas une adresse comme la liste chainée ... vu qu'on n'a "que" le premier index, si je me souviens bien ?

Merci de vos éclaircissements...


Publicité
koala01
 Posté le 14/11/2006 à 20:14 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
Astucien

Salut,

Le seul avantage du tableau, c'est que tu as un acces "aléatoire" de complexité 1 aux éléments du tableau...

C'est à dire que, pour tout tableau contenant N élments, l'acces à n'importe quel élément compris entre 0 et (N-1) pourra se faire en une seule commande:

tab[10]; // on accede au 11eme élément
tab[150]; //ou au 151eme sans perdre de temps

Mais c'est, de manière générale, le seul avantage que l'on puisse leur trouver... surtout en C ou en C++... (je parle, ici, des tableaux "bruts" et non de la classe std::vector<type> du C++ [clindoeil])

Avec un tableau de N éléments, le fait d'essayer de définir une valeur pour l'élément N+1 est vouée à l'échec, avec de nombreuses complications... A moins qu'il n'aie été alloué dynamiquement, et que tu penses, le cas échéant, à le réallouer à une taille correcte (mais, dans ce cas, il ne faudra pas oublier de le libérer quand tu n'en a plus besoin [langue])

De la meme manière, le fait d'essayer d'insérer un nouvel élément entre deux éléments existants demandera beaucoup plus de travail:

  • allocation de la mémoire suffisante pour contenur le nouveau nombre d'éléments
  • décalage de tous les éléments qui doivent venir apres celui qu'on insere vers la fin du tableau
  • placement du nouvel élément à sa place
  • ... libération éventuelle du tableau devenu "inutile" (selon la méthode utilisée [clindoeil])

Fatalement, ce qui fait la force de l'un fait la faiblesse de l'autre, et vice-versa...

En effet, l'inconvéniant des liste chainées est que l'acces à un élément choisi au hasard dans une liste contenant N élément se fera avec une complexité allant de 1 à N:

Si tu as "la chance" que l'élément recherché soit directement accessible par rapport à l'élément sur lequel tu te trouve, tu aura un acces "direct" à l'élément recherché...

Si, pour ton plus grand malheur, tu te trouve sur le premier élément de la liste, et que tu veux accéder au Nieme élément, il faudra utiliser une boucle qui sera parcourue N fois pour y accéder...

Par contre, l'insertion d'un nouvel élément de la liste, quelle que soit sa position (au début, à la fin, ou entre deux éléments déjà existant) sera beaucoup plus facile:

  • tu fais pointer le pointeur "suivant" de l'élément à rajouter vers... celui qui vient logiquement tout suite apres,
  • tu fais pointer le pointeur "suivant" de l'élément qui vient juste avant sur celui à rajouter
  • (dans le cas d'une liste doublement chainée, tu fais pointer les pointeur "précédent" en conséquence [clindoeil])

Tu évite donc d'avoir à bouger un grand nombre d'éléments pour avoir la place d'y mettre ton nouveau [clindoeil], avec le gain de rapidité d'exécution que le fait de ne pas devoir exécuter une boucle pour le déplacement te fait gagner...

Une troisième solution, que tu n'a pas citée est l'arbre binaire...

L'acces au données d'un arbre binaire, s'il a été correctement trié, se fera selon une complexité allant de 1 à logN^-1, ce qui sera, surtout pour les structures contenant de nombreux éléments, certes moins rapide que l'utilisation de tableaux, mais beaucoup plus rapide que l'utilisation des listes...

Ainsi, en trois exécutions de boucle maximum, tu es sur de trouver n'importe quel élément dans un arbre binaire, correctement rempli, qui en contient 8... avec 8 essais, tu es sur de trouver ton éléments parmi un total de 255, et tu es sur de trouver ton élément en 16 essais maximum parmis 65.535... (ou parmis plus de 4 milliards et demis d'éléments en seulement 32 essais [langue])

L'inconvéniant de l'abre binaire réside dans le fait qu'il faut absolument que les éléments soient différents, et dans le fait que le tri/le remplicage correct d'un arbre est susceptible de prendre plus de temps...

Enfin, visiblement, tu as quand meme oublié quelque chose au sujet des tableaux...

Quand tu déclare un tableau sous la forme de

int tab[10000];

Bien sur, tab est un pointeur qui pointe à la fois sur le premier élément du tableau (tab[0]) et sur... le tableau en lui meme...

Mais chaque élément du tableau est indexé, ce qui fait que tu peux à tout moment accéder à tab[N] pour autant que 0<=N<taille du tableau, et ce, comme je l'ai indiqué, sans devoir passer par les (N-1) autres éléments du tableau [clindoeil]

Bref, en ce qui concerne la rapidité d'exécution, il faut voir l'usage que tu prévois faire...

Si tu prévois un usage sous la forme d'un nombre bien fini d'éléments, sans prévoir d'en rajouter (les 12 mois de l'année, les 7 jours de la semaine, les 4 opérations de base...) un tableau sera vraissemblablement plus efficace...

Si tu prévois un usage sous forme d'un nombre non fini d'éléments, avec des rajoutes/suppressions à des endroits choisis aléatoirement, une liste est vraissemblablement préférable...

Si enfin, tu prévois d'insérer "en une seule fois" un nombre non fini d'éléments, de les trier, puis d'effectuer surtout des recherches, l'arbre binaire sera de nature à présenter tout son potentiel ...

Quoi qu'il en soit, la meilleure solution sera toujours... celle que tu auras choisie en fonction des différent impératifs auxquels tu es confronté [clindoeil]

Malcolm
 Posté le 14/11/2006 à 21:54 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
  Astucien

Je te remercie de tes précisions. En fait, je m'interrogeais dessus puisque c'était le thème du cours

Après quelques recherches, j'en étais parvenu aux mêmes conclusions, sauf l'arbre binaire, ça m'a l'air intéressant c'te bestiole je me documenterai dessus pour info, bien que je n'aie pas besoin d'en savoir plus pour le moment. (c'est juste de la curiosité).

Merci de ta réponse !

koala01
 Posté le 14/11/2006 à 22:39 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
Astucien

Pour que tu puisse comprendre l'idée d'un arbre binaire...

Il se base sur une structure du genre de

typedef struct SFeuille
{
type valeur;
struct *SFeuille FeuilleGauche;
struct *SFeuille FeuilleDroite;
} Feuille;

L'idée est que l'on décide "unilatéralement" que FeuilleGauche pointra, par exemple, vers un élément plus petit que celui sur lequel on se trouve, et que feuille droite pointra alors sur... un élément plus grand que celui sur lequel on se trouve... (ou l'inverse... apres tout, le tout étant que tu te tiennes à ta décision [clindoeil])

Si l'élément sur lequel tu te trouve n'est pas celui que tu cherche, tu n'as pas énormément de solution: soit celui que tu recherche est plus grand (il faudra alors aller du coté dont tu as décidé que c'était le "plus grand"), soit il est plus petit (et il faudra alors aller du coté "plus petit")...

Du point de vue de la sémantique, la "feuille" que tu gardes à disposition pour entrer dans l'arbre est la "racine" (ou le tronc), une feuille qui aurait une connection (à gauche, à droite, ou les deux) avec une autre feuille serait une "branche", et une feuille qui n'aurait pas de connection avec d'autre(s) feuille(s) s'appellerait une "feuille"...

La "représentation graphique" pourrait ressembler à

représentation d'un arbre binaire

Ici, tu as quatre niveaux, et 15 possiblités...

A chaque fois que tu descend d'un niveau (en suivant "plus grand" ou "plus petit", du divise le nombre d'éléments potentiels par... deux... Pour autant que toutes les "feuiles" se trouvent à un meme niveau, et que toutes les branches (y compris la racine) pointent verts deux branches ou feuilles de niveau inférieur...

Si tu arrivais à créer un tel arbre, correctement rempli, avec l'ensemble de la population mondiale, il ferait moins de 64 niveaux... (je te laisse calculer la valeur de (2^64) -1 [clindoeil])

En 64 essais maximum, tu serais donc en mesure d'assurer retrouver le moindre papou trainant dans une savane quelconque [langue]

La grosse contrainte est que l'arbre doit etre correctement rempli et trié, et que, si tu n'y prend pas garde, tu pourrait très bien te retrouver avec un arbre ressemblant à

arbre binaire mal rempli

ce qui, tu t'en doute, te fera perdre tout l'intéret de la chose [clindoeil] (vu que tu retombera dans une sorte de liste simplement chainée...)

koala01
 Posté le 14/11/2006 à 22:54 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
Astucien

Par contre, un avantage non négligeable, c'est que, malgré la complexité apparente de la chose, il ne te faudra, grace à la récursivité, que trois lignes et deux tests pour afficher tous les éléments parfaitement triés que l'arbre contient, et ce, meme si l'une ou l'autre des branches venait à etre amputée d'un de ses "descendants"...

Une fonction du genre de

Ecrit(Feuille *actuelle)
{
Si actuelle->FeuilleGauche<>NULL
Ecrit(actuelle->FeuilleGauche)
FinSi
Affiche actuelle->Valeur;
Si actuelle->FeuilleDroite<>NULL
Ecrit(actuelle->FeuilleDroite
FinSi
}

fera parfaitement le travail



Modifié par koala01 le 14/11/2006 22:57
fleuretta
 Posté le 16/11/2006 à 03:27 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
Astucienne

Une chance que vous vous comprenez les gars car moi je n'ai rien compris...et c'est tout à fait normal j'y connais rien de rien (et vous le savez) mais j'ai eu du plaisir à vous lire... surtout que je connais les deux pros.

Bonne chance pour ton cours Matthieu

Salut petite bête poilu

[fleur]

Malcolm
 Posté le 16/11/2006 à 13:30 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
  Astucien

on peut aussi pouvoir procéder à des tris (à bulle, dichotomie, etc...) sur l'arbre binaire, ou on le fait en en recréant un autre ?
koala01
 Posté le 16/11/2006 à 15:05 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
Astucien
On peut parfaitement trier un arbre binaire (finalement, il n'y a aucune différence entre la racine et une feuille [clindoeil]), mais, du fait meme de sa structure, la création d'un algorithme n'est pas la partie la plus facile du travail [langue]
koala01
 Posté le 20/11/2006 à 15:41 
Aller en bas de la page Revenir au message précédent Revenir en haut de la page
Astucien

juste un petit up apres avoir vérifier la sémantique du terme "dichotomie"...

A vrai dire, La structure meme de l'abre binaire, et la manière dont il est rempli, est la solution la plus efficace existante pour une recherche dichotomique...

Du moins, si la recherche s'effectue sur la valeur qui a été utilisée pour le tri...

En effet, on remplace les termes "racine", "branche" et "feuille" dans un arbre, comme le montre cette image,

valeurs dans un arbre binaire

on constate que cela représente justement l'idée que l'on se fait d'une recherche dichotomique... (qui consiste à prendre la liste d'éléments par leur milieu, puis par le milieu de ce qui reste)

Evidemment, une structure completement remplie sera l'idéal d'efficacité recherché... mais un problème profond lors de l'insertion ou de la suppression d'un élément...

Page : [1] 
Page 1 sur 1

Vous devez être connecté pour poster des messages. Cliquez ici pour vous identifier.

Vous n'avez pas de compte ? Créez-en un gratuitement !


Les bons plans du moment PC Astuces

Tous les Bons Plans
599 €Portable 15,6 pouces Asus Vivobook (FullHD, Ryzen 5, 8Go, SSD 512 Go) à 599 €
Valable jusqu'au 04 Décembre

Amazon fait une promotion sur le PC portable 15,6 pouces Asus Vivobook S512DA-EJ209T qui passe à 599 € alors qu'on le trouve ailleurs à partir de 700 €. Ce portable très bien équipé possède un écran 15,6 pouces Full HD (1920x1080) antireflet, un processeur AMD Ryzen 5 3700U, 8 Go de RAM, un processeur graphique AMD Radeon RX Vega 8 et un SSD de 512 Go. Le WiFi, le bluetooth et l'ethernet Gigabit sont de la partie. Le tout tourne sous Windows 10. 


> Voir l'offre
129 €Ecran 27 pouces Samsung C27F398 (incurvé, 4 ms, FreeSync) à 129 €
Valable jusqu'au 04 Décembre

Amazon propose actuellement l'écran 27 pouces Samsung C27F398WU à 129 € livré gratuitement. On le trouve ailleurs à partir de 169 €. Cet écran dispose d'une dalle VA incurvée Full HD (1920x1080) et offre un temps de réponse de 4ms. Il possède des entrées VGA et HDMI. Il possède des fonctions d'anti scintillement et anti lumière bleue.


> Voir l'offre
79,14 €Souris Logitech MX Master 3 (unify, bluetooth, capteur laser) à 79,14 € livrée
Valable jusqu'au 03 Décembre

Amazon Espagne fait une promotion sur la nouvelle souris sans fil Logitech MX Master 3 qui passe à 74,38 € (avec la TVA ajustée). Comptez 4,76 € pour la livraison en France soit un total de 79,14 € livrée alors qu'on la trouve ailleurs à partir de 109 €. Cette souris offre une double connectivité sans fil unify ou bluetooth. 

Elle vous permet de contrôler jusqu'à 3 ordinateurs différents à l'aide d'une seule souris. Copiez et collez du texte d'un écran à un autre, ou encore transférez des fichiers d'un ordinateur à un autre avec une facilité déconcertante.

Conçue pour offrir précision, contrôle et confort aux utilisateurs expérimentés, la souris sans fil Logitech MX Master 3 se caractérise notamment par une forme parfaitement adaptée à la main, des fonctionnalités avancées et une conception incroyable. Elle dispose d'une molette pour le pouce afin de faire défiler le contenu de l'écran latéralement d'un simple mouvement du pouce. Et avec le logiciel Logitech Options vous allez pouvoir paramétrer au mieux votre souris. Ainsi, vous allez pouvoir ajuster la vitesse de défilement, naviguer au sein du contenu sous forme d'onglets, changer d'application, régler le volume et bien d'autres choses. Son capteur laser Dark field vous permettra de l'utiliser sur n'importe quelle surface.

Vous pouvez utiliser votre compte Amazon France sur Amazon Espagne et il n'y a pas de douane.


> Voir l'offre

Sujets relatifs
Apprendre les bases du langage VBA sous Excel
[Langage C] Tests unitaires
[info] Swift: Pourquoi Apple a créé un nouveau langage de programmation
meilleur langage outre que C++
Les tableaux de string en c++
Précision de variable en Langage C
passage de tableaux en variable dans les fonctions
Calcul langage C
fichier entête langage C
choisir un langage C++,c#,vb,java,delphi
Plus de sujets relatifs à Langage C : tableaux, listes chainées
 > Tous les forums > Forum Autres langages