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


Docente: R. Silvestri
Esercitatore: A. Carosi
Tutor: J. Stefa

Esercitazioni del 27 novembre 2007

Esercizio 1

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

Esercizio 2

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").

Esercizio 3

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.



Soluzioni

Esercizio 2
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;
}

Esercizio 3

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; 
}

-- RiccardoSilvestri - 30 Nov 2007

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2007-12-03 - RiccardoSilvestri






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback