Tri conditionnel d'une liste chaînée

**floopi51** · 27/02/2013, 12h09

Bonjour,

J'ai une liste chaînée contenant des noms de villes. Ces villes sont rangées dans la liste selon un critère : elles ont une sous-chaine commune.
Je veux faire un tri de la liste chaînée d'abord sur les noms quoi commencent par la sous-chaîne puis les noms qui contiennent la sous-chaîne.
Un exemple sera peut-être plus parlant :
La liste de ville pour la sous-chaîne "TOURS" contient : Chambray-Les-Tours, Joue-Les-Tours, Tours, Tours-en-Savoie.
Je veux que ma liste triée soit : Tours, Tours-en-Savoie, Chambray-Les-Tours, Joué-les-Tours.

Je trie au fur et à mesure des insertions.

Mon problème : l'insertion avec tri se passe sans problème mais le parcours de la liste complète après toutes les insertions conduit à un crash donc il doit y avoir un problème au niveau de l'insertion mais je n'arrive pas à l'identifier.

Si quelqu'un a une idée, MERCI !!!!

Voici mon code :

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
****************
dans le .h : 
 
//un element (node) de la liste
struct node {
    unsigned char myname[MAXI];
    struct node *p_next; //
    struct node *p_prev;
};
 
// la liste
typedef struct dlist {
    size_t nbName;
    size_t lengthAllNames;
    struct node *p_tail;
    struct node *p_head;
} Dlist;
 
*****************
//Dans le .c
//la fonction d'ajout par tri :
 
//Ajouter un élément dans la liste en plaçant en début de liste les noms qui commencent par KEY = sous-chaine
Dlist* dlist_addSortedData(Dlist *p_list, unsigned char * data, unsigned char* myKey) {
    int keySize = strlen((char*)myKey);
    struct node *tmp_ptr;
 
    if(p_list != NULL) {
        struct node *p_new = (struct node *)malloc(sizeof(struct node)); //Création d'un nouveau node
        bzero(p_new, sizeof(struct node));
        if (p_new != NULL) {// On vérifie si le malloc n'a pas échoué
            //on crée la nouvelle structure
            bzero(p_new->myname, MAXI);
            strncpy((char*)p_new->myname,(char*)data, strlen((char*)data));
            int endOfWord = strlen((char*)data) + 1;
            p_new->myname[endOfWord] = '\0';
 
            if (p_list->p_tail == NULL) { // Cas où notre liste est vide (pointeur vers fin de liste à  NULL)
                p_new->p_prev = NULL; // On fait pointer p_prev vers NULL
                p_list->p_head = p_new; // On fait pointer la tête de liste vers le nouvel élément
                p_list->p_tail = p_new; // On fait pointer la fin de liste vers le nouvel élément
 
            } else { // Cas où des éléments sont déjà présents dans notre liste
                tmp_ptr = p_list->p_head;
 
               //On regarde d'abord si les données à insérer commence par la sous-chaine myKey
                if(strncmp((char*)data, (char*)myKey, keySize) == 0) {
 
                    //on insère en triant dans les noms qui commencent par myKey
                    while(strncmp((char*)tmp_ptr->myname, (char*)myKey, keySize) == 0) {
                        while((tmp_ptr->p_next != NULL) && strcmp((char*)tmp_ptr->myname, (char*)data) < 0) {
                            tmp_ptr = tmp_ptr->p_next;
                        }
 
                        if (strcmp((char*)tmp_ptr->myname, (char*)data) < 0) {
                            // tmp->ptr->myName < data
                            // data va dans le next de tmp_ptr
                            if(tmp_ptr->p_next != NULL) {
                                tmp_ptr->p_next->p_prev = p_new;
                                p_new->p_next = tmp_ptr->p_next;
                            }
 
                            tmp_ptr->p_next = p_new;
                            p_new->p_prev = tmp_ptr;
 
                            p_list->nbName++; // Incrémentation du nombre d'éléments de la liste
                            p_list->lengthAllNames += (strlen((char*)p_new->myname));
                            break;
 
                        } else {
                            //data < tmp_ptr->myName
                            if (tmp_ptr->p_prev == NULL) {
                                //on est en tête de liste
                                p_new->p_next = p_list->p_head;
                                p_list->p_head = p_new;
                            } else {
                                p_new->p_prev = tmp_ptr->p_prev;
                                tmp_ptr->p_prev->p_next = p_new;
                            }
                            tmp_ptr->p_prev = p_new;
                            p_new->p_next = tmp_ptr;
 
                            p_list->nbName++; // Incrémentation du nombre d'éléments de la liste
                            p_list->lengthAllNames += (strlen((char*)p_new->myname));
                            break;
                        }
                    }
                } else {
                     //on passe les éléments qui commencent par KEY
                    while((tmp_ptr->p_next != NULL) && strncmp((char*)tmp_ptr->myname, (char*)myKey, keySize) == 0) {
                        tmp_ptr = tmp_ptr->p_next;
                    }
 
      /////////  Ajout par rapport au post original
                    if(tmp_ptr->p_next == NULL && tmp_ptr->p_prev == NULL) { //on n'a qu'un élément dans la liste
                        if(strncmp((char*)tmp_ptr->myname, (char*)myKey, keySize) == 0) {
                            //cet élément est la tête de liste et il contient KEY en début
                            // ==> on met p_new après cet élément
 
                            tmp_ptr->p_next = p_new;
                            p_new->p_prev = tmp_ptr;
 
                            p_list->nbName++; // Incrémentation du nombre d'éléments de la liste
                            p_list->lengthAllNames += (strlen((char*)p_new->myname));
                        }
 
                    } else {
         //////////////////////
                        //puis on fait un tri normal
                        while((tmp_ptr->p_next != NULL) && (strcmp((char*)tmp_ptr->myname, (char*)data) < 0)) {
                            tmp_ptr = tmp_ptr->p_next;
                        }
 
                        if (strcmp((char*)tmp_ptr->myname, (char*)data) < 0) {
                            // tmp->ptr->myName < data
                            // data va dans le next de tmp_ptr
                            if(tmp_ptr->p_next != NULL) {
                                tmp_ptr->p_next->p_prev = p_new;
                                p_new->p_next = tmp_ptr->p_next;
                            }
 
                            tmp_ptr->p_next = p_new;
                            p_new->p_prev = tmp_ptr;
 
                            p_list->nbName++; // Incrémentation du nombre d'éléments de la liste
                            p_list->lengthAllNames += (strlen((char*)p_new->myname));
 
                        } else {
                            //data < tmp_ptr->myName
                            if (tmp_ptr->p_prev == NULL) {
                                //on est en tête de liste
                                p_new->p_next = p_list->p_head;
                                p_list->p_head = p_new;
                            } else {
                                p_new->p_prev = tmp_ptr->p_prev;
                                tmp_ptr->p_prev->p_next = p_new;
                            }
                            tmp_ptr->p_prev = p_new;
                            p_new->p_next = tmp_ptr;
 
                            p_list->nbName++; // Incrémentation du nombre d'éléments de la liste
                            p_list->lengthAllNames += (strlen((char*)p_new->myname));
                        }
                    }
 
                }
 
            }
 
        } else {
            printf("dlist_addSortedData failed ALLOC\n");
            return NULL;
        }
 
    }
 
    return p_list;
}

