Soluzione dell'Homework 7
Vedi anche
HomeWork7aa0203,
DomandeHomework7aa0203,
RisultatiHomework7aa0203.
Ecco la mia implementazione dell'esercizio 7
/*
Gestione di una lista doppiamente linkata:
add <intero> aggiunge un nodo subito dopo il nodo corrente
del elimina il nodo corrente e setta il nodo corrente al nodo precedente (successivo se non esiste)
print stampa la lista con un asterisco a fianco del nodo corrente
next seleziona il prossimo nodo
prev seleziona il nodo precedente
sort ordina la lista con merge-sort
*/
#include <stdio.h>
/* definizione della struttura del nodo */
typedef
struct nodo {
int valore;
struct nodo * next;
struct nodo * prev;
} Nodo ;
#define MAXLINE 1000
#define TRUE 1
#define FALSE 0
void add(Nodo ** lista, Nodo ** corrente, int valore);
void del(Nodo ** lista, Nodo ** corrente);
void prev(Nodo ** corrente);
void next(Nodo ** corrente);
void print(Nodo * lista, Nodo * corrente);
void sort(Nodo ** lista);
Nodo * merge(Nodo * L1, Nodo * L2);
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
void push(Nodo * elemento, Nodo ** lista);
int main(int argc, char * argv[]) {
char riga[MAXLINE] = { 0 };
int val = 0;
Nodo * lista = NULL;
Nodo * corrente = NULL;
scanf("%[^\n]",riga);
while (0 != strcmp(riga,"fine")) {
if (1 == sscanf(riga,"add%*[ ]%d",&val))
add(&lista, &corrente, val);
else
if (0 == strcmp(riga,"del")) {
if (lista != NULL)
del(&lista, &corrente);
else
printf("vuota\n");
} else
if (0 == strcmp(riga,"next"))
next(&corrente);
else
if (0 == strcmp(riga,"prev"))
prev(&corrente);
else
if (0 == strcmp(riga,"sort")) {
if (lista != NULL)
sort(&lista);
else
printf("vuota\n");
} else
if (0 == strcmp(riga,"print")) {
if (lista != NULL)
print(lista, corrente);
else
printf("vuota\n");
};
scanf("\n%[^\n]",riga);
}
}
/*
Aggiungo un nuovo nodo alla lista
*/
void add(Nodo ** lista, Nodo ** corrente, int valore)
{
/* alloco un nuovo nodo */
Nodo * nuovo = (Nodo*)malloc(sizeof(Nodo));
nuovo->valore = valore;
nuovo->next = NULL;
nuovo->prev = NULL;
/* caso speciale del primo nodo */
if (*lista == NULL) {
*lista = nuovo;
*corrente = nuovo;
return;
}
/* taglia e cuci della lista */
if (*corrente != NULL) {
nuovo->next = (*corrente)->next;
nuovo->prev = *corrente;
(*corrente)->next = nuovo;
if (nuovo->next != NULL)
nuovo->next->prev = nuovo;
}
/* aggiorno il cursore */
*corrente = nuovo;
}
/*
Elimino il nodo corrente
*/
void del(Nodo ** lista, Nodo ** corrente)
{
Nodo * dacancellare = *corrente;
if (*corrente == NULL)
return;
/* il prossimo nodo (se c'e') diventa il nodo corrente */
if ((*corrente)->next != NULL)
*corrente = (*corrente)->next;
else
*corrente = (*corrente)->prev;
/* taglia e cuci della lista */
if (dacancellare->prev != NULL)
dacancellare->prev->next = dacancellare->next;
if (dacancellare->next != NULL)
dacancellare->next->prev = dacancellare->prev;
if (*lista == dacancellare)
*lista = dacancellare->next;
/* libero la memoria */
free(dacancellare);
}
/*
Mi sposto sul nodo precedente
*/
void prev(Nodo ** corrente)
{
if (*corrente == NULL || (*corrente)->prev == NULL)
return;
else
*corrente = (*corrente)->prev;
}
/*
Mi sposto sul nodo successivo
*/
void next(Nodo ** corrente)
{
if (*corrente == NULL || (*corrente)->next == NULL)
return;
else
*corrente = (*corrente)->next;
}
/*
Stampa della lista
*/
void print(Nodo * lista, Nodo * corrente)
{
if (lista == NULL) return;
if (lista == corrente)
printf("%d *\n",lista->valore);
else
printf("%d\n",lista->valore);
print(lista->next,corrente);
}
/*
Mergesort della lista
*/
void sort(Nodo ** lista)
{
Nodo * pari = NULL;
Nodo * dispari = NULL;
/* caso base, 0 o 1 elementi */
if (*lista == NULL) return;
if ((*lista)->next == NULL) return;
/* divido la lista in due gruppi di pari dimensioni */
split(*lista,&pari,&dispari);
/* ordino le due parti */
sort(&pari);
sort(&dispari);
/* ora che sono ordinate le posso fondere */
*lista = merge(pari,dispari);
}
/*
merge distruttivo di due liste doppiamente linkate e ordinate
*/
Nodo * merge(Nodo * L1, Nodo * L2)
{
Nodo * minore = NULL;
/* casi base */
if (L1 == NULL) return L2;
if (L2 == NULL) return L1;
/* trovo il minore */
if (L1->valore < L2->valore) {
minore = L1;
minore->next = merge(minore->next,L2);
} else {
minore = L2;
minore->next = merge(L1,minore->next);
}
/* aggiusto il legame inverso */
if (minore->next != NULL)
minore->next->prev = minore;
/* torno il primo nodo */
return minore;
}
/*
divido una lista in due (elementi in posizione pari/dispari)
*/
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
{
/* caso base: nessun elemento */
if (lista == NULL) {
*pari = NULL;
*dispari = NULL;
return;
}
/* se ci sono almeno 2 elementi ricorro saltando i primi due
ed ottengo il resto della lista separato in pari e dispari */
if (lista->next != NULL)
split(lista->next->next,pari,dispari);
/* aggiungo i due elementi iniziali a pari e dispari */
/* prima il secondo (se c'e') */
if (lista->next != NULL)
push(lista->next,dispari);
/* poi il primo */
push(lista,pari);
}
void push(Nodo * elemento, Nodo ** lista)
{
if (*lista != NULL)
(*lista)->prev = elemento;
elemento->next = *lista;
*lista = elemento;
}
--
AndreaSterbini - 04 Dec 2002
Set ALLOWTOPICCHANGE =
DocentiProg1Group