Liste doublement chaînée

struct dlist_t{ int data; struct dlist_t* prev; struct dlist_t* next; }; typedef struct dlist_t dl;

Écrire les fonctions suivantes, ainsi qu'un ensemble de tests pertinents //Cherche si la clé k est présente dans // la liste l //Renvoi la cellule de la liste contenant k si k est présent // NULL sinon dl* dl_pres(int k, dl* l); //Ajoute la clé k à la liste // pointée par l //Si *l==NULL, alors une nouvelle liste // cyclique est crée //Renvoi vrai si l'ajout a été effectué // faux sinon bool dl_ajout(int k, dl** l); //Retire la cellule contenant la clé k // dans la liste pointée par l //Si la première cellule est modifiée, ce // changement est répercuté sur l //Renvoi vrai si la cellule a été retirée // faux sinon bool dl_retire(int k, dl** l);

Complexité

Pour chacune des trois fonctions que l'on vient de définir, calculer le nombre d'instructions élémentaires dans le cas défavorable.
Quelles seraient les différences si l'on ajoutait les éléments au début, à la fin, de manière ordonnés?

Indexage

On veut créer un tableau tab de listes doublement chaînées. Les données des cellules seront des chaines de caractères: const char*. Le but étant que la liste pointée par tab['a'] ne contient que des cellules dont le texte commence par un 'a'.

struct il_t{ const char* data; struct il_t* prev; struct il_t* next; }; typedef struct il_t il; il* itab[26];

Écrire les fonctions suivantes, ainsi qu'un ensemble de tests pertinents //Cherche si la clé k est présente dans // l'indexeur l //Renvoi la cellule contenant k si k est présent // NULL sinon il* il_pres(const char* k, il** l); //Ajoute la clé k à la l'indexeur l //Si *l==NULL, alors un nouvel indexeur est créé //Renvoi vrai si l'ajout a été effectué // faux sinon bool il_ajout(const char* k, il*** l); //Retire la cellule contenant la clé k // dans l'indexeur //Renvoi vrai si la cellule a été retirée // faux sinon bool il_retire(const char* k, il** l);

char il_cle(const char* k){ char key = k[0]; if('a' <= key && 'z' >= key){ key = key + ('A' - 'a'); }else if(key>'Z' || key<'A'){ key = 'X'; } return key; }

il* il_pres(const char* k, il** l){ if(k == NULL || l == NULL){ return NULL; } char key = il_cle(k); il* tmp = l[key-'A']; int cmp = 1; while(tmp != NULL && (cmp = strcmp(k,tmp->data)) > 0){ tmp = tmp->next; } if(cmp == 0){ return tmp; }else{ return NULL; } }

bool il_ajout(const char* k, il*** l){ if(k == NULL){ return false; } int key = il_cle(k) - 'A'; if(*l == NULL){ *l = (il**) malloc(sizeof(il*) * 26); if(*l == NULL) return false; memset(*l, 0, 26*sizeof(il*)); } il* n = (il*) malloc(sizeof(struct il_t)); if(n == NULL) return false; n->data = k; n->prev = NULL; n->next = NULL; il** tab = *l; if(tab[key] == NULL){ tab[key] = n; return true; }

if(strcmp(k, tab[key]->data) > 0){ n->next = tab[key]; tab[key]->prev = n; tab[key] = n; return true; } il* tmp = tab[key]; int cmp; while(tmp->next != NULL && (cmp = strcmp(k,tmp->next->data)) < 0){ tmp = tmp->next; } n->next = tmp->next; n->prev = tmp; tmp->next = n; if(n->next != NULL) n->next->prev = n; return true; }

bool il_retire(const char* k, il** l){ il* tmp; if(l == NULL || k == NULL || (tmp = il_pres(k,l)) == NULL){ return false; } if(tmp->prev != NULL) { tmp->prev->next = tmp->next; } else { il** place = l + (il_cle(k) - 'A'); *place = tmp->next; } if(tmp->next != NULL) { tmp->next->prev = tmp->prev; } free(tmp); return true; }