**Kirilenko** · 27/02/2013, 12h54

Bonjour,

Le mieux, pour savoir pourquoi ça plante, c'est d'utiliser un débogueur. Sous Unices, valgrind te permettra de localiser les accès mémoires douteux, tandis qu'avec gdb, tu pourras analyser efficacement le contenu de tes données au fur et à mesure de l'exécution. En l'état, le code source de ta fonction est quand même assez long (m'est avis qu'on peut faire plus simple). Personnellement, j'ai testé sur les entrées que tu as données, le résultat est erroné (liste incomplète), mais les accès mémoires se font apparemment correctement.

Bonne journée !

**floopi51** · 27/02/2013, 16h08

Envoyé par Kirilenko

Bonjour,

Le mieux, pour savoir pourquoi ça plante, c'est d'utiliser un débogueur. Sous Unices, valgrind te permettra de localiser les accès mémoires douteux, tandis qu'avec gdb, tu pourras analyser efficacement le contenu de tes données au fur et à mesure de l'exécution. En l'état, le code source de ta fonction est quand même assez long (m'est avis qu'on peut faire plus simple). Personnellement, j'ai testé sur les entrées que tu as données, le résultat est erroné (liste incomplète), mais les accès mémoires se font apparemment correctement.

Bonne journée !

Merci pour ta réponse.
J'ai refait tourner le code avec une liste courte et j'ai trouvé un premier oubli. J'ai modifié le code dans le post original avec cette correction.

Le problème du debugger c'est que en exécution pas à pas sur une petite liste ça fonctionne mais dès que je passe à un code plus complet, ça plante.

**Médinoc** · 04/03/2013, 14h31

Je pense que tu devrais décomposer ton code un peu plus: Te faire une fonction pour sortir un élément de la liste, et une pour l'insérer. Vérifier comment ces fonctions se comportent au début, au milieu et à la fin de la liste...

Et aussi, mettre la comparaison dans une fonction à part.

**floopi51** · 04/03/2013, 16h26

Envoyé par Médinoc

Je pense que tu devrais décomposer ton code un peu plus: Te faire une fonction pour sortir un élément de la liste, et une pour l'insérer. Vérifier comment ces fonctions se comportent au début, au milieu et à la fin de la liste...

Et aussi, mettre la comparaison dans une fonction à part.

Merci de ta réponse !
J'ai mis ça de côté pour l'instant, je reviendrai sur ce code plus tard.

Tri conditionnel d'une liste chaînée

C

Discussions similaires

Partager

Partager