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

#define LEN 10

typedef char stringa[LEN];

typedef struct el {
	int info1;
	stringa info2;
	struct el *next;
} elem;


elem *CreaElem()
{
	elem *e;
	
	e=malloc(sizeof(elem));
	if(e==NULL) {
		printf("Memoria esaurita\n");
		exit(1);
	} else
		return e;
}

void Appendi(elem *nuovo, elem **testa, elem **coda)
{
	nuovo->next=NULL; /* la coda punta a NULL */
	if(*testa==NULL)
		*testa=nuovo;
	else
		(*coda)->next=nuovo;
	*coda=nuovo;
	return;
}


void StampaLista(elem *l)
{
	printf("---inizio lista---\n");
	for(;l!=NULL;l=l->next)
		printf("Info1: %d\t\tInfo2: %s\n",l->info1,l->info2);
	printf("---fine lista---\n");
	return;
}

elem *LeggiElem(elem *e)
{
	printf("Campo info1 = ");
	scanf("%d",&e->info1);getchar();
	printf("Campo info2 = ");
	gets(e->info2);/*getchar();*/

	return e;
}


elem *CostruisciLista()
/* legge valori e aggiunge in coda */
{	elem *testa,*coda, *nuovo;
	int ch;
	
	testa=NULL;
	coda=NULL;
	
	do {
		printf("Elemento? ");
		ch=getchar();getchar();
		if((ch=='s')||(ch=='S')) {
			nuovo=LeggiElem(CreaElem());
			nuovo->next=NULL;
			if(testa==NULL)
				testa=nuovo;
			else /* nemmeno coda e` NULL */
				coda->next=nuovo;
			coda=nuovo;
		} else
			return testa;
	} while (1);
}


void menu()
{
	char lettera;
	
	printf("\n\n");
	for(lettera='A';lettera<='D';lettera++)
		printf("[%c] Compito %c\n",lettera,lettera);
	printf("[0] Termine\n");
	printf("\tscegli opzione...");
	return;
}

int IniziaPer(char ch, elem *e)
{
	if(e->info2[0]==ch)
		return 1;
	else
		return 0;
}


void CompitoA(elem **L, elem **Lprimo)
{
	elem *e, 	/* scorre L */
		 *coda, /* di Lprimo */
		 *prec; /* precede e */
	
	*Lprimo=NULL;
	coda=NULL;
	
	e=*L;
	while(e!=NULL) {
		if(IniziaPer('a',e)||IniziaPer('A',e)) {
			/* scollega prima e da L */
			if(e==*L)
				*L=e->next;
			else
				prec->next=e->next;
			
			/* collega ora e in coda a Lprimo */
			if(*Lprimo==NULL)
				*Lprimo=e;
			else /* nemmeno coda e` NULL */
				coda->next=e;
			coda=e;
		} else /* aggiorno prec solo se non estraggo niente da L */
			prec=e;
		e=e->next;
		coda->next=NULL;
	}
	
	return;
}

void CompitoB(elem *L1, elem *L2, elem **L)
{
	elem *l,
		 *coda, /* di L */
		 *nuovo,
		 buffer;
	
	*L=NULL;
	coda=NULL;
	
	while((L1!=NULL)&&(L2!=NULL)) {
		if(L1->info1<L2->info1) {
			buffer=*L1;
			L1=L1->next;
		} else {
			if(L1->info1==L2->info1)
				L1=L1->next;
			buffer=*L2;
			L2=L2->next;
		}
		nuovo=CreaElem();
		*nuovo=buffer;
		Appendi(nuovo,L,&coda);
	}
	
	/* almeno uno fra L1 e L2 e` NULL */
	if(L1!=NULL)
		l=L1;
	else if(L2!=NULL)
		l=L2;
	else
		l=NULL;
	while(l!=NULL) {
		nuovo=CreaElem();
		*nuovo=*l;
		Appendi(nuovo,L,&coda);
		l=l->next;
	}
	
	return;
}

elem *CercaPosizione(elem *l, int n)
/* ritorna l'indirizzo dell'elemento che precede la posizione cercata 
   NULL se l'elemento non c'e` o e` il primo */
{
	if(n==1)
		return NULL;
		
	for(;n>2;n--)
		if(l==NULL)
			break;
		else
			l=l->next;
	
	return l;
}

void CompitoC(elem **L1, elem *L2)
{
	elem *morituro, *prec;
	
	for(;L2!=NULL;L2=L2->next) {
		if(L2->info1==1) {/* devo eliminare la testa di L1 */
			morituro=*L1;
			*L1=(*L1)->next;
		} else {
			prec=CercaPosizione(*L1,L2->info1);
			if(prec==NULL)
				continue;
			morituro=prec->next;
			prec->next=morituro->next;
		}
		free(morituro);
	}
	
	return;
}


void CompitoD(elem **L, elem **L1, elem **L2)
{
	elem *e, *coda1, *coda2;
	
	*L1=NULL;
	coda1=NULL;
	
	*L2=NULL;
	coda2=NULL;
	
	while(*L!=NULL) {
		e=*L;
		*L=e->next;
		if((e->info2[0]>='A')&&(e->info2[0]<='Z'))
			Appendi(e,L1,&coda1);
		else
			Appendi(e,L2,&coda2);
	}
	
	return;
}


void DistruggiLista(elem *l)
{
	elem *morituro;
	while(l!=NULL) {
		morituro=l;
		l=l->next;
		free(morituro);
	}
	
	return;
}


main()
{
	char compito;
	
	do {
		menu();
		compito=getchar();getchar();
		switch (compito) {
			case 'a':
			case 'A': 
				{
					elem *L, *Lprimo;
					L=CostruisciLista();
					printf("Lista L:\n");
					StampaLista(L);
					CompitoA(&L,&Lprimo);
					printf("Lista L dopo estrazione:\n");
					StampaLista(L);
					printf("Lista Lprimo:\n");
					StampaLista(Lprimo);
					DistruggiLista(L);
					DistruggiLista(Lprimo);
					break;
				}
			case 'b':
			case 'B':
				{
					elem *L1, *L2, *L;
					/* non c'e` controllo sui valori strettamente crescenti! */
					L1=CostruisciLista();
					printf("Lista L1:\n");
					StampaLista(L1);
					L2=CostruisciLista();
					printf("Lista L2:\n");
					StampaLista(L2);
					CompitoB(L1,L2,&L);
					printf("Lista L (risultato fusione):\n");
					StampaLista(L);
					DistruggiLista(L1);
					DistruggiLista(L2);
					DistruggiLista(L);
					break;
				}
			case 'c':
			case 'C':
				{
					elem *L1, *L2;
					L1=CostruisciLista();
					printf("Lista L1:\n");
					StampaLista(L1);
					L2=CostruisciLista();
					printf("Lista L2:\n");
					StampaLista(L2);
					CompitoC(&L1,L2);
					printf("Lista L1:\n");
					StampaLista(L1);
					DistruggiLista(L1);
					DistruggiLista(L2);
					break;
				}
			case 'd':
			case 'D':
				{
					elem *L1, *L2, *L;
					L=CostruisciLista();
					printf("Lista L:\n");
					StampaLista(L);
					CompitoD(&L,&L1,&L2);
					printf("Lista L1:\n");
					StampaLista(L1);
					printf("Lista L2:\n");
					StampaLista(L2);
					printf("Lista L:\n");
					StampaLista(L);
					DistruggiLista(L1);
					DistruggiLista(L2);
					DistruggiLista(L);
					break;
				}
			case '0':
				break;
			default:
				printf("Opzione illegale\n");
		}
	} while(compito!='0');
	
	return 0;

}