aide pour le tri d'une liste

bonjour à tous
je me représente d'abord (car j'étais inscrit déja ici pseudo logfile mais mais mon ordi a crashé puis j'ai changé de connexion internet)
J'ai 45 ans , je programme en C en autodidacte depuis quelques temps déjà
Mon projet principal est un jeu déchec que j'ai porté sur winboard depuis peu
Mais j'ai un soucis pour effectuer un tri au niveau des coups légaux .
Explicatin

pour enregistrer les coups à chaque niveau de l'arbre j'ai une structure du type :
Code:

1 2 3 4 5 6 7 8 9 10 typedef struct le_COUP { int dep; /*n°case depart du coup*/ int arr; /*n° case d'arrivee du coup*/ int piece_jouee; /*piece jouee (roi , pion , etc ....*/ int type; /*type de coup (normal ,prise , roque etc...)*/ int ext_type; /*si le coup attaque le roi , ---> = ATTAQUE_ROI*/ int ep; /*case de prise en passant (VIDE ou n°case)*/ int val; /*valeur du coup*/ } COUP;
a chaque niveau , je déclare une table locale liste_coups[200]
l'accès à chaque coup est :

liste_coups[i].dep ,etc ....

Je voudrais trier ces listes de coups pour analyser le "meilleur coup" d'abord et ainsi par ordre
décroissant

Si j'apelle ma procédure de tri en envoyant le nombre de coups légaux et l'adresse
du 1er élèment de ma liste : tri(ctr_coups,&liste_coups[0]);

le tri s'effectue bien dans la procédure mais au retour , les coups sont toujours dans
le même ordre ! Comme je ne maitrise pas bien les pointeurs , je suis
un peu perdu ...
Si quelqu'un avait des idées ou suggestions
Car ce problème me bloque depuis un bon moment

