Appunti di Fondamenti di informatica del corso di Ingegneria elettronica

Implementazione della funzione suf_insert()

L'inserimento di un suffisso può richiedere la modifica del puntatore di testa della lista (nel caso in cui la lista sia vuota). Per questo motivo, la funzione suf_insert() deve ricevere l'indirizzo del puntatore stesso.

Rappresentazione sequenziale:

struct list{
    float * buffer;
    int size;
    int head;
    int tail;
};

/* Alloca il buffer su cui sono memorizzati i valori della lista e
 * asserisce l'invariante della rappresentazione:
 * se head==tail la lista è vuota;
 * altrimenti head è l'indice dell'elemento di testa e
 * tail è l'indice della prima posizione successiva all'elemento di coda
 */
void init(struct list * ptr, int size){
    ptr->buffer = (float *) malloc(size*sizeof(float));
    ptr->size = size;
    ptr->head = 0;
    ptr->tail = 0;
}

// Inserimento in coda: aumenta tail
Boolean suf_insert(struct list * ptr, float value){

if((ptr->tail+1)%ptr->size != ptr->head){
    <span>24. ptr->buffer[ptr->tail] = value;</span>
    <span>25. ptr->tail = (ptr->tail+1)%ptr->size;</span>
    <span>26. return TRUE;</span>
}
else
    <span>29. return FALSE;</span>
}

<span>//inserimento in testa: riduce head</span>
Boolean pre_insert(struct list * ptr, float value){
    <span>34. if((ptr->tail+1)%ptr->size != ptr->head){</span>
        <span>35. ptr->head = (ptr->head + ptr->size-1)%ptr->size;</span>
        <span>36. ptr->buffer[ptr->head] = value:</span>
        <span>37. return TRUE;</span>
    }
    else
        <span>40. return FALSE;</span>
}

<span>//visita di stampa</span>
void visit(struct list * ptr){
    <span>45. int index;</span>
    <span>46. for(index=ptr->head; index!=ptr->tail; index=(index+1)%ptr->size){</span>
        printf("<span>%d</span>", ptr->buffer[index]);
    }
}

<span>//ricerca: restituisce TRUE se il valore è contenuto nella lista</span>
Boolean search(struct list * ptr, float value){
    Boolean found = FALSE;
    <span>54. int index=ptr->head;</span>
    <span>55. while(found == FALSE && index!=ptr->tail){</span>
        <span>56. if(ptr->buffer[index]==value)</span>
            found=TRUE;

else59. index = (index+1)%ptr->size);
60. }
61. return found;
62. }

Osservazioni:

Le operazioni di inserimento e cancellazione restituiscono un Booleano per trattare le eccezioni in cui la lista è piena o vuota.

Nell'operazione di inserimento in testa per decrementare head di 1 si usa l'espressione head=(head+size-1)%size che include senza eccezione il caso in cui head vale 0.

Nelle operazioni di visita e di ricerca potrebbe essere passata la lista piuttosto che il suo indirizzo (i.e. il prototipo della funzione potrebbe avere la forma void visit(struct list);) visto che l'operazione non modifica il valore di alcun membro della struttura.

Nella implementazione, si è invece passato l'indirizzo per la ragione dell'efficienza, in modo da ridurre il numero dei parametri copiati sullo stack.

Rappresentazione collegata con array e indice

struct record{
  float value;
  int next;
};

struct list{
  int size;
  int head;
  struct record *array;
};

first: <ul>
    <li>int free;</li>
    <li>int size;</li>
    <li>struct record * buffer;</li>
</ul>

<!-- Inizializzazione - alloca il buffer e asserisce l'invariante della lista: -->
<ul>
    <li>first ha il valore illegale che indica che non ci sono elementi memorizzati;</li>
    <li>free indirizza il primo record;</li>
    <li>tutti i records sono concatenati a partire dal primo per averli disponibili come records liberi.</li>
</ul>

<pre>
19. void init(struct list * ptr, int size){
20. int count;
21.
22. ptr->buffer=(struct record *)malloc(size*sizeof(struct record));
23. ptr->size = size;
24. ptr->first = ptr->size; //first = valore illegale
25. ptr->free = 0; //il primo elemento disponibile è il primo elemento dell'array
26.
27. for(count=0; count<ptr->size; count++) //ogni record viene collegato a quello successivo
28. ptr->buffer[count].next = count+1; //l'ultimo sarà collegato a un valore illegale
29. }
30.
31. //visita
32. void visit(struct list * ptr){
33. int position =
</pre>

ptr->first; // la prima posizione da visitare è il primo elemento
while(position != ptr->size){
    printf("%f", ptr->buffer[position].value);
    position = ptr->buffer[position].next;
}
}

//ricerca
Boolean search(struct list * ptr, float value){
    int position;
    Boolean found;

    position = ptr->first;
    found = FALSE;

    while(position != ptr->size && found == FALSE){
        if(ptr->buffer[position].value == value)
            found == TRUE;
        else
            position = ptr->buffer[position].next;
    }
}

/* Inserimento in testa - se la lista non è vuota, ne sgancia il primo elemento,
lo aggancia in testa alla lista dei valori e ci memorizza il valore da inserire.
In pratica il nuovo valore viene fisicamente inserito alla fine dell'array,
dopodiché esso punterà a quello che era il primo elemento prima del suo inserimento,
alla fine l'indice del primo elemento "first"

assume il valore dell'indice61. dell'elemetno che volevamo inserire in testa, così da renderlo il primo in visita.62. */63. Boolean pre_insert(struct list * ptr, int value){64. int moved;65.

if(ptr->free != ptr->size){ //se free=size allora che la lista è piena67. moved = ptr->free;68. ptr->free = ((ptr->buffer)[ptr->free]).next;69.

ptr->buffer[moved].value = value;71. ptr->buffer[moved].next = ptr->first;72. ptr->first = moved;73.

return TRUE;75. }76. else77. return FALSE;78. }

