Tri conditionnel d'une liste chaînée
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. :cry:
Si quelqu'un a une idée, MERCI !!!!
Voici mon code :
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
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;
} |
