IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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

C Discussion :

Projet radix sort


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2015
    Messages : 7
    Par défaut 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    BaseNIntegerList *BaseNIntegerList[];
    mais mon prof me l'a fait remplacer par un
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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)
    Fichiers attachés Fichiers attachés

  2. #2
    Membre Expert
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    TYPE *ptr_unique = malloc(sizeof(TYPE));
    En mémoire, cela peut se représenter par :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    TYPE *ptr_to_array = malloc(sizeof(TYPE) * n);
    En mémoire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
                         +---+
                         |   |
                         +---+

  3. #3
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2015
    Messages : 7
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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;
    }

  4. #4
    Membre Expert
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Par défaut
    Citation Envoyé par Doulmagus Voir le message
    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 :
    Citation Envoyé par Doulmagus Voir le message
    et dans BaseNIntegerListOfList.h
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    BaseNIntegerList tabDeBaseNIntegerList;

  5. #5
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2015
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Territoire de Belfort (Franche Comté)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2015
    Messages : 7
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    BaseNIntegerList tabDeBaseNIntegerList;
    mais à ce moment la admettons je déclare
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    BNI_ListOfList->tabDeBaseNIntegerList[cpt]
    soit de type BaseNIntegerList
    actuellement j'ai les structures
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  6. #6
    Membre Expert
    Inscrit en
    Mars 2005
    Messages
    1 431
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 1 431
    Par défaut
    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.

Discussions similaires

  1. Réponses: 12
    Dernier message: 06/06/2016, 08h56
  2. Le projet Hudson sort en version 3.0
    Par Hinault Romaric dans le forum Intégration Continue
    Réponses: 4
    Dernier message: 01/02/2013, 09h52
  3. création programme de tri (radix sort)
    Par zozo0 dans le forum Débuter
    Réponses: 2
    Dernier message: 12/02/2012, 21h18
  4. Radix sort a du mal sur android ?
    Par Mikiya dans le forum Android
    Réponses: 0
    Dernier message: 15/02/2011, 07h42
  5. Réponses: 0
    Dernier message: 25/01/2011, 13h10

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