Additions:
// lista senza alcun nodo
// scorro lista in cerca dell'ultimo nodo
// se l'ultimo nodo e' pieno occorre creare ed aggiungere un nuovo nodo alla lista
// ho trovato il nodo che contiene l'i-esimo elemento
// il nodo attuale no contiene l'i-esimo elemento
// vedo quanti elementi contiene e decremento i
// passo al successivo nodo
// ho trovato il nodo che contiene l'i-esimo elemento
// devo ricompattare gli elementi del nodo che sono dopo i
// li sposto di una posizione verso sinistra
// aggiorno contatore elementi in uso
// se il nodo e' vuoto, deve essere eliminato
// il nodo era in testa alla lista
// devo aggiornare il puntatore alla testa della lista
else // aggiorno il puntatore del predecessore
// passo al nodo successivo, decremento i in base a quanti elementi ho già visto
Deletions:
else
Additions:
struct node_t * next; // nodo successivo
int used; // numero di elementi presenti nel nodo
int data[MAX_N_ELEM_NODE]; // elementi
node_t * head; // nodo in testa alla lista
Deletions:
struct node_t * next;
int used;
int data[MAX_N_ELEM_NODE];
node_t * head;
Additions:
%%(c;unrolled_linked_list.c)
#include
#include
#include "unrolled_linked_list.h"
static node_t * new_node() {
node_t * n = malloc(sizeof(node_t));
if (n == NULL) {
printf("Allocation error");
exit(1);
}
n->used = 0;
n->next = NULL;
return n;
}
unrolled_list_t * new_unrolled_list() {
unrolled_list_t * list = malloc(sizeof(unrolled_list_t));
if (list == NULL) {
printf("Invalid list!");
exit(1);
}
list->head = NULL;
return list;
}
void append_elem(unrolled_list_t * list, int x) {
if (list == NULL) {
printf("Invalid list!");
exit(1);
}
node_t * tail = NULL;
if (list->head == NULL) {
tail = new_node();
list->head = tail;
} else {
tail = list->head;
while (tail->next != NULL)
tail = tail->next;
if (tail->used >= MAX_N_ELEM_NODE) {
node_t * n = new_node();
tail->next = n;
tail = n;
}
}
tail->data[tail->used] = x;
tail->used += 1;
}
int get_elem(unrolled_list_t * list, int i) {
if (list == NULL) {
printf("Invalid list!");
exit(1);
}
node_t * n = list->head;
while (n != NULL) {
if (i < n->used)
return n->data[i];
i -= n->used;
n = n->next;
}
printf("Invalid index!");
exit(1);
}
void remove_elem(unrolled_list_t * list, int i) {
if (list == NULL) {
printf("Invalid list!");
exit(1);
}
node_t * n = list->head;
node_t * prev = NULL;
while (n != NULL) {
if (i < n->used) {
for (; i < n->used - 1; i++)
n->data[i] = n->data[i + 1];
n->used -= 1;
if (n->used == 0) {
if (prev == NULL)
list->head = n->next;
else
prev->next = n->next;
free(n);
}
return;
}
i -= n->used;
prev = n;
n = n->next;
}
printf("Invalid index!");
exit(1);
}
int list_size(unrolled_list_t * list) {
int count = 0;
node_t * n = list->head;
while (n != NULL) {
count += n->used;
n = n->next;
}
return count;
}
void delete_unrolled_list(unrolled_list_t * list) {
node_t * n = list->head;
while (n != NULL) {
node_t * current = n;
n = n->next;
free(current);
}
free(list);
}
Additions:
%%(c;unrolled_linked_list.h)
#ifndef UNROLLED_LINKED_LIST_H
#define UNROLLED_LINKED_LIST_H
#define MAX_N_ELEM_NODE 8
typedef struct node_t {
struct node_t * next;
int used;
int data[MAX_N_ELEM_NODE];
} node_t;
typedef struct unrolled_list_t {
node_t * head;
} unrolled_list_t;
unrolled_list_t * new_unrolled_list();
void append_elem(unrolled_list_t * list, int x);
int get_elem(unrolled_list_t * list, int i);
void remove_elem(unrolled_list_t * list, int i);
int list_size(unrolled_list_t * list);
void delete_unrolled_list(unrolled_list_t * list);
#endif
Deletions:
TBA
Additions:
==Esercizio 2==
TBA