L9 Programmazione dei Calcolatori (C Linked Lists)

Academic Year: 2022-2023 Class: Programmazione Calcolatori (Class) Created: March 12, 2023 Tag: C MOC Type: Lecture

---

Info utili precedenti: L8 Programmazione dei Calcolatori (C Linked Lists)

Node Search

node *search(linked_list L, int pos){
	node *p = L.a;
	int i = 0;
	
	while( p != NULL && i < pos ){ // se p è NULL, la lista è finita
		p = p->next;
		i++;
	}
 
return p;
}

Costo: O(n), lineare dipende dall’input pos

inserire nuovo elemento in una lista frammentata

• cambiare puntatore next con posizione del nuovo elemento successivo
• creare nuovo elemento con head e nest
• cambiare head dell’ elemento d’eccessivo al nuovo elemento inserito oss: questo meccanismo funziona per l inserimento di un nuovo elemento in tutte le posizioni tranne che nella prima

linked_list insert(linked_list L, int pos, float e){
	
	if(pos > 0 && pos <= L.size){
		node *p = malloc(sizeof(node));
		node *q = search(L, pos-1);
		
		p->data = e;
		p->next = q->next;
		q->next = p;
		L.size++;
		
	} else if(pos == 0) {
		L = in0(L, e);
	}
	return L
}

Costo: O(n), dipende dalla funzione search (lineare) il resto ha tutto costo costante

inserimento elemento in posizione 0

linked_list in0(linked_list L, float e){
	node *p = malloc(sizeof(node));
	
	p->data = e;
	p->next = NULL;
	L.a = p;
	L.size++;
	
	return L;
// crea nodo con valore e e lo inserisce in testa alla lista
}

Cancellazione di un elemnto

Cancella l’elemento in una specifica posizione di una lista e restituisce la nuova lista

Cancellazione di elemento iniziale

Cancellazione di una lista con elemento stringa

Int main input

• l’int main può prendere come input … es: