Traccia d'esame 3 - Liste

/* Function:  CoppieCorrispondenti
 * Usage: L = CoppieCorrispondenti (L1, L2)
 * Prototype: lista CoppieCorrispondenti(lista L1, lista L2);
 * ----------------------------------------------------------------------
 * Crea una nuova lista L inserendo in essa quei valori che si trovano sia in L1 che in L2
 * nella stessa posizione (NOTA: sarà preferita una soluzione ricorsiva).
 */

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

typedef struct nodo *lista;

typedef struct nodo {
    int val;
    lista next;
} nodo;

lista creaLista (void);
lista inserTesta (lista L, int elem);
void inserCoda (lista L, int elem);
void stampaLista (lista L);
lista ultimoNodo (lista L);
lista CoppieCorrispondentiIterativa(lista L1, lista L2);
lista CoppieCorrispondenti(lista L1, lista L2);

int main (void) {
    lista L1, L2, L;
    printf("Creazione lista 1:\n");
    L1 = creaLista();
    printf("\nCreazione lista 2:\n");
    L2 = creaLista();
    stampaLista(L1);
    stampaLista(L2);
    printf("\nElenco coppie corrispondenti:\n");
    L = CoppieCorrispondenti(L1, L2);
    stampaLista(L);
}

lista creaLista (void) {
    lista L = NULL;
    nodo N;
    int buffer, primo = 1;
    while (1) {
        printf("Inserisci il prossimo valore (0 per terminare): ");
        scanf("%d", &buffer);
        if (buffer == 0) {
            break;
        }
        else {
            if (primo == 1) {
                L = inserTesta (L, buffer);
                primo = 0;
            }
            else {
                inserCoda (L, buffer);
            }
        }
    }
    return L;
}

lista inserTesta (lista L, int elem) {
    nodo *N;
    N = malloc(sizeof(nodo));
    if (N == NULL) {
        printf("Memoria insufficiente\n");
    }
    else {
        N->next = L;
        N->val = elem;
        L = N;
    }
    return L;
}

void inserCoda (lista L, int elem) {
    nodo *N;
    nodo *M;
    N = malloc(sizeof(nodo));
    if (N == NULL) {
        return;
    }
    else {
        M = ultimoNodo (L);
        M->next = N;
        N->val = elem;
        N->next = NULL;
    }
}

lista ultimoNodo (lista L) {
    while (L->next != NULL) {
        L = L->next;
    }
    return L;
}

lista CoppieCorrispondentiIterativa(lista L1, lista L2) {
    lista L = NULL;
    nodo *N;
    int primo = 1;
    while ((L1 != NULL) && (L2 != NULL)) {
        if (L1->val == L2->val) {
            N = malloc(sizeof(nodo));
            if (N == NULL) {
                printf("Memoria esaurita\n");
                return L;
            }
            else {
                if (primo == 1) {
                    N->val = L1->val;
                    N->next = L;
                    L = N;
                    primo = 0;
                }
                else {
                    N->val = L1->val;
                    N->next = NULL;
                    L->next = N;
                }
            }
        }
        L1 = L1->next;
        L2 = L2->next;
    }
    return L;
}

lista CoppieCorrispondenti(lista L1, lista L2) {
    lista L = NULL;
    nodo *N;
    if ((L1 == NULL) || (L2 == NULL)) {
        return L;
    }
    else if (L1->val == L2->val) {
        N = malloc(sizeof(nodo));
        if (N == NULL) {
            printf("Memoria esaurita\n");
            return L;
        }
        else {
            N->val = L1->val;
            N->next = L;
            L = N;
        }
    }
    else {
        return CoppieCorrispondenti(L1->next, L2->next);
    }
    L->next = CoppieCorrispondenti(L1->next, L2->next);
    return L;
}

void stampaLista (lista L) {
    printf("\nI valori inseriti sono:\n");
    while (L != NULL) {
        printf("%d ", L->val);
        L = L->next;
    }
    printf("\n");
}