[C] Piccolo esercizio sulle liste

[jarrod]

Questa è la consegna:
Scrivere un programma in C che inserisce da stdin numeri float (con terminazione di input al primo numero negativo) e crea una lista che ripropone esattamente l’ordine di inserimento. Successivamente chiedere all’utente di inserire altri due valori float A e B, controllando che B sia strettamente maggiore di A e che siano entrambi positivi, scorrere la lista verificando che ciascun valore sia maggiore o uguale ad A e che la somma di due valori consecutivi sia sempre strettamente
minore di B, mostrando a video il risultato della verifica. Ad esempio per A = 2.3 e B = 100.24 un vettore valido è:
51.3 -> 44.2 -> 36.1 -> 55.7 -> 3.2 -> 96.1 -> 2.3 -> 22.2 -> 77.8 -> 2.7 -> 22.2

Questo è l'intero esercizio svolto dal prof:

#define _CRT_SECURE_NO_WARNINGS

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct item
{
	float element;
	struct item *next;
} node;
typedef node *list;

list emptyList()
{
	return NULL;
}

bool empty(list l)
{
	return l == NULL;		//se l è NULL ritorna 1
}

list tail(list l)
{
	if (l == emptyList()){
		abort();
	}
	return l->next;
}

list consList(float element, list next)
{
	list l = malloc(sizeof(node));
	l->element = element;
	l->next = next;
	return l;
}

list insertTail(float element, list l)
{
	if (empty(l))
	{
		return consList(element, emptyList());
	}
	list root = l;
	list prev = l;
	while (!empty(l))
	{
		prev = l;
		l = tail(l);
	}
	prev->next = consList(element, emptyList());
	return root;
}

bool check(float A, float B, list l)
{
	if (B <= A) return false;
	if (A < 0 || B < 0) return false;
	float sum = 0;
	while (!empty(l))
	{
		if (A > l->element)
			return false;
		if (sum + l->element >= B)
			return false;
		sum = l->element;
		l = tail(l);
	}
	return true;
}

int main()
{
	float num;
	list myList = emptyList();
	do
	{
		printf("Inserisci un numero da mettere in lista: ");
		scanf("%f", &num);
		if (num >= 0)
			myList = insertTail(num, myList);
	} while (num >= 0);

	float A, B;
	printf("Inserisci A (scorrere la lista verificando che ciascun valore sia maggiore o uguale ad A): ");
	scanf("%f", &A);
	printf("Inserisci A (la somma di due valori consecutivi sia sempre strettamente minore di B): ");
	scanf("%f", &B);
	bool ris = check(A, B, myList);
	if (ris)
	{
		printf("Lista corretta.");
	}
	else
	{
		printf("List errata.");
	}
}

C'è un piccolo passaggio in cui non capisco il meccanismo che c'è dietro.. si trova esattamente qui

list insertTail(float element, list l)
{
	if (empty(l))
	{
		return consList(element, emptyList());
	}
	list root = l;
	list prev = l;
	while (!empty(l))
	{
		prev = l;
		l = tail(l);
	}
	prev->next = consList(element, emptyList());
	return root;
}

Qualcuno mi spiega che cosa succede, perchè ci ho guardato un sacco di volte con il debug ma non capisco esattamente che cosa fa? Inoltre non capisco che cosa intende per 'prev'..

[Super Squirrel]

Con prev credo intenda previous ossia il nodo precedente.
Per quanto riguarda la funzione insertTail, premesso che l'argomento l passato alla funzione è un puntatore a nodo che punta alla testa della lista, non fa altro che aggiungere in coda alla lista un nuovo nodo (che ha come membri element=element e next=NULL) per poi ritornare la testa della lista. Se l punta a NULL, ossia la lista è vuota, allora torna direttamente il puntatore al nuovo nodo. In caso di lista non vuota, invece, una volta salvato l'indirizzo della testa della lista in root, utilizza i puntatori l e prev per determinare rispettivamente la fine della lista (NULL) e la coda della lista (l'indirizzo dell'ultimo nodo). Per come è implementata la funzione sono infatti necessari due puntatori visto che alla fine del ciclo while l punta a NULL e quindi senza la variabile puntatore prev l'informazione sulla coda andrebbe persa.

Premesso che io avrei impostato il programma diversamente (per esempio al posto di tutte quelle funzioni dai nomi strani avrei fatto un'unica funzione di tipo void che aggiunge un elemento in coda alla lista), per evitare controlli e assegnazioni superflue modificherei la funzione insertTail così:

list insertTail(float element, list l)
{
    if(empty(l))
    {
        return consList(element, emptyList());
    }
    list root = l;
    list prev;
    do
    {
        prev = l;
        l = tail(l);
    }
    while(!empty(l));
    prev->next = consList(element, emptyList());
    return root;
}

Nella funzione check, visto che A e B devono essere positivi, nella condizione del secondo if dovrebbe essere usato il simbolo <=. Inoltre, poiché abbiamo già appurato nel primo if che B è strettamente maggiore di A, nel secondo if basta controllare solo A se è positivo.

[jarrod]

Grazie mille, sei stato chiarissimo!