Appunti codici per esame orale Fondamenti di informatica

Coding lista in forma sequenziale

Inizializzazione

struct cList {
    float *buffer;
    int size, head, tail;
};
int main() {
    struct cList l;
    init(&l, 8);
}
void init(struct cList *ptr, int size) {
    ptr->head = 0;
    ptr->tail = 0;
    ptr->size = size;
    ptr->buffer = (float *)malloc(size * sizeof(float));
}

Lista Vuota

head == tail

Lista Piena

(tail + 1) % size == head

Inserimento in coda

int main() {
    struct cList l;
    init(&l, 8);
    suf_insert(&l, 3);
}
typedef unsigned short int boolean;
#define TRUE
#define FALSE

boolean suf_insert(struct cList *ptr, float value) {
    if ((ptr->tail+1) % (ptr->size) != ptr->head) {
        ptr->buffer[ptr->tail] = value;
        ptr->tail = (ptr->tail+1) % (ptr->size);
        return TRUE;
    } else {
        return FALSE;
    }
}

Inserimento in testa

boolean pre_insert(struct cList *ptr, float value) {
    if ((ptr->tail+1) % (ptr->size) != ptr->head) {
        ptr->head = (ptr->head + ptr->size -1) % (ptr->size);
        ptr->buffer[ptr->head] = value;
        return TRUE;
    } else {
        return FALSE;
    }
}

Visita

void visit(struct cList *ptr) {
    int count;
    for (count = ptr->head; count != ptr->tail; count = (count+1) % (ptr->size)) {
        printf("%f\n", ptr->buffer[count]);
    }
}

Ricerca

boolean search(struct cList *ptr, float target) {
    int count;
    count = ptr->head;
    while (count != ptr->tail) {
        if (ptr->buffer[count] == target) {
            return TRUE;
        } else {
            count = (count + 1) % (ptr->size);
        }
    }
    return FALSE;
}

Lista in forma collegata con array e indici

Inizializzazione

struct record {
    float value;
    int next;
};
struct list {
    int first, free, size;
    struct record *buffer;
};
int main() {
    struct list l;
    init(&l, 8);
}

void init(struct list *ptr, int size) {
    int count;
    ptr->size = size;
    ptr->first = size;
    ptr->buffer = (struct record *)malloc(size * sizeof(struct record));
    ptr->free = 0;
    for (count = 0; count < size; count++) {
        ptr->buffer[count].next = count + 1;
    }
}

Visita

void visit(struct list *ptr) {
    int count;
    count = ptr->first;
    while (count != ptr->size) {
        printf("of \n %f", ptr->buffer[count].value);
        count = ptr->buffer[count].next;
    }
}

Ricerca

boolean search(struct list *ptr, float target) {
    int count;
    count = ptr->first;
    while (count != ptr->size) {
        if (ptr->buffer[count].value == target) {
            return TRUE;
        } else {
            count = ptr->buffer[count].next;
    }
    return FALSE;
}

Inserimento in testa

boolean pre_insert(struct list *ptr, float value) {
    int moved;
    if (ptr->free != ptr->size) {
        moved = ptr->free;
        ptr->free = ptr->buffer[ptr->free].next;
        ptr->buffer[moved].value = value;
        ptr->buffer[moved].next = ptr->first;
        ptr->first = moved;
        return TRUE;
    } else {
        return FALSE;
    }
}

Inserimento in coda

boolean suf_insert(struct list *ptr, float value) {
    int moved;
    int *positionPtr;
    if (ptr->free != ptr->size) {
        moved = ptr->free;
        ptr->free = ptr->buffer[ptr->free].next;
        ptr->buffer[moved].value = value;
        ptr->buffer[moved].next = ptr->size;
        positionPtr = &(ptr->first);
        while (*positionPtr != ptr->size) {
            positionPtr = &(ptr->buffer[*positionPtr].next);
        }
        *positionPtr = moved;
        return TRUE;
    } else {
        return FALSE;
    }
}

Inserimento in ordine

boolean ord_insert(struct list *ptr, float value) {
    int moved;
    int *positionPtr;
    if (ptr->free != ptr->size) {
        moved = ptr->free;
        ptr->free = ptr->buffer[ptr->free].next;
        positionPtr = &(ptr->first);
        while (*positionPtr != ptr->size && ptr->buffer[*positionPtr].value < value) {
            positionPtr = &(ptr->buffer[*positionPtr].next);
        }
        ptr->buffer[moved].value = value;
        ptr->buffer[moved].next = *positionPtr;
        *positionPtr = moved;
        return TRUE;
    } else {
        return FALSE;
    }
}

Lista in forma collegata con puntatori

Inizializzazione

struct list {
    float value;
    struct list *next_ptr;
};
int main() {
    struct list *headPtr;
    init(&headPtr);
}
void init(struct list **ptrPtr) {
    *ptrPtr = NULL;
}

Visita

void visit(struct list *ptr) {
    while (ptr != NULL) {
        printf("%f\n", ptr->value);
        ptr = ptr->next_ptr;
    }
}

Ricerca

boolean search(struct list *ptr, float target) {
    while (ptr != NULL) {
        if (ptr->value == target) {
            return TRUE;
        } else {
            ptr = ptr->next_ptr;
        }
    }
    return FALSE;
}

Inserimento in testa

void pre_insert(struct list **ptrPtr, float value) {
    struct list *tmpPtr;
    tmpPtr = *ptrPtr;
    *ptrPtr = (struct list *)malloc(sizeof(struct list));
    (*ptrPtr)->value = value;
    (*ptrPtr)->next_ptr = tmpPtr;
}

Inserimento in coda

void suf_insert(struct list **ptrPtr, float value) {
    while (*ptrPtr != NULL) {
        ptrPtr = &((*ptrPtr)->next_ptr);
    }
    pre_insert(ptrPtr, value);
}

Inserimento in ordine

void ord_insert(struct list **ptrPtr, float value) {
    while (*ptrPtr != NULL && (*ptrPtr)->value < value) {
        ptrPtr = &((*ptrPtr)->next_ptr);
    }
    pre_insert(ptrPtr, value);
}

Copia di una lista

void copy(struct list **ptrPtr, struct list *srcPtr) {
    init(ptrPtr);
    while (srcPtr != NULL) {
        suf_insert(ptrPtr, srcPtr->value);
        srcPtr = srcPtr->next_ptr;
    }
}