Implémenter un tas en C
Résolu/Fermé
dany
-
8 déc. 2005 à 01:34
mamiemando Messages postés 33390 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 28 novembre 2024 - 20 juil. 2008 à 14:29
mamiemando Messages postés 33390 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 28 novembre 2024 - 20 juil. 2008 à 14:29
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
- Comment faire un tableau - Guide
- Tableau ascii - Guide
- Comment connecter chromecast à la télé - Guide
- Comment imprimer un tableau excel sur une seule page - Guide
7 réponses
mamiemando
Messages postés
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
7 803
8 déc. 2005 à 02:03
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 ** :
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 :
Pour passer d'un objet à un pointeur :
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*.
Si tu as d'autres questions n'hésite pas à repasser
Bonne chance
#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
mamiemando
Messages postés
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
7 803
12 déc. 2005 à 20:04
12 déc. 2005 à 20:04
C'est cool :-) Tu repasses quand tu veux ;-)
mamiemando
Messages postés
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
7 803
14 déc. 2005 à 19:41
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
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 ^.^
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
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) :
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
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
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*/
}
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
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
7 803
>
cathy
20 juil. 2008 à 14:29
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
Merci de ta contribution mais le sujet à trois ans et a déjà été résolu.
Bonne continuation
