Fondamenti di informatica per Biomedica - 25 maggio 2015 Esempi di domande aperte ------------------------------------------------------------------- 1. Siano dati degli oggetti dalla forma { key: ..., prec: ..., succ: ... } /* DATO */ dove il campo "key" contiene una stringa, e i campi "prec" e "succ" sono utilizzato per collegare gli elementi in una lista bidirezionale Scrivere le seguenti funzioni, indicando prima l'algoritmo seguito e la complessita` di ciascuna di esse. In ogni funzione il parametro di ingresso p e` un riferimento a un qualunque elemento della lista (o null se la lista e` vuota) function conta(p) restituisce il numero di elementi nella lista function elimina(p, k) elimina gli elementi dalla lista con key == k, restituisce un riferimento a un qualunque elemento della lista risultante (o null se la lista e` vuota) function uniq(p) lascia nella lista un solo elemento per ciascun valore di key, restituisce un riferimento a un qualunque elemento della lista risultante function insert(p, x) se x non coincide con nessun valore key contenuto nella lista, aggiunge un nuovo elemento alla lista, altrimenti lascia la lista inalterata. Ritorna un riferimento a un qualunque elemento della lista risultante. ======== Esempi di soluzione ======= Esercizio 1 La funzione conta() ha complessita` O(N). Per realizzarla bisogna scandire la lista nelle due direzioni a partire dall'elemento corrente function conta(p) { var n = 0 /* lunghezza */, cur; if (p == null) { return 0; } for (p = cur.succ; cur != null; cur = cur.succ) { n++; /* conta in avanti */ } for (p = cur.prec; cur != null; cur = cur.prec) { n++; /* conta indietro */ } return n+1; } La funzione elimina richiede allo stesso modo una scansione nelle due direzioni con eliminazione. Per semplificarci la vita (senza modifica della complessita`) possiamo portarci ad una estremita` e fare un solo ciclo di cancellazione. function elimina(p, k) { var cur; if (p == null) { return null; } while (p.prec != null) { p = p.prec; } for (cur = p; cur != null; cur = cur.succ) { if (cur.key == k) { /* elimina */ /* aggancia gli elementi prima e dopo cur */ if (cur.prec != null) { cur.prec.succ = cur.succ; } if (cur.succ != null) { cur.succ.prec = cur.prec; } if (cur == p) { /* eliminiamo il primo elemento */ p = cur.succ; } } } return p; } La funzione uniq(p) richiede la scansione della lista per eliminare duplicati. Per tener traccia degli elementi gia` trovati possiamo usare una mappa con chiave uguale al campo key, in questo modo la complessita` rimane O(N). La lista risultante non sara` mai vuota (salvo che non lo sia in ingresso) function uniq(p) { var m = {}, cur; if (p == null) { return null; } while (p.prec != null) { p = p.prec; } for (cur = p; cur != null; cur = cur.succ { if (m[cur.key] == undefined) { m[cur.key] = true; } else { /* elimina */ /* aggancia gli elementi prima e dopo cur */ if (cur.prec != null) { cur.prec.succ = cur.succ; } if (cur.succ != null) { cur.succ.prec = cur.prec; } } } return p; } Infine la funzione insert richiede di nuovo la scansione completa, dopodiche` l'inserimento puo` avvenire ovunque. function insert(p, k) { if (p == null) { return { key: k, prec: null, succ: null }; while (p.prec != null) { p = p.prec; } for ( ; p.succ != null; i = p.succ) { if (p.key == p) { return p; } /* duplicato */ } /* nessun duplicato, inseriamo dopo p */ p = { key: k, prec: p, succ: null }; p.prec.succ = p; return p; }