Implémenter un tas en C

Résolu/Fermé

dany - 8 déc. 2005 à 01:34
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 20 juil. 2008 à 14:29

Bonjour tout le monde,

tout d'abord merci à tous ceux qui nous aident sur ce forum c'est vraiment sympa de votre part =)

mon probleme actuel : j'ai un projet à rendre dans lequel on doit implémenter des primitives destinées à travailler sur les tas (heap), avec comme priorité "clé du père inférieure à clé du fils".

les fonctions et procédures doivent être écrites en C, langage dans lequel je débute tout juste...
voici quelques-unes des primitives :
- heap(tmax) pour créer un tas de taille maximale tmax
- insert(i,val) pour insérer un élément i de valeur val
- remove(i) pour retirer l'élément i
- findmin() pour retourner l'élément de plus petite valeur
- deletemin() pour détruire le minimum...
etc....

apparement, il faut utiliser des tableaux pour manipuler les éléments du tas. pour les algos je pense m'en sortir (quoique...). mon probleme est surtout de l'ordre syntaxique, je ne sais pas si mes connaissances en C sont assez "larges" pour mener ce projet : par exemple, faut-il utiliser des pointeurs de pointeurs? ou manipuler pleins de pointeurs? parce que j'ai beaucoup de mal avec ça pour l'instant, je viens juste d'apprendre la récursion en C, et niveau tableaux on n'a fait que des trucs de bases.

si vous avez quelques pistes a me proposer je vous serai très reconnaissante.
et je crois que d'autres questions plus précises arriveront un peu plus tard, quand j'aurai avancé dans ma réflexion ^.^

merci à ceux qui me répondront.

A voir également:

Expliquez comment implémenter deux piles dans un tableau a[1..n] de telle manière qu'aucune des piles ne déborde à moins que
Tableau croisé dynamique - Guide
Tableau ascii - Guide
Comment connecter chromecast à la télé - Guide
Deux comptes whatsapp - Guide
Tableau word - Guide

7 réponses

Réponse 1 / 7

mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
8 déc. 2005 à 02:03

Tu vas en effet avoir un tableau de pointeur (void *) (adresse générique) de taille statique (la taille max). Or si un tableau d'int est un int *, un tableau de void * est un void ** :

#include <stdlib.h>
#include <stdio.h>

struct heap{
   size_t taille_max;
   void ** data;
};

struct heap new_heap(size_t t_max){
   struct heap h;
   h.taille_max=t_max;
   //Allouer taille_max cases de taille sizeof(void *)
   //Mettre toute cette zone à 0 (calloc et non malloc)
   h.data=(void **)calloc(taille_max,sizeof(void *));
   return h;
}

void delete_heap(heap h){
   for(unsigned int i=0;i<h.taille_max;++i){
      //Si la case i contient une adresse non nulle
      //supprimer ce qui s'y trouve
      if (data[i]) free(data[i]);
   }
   //Maintenant que le tableau est purgé,
   //supprimer le tableau
   free(data);
}