edit :
j'ajoute mon code de tri (qui ne fonctionne pas en l'état : erreur de compilation : D:\ECHECS\JARS\divers.c In function `tri':
124 D:\ECHECS\JARS\divers.c invalid lvalue in assignment )
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 31 32 33 34 35 void tri(int x,COUP *p) { int i,j; int n; int m; COUP *tmp; COUP *tmp1; n = x; m = n; tmp = NULL; while(m != 0) { m = m/2; for(j=0;j<=(n-2);j++) { i = j; onze: if(p->val < (p+1)->val) { tmp = (p+1); (p+1) = p; p = tmp; i = i-1; if(i >= 1) goto onze; } } } }
merci d'avance et à bientot

Citation:

Envoyé par dany9

Comme je ne maitrise pas bien les pointeurs , je suis
un peu perdu ...

Il est vrai qu'en changeant ta structure en y ajoutant un pointeur vers une une structure le_COUP, tu pourrais
1) ne plus utiliser de tableau, mais uniquement un pointeur vers le premier élément.
2) ceci pourrait te permettre d'accéder aux système de tri de liste qui sont très intéressant.
3) Tu ne serais plus limité à un nombre quelconque de coup

Un pansement pour faire face à ce problème :
locale liste_coups[i] => locale liste_coups[tab_tri[i]] ou tab_tri est un tableau de 200 unsigned char* qui donne le i ème élément trié:
tab_tri[0] : indice du meilleur coup
tab_tri[1] : indice du second coup

* : si tu passes en dessus de 256 coups, ne plus prendre char, mais short...
...

merci pour ta réponse rapide et ... pertinente !
Il est vrai que j'ai trop négligé les pointeurs ; il faudrait que je m'y mette .... mais leur complexité m'a toujours rebuté

Quand tu parles de pointeur vers le 1er élèment , ça donnerai ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 typedef struct le_COUP { int *debut_liste /* pointeur vers le 1er élèment*/ int dep; /*n°case depart du coup*/ int arr; /*n° case d'arrivee du coup*/ int piece_jouee; /*piece jouee (roi , pion , etc ....*/ int type; /*type de coup (normal ,prise roque etc...)*/ int ext_type; /*si le coup est une prise qui attaque le roi , ---> = ATTAQUE_ROI*/ int ep; /*case de prise en passant (VIDE ou n°case)*/ int val; /*valeur du coup*/ } COUP;
Pour gérer ce genre de structure il faut maitriser les listes chainées non ? J'ai toujours eu du mal avec ça!

Sinon dans ton dernier exemple (pansement) , c'est le tableau tab_tri[i] qui va contenir les addresses permutées lors du tri c'est ça ?
Et c'est là que je bloque aussi : tu as marqué locale , la liste va être tri dans la procédure tri donc localement non ? (une bouée : je coule !)

Correction :
Code:

1 2 3 4 5 6 7 8 9 10 11 typedef struct le_COUP { Le_COUP *suiv /* pointeur vers l'élèment suivant */ int dep; /*n°case depart du coup*/ int arr; /*n° case d'arrivee du coup*/ int piece_jouee; /*piece jouee (roi , pion , etc ....*/ int type; /*type de coup (normal ,prise roque etc...)*/ int ext_type; /*si le coup est une prise qui attaque le roi , ---> = ATTAQUE_ROI*/ int ep; /*case de prise en passant (VIDE ou n°case)*/ int val; /*valeur du coup*/ } * COUP_1;
Tu as un pointeur vers l'item suivant et tu mémorises un pointeur vers le premier coup.

Citation:

Envoyé par dany9

Pour gérer ce genre de structure il faut maitriser les listes chainées non ? J'ai toujours eu du mal avec ça!

Ce serait un bon exercice ! Non ?

Citation:

Envoyé par dany9

Sinon dans ton dernier exemple (pansement) , c'est le tableau tab_tri[i] qui va contenir les adresses permutées lors du tri c'est ça ?

Oui

Citation:

Envoyé par dany9

Et c'est là que je bloque aussi : tu as marqué locale , la liste va être tri dans la procédure tri donc localement non ? (une bouée : je coule !)

locale ???
Tu devras passer comme informations à ta fonction, liste_coups et tab_tri (les pointeurs vers les premiers éléments de ton tableau).

merci encore pour ton aide

Autrement dit , il faut me plonger dans les pointeurs jusqu'au cou !

Sinon comme je suis têtu , je vais tester ta méthode avec tab_tri[] (un tableau de pointeurs autrement dit ?)

Je te dirais si c'est bon

à plus!

Citation:

Envoyé par dany9

e vais tester ta méthode avec tab_tri[] (un tableau de pointeurs autrement dit ?)

Non, un tableau d'indices

bon ... y a surement qque chose qui m'échappe encore ...
maintenant j'envoie donc l'addresse du 1er element de la table liste_coups (p) pour avoir accès aux valeurs triées et l'addresse du 1er element de la table tab_tri (table qui contient les indices des coups autrement dit tab_tri[0] = 0 , tab_tri[1] = 1 etc ...)

accès au coup maintenant :

Code:

liste_coups[tab_tri[i]].dep , etc ...

maintenant on permute seulement les indices de tab_tri[]

J'ai modifié le code de tri , il compile mais erreur d'exécution :
"Une violation d'accès (erreur de segmentation) est apparue dans votre programme "
???

(les deux boucles avec printf sont là pour voir "si ça trie":? je les vire après

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
31
32
33
34
35
36
37
38
39
40
41
void tri(int x,COUP *p, int *r)
{
    int   i,j;
    int   n;
    int   m;
    int  *tmp;
 
    n = x;
    m = n;
    tmp = NULL;
 
    for(i=0;i<x;i++)
      {
        printf("%d   \n",*(r));
        r++;
      }
 
   while(m != 0)
        {
            m = m/2;
                for(j=0;j<=(n-2);j++)
                    {
                        i = j;
                        while(i>=1)
                          {
                             if(p->val < (p+i)->val)
                               {
                                  *(tmp) = *(r+i);
                                  *(r+i) = *(r);
                                  *(r) = *(tmp);
                                  i = i-1;   
                               }
                          }
                    }
        } 
    for(i=0;i<x;i++)
      {
        printf("%d   \n",*(r));
        r++;
      }
}

Je n'ai pas le temps de tout regarder, mais :
1) travaille avec les indices de r ou garde en mémoire le r d'origine => c'est sur que là, il y a une erreur :aie:
2) vire le goto et met un while... On dirait du basic :lol:

goto viré!

premier post édité , goto viré (je traine cette procédure tri depuis longtemps ,
je l'avais prise de mon prog d'échecs en ... QB45 ... :oops: je n'avais jamais pris la peine de la moderniser)

bon merci quand même , si tu as un peu plus de temps une autre fois , pense à moi
bye

Tu n'as toujours pas corrigé le point 1 !
enlève r++ et remplace *r par *(r+i)
Fais qqc d'équivalent dans le while.

Citation:

Envoyé par troumad

Correction :

Code:

1
2
3
4
5
6
7
8
9
10
11
typedef struct le_COUP
    {
		Le_COUP *suiv     /* pointeur vers l'élèment suivant */
        int dep;	           /*n°case depart du coup*/
		int arr;	           /*n° case d'arrivee du coup*/
		int piece_jouee;       /*piece jouee  (roi , pion , etc ....*/
	    int type;	           /*type de coup (normal ,prise roque etc...)*/
	    int ext_type;          /*si le coup est une prise qui attaque le roi , ---> = ATTAQUE_ROI*/
		int ep;		           /*case de prise en passant (VIDE ou n°case)*/
        int val;               /*valeur du coup*/
	} * COUP_1;

J'apporte à mon tour une petite correction:

Code:

1
2
3
4
5
typedef struct le_COUP
{
    struct le_COUP *suiv     /* pointeur vers l'élèment suivant */
    /* ... */
} COUP;

Meilleures salutations

Thierry

hello!
voila j'ai simplifié ma méthode de tri
maintenant j'utilise un genre de tri a bulle mais ... même message d'erreur que précédemment (segmentation)
Pourtant là j'utilise effectivement les indices de r non?

C'est lorsque je veux permuter *(r+j) et *(r+i) que ça "foire" ... je dois tout de même pas être trop loin de la soluce

troumad : dans le précédent code , j'avais effectivement pas vu que à cause de r++ le tmp tombait "hors de r" dès la première itération !!...:oops:

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
31
32
33
34
35
36
37
38
void tri(int x,COUP *p, int *r)
{
    int   i,j;
    int   n;
    int   m;
    int  *tmp;
    int  *tmp1;
 
 
    n = x;
    m = n;
    tmp = NULL;
    tmp1 = r;  /* sauvegarde de l'addresse de debut de tab_tri[]*/
 
 
    for(j=0;j<=(x-1);j++)
      {
         for(i=j+1;i<x;i++)
           {
            printf("%d  %d \n",j,i);
             if((p+j)->val < (p+i)->val)
               {
                  *(tmp) = *(r+j);
                  *(r+i) = *(r+j);
                  *(r+i) = *(tmp);                   
                }
           }
      }
 
    /*boucle temporaire : visualisation des
       indices triés lorsque ça marchera , 
       je l'enlèverai */
    for(i=0;i<x;i++)
      {
        printf("%d   \n",*(tmp1));
        tmp1++;
      }
}

Une erreur se trouve ici :

Code:

1
2
3
4
5
6
 
    tmp = NULL;
    ....
                  *(tmp) = *(r+j);
                  *(r+i) = *(r+j);
                  *(r+i) = *(tmp);

Fait plutôt :

Code:

1
2
3
4
5
6
7
 
int tmp;
...
 
                  tmp = *(r+j);
                  *(r+i) = *(r+j);
                  *(r+i) = tmp;

Jc

merci à to pour cette petite correction

Il n y a plus de mess d'erreur mais ça ne trie pas

Je sais pourquoi ... je modifie et je vous tiens au courant!

Quel forum d'enfer !