Trie par tableau d'indexRésolu

Question

Voici mon probleme : J'ai plusieurs caracteres nommés "telephone"
enregistré par une structure qui me permettent de les enregistrer.Ce
que je souhaite faire c'est ordonner ces numero de telephone , pas
directement dans la structure,mais dans un tableau d'index qui va
enregistrer la position de chaque numero de telephone par ordre
croissant.


Par exemple : 


/* nom et numero de telephone */


bernard  06


titi     02


toto     04


dans mon tableau d'index j'aurais [ 2, 3, 1 ]


Maintenant voici mon code car cela ne fonctionne pas trop :-(

Code : C

typedefstruct  
{

        char             nom[MAX_NOM];

        char             telephone[10]; 
}personne; 

typedefstruct
{

    personne    T[MAX_NUMEROS];

    int         dernier;
}rep;

void ajout(int *nombre_de_numeros_dans_repertoire,rep repertoire,int index_telephone[])

{
int position_index = 0;
int position_du_numero_dans_repertoire = *nombre_de_numeros_dans_repertoire;
int g = 0;
int d = (*nombre_de_numeros_dans_repertoire) - 1 ;
int m = 0 ;
int i =0;

    
printf("
Nom renvoye : %s",(repertoire.T[*nombre_de_numeros_dans_repertoire].nom));
printf("
Numero renvoye : %s",(repertoire.T[*nombre_de_numeros_dans_repertoire].telephone));

/* ajout du nouveau numero de telephone dans l'index */
if(*nombre_de_numeros_dans_repertoire == 0)/* Si c'est  le premier element on ajoute directement le numero dans l'index*/

    {position_index == 0; }  /* egale à la position du numero de telephone dans le repertoire*/
else

    {

    /* sinon on cherche la position dans l'index pour ce numero */

    /* m : milieu ; d=droite ; g=gauche */

    puts("
On cherche sa position");

        while(g != d)

            {

                    m = ((g+d)/2);

                            if(strcmp (repertoire.T[*nombre_de_numeros_dans_repertoire].telephone,(repertoire.T[index_telephone[m]].telephone)) < 0)

                                            {d  = m + 1;}

                            else

                                            {g  = m + 1;}

            }

    position_index = d ;

    printf("position : %d",d);

  

    }
/* on doit d'abord decaler */


   if(*nombre_de_numeros_dans_repertoire != 0)

     {  for(i= *nombre_de_numeros_dans_repertoire ;i >= position_index ; i--);

        {

        repertoire.T[i]=repertoire.T[i-1];

        }

     }
/* ensuite on ajoute le numero de la position dans l'index */

index_telephone[position_index] = position_du_numero_dans_repertoire;

/* Affichage du contenu de l'index */

for(i = 0; i<=(*nombre_de_numeros_dans_repertoire) ; i++ )

    {printf("
%d : %d avec comme numero %s",i,index_telephone[i],(repertoire.T[index_telephone[i]].telephone));}

}

24Karas · Accepted Answer

oups désolé, j'ai oublié un petit test pour la fin du tableau ;-)
il faut changer dans la fonction ajout :

while (strcmp(szNumToAdd,repertoire->T[tOrderNum[uPosIndex]].szTelephone) > 0)

devient maintenant

while ((uPosIndex < *uNbNum) && (strcmp(szNumToAdd,repertoire->T[tOrderNum[uPosIndex]].szTelephone) > 0))

j'espere que maintenant c'est OK

++
24K

24Karas · Answer

voilà une solution que je te propose, si ça peut t'aider.
c'est pas super performant (2 parcours de boucle) mais ça marche. et puis si tu veux plus rapide, stock tout dans un arbre
Pour les num de telephone, stock des entiers

// type
typedef struct t_num{
        char            szNom[10];
        unsigned int    uTelephone;
}t_num;

int main (void)
{
        unsigned int    uNbNum;
        t_num           tNum[10];
        unsigned int    tOrder[10];
        unsigned int    uI;
        unsigned int    uJ;
        unsigned int    uPos;

        // ajouter quelques trucs
        uNbNum = 4;
        strcpy(tNum[0].szNom            ,"a");
        tNum[0].uTelephone = 496245659; // <=> 0496245659
        strcpy(tNum[1].szNom            ,"b");
        tNum[1].uTelephone = 496814500;
        strcpy(tNum[2].szNom            ,"c");
        tNum[2].uTelephone = 596985659;
        strcpy(tNum[3].szNom            ,"d");
        tNum[3].uTelephone = 396245659;

        // tri
        for (uI=0;uI<uNbNum;uI++)
        {
                uPos = 0;

                for (uJ=0;uJ<uNbNum;uJ++)
                {
                        if (tNum[uJ].uTelephone < tNum[uI].uTelephone)
                        {
                                uPos++;
                        }
                }
                tOrder[uPos] = uI;
        }

        // affiche
        for (uI=0;uI<uNbNum;uI++)
        {
                fprintf (stderr,"%0.10u %s
",tNum[tOrder[uI]].uTelephone,tNum[tOrder[uI]].szNom);
        }
        return 0;
}

++
24K

24Karas · Answer

j'ai oublié de préciser, dans mon cas, les numéros de tel doivent etre uniques, sinon écrasement. de toute façon je vois mal deux personnes avec meme num.

++

Utilisateur anonyme · Answer

aprés corrections ca donne ca, c'est mieux mais pas encore ca, et la j'ai du mal :-(

Code : C
void ajout(int *nombre_de_numeros_dans_repertoire,rep repertoire,int index_telephone[])

{
int position_index = 0;
int position_du_numero_dans_repertoire = *nombre_de_numeros_dans_repertoire;
int i =0;

    
printf("
Nom renvoye : %s",(repertoire.T[*nombre_de_numeros_dans_repertoire].nom));
printf("
Numero renvoye : %s",(repertoire.T[*nombre_de_numeros_dans_repertoire].telephone));
printf("
Nombre de numero dans repertoire : %d",*nombre_de_numeros_dans_repertoire);

/* ajout du nouveau numero de telephone dans l'index */
if((*nombre_de_numeros_dans_repertoire) == 0)/* Si c'est  le premier element on ajoute directement le numero dans l'index*/

    {position_index == 0; }  /* egale à la position du numero de telephone dans le repertoire*/
else

    {

    /* sinon on cherche la position dans l'index pour ce numero */


    puts("
On cherche sa position");


    for(i=0;i<=(*nombre_de_numeros_dans_repertoire)-1;i++)/*-1 car un numero en  moins dans l'index actuel car par encore ajouté */

    {

 

     if(strcmp (repertoire.T[*nombre_de_numeros_dans_repertoire].telephone,(repertoire.T[index_telephone[i]].telephone)) < 0)

          {

            

            position_index = i;

            i=*nombre_de_numeros_dans_repertoire; /* permet de quitter la boucle car position trouvee*/

          }  

      else

            {   position_index = *nombre_de_numeros_dans_repertoire; }  

    }


    

    printf("
position_INDEX : %d",d);

  

    }

    

    

    
/* on doit d'abord decaler */
/* il ecrase le numero mais decale pas */

   if((*nombre_de_numeros_dans_repertoire) != 0)

     {  for(i= (*nombre_de_numeros_dans_repertoire) ;i >= position_index ; i--);

        {

        

        index_telephone[i+1]=index_telephone[i];

        }

     }

     
/* ensuite on ajoute le numero de la position dans l'index */

index_telephone[position_index] = position_du_numero_dans_repertoire;

/* Affichage du contenu de l'index */

for(i = 0; i<=(*nombre_de_numeros_dans_repertoire) ; i++ )

    {printf("
%d : num index : %d avec comme numero pointe %s",i,index_telephone[i],(repertoire.T[index_telephone[i]].telephone));}

}


si je test le programme et que j'entre par exemple les numeros


11


33


44


et aprés que je souhaite ajoute 22 ca devrais afficher


11


22


33


44 


mais NAN ca plante   surement durant le decalage ? car ça l'affiche :


11


22


44 et planté

24Karas · Answer

bon j'ai refais un truc pour garder ta logique, mais il insert dans le tableau en passant en parametre. tu peux faire autrement si tu veux mais j'trouve ça plus logique d'ajouter dans la fonction ajout ;-) #include #include #define MAX_NOM 256 #define MAX_NUMEROS 256 typedef struct t_personne{ char szNom[MAX_NOM]; char szTelephone[10]; }t_personne; typedef struct t_rep{ t_personne T[MAX_NUMEROS]; unsigned int uNbNum; }t_rep; void ajout(unsigned int *uNbNum,t_rep *repertoire,unsigned int tOrderNum[],char *szNumToAdd, char *szNom) { unsigned int uPosIndex = 0; unsigned int uI =0; // ajoute dans la table des numeros strcpy(repertoire->T[*uNbNum].szTelephone,szNumToAdd); strcpy(repertoire->T[*uNbNum].szNom,szNom); // new num if (*uNbNum == 0) { tOrderNum[0] = 0; (*uNbNum)++; } else { uPosIndex = 0; while (strcmp(szNumToAdd,repertoire->T[tOrderNum[uPosIndex]].szTelephone) > 0) { uPosIndex++; } // décale et insere if (uPosIndex == *uNbNum) { tOrderNum[*uNbNum] = *uNbNum; } else { for (uI=*uNbNum;uI>uPosIndex;uI--) { tOrderNum[uI] = tOrderNum[uI-1]; } tOrderNum[uPosIndex] = (*uNbNum); } (*uNbNum)++; } } int main (void) { // vars t_rep rep; unsigned int tOrdered[MAX_NUMEROS]; unsigned int uI; // ajoute quelques num rep.uNbNum = 0; ajout(&rep.uNbNum,&rep,tOrdered,"789","toto"); ajout(&rep.uNbNum,&rep,tOrdered,"123","titi"); ajout(&rep.uNbNum,&rep,tOrdered,"456","tutu"); // affiche for(uI=0;uI

Utilisateur anonyme · Answer

Merci beaucoup poue le code ca m'a bien aidé, par contre si je teste avec les lignes :

    ajout(&rep.uNbNum,&rep,tOrdered,"123","titi");
    ajout(&rep.uNbNum,&rep,tOrdered,"456","tutu");
    ajout(&rep.uNbNum,&rep,tOrdered,"111","tutu");
    ajout(&rep.uNbNum,&rep,tOrdered,"789","toto");

le 789 ne veut pas entrer ça plante!!! pourquoi?

Utilisateur anonyme · Answer

encore merci , tu me sauves la vie ;-)

Utilisateur anonyme · Answer

es t'il possble avec ce code de faire une recherche par dichotomie pour trouver la position ?

Utilisateur anonyme · Answer

Lorsque j'ajoute une longue chaine ca ecrie n'importe quoi :

    ajout(&repertoire,index_telephone,"12324254232352345","titi");
    ajout(&repertoire,index_telephone,"456","tutu");
    ajout(&repertoire,index_telephone,"111","tutu");

24Karas · Answer

Bon, derniere reponse, parce qu'il faut chercher un peu, les reponses tombent pas du ciel.
je sais pas quel IDE et compilo tu utilises mais il existe de bon debugger sous windows et sous linux. donc faut s'en servir. google est aussi une source d'info.

donc pour la premiere question : bien sur il est possible de faire de la dichotomie, mais je comprend toujours pas l'intérêt de faire 2 tableaux. c'est bien plus facile de faire UN seul tableau et de le trier au vol ou meme à la fin ou bien de faire un arbre comme ça tout est ordonné directement à l'insertion

pour la seconde question : il faut COMPRENDRE le code et non le recopier !
en lisant un peu tu verrais que la taille maximum d'un numéro que j'ai fixé est de 10 caracteres :
char    szTelephone[10];

alors bonne continuation et cherche un peu ça fait du bien à la cervelle ;-)

Utilisateur anonyme · Answer

Oui j'avais pensé a ca, mais mon numero de teelephone se conmpose des 10 caracteres + le '\0' de fin .quand on initialise char    szTelephone[10]; on a bien 11 caracteres dans le tableau ( de 0 à 10). Donc pourquoi ca plante avec un numzero à 10 chiffres.

24Karas · Answer

fprintf (stderr,"-->%d
",sizeof(rep.T[0].szTelephone)/sizeof(char));
ça donne pas 11 ça

Trie par tableau d'index

12 réponses

Votre réponse

Discussions similaires