Un pointeur c'est en fait très simple : tout objet est stocké à une adresse mémoire. Un pointeur sur un objet est simplement l'adresse de cet objet (donc une valeur sur 4bits alors qu'un objet peut être beaucoup plus gros !).

Pour passer d'un pointeur à un objet :

plop * pointeur=...;
plop objet = *pointeur;

Pour passer d'un objet à un pointeur :

plop objet = ...;
plop * pointeur= & objet;

Si l'on est capable de manipuler des adresses d'int ou de struct, rien n'empeche de manipuler des adresses d'adresse (pointeur doubles) ou adresse d'adresse d'adresse (pointeur triple)...

Pour ce qui est des tableaux alloué statiquement (int tab[255]) il faut bien voir qu'on alloue 255 int consécutifs et qu'à l'adresse tab ce trouve en fait tab[0] (*tab==tab[0]). La valeur entre crochet ne fait que spécifier de combien on se décale par rapport à tab[0]. C'est pour ça que les tableaux d'int sont des int*.

int       int      ...
tab[0]   tab[1] ...
*tab
 ^
 |
tab
int *

Si tu as d'autres questions n'hésite pas à repasser

Bonne chance

Réponse 2 / 7

mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
12 déc. 2005 à 20:04

C'est cool :-) Tu repasses quand tu veux ;-)

Réponse 3 / 7

mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
14 déc. 2005 à 19:41

%lf

Pour retrouver la raison d'une erreur de segmentation, si tu es sous linux :

$ gcc -g -o plop.exe main.c
$ gdb plop.exe
gdb> r
erreur de segmentation
gdb> bt

Ca affiche la pile d'appel, ie la ligne ou ça a planté de chaque fonction appelées au moment ou ça a planté.

Bonne chance

Réponse 4 / 7

dany
12 déc. 2005 à 01:27

salut mamiemando,

merci pour ta réponse, super bien expliqué c'est génial =)
je ne connaissais pas tout (structures et allocation mémoire, j'ai pas encore appris...), mais grâce à quelqu'un dans mon cours on a réussi a compiler ce qu'on avait écrit... reste juste à tester avec un logiciel graphique... si jamais ça marche pas, je repasserai!!

merci encore, ce forum est une bénédiction ^.^

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 7

dany
14 déc. 2005 à 17:27

salut,

j'ai encore une question : comment on fait pour lire une chaine de caractères sur le terminal?
je sais qu'il faut utiliser un scanf mais ça me fait une erreur de segmentation. c'est encore une histoire de pointeur je pense...
j'ai écrit (dans le main) :

char * str; // str est la chaine de caracteres a saisair
scanf("%s",str);

et ça ne marche évidemment pas.

en fait, dans le projet il est écrit "Un menu permettra de choisir les différentes opérations à effectuer".
j'ai donc pensé à faire un scanf, ainsi quand l'utilisateur tape heap(10) dans le terminal, le programme appelle la fonction heap avec en paramètre la taille maximale du tas (ici, c'est 10). le problème, c'est que je ne sais pas lire séparement la chaine de caractère "heap" de l'entier 10. et comme il n'y a pas que heap comme opération, il faut que je compare la chaine saisie str à d'autres cahines comme "insert", "remove", etc... pour savoir quelle fonction appeler à chaque fois.
comment fait-on pour comparer 2 chaines de caractères? (avec une boucle sur les caracteres?)

si ça se trouve, c'est même pas comme ça qu'on fait un menu mais je n'ai pas d'autre idée =(
je pose des questions un peu élémentaires mais j'ai consulté le manuel et ça ne m'en dit pas plus (et l'anglais n'est pas trop mon fort héhé)

merci d'avance pour votre aide

cathy
19 juil. 2008 à 15:59

tun'as pas allouer de mémoire pour stocker la chaine de caractère que tu vas saisir.
Donc avant d'appeler la fonction scanf, tu dois faire une allocation de mémoire via la fonction
malloc qui se trouve dans la bibliothèque stdlib.h.Tu devrais avoir un truc du style

#include<stdlib.h>
.........
........
........
int main(){
.........
........
........
str=(char *)malloc(60*sizeof(char));
/*dans cette exemple ta chaine de caractère devra compter moins de 60 éléments*/
}

mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749 > cathy
20 juil. 2008 à 14:29

Hello cathy,

Merci de ta contribution mais le sujet à trois ans et a déjà été résolu.

Bonne continuation

Réponse 6 / 7

dany
14 déc. 2005 à 18:05

ps: quelle est la spécification de conversion pour une double?? jai mis

%f

mais ça fait une erreur de segmentation =(

Réponse 7 / 7

dany
14 déc. 2005 à 23:45

merci =)

Discussions similaires

ou sont les bananes ?

Bibliothèque

Un seul de mes écouteurs marche. Que faire ?

Tableau croisé dynamique avec plusieurs en-têtes identiques

Trouver le nom d'un tableau avec sa photo.

Discussions similaires

Newsletters