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
|
---
tags:
- sorbonne
- informatique
semestre: 2
---
On va implémenter un table de hashage et des files
## Files
On utilise par défaut des piles « Last In First Out » (LIFO) dans les listes
|> on ajoute en tête, on retire la tête
Mais comment faire une file ?
|> est un « First In First out »
On a les structs suivantes :
```c title=queue_list.c
typedef struct _cell{
int donnee;
struct _cell *suivant;
} cell;
typedef struct _fifo{
cell *first;
cell *last;
} fifo;
```
On utilise maintenant le type `*fifo` pour représenter une liste
```c title=queue_list.c
fifo *list = NULL; // est une nouvelle liste de type FIFO
```
Bibliothèque minimale pour les listes FIFO contient :
- `new_fifo` -> crée une nouvelle liste FIFO
- `is_empty` -> vérifie si la liste est vide
- `add` -> ajoute un élément à la fin
- `pop` -> retire le premier élément
- `print_fifo` -> affiche la liste
```c title=queue_list.c
fifo *new_fifo(){
fifo *f = malloc(sizeof(fifo));
f->last = NULL;
f->first = NULL;
return f;
}
int is_empty(fifo f){
assert((f.last && f.first) || (!f.last && !f.first)); // permet de faire une vérification et de faire en sorte que le programme s'arrête proprement
return !f.first && !f.last;
}
void add(fifo *f, int val){
if (*f == NULL) return;
cell *c = malloc(sizeof(cell));
c->suivant = NULL;
c->donnee = val;
if (is_empty(*f)) f->first = c;
else f->last->suivant = c;
f->last = c;
}
int pop(fifo *f){
if (!f || is_empty(f)) return 0;
cell *c = f->first;
int d = c->donnee;
f->first = c->suivant;
free(c);
if (!f->first) free(f);
return d;
}
void print_fifo(fifo *f){
if (!f) {
printf("\n");
return;
}
cell *first = f->first;
printf("{");
while (first){
printf("%d, ", first->donnee);
first = first->suivant;
}
printf("}\n");
}
```
## Table de hashage
Comme on ne peut pas représenter toutes les possibilités, on a besoin de trouver une structure de donnée et sa fonction pour les séparer
|> est le principe des maps
Soit $h$ une fonction de hashage de taille $t$
|> les valeurs qu'elles donnent sont dans $[0, t-1]$
Une fonction de hashage peut être la somme de la taille des caractères ASCII modulo la taille
|> $h$ de `"LU1IN002"` vaut donc `76+85+49+73+78+48+48+50 = 507` et si sa taille vaut 500, alors $h$ vaut `7`
|> cette fonction n'est pas très efficace car elle provoque beaucoup de collisions ($h$ de `"LU2IN001"` vaut aussi `7`)
Pour gérer les collisions, on a deux grandes possibilités :
- on prend la case d'après (hashage linéaire)
- on utilise une liste pour représenter les collisions dans la case
|> cette liste devra contenir la clé et la valeur pour bien tout vérifier
Exemple de fonction de hashage
```c title=hash.c
int h(char *key, int t){
int sum = 0;
while (*key != '\0') {
sum += *key;
key = key+1;
}
return sum % t;
}
```
Pour construire le stockage, on fait :
```c title=hash.c
typedef struct _DataHash{
char *key;
int val;
} DataHash;
int main(){
DataHash t_hash[] = cell[TAILLE];
int ki = h("LUIN002", TAILLE);
t_hash[ki].key = "LUIN002";
t_hash[ki].val = 753;
}
```
Fonctions usuelles :
```c title=hash.c
int add_hash(DataHash t_hash[], int size, char *key, int val){
int ki = h(key, size);
int i = ki+1;
while (t_hash[ki] != NULL && i != ki) i = (i+1)%size;
if (!t_hash[ki]) return 0;
t_hash[ki] = DataHash{key, val};
return 1;
}
```
On peut aussi gérer les collisions à l'aide d'une liste
|> on a des pointeurs vers des listes au lieu d'avoir directement la valeur dans `DataHash`
|
