Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Community Manager

    Avatar de Siguillaume
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    août 2007
    Messages
    5 867
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : août 2007
    Messages : 5 867
    Points : 31 324
    Points
    31 324

    Par défaut Apprendre à programmer les arbres en langage C

    Bonjour, je vous présente ce tutoriel de CGi pour apprendre à programmer des arbres binaires en langage C.
    Tout comme les listes chaînées, les arbres servent à mémoriser des données. Ils sont constitués d'éléments que l'on appelle souvent des nœuds (node). Ils sont semblables aux listes chaînées par le fait que les éléments sont chaînés les uns avec les autres, mais avec la possibilité que plusieurs branches partent d'un nœud, d'où leur nom (on pourrait très bien voir une liste chaînée comme un arbre à une seule branche). Il est courant d'appeler le premier élément d'un arbre la racine. La racine est un nœud qui n'a pas de parent. On peut aussi entendre parler de feuilles, ce sont les nœuds qui sont au bout des branches et qui n'ont donc pas d'enfants.

    Ce tutoriel étant destiné à aborder les arbres, nous allons donc en créer un qui sera le plus simple possible, ce sera un arbre binaire.
    Bonne lecture
    Vous avez envie de contribuer au sein du Club Developpez.com ? Contactez-nous maintenant !
    Vous êtes passionné, vous souhaitez partager vos connaissances en informatique, vous souhaitez faire partie de la rédaction.
    Il suffit de vous porter volontaire et de nous faire part de vos envies de contributions :
    Rédaction d'articles/cours/tutoriels, Traduction, Contribution dans la FAQ, Rédaction de news, interviews et témoignages, Organisation de défis, de débats et de sondages, Relecture technique, Modération, Correction orthographique, etc.
    Vous avez d'autres propositions de contributions à nous faire ? Vous souhaitez en savoir davantage ? N'hésitez pas à nous approcher.

  2. #2
    Community Manager

    Avatar de Siguillaume
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    août 2007
    Messages
    5 867
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : août 2007
    Messages : 5 867
    Points : 31 324
    Points
    31 324

    Par défaut Apprendre à programmer les arbres tassés en langage C

    Bonjour, je vous présente la deuxième partie du tutoriel sur apprendre à programmer les arbres, avec dans cette seconde partie, les tas.

    Sur les arbres binaires de recherche, nous avions mentionné un défaut, qui est le fait que certaines branches peuvent être beaucoup plus longues que d'autres dans certaines circonstances. Ce qui a un effet néfaste sur les performances. L'arbre que nous allons aborder pallie ce problème. La hauteur de sa plus grande branche ne pourra être supérieure que d'une unité par rapport à la plus petite. C'est-à-dire que si sa plus grande branche passe par 15 nœuds sa plus petite passera par 14 nœuds au minimum (15 au cas où l'arbre est complet). Bien sûr comme dans tout arbre, les données seront insérées selon un certain ordre, afin de les retrouver facilement. Ce type d'arbre est très bien adapté pour servir de file de priorité. C'est ce que nous allons construire dans l'exemple suivant.
    Bonne lecture.
    Vous avez envie de contribuer au sein du Club Developpez.com ? Contactez-nous maintenant !
    Vous êtes passionné, vous souhaitez partager vos connaissances en informatique, vous souhaitez faire partie de la rédaction.
    Il suffit de vous porter volontaire et de nous faire part de vos envies de contributions :
    Rédaction d'articles/cours/tutoriels, Traduction, Contribution dans la FAQ, Rédaction de news, interviews et témoignages, Organisation de défis, de débats et de sondages, Relecture technique, Modération, Correction orthographique, etc.
    Vous avez d'autres propositions de contributions à nous faire ? Vous souhaitez en savoir davantage ? N'hésitez pas à nous approcher.

  3. #3
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    26 824
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 26 824
    Points : 39 523
    Points
    39 523

    Par défaut

    C'est bizarre, avec ce paragraphe d'introduction on s'attend plutôt à voir un article sur les arbres binaires de recherche auto-équilibrés qu'un article sur les tas...

    En même temps, je te remercie pour cet article, très instructif. Je n'avais jamais compris le principe des arbres "tas" avant...
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  4. #4
    Nouveau Candidat au Club
    Profil pro
    enseignant
    Inscrit en
    octobre 2008
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : enseignant

    Informations forums :
    Inscription : octobre 2008
    Messages : 1
    Points : 1
    Points
    1

    Par défaut Pourquoi des fonctions sont en static ?

    Bonjour,
    Tout d'abord grand merci pour ces deux tutos sur les arbres, c'est pour bonne entrée en matière pour me replonger dans le Cormen (Algorithmes).
    Donc ma question à propos de static sur les deux fonctions reorganizeHeap et HeapRealloc : en C++ Ok mais je n'ai jamais compris l'intérêt en C et encore moins vu en pratique.
    Merci par avance

  5. #5
    Membre émérite
    Homme Profil pro
    sans emploi
    Inscrit en
    janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : janvier 2014
    Messages : 539
    Points : 2 598
    Points
    2 598

    Par défaut

    static est, en C concernant les fonctions, à opposer à extern. Par défaut les fonctions sont visibles de l'extérieur d'un module : elles sont par défaut déclarées en extern (implicite). Déclarer une fonction C en static permet d'en réduire la visibilité au module où elle est déclarée, elle ne pourra plus être accessible d'un autre module. Cela concerne les fonctions qui n'ont rien à faire dans un API et qui ne servent qu'en interne à un module.
    Les deux fonctions que tu cites ont cette propriété, personne n'a à les utiliser en dehors du module, d'où le static.

    static est également très utile pour créer des fonctions qui remplaceront avantageusement les macros ; ce sont les fonctions static inline dans les headers.

  6. #6
    Nouveau Candidat au Club
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    avril 2018
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 21
    Localisation : Maroc

    Informations professionnelles :
    Activité : Chercheur en informatique

    Informations forums :
    Inscription : avril 2018
    Messages : 1
    Points : 1
    Points
    1

    Par défaut question cansernant les paramatre de la fonction addNode

    bojour
    d'abord je remerci tous ceux qui participer pour construire cette article.
    je suis un debutant, ce qui fait que mon question EST un peu basique, ma question es la suivante :
    pour quoi on passe un pointeure de pointeur en paramatre dans la fonction addNode , je pence que on aurait pu lui passer que un pointeure

  7. #7
    Expert confirmé
    Inscrit en
    mars 2005
    Messages
    1 374
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 374
    Points : 4 028
    Points
    4 028

    Par défaut

    On a choisi de représenter un arbre vide par un pointeur nul de type nœud (c'est une conception courante). Si l'on veut pouvoir ajouter un nœud à un arbre vide, et donc attribuer une autre valeur que NULL à son pointeur de nœud racine, il faut passer ce dernier par référence. En C, on passe une variable par référence en passant son adresse et donc en augmentant le niveau d'indirection.

    Si l'on passait par copie :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    void add_node(node *tree, int value);
     
    // ...
     
    {
        node *tree = NULL; // arbre vide
        add_node(tree, 42); // par copie..
        assert(tree == NULL); // fail, tree n'est pas modifié !
    Puisque l'on passe par référence :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    void add_node(node **tree, int value);
     
    // ...
     
    {
        node *tree = NULL; // arbre vide
        add_node(&tree, 42); // par référence..
        assert(tree != NULL); // ok, tree n'est plus vide

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    6 724
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 6 724
    Points : 19 061
    Points
    19 061
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par yassine316 Voir le message
    pour quoi on passe un pointeure de pointeur en paramatre dans la fonction addNode , je pence que on aurait pu lui passer que un pointeure
    Bonjour

    Une fonction qui reçoit un élément en paramètre ne reçoit qu'une copie de ce qu'on lui envoie. N'oublie jamais ce point et tu t'en sortiras en C.
    Exemple
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int main() {
    	int x=500;
    	fct(x);	// Ici la fonction ne reçoit qu'une copie de "x" (même si cette copie est stockée dans une variable portant le même nom)
    	// Ici "x" est resté inchangé
    	printf("x=%d\n", x);
    }
     
    void fct(int x) {
    	x=123;	// Ici affectation de "123" dans la variable locale "x" (qui ne contient qu'une copie de ce qu'on a envoyé à la fonction). Quel que soit ce qu'on lui envoie, ça reste inchangé
    }

    Si on veut qu'une fonction modifie une variable, alors il faut lui passer l'adresse de cette variable. La fonction stockera une copie de cette adresse mais les adresses étant communes à tout le code, même avec une copie de l'adresse on peut quand-même aller à cette adresse et modifier ce qui s'y trouve.
    Et une adresse est stockée dans un pointeur (pointeur du type de la variable d'origine)
    Exemple
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int main() {
    	int x=500;
    	fct(&x);	// Ici la fonction reçoit une copie de l'adresse de "x". Mais même une copie de l'adresse reste l'adresse réelle de "x".
    	// Ici "x" a été modifié
    	printf("x=%d\n", x);
    }
     
    void fct(int *pt) {
    	*pt=123;	// Ici affectation de "123" à l'adresse copiée dans "pt". Si cette adresse est l'adresse d'une variable réelle, alors cette variable est modifiée
    }

    Donc la règle est la suivante: une fonction qui doit modifier une variable de type truc reçoit l'adresse de cette variable et stocke cette adresse dans un truc étoile.

    Si maintenant le type "truc" est déjà un pointeur (de type donc xxx étoile), la règle ne change pas. On lui passe l'adresse de cette variable. Et cette adresse sera alors stockée dans un xxx étoile étoile.

    Exemple avec "tree" de type "node étoile"...

    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int main() {
    	node* tree=NULL;
    	fct(&tree);		// Ici, comme avant, la fonction reçoit une copie de l'adresse de "tree". Mais "tree" étant un "node étoile", cette adresse sera stockée dans un "node étoile étoile"
     
    	// Ici "tree" a été modifié
    	printf("tree=%p\n", tree);
    }
     
    void fct(node* *pt /* Qu'on écrit plutôt "node **pt") */ {
    	*pt=malloc(sizeof(node));	// Ici le retour de "malloc" est stocké à l'adresse placée dans "pt" (donc à l'adresse référencée par la variable "node"
    }
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

Discussions similaires

  1. Réponses: 0
    Dernier message: 19/02/2016, 17h48
  2. Les arbres binaires (langage Caml)
    Par bambina dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 15/02/2012, 00h31
  3. les arbres en langage c
    Par anasultras dans le forum C
    Réponses: 3
    Dernier message: 12/05/2009, 15h20

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo