Eser271107 < Programmazione1

<h1>Programmazione 1 <small>&nbsp; &nbsp;(P-Z) a.a. 2007-08</small></h1>
<br>
<big>Docente: R. Silvestri<br>
Esercitatore: A. Carosi<br>
Tutor: J. Stefa</big>
<br>

<h2>Esercitazioni del 27 novembre 2007</h2>

<b>Esercizio 1</b>
<div align="justify"> <blockquote>
Corrisponde all'esercizio <tt>3</tt> del 20/11/2007. 
</blockquote></div>

<b>Esercizio 2</b>
<div align="justify"> <blockquote>
Data la struttura:
</blockquote></div>
<div align="justify"> <blockquote><tt>
typedef struct {<br>
&nbsp;&nbsp;int pos;<br>
&nbsp;&nbsp;char *str;<br>
} Element;<br>
</tt></blockquote></div>
<div align="justify"> <blockquote>
Implementare le funzioni di <tt>push</tt> e <tt>pop</tt> di una lista
concatenata con elementi di tipo <tt>Element</tt>. La funzione
<tt>push</tt> inserisce un nuovo elemento in testa alla lista, mentre
la funzione <tt>pop</tt> estrae ed elimina l'elemento in testa alla
lista. Il campo <tt>pos</tt> contiene la posizione dell'elemento nella
lista (il primo elemento &egrave; in posizione <tt>1</tt>). Fornire
una funzione di stampa della lista concatenata, stampa dell'elemento in una
certa posizione (se presente) e di cancellazione della lista intera.<br>
Integrare in fine le funzioni in un programma che fornisce un
men&ugrave; all'utente per operare sulla lista concatenata (le voci
del men&ugrave; possono essere: "inserisci stringa (push)",
"stampa lista", "pop" e "reset").
</blockquote></div>

<b>Esercizio 3</b>
<div align="justify"> <blockquote>
Data la struttura:
</blockquote></div>
<div align="justify"> <blockquote><tt>
typedef struct {<br>
&nbsp;&nbsp;char *stringa;<br>
} Element;<br>
</tt></blockquote></div>
<div align="justify"> <blockquote>
Implementare la funzione di inserimento di una struttura di tipo <tt>Element</tt> in una
lista concatenata ordinata secondo l'ordine
lessicografico del campo <tt>stringa</tt>. L'ordine lessicografico, cos&igrave; definito: la stringa <tt>str1</tt> precede ls stringa <tt>str2</tt> se e solo se esiste un
indice <tt>i</tt> tale che :<br>
</tt></blockquote></div>
<div align="justify"> <blockquote>
1) <tt>str1[j] == str2[j]</tt>, per <tt>j < i</tt><br>
2) <tt>str1[i] < str2[i]</tt><br>
</tt></blockquote></div>
<div align="justify"> <blockquote>
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.
</blockquote></div>
<br>
<br>
<br>
<h3>Soluzioni</h3>
<b>Esercizio 2</b>
<div align="justify"><blockquote>
Valutare le seguenti funzioni :<br>
<pre><tt>
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;
}
</pre></tt></blockquote></div>

<b>Esercizio 3</b>
<div align="justify"><blockquote>
Valutare la seguente funzione di inserimento :<br>
<pre><tt>
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; 
}
</pre></tt></blockquote></div>

-- Users.RiccardoSilvestri - 30 Nov 2007
This topic: Programmazione1 > WebHome > Prog1PZ > DiarioPZ0708 > Eser271107
Topic revision: r2 - 2007-12-03 - RiccardoSilvestri