Eser041207 < Programmazione1

Tags: view all tags

<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 04 dicembre 2007</h2>

<b>Esercizio 1</b> <div align="justify"> <blockquote> 
Data la struttura: 
<pre><tt> 
struct typedef { 
      int seq; 
      double value; 
} Element; </tt></pre> 
Considerare una struttura dati a coda (<tt>Queue</tt>) di dimensioni limitate (es. <tt>10</tt>) che contiene
elementi di tipo <tt>Element</tt>. 
Il campo <tt>seq</tt> di <tt>Element</tt> contiene un valore sequenziale che viene incrementato 
ogni volta che viene creato un nuovo elemento; il campo <tt>value</tt> contiene un valore reale casuale.
<br>La struttura <tt>Queue</tt> &egrave; caratterizzata dal permettere l'inserimento in fondo e l'eliminazione in testa.
Implementare le due funzioni di <tt>enqueue()</tt>, che permette di inserire un nuovo elemento solo se <tt>Queue</tt> non &egrave; piena, e <tt>dequeue()</tt>, che permette l'estrazione di un elemento da <tt>Queue</tt> solo se questa non &egrave; vuota. <br>
Integrare le funzioni in un programma in cui si eseguono sequenze casuali 
di <tt>enqueue</tt> e <tt>dequeue</tt>.<br>
<strong>Consiglio:</strong> definire le funzioni <tt>enqueue()</tt> e <tt>dequeue()</tt> nel modo seguente:<br>
<tt>void enqueue(Queue **, double);<br>
double dequeue(Queue **);</tt>
</blockquote></div> <br>

<b>Esercizio 2</b>
<div align="justify"> <blockquote>
Date due liste concatenate <tt>A</tt> e <tt>B</tt>, contenenti elementi di tipo <tt>Element</tt> (vedi esercizio precedente), implementare la funzione <tt>merge</tt> che prende in input le due liste e restituisce la lista concatenata ordinata sul campo <tt>seq</tt>, risultante dall'unione delle due stringhe.<br> 
La funzione deve essere implementata in modo che ad ogni sua esecuzione, soltanto un nuovo elemento (non gi&agrave; presente) viene aggiunto nella lista ordinata, mentre i parametri di <tt>merge</tt> sono sempre i puntatori al primo elemento di <tt>A</tt> e <tt>B</tt>.   
</blockquote></div>
<br>

<b>Esercizio 3</b>
<div align="justify"> <blockquote>
Data l'espressione numerica in notazione infissa <tt>Infix = (6 + 2) * 5 - 8 / 4</tt> (con gli operatori al centro 
degli operandi) la corrispondente espressione numerica in notazione postfissa &egrave; <tt>Postfix = 6 2 + 5 * 8 4 / -</tt> (con gli operatori che seguono gli operandi). Scrivere un programma che legge in input da prompt dei comandi un'espressione numerica in notazione infissa con numeri interi ad una cifra, e restituisce la stessa espressione numerica in notazione postfissa.
Il programma deve utilizzare due liste concatenate di caratteri (<tt>char</tt>), una per l'espressione in forma infissa ed una per l'espressione in notazione postfissa, ed inoltre si richiede di utilizzare uno stack degli operandi (<tt>Stack</tt>) in cui &egrave; possibile operare attraverso le funzioni <tt>push()</tt> e <tt>pop()</tt> viste nella scorsa esercitazione.<br>
L'algoritmo per la costruzione della notazione postfissa &egrave; di seguito descritto:<br>
<pre><tt>
1)    Inserire un simbolo '(' in cima allo Stack.
2)    Inserire un simbolo ')' alla fine di Infix.
3)    Finch&egrave; Stack non &egrave vuoto, leggere Infix da sinistra verso destra, e:
3.1)    Se il carattere corrente di Infix &egrave; un numero, copiarlo nell'elemento successivo di Postifx.
3.2)    Se il carattere corrente di Infix &egrave; '(', eseguire un push() in Stack.
3.3)    Se il carattere corrente di Infix &egrave; un operatore:
3.3.1)    Eseguire un pop() degli operatori in Stack finch&egrave; questi hanno precedenza maggiore o uguale 
          all'operatore corrente, e copiarli in Postfix.
3.3.2)    Eseguire un push() dell'operatore corrente in Stack.
3.4)    Se il carattere corrente di Infix &egrave; ')':
3.4.1)    Eseguire un pop() degli operatori in Stack ed inserirli in Postfix, finch&egrave; un '(' 
          resta in cima allo Stack.
	  Eseguire un pop() e scartare il simbolo '(' dallo Stack.
</tt></pre>
La lista concatenata <tt>Postfix</tt> cresce mano mano che vengono letti gli operandi in <tt>Infix</tt> e gli operatori vengono rimossi dallo stack.<br>
Supponiamo inoltre che gli operatori possibili siano: <tt>+</tt>, <tt>-</tt>, <tt>*</tt> e <tt>/</tt>, e che le precedenze siano rispettivamente <tt>1</tt>, <tt>1</tt>, <tt>2</tt> e <tt>2</tt>.
<br><br>
<strong>Nota:</strong> riassumendo quanto visto precedentemente, lo <tt>Stack</tt> pu&ograve; essere implementato attraverso la lista concatenata seguente:
<pre><tt>
typedef struct stackNode {
  char data;
  struct stackNode* next;
} Stack;
</tt></pre>
Mentre le operazioni di <tt>push()</tt> e di <tt>pop()</tt>, permettono rispettivamente di inserire un elemento in cima, e di eliminare l'elemento dalla cima di una lista concatenata.
<br><br>
<strong>Consiglio:</strong> utilizzare le funzioni cos&igrave; definite:
<pre><tt>
void push(Stack **head, char s);
char pop(Stack **head);
</tt></pre>
</blockquote></div>


-- Users.RiccardoSilvestri - 13 Dec 2007