/* Inserimento in coda - se la lista non è vuota, ne sgancia l'ultimo elemento81. e lo aggancia in coda alla lista dei valori, ci copia sopra il valore da82. inserire e attribuisce il valore illegale al successore. Altrimenti return FALSE83. */84. Boolean suf_insert(struct list * ptr, float value){85. int moved;86. int * position_ptr;87.

if(ptr->free != ptr->size){89. moved = ptr->free;90. ptr->free = ((ptr->buffer)[ptr->free]).next;91.

position_ptr = &ptr->first;
while(*position_ptr != ptr->size)
    position_ptr = &(ptr->buffer)[*position_ptr].next;

*position_ptr = moved; // Non è sbagliato, i puntatori funzionano così. Essendo un
ptr->buffer[moved].value = value; // indirizzo, è come se scrivessimo un valore su
ptr->buffer[moved].next = ptr->size; // tale indirizzo (quindi sul campo .next dell'ultimo)
return TRUE;
}
else
    return FALSE;
}

/* Inserimento ordinato - Assume che la lista sia ordinata.
inserisce il nuovo elemento in ordine, rispetto alla funzione precedente vi è
l'introduzione di una seconda condizione sul while e uno swap nell'inserimento finale
*/
Boolean ord_insert(struct list * ptr, float value){
    int moved;
    int * position_ptr;

    if(ptr->free != ptr->size){
        moved = ptr->free;
        ptr->free = ptr->buffer[ptr->free].next;

        position_ptr = &ptr->first;
        while(*position_ptr != ptr->size && ptr->buffer[*position_ptr].value < value)
            position_ptr = &(ptr->buffer)[*position_ptr].next;

        ptr->buffer[moved].next = *position_ptr;
        *position_ptr = moved;
        return TRUE;
    }
    else
        return FALSE;
}

= &ptr->first;119. while(*position_ptr != ptr->size && ptr->buffer[*position_ptr].value < value)120. position_ptr = &((ptr->buffer[*position_ptr]).next);121. ptr->buffer[moved].value = value;122. ptr->buffer[moved].next = *position_ptr;123. *position_ptr = moved;124. return TRUE;125. }126. else127. return FALSE;128. }Osservazioni:Nel corpo della funzione viene definito un puntatore position_ptr che attraversò il ciclo while viene• manipolato fino ad indirizzare il record sul quale deve essere operato l'inserimento.Se la lista è inizialmente vuota, l’indice del record su cui operare l'inserimento è quello contenuto• nel campo first della lista; se invece la lista è non vuota allora l’indice dei record su cui operarel'inserimento è contenuto nel campo next di uno dei record che stanno nel buffe r.L'uso del puntatore position_ptr permette di unificare i due

struct list{
    • float value;
    • struct list * next_ptr,
    • };
•• //inizializzazione
•7. void init(struct list ** ptrptr){
•8. *ptrptr = NULL;
•9. }
•10.
•11. //visita - si passa l'intera lista
•12. void visit(struct list * ptr){
•13. while(ptr != NULL){
•14. print("%f", ptr->value);
•15. ptr = ptr->next_ptr;
•16. }
•17. }
•18.
•19. /* ricerca - se il valore è contenuto restituisce TRUE e scrive
•20. in *ptrptr il puntatore all'elemento che lo contiene.
•21. restituisce FALSE altrimenti.
•22. */
•23. Boolean search(struct list * ptr, float value, struct list ** ptrptr){
•24. Boolean found;
•25.
•26. found = FALSE;
•27. while(ptr != NULL && found == FALSE){
•28. if(ptr->value == value){
•29. found = TRUE;
•30. *ptrptr = ptr;
•31. }
•32. else
•33. ptr = ptr->next_ptr;
•34. }
•35. return found;
•36. }
•37.
•38. //inserimento in testa
•39. void pre_insert(struct list ** ptrptr, float value){
•40. struct list * tmp_ptr;
•41. tmp_ptr = *ptrptr;
•42.

ptrptr = (struct list *) malloc(sizeof(struct list));
(*ptrptr)->value = value;
(*ptrptr)->next_ptr = tmp_ptr;

/* Preleva il primo elemento - se la lista è vuota restituisce FALSE
altrimenti restituisce TRUE, scrive in *value_ptr il valore
nell'elemento in testa e lo cancella dalla lista. */
Boolean consume_first(struct list ** ptrptr, float * value_ptr){
if(*ptrptr !=NULL){
*value_ptr = (*ptrptr)->value;
*ptrptr = (*ptrptr)->next_ptr;
return TRUE;
}
else
return FALSE;
}

/* inserimento in coda - scorre il doppio puntatore fino a che questo
non punta un puntatore nullo (ovvero il campo .next_ptr dell'ultimo)
ovvero il puntatore su cui applicare malloc.
poi applica un inserimento in testa sulla sottolista puntata dal
doppio puntatore. */
void suf_insert(struct list ** ptrptr, float value){
while(*ptrptr != NULL)
ptrptr = &((*ptrptr)->next_ptr);