Programmazione 1    (P-Z) a.a. 2007-08

Corrisponde all'esercizio 3 del 20/11/2007.

Data la struttura:

typedef struct {
  int pos;
  char *str;
} Element;

Implementare le funzioni di push e pop di una lista concatenata con elementi di tipo Element. La funzione push inserisce un nuovo elemento in testa alla lista, mentre la funzione pop estrae ed elimina l'elemento in testa alla lista. Il campo pos contiene la posizione dell'elemento nella lista (il primo elemento è in posizione 1). Fornire una funzione di stampa della lista concatenata, stampa dell'elemento in una certa posizione (se presente) e di cancellazione della lista intera.
Integrare in fine le funzioni in un programma che fornisce un menù all'utente per operare sulla lista concatenata (le voci del menù possono essere: "inserisci stringa (push)", "stampa lista", "pop" e "reset").

Data la struttura:

typedef struct {
  char *stringa;
} Element;

Implementare la funzione di inserimento di una struttura di tipo Element in una lista concatenata ordinata secondo l'ordine lessicografico del campo stringa. L'ordine lessicografico, così definito: la stringa str1 precede ls stringa str2 se e solo se esiste un indice i tale che :

1) str1[j] == str2[j], per j < i
2) str1[i] < str2[i]

Fornire una funzione di stampa della lista concatenata ordinata ed integrare le funzioni implementate in un programma che permette di inserire le stringhe da prompt dei comandi.

Valutare le seguenti funzioni :

void printStack (Stack *s) {
  while (s) {
    printf ("%d) %s\n", (s->e)->pos, (s->e)->str);
    s = s->next;
  }
}

void push(Stack **tmp, char *s) {
  
  Element* etmp = (Element *)malloc(sizeof(Element));
  if (!etmp) exit(1);
  etmp->pos = 1;
  etmp->str = s;

  Stack* ltmp = (Stack *)malloc(sizeof(Stack));
  if (!ltmp) exit(1);
  ltmp->next = NULL;
  ltmp->e = etmp;
  
  // mette in testa alla lista
  if ((*tmp)) ltmp->next = (*tmp); 
  (*tmp) = ltmp;

  // aggiorna il campo "pos" dei restanti elementi
  Stack *tt = ltmp->next;
  while(tt) {
    (tt->e)->pos++;
    tt = tt->next;
  }
}

Element* pop(Stack **tmp) {
  
  Element* etmp = (*tmp)->e;
  if ((*tmp)->next) (*tmp) = (*tmp)->next;
  else (*tmp) = NULL;

  // aggiorna il campo "pos" dei restanti elementi
  Stack *tt = (*tmp);
  while(tt) {
    (tt->e)->pos--;
    tt = tt->next;
  }

  return etmp;
}

Valutare la seguente funzione di inserimento :

void insert(List **l, const char *s) {
  
  Element* enew = (Element *)malloc(sizeof(Element));
  if (!enew) exit(1);
  enew->stringa = (char *)s;

  List* lnew = (List *)malloc(sizeof(List));
  if (!lnew) exit(1);
  lnew->e = enew;
  lnew->next = NULL;

  if (!(*l)) {
    (*l) = lnew;
    return;
  }

  List *ltmp = (*l);
  while (ltmp) {
    if (strcmp((ltmp->e)->stringa, s) >= 0) {
      lnew->next = (*l);
      (*l) = lnew;
      return;
    }
    ltmp = (*l)->next;
    l = &((*l)->next);
  }

  (*l) = lnew; 
}