Projet radix sort

Version imprimable

1 pièce(s) jointe(s)

Projet radix sort

Bonjour, je suis actuellement sur mon projet de C dans lequel je dois effectuer un tri par base (ou radix sort), je précise que je fais du C que depuis récemment.
Le problème qui se pose c'est que là où j'en suis j'ai des fonctions qui appellent d'autres fonctions, dans lequel il y a des malloc et que dés que je sors d'une fault segmentation, ben c'est la fonction suivante, et je tourne en rond. Déjà j'aimerais votre avis sur le createBucketList(int base), parce qu'elle me pose des problèmes de segmentation fault lorsque je veux initialiser ses champs. Je précise que dans la structure BNIntLofL j'avais déclaré en premier lieu un

Code:

BaseNIntegerList *BaseNIntegerList[];

mais mon prof me l'a fait remplacer par un

Code:

BaseNIntegerList *BaseNIntegerList;

que ce n'était pas la peine, que j'avais simplement à rajouter un x*sizeof() dans le malloc.

EDIT : 19:53

dans createBucketList j'ai enlevé "*" lorsque je fais le second malloc
Code:

1 2 *L_BNI_LOL->BaseNIntegerList = (BaseNInt*) malloc(base*(sizeof(BaseNInt)));
en contrepartie j'ai un warning "incompatible pointer type" mais j'ai beaucoup moins de mal à exécuter.
J'ai aussi commenté
Code:

1 2 3 L_BNI_LOL->BaseNIntegerList[compteurBase]->first = NULL; L_BNI_LOL->BaseNIntegerList[compteurBase]->last = NULL;
et la quelques chose d'assez étrange (pour moi) se produit si je fais
Code:

1 2 3 4 5 printf("\nfirst 0: %p", L_BNI_LOL->BaseNIntegerList[0]->first); printf("\nlast 0: %p \n", L_BNI_LOL->BaseNIntegerList[0]->last); printf("\nfirst 1: %p", L_BNI_LOL->BaseNIntegerList[1]->first); printf("\nlast 1: %p \n", L_BNI_LOL->BaseNIntegerList[1]->last);
dans le main hé bien les 2 du milieu (last 0 et first 1) renvois la même valeur (je mets la PJ à jour)

Je n'ai pas téléchargé l'archive de ton projet et sincèrement je doute que quelqu'un le fasse. Ne le prends pas mal mais nous avons tous quelque chose à faire de notre temps libre et faire les devoirs des étudiants ne branche pas grand monde.

Si c'est ton algorithme qui pêche, tu n'es pas sur le bon forum. S'il s'agit de ton implémentation, tu dois être plus précis dans la description de ton problème, identifier un court morceau de code qui ne fonctionne pas avant de nous le soumettre. Tu l'as fait dans ton edit mais il n'y a pas assez d'information du coup ;) , poste la fonction ou au moins les déclarations des variables et les définitions des structs utilisées.

Voici quelques remarques sur les morceaux de code que tu as posté :
- Tu as une variable du même nom que son type BaseNIntegerList, je ne sais même pas si ça compile et c'est en tout cas une très mauvaise idée : renomme l'un ou l'autre.
- Qu'est-ce que BaseNInt ?
- Ne laisse jamais passer un warning dont tu ne connais pas exactement la cause : il s'agit presque toujours d'une erreur de programmation (c'est le cas ici).
- Ne caste pas le résultat de malloc, c'est inutile et dangereux. Inutile car cette fonction renvoie un void * qui est implicitement promu au type de la variable affectée. Dangereux car cela peut empêcher le compilateur de t'informer d'une erreur (types incompatibles notamment).

D'autre part, il y a une différence fondamentale entre un pointeur vers un tableau (TYPE *p) et un tableau de pointeurs (TYPE *p[]) - vers des tableaux, ou pas.. Voici pourquoi ton prof t'as fait faire la modif :

Voici la déclaration et l'initialisation d'un pointeur vers un unique objet de type TYPE :
Code:

1 2 TYPE *ptr_unique = malloc(sizeof(TYPE));
En mémoire, cela peut se représenter par :
Code:

1 2 3 4 5 6 7 8 9 10 +---+ | x | +-|-+ | | v +---+ | | +---+
Voici la déclaration et l'initialisation d'un pointeur vers un tableau d'objets de type TYPE :
Code:

1 2 TYPE *ptr_to_array = malloc(sizeof(TYPE) * n);
En mémoire :
Code:

1 2 3 4 5 6 7 8 9 10 +---+ | x | +-|-+ | | v +---+---+---+---+---+---+-- | | | | | | | ... +---+---+---+---+---+---+--
Voici la déclaration et l'initialisation dynamique d'un tableau de pointeurs vers des objets de type TYPE (note que cela pourrait aussi être des tableaux de TYPE) :
Code:

1 2 3 4 5 TYPE *array_of_ptr[] = { NULL, NULL, NULL, ... NULL, NULL }; for (unsigned int i = 0; i < sizeof pp_n; ++i) array_of_ptr[i] = malloc(sizeof(TYPE));
Et en mémoire :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 +---+---+---+---+---+---+-- | x | x | x | x | x | x | ... +-|-+-|-+-|-+-|-+-|-+-|-+-- | | | | | | | | | | | | v | | | | | +---+ | | | | | | | | | | | | +---+ | | | | | v | | | | +---+ | | | | | | | | | | +---+ | | | | v | | | +---+ | | | | | | | | +---+ | | | v | | +---+ | | | | | | +---+ | | v | +---+ | | | | +---+ | v +---+ | | +---+

En fait quand on fait : Type Variable = (Type*)malloc(sizeof(Type)); on transforme le type de la variable en *Type ? Donc si j'enlève (Type*) devant malloc je dois déclarer des *Type avant chaque malloc du coup.

sinon pour les structs : - dans BaseNIntegerList.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
typedef char* CHAINE;
 
// Struct des elements + typedef de la liste associee
typedef struct elem {
            struct elem *prev;
            CHAINE valeur;
            struct elem *next;
} element;
typedef element * listOfElem;
 
//Struct BaseNInt + typedef de la liste associee
typedef struct BNInt {
            struct elem *first; // Un pointeur vers le premier element de la liste
            struct elem *last;  // Un pointeur vers le dernier element de la liste
            int base;           // La base utilisee pour representer les entiers
            int nbElem;         // Le nombre d'elements dans la liste
} BaseNInt;
typedef BaseNInt * BaseNIntegerList ;

et dans BaseNIntegerListOfList.h

Code:

1
2
3
4
5
6
7
8
9
 
#include "BaseNIntegerList.h"
 
typedef struct BNIntLofL {
            int base;
            BaseNIntegerList *tabDeBaseNIntegerList;
} BaseNIntLofL;
 
typedef BaseNIntLofL * BaseNIntegerListOfList;

j'ai changé le nom de la variable en passant, sur le coup ça m'avait pas choqué. Et enfin mon constructeur de BaseNIntegerListOfList (aprés modification mais pas encore testé) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
BaseNIntegerListOfList createBucketList(int base)
{
    int cpt = 0;
 
    BaseNIntegerListOfList BNI_ListOfList = malloc(sizeof(BaseNIntLofL));
    BaseNIntegerList BNI = malloc(base*(sizeof(BaseNInt)));
    BNI_ListOfList->base = base;
 
    //BNI_ListOfList->tabDeBaseNIntegerList = malloc(base*(sizeof(BaseNInt)));
    for(cpt=0;cpt<base;cpt++)
    { 
        BNI[cpt].base = base; 
        BNI[cpt].first = NULL;
        BNI[cpt].last = NULL;
        BNI[cpt].nbElem = 0;
    }
    *BNI_ListOfList->tabDeBaseNIntegerList = BNI;
    return BNI_ListOfList;
}

Citation:

Envoyé par Doulmagus

En fait quand on fait : Type Variable = (Type*)malloc(sizeof(Type)); on transforme le type de la variable en *Type ? Donc si j'enlève (Type*) devant malloc je dois déclarer des *Type avant chaque malloc du coup.

On ne change pas le type de la variable à laquelle on affecte le résultat, ça c'est impossible ! ;) C'est la valeur de retour de malloc (de type void *, soit pointeur vers un type indéfini, seulement connu du programmeur) que tu castes.

Ton affectation ci-dessus est invalide car tu tentes de mettre une valeur de type pointeur vers Type (Type *) dans une variable de type Type. Variable doit être déclarée comme ceci :

Code:

Type *variable;
Citation:
Envoyé par Doulmagus
et dans BaseNIntegerListOfList.h
Code:

1 2 3 4 5 6 7 8 9 #include "BaseNIntegerList.h" typedef struct BNIntLofL { int base; BaseNIntegerList *tabDeBaseNIntegerList; } BaseNIntLofL; typedef BaseNIntLofL * BaseNIntegerListOfList;
Attention ici tabDeBaseNIntegerList est de type BaseNInt ** (pointeur vers pointeur vers BaseNInt), je ne suis pas sûr que c'est ce que tu veux faire, tu dois avoir un niveau d'indirection de trop. Essaie en le déclarant comme ceci (et en modifiant ses affectations ailleurs dans ton code, bien sûr) :

Code:

BaseNIntegerList tabDeBaseNIntegerList;

D'accord et du coup comme on travaille presque qu'avec les typedef * truc, ça explique pourquoi on met jamais * devant nos déclarations. Par contre, je veux bien déclarer mon tableau comme tu l'as indique

Code:

BaseNIntegerList tabDeBaseNIntegerList;

mais à ce moment la admettons je déclare
Code:

1 2 3 BaseNIntegerList LOL = L_BNI_LOL->tabDeBaseNIntegerList; mais si fais L_BNI_LOL->tabDeBaseNIntegerList[truc]
c'est plus une BaseNIntegerList mais juste une BaseNInt à laquelle j'accède enfin netBeans me dit ça en tout cas quand je veux faire
Code:

1 2 3 4 BaseNIntegerList BNI = L_BNI_LOL->tabDeBaseNIntegerList; BNI = insertTail(BNI, val); L_BNI_LOL->tabDeBaseNIntegerList[1] = BNI;
Du coup la question de est ce que mon

Code:

typedef BaseNInt * BaseNIntegerList ;

est bien nécessaire, sinon je dois remodifier les prototypes des fonctions sur les BaseNIntegerList puisque je ne pourrai plus utiliser mon insertHead avec les []
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 BaseNIntegerList insertHead(BaseNIntegerList L_BNI, CHAINE val) { //On declare l'element à integrer dans la liste listOfElem nouveau; nouveau = malloc(sizeof(element)); nouveau->valeur = val; //Cas de la liste vide nbElem = 0 if(hasNoElem(L_BNI)) { nouveau->next = NULL; nouveau->prev = NULL; L_BNI->last = nouveau; L_BNI->first = nouveau; } else //Cas d'une liste non vide { //Raccordement de l'element à la liste nouveau->next = L_BNI->first; nouveau->prev = NULL; L_BNI->first->prev = nouveau; L_BNI->first = nouveau; } L_BNI->nbElem = L_BNI->nbElem + 1; return L_BNI; }
EDIT : j'ai fait des test, sans * dans la structure, sans le typedef que je remets en question plus haut, rien n'y fait pour l'instant, je n'arrive pas à faire en sorte que

Code:

BNI_ListOfList->tabDeBaseNIntegerList[cpt]

soit de type BaseNIntegerList
actuellement j'ai les structures
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 typedef struct elem { struct elem *prev; CHAINE valeur; struct elem *next; } element; typedef element * listOfElem; typedef struct BNInt { struct elem *first; struct elem *last; int base; int nbElem; } BaseNInt; typedef BaseNInt * BaseNIntegerList ; typedef struct BNIntLofL { int base; BaseNIntegerList tabDeBaseNIntegerList; } BaseNIntLofL; typedef BaseNIntLofL * BaseNIntegerListOfList;
et si je fais
Code:

1 2 3 4 5 6 7 8 9 10 11 12 BaseNIntegerListOfList BNI_ListOfList ; BNI_ListOfList = malloc(sizeof(BaseNIntLofL)); BNI_ListOfList->tabDeBaseNIntegerList = malloc(base*sizeof(BaseNInt)); for(cpt=0;cpt<base;cpt++) { BNI_ListOfList->tabDeBaseNIntegerList[cpt].base = base; BNI_ListOfList->tabDeBaseNIntegerList[cpt].first = NULL; BNI_ListOfList->tabDeBaseNIntegerList[cpt].last = NULL; BNI_ListOfList->tabDeBaseNIntegerList[cpt].nbElem = 0; }
sauf que du coup BNI_ListOfList->tabDeBaseNIntegerList[cpt] est une BaseNInt et pas une BaseNIntegerList comme je le voudrais, ce que je ne comprends d'ailleurs pas trés bien puisque pour créer mes BaseNIntegerList j'ai
Code:

1 2 3 4 5 6 7 8 9 10 BaseNIntegerList createIntegerList(int integer) { BaseNIntegerList List_BNI; List_BNI = malloc(sizeof(BaseNInt)); List_BNI->base = integer; List_BNI->nbElem = 0; List_BNI->first = NULL; List_BNI->last = NULL; return List_BNI; }
et que dans createBucketList je fais exactement le même malloc avec un *base

10/12/2015, 11h47
Matt_Houston
Ok je pense que j'ai saisi ce que tu voulais obtenir. En fait ta déclaration précédente est tout à fait correcte également : cela dépend de la façon dont tu veux créer tes BaseNInt.

tabDeBaseNIntegerList peut-être :
- un pointeur vers un tableau de pointeurs de BaseNInt : BaseNInt **. Dans ce cas, il te faut allouer le tableau de pointeurs avec malloc(sizeof(BaseNInt *) * n), puis chaque élément du tableau avec malloc(sizeof(BaseNInt)) comme tu le fais déjà. Tu accèdes ensuite aux membres de la structure comme ceci : tabDeBaseNIntegerList[i]->nbElem .
- Un pointeur vers un tableau de BaseNInt : BaseNInt * (c'est ce que je t'avais suggéré). Dans ce cas, il te faut allouer le tableau de BaseNInt avec malloc(sizeof(BaseNInt) * n), puis tu peux accéder aux membres de chaque élément sans indirection supplémentaire : tabDeBaseNIntegerList[i].nbElem.
Ces deux méthodes sont équivalentes, ma suggestion est moins complexe : moins d'appels à malloc, donc moins d'appels à free, les BaseNInt sont stockés de manière contigüe... C'est préférable si tu ne redimensionnes jamais ta liste de listes, mais c'est moins flexible si tu dois le faire et si la taille de BaseNInt est appelé à grossir (c'est pour l'instant une toute petite structure dont la copie ne coûte rien).

D'autre part, effectivement les typedef sur les types de pointeur peuvent porter à confusion en dissimulant les indirections et en multipliant le nombre de types déclarés, cela nuit à la lisibilité. Je ne sais pas si c'est une idée de ton prof mais comme tu ne sembles pas encore très à l'aise avec les pointeurs tu devrais peut-être d'abord essayer de faire tourner ton programme sans les typedef, quitte à les décommenter plus tard.
10/12/2015, 12h12
Doulmagus
Ok je viens de voir ta réponse, j'aurais le temps de l'étudier ce soir, et je te redirai ce qu'il en advient.
Ps: en fait dés qu'on a introduit les pointeurs on nous a fait déclarer des typedef * list, sauf qu'en TD et TP ça se résume à un seul typedef par exercice généralement donc je me suis jamais autant emmêlé.

EDIT 18:04
Ah et bien voila ça fonctionne (pour l'instant), je pense qu'il devait me manquer un malloc, j'avais eu l'intuition d'en mettre deux
Code:

1 2 3 BNI_ListOfList = malloc(sizeof(BaseNIntLofL)); BNI_ListOfList->tabDeBaseNIntegerList = malloc(sizeof(BaseNInt*) * base);
mais je ne pensais pas qu'il fallait en plus un malloc par BaseNIntegerList. Du coup je dois pouvoir finir les algos précédemment entamés. Je reviendrai te dire si j'ai réussi. Merci en tout cas.
10/12/2015, 19h10
Doulmagus

Bon ben c'est globalement tout bon j'ai pu dé-commenter les algos, changer le nom du champ et tout a fonctionné du premier coup. Une dernière (ou peut être pas) question, quand je vais faire mes free, il en faudra un pour chaque variable sur laquelle j'ai fait un malloc

Code:

free(variable);

sauf que j'ai vu une fois qu'on pouvait faire juste aprés un

Code:

variable = NULL

, est-ce utile ?
11/12/2015, 08h30
ternel

Ca dépend, si la variable est détruite juste après (car on sort du bloc ou elle a été créée), non, on peut s'en passer.
Mais sinon, oui, c'est utile, pour permettre au reste du code de pouvoir détecter que la mémoire a été libérée, et ne pas risquer une corruption mémoire

C'est une bonne habitude à prendre, en effet. free ne modifiant pas la valeur de son paramètre, il n'y a aucun moyen pour le programmeur de savoir ensuite si cette variable pointe vers une zone mémoire allouée ou pas. En la réinitialisant à NULL, il n'y a plus d'ambiguïté.

De plus le programme craquera probablement immédiatement si l'on essaie de faire quelque chose avec un pointeur nul, alors qu'il peut se passer n'importe quoi si l'adresse est valide (mais pointe sur une zone non-allouée).

Citation:

Envoyé par leternel

Ca dépend, si la variable est détruite juste après (car on sort du bloc ou elle a été créée), non, on peut s'en passer.
Mais sinon, oui, c'est utile, pour permettre au reste du code de pouvoir détecter que la mémoire a été libérée, et ne pas risquer une corruption mémoire

Parfaitement, j'illustre :
Code:

1 2 3 4 5 6 7 8 9 10 11 void do_something() { int *foo = malloc(sizeof(int)); *foo = 18; /* * traitement... */ free(foo); foo = NULL; // inutile ici, car foo ne pourra pas être réutilisé }
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 void do_something_else(size_t n) { int *footab[n]; // initialisation for (unsigned int i = 0; i < n; ++i) { footab[i] = malloc(sizeof(int)); *footab[i] = (int)i; } /* * traitement... */ // libération de quelques éléments free(footab[2]); footab[2] = NULL; free(footab[6]); footab[6] = NULL; free(footab[7]); footab[7] = NULL; /* * traitement... */ // libération des éléments restants for (unsigned int i = 0; i < n; ++i) { /* grâce à NULL, on peut savoir ici quels éléments sont déjà libérés et ne pas les traiter (un free() ça va, deux bonjour les dégâts !) */ if (footab[i]) free(footab[i]); } }
À noter qu'on utilise en général une macro (ou une fonction) pour améliorer la lisibilité et éviter les oublis :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 // 'safe' free, version macro #define sfree(p) { \ free(p); \ (p) = NULL; \ } // 'safe' free, version fonction inline void sfree(void **p) { free(*p); *p = NULL; }

11/12/2015, 14h55
Médinoc

À ta place, j'utiliserais une virgule pour la version macro, moins de risque de problème avec un if(condition) sfree(p)...
11/12/2015, 15h41
Matt_Houston

D'où les accollades. ;) La virgule fonctionne aussi, c'est vrai.