edutecnica


Esercizio no.9:soluzione

#include<iostream>
using namespace std;

/*definisco la struttura record */
struct T {
      int x;
      T* y;
};
//anche stavolta definiamo i prototipi
void push(T *j);
T *pop(T *j);
// pop restituisce un puntatore all'inizio della coda

void print(T *j);

main() {
T *j;//primo
j->x=0;j->y=NULL;//iniz.lista vuota
int ch;
do{
     ch=0;
     cout<<"1]inserisci\n";
     cout<<"2]togli\n";
     cout<<"0]exit\n";
     cin>>ch;
     switch(ch) {
          case 1:push(j);print(j);break;
          case 2:j=pop(j);print(j);;break;
          case 0:cout<<"EXIT";break;
          default:cout<<"-non valido-";break;
     }//end switch
}while(ch);
}//fine main

void push(T *j){
int n;
cout<<"ins:";
if((cin>>n).good())
     if(!j->x && j->y==NULL)j->x=n;//se è il primo
     else{
          T *p = new T;
          p->x = n;
          p->y = NULL;
          T *q =j;
          while(q->y!=NULL)q= q->y;//scansione
          q->y=p;
     }//fine if(!j->x && j->y==NULL)
}//fine push

/* funzione pop */
T *pop(T *j){
int index,i,n=0; T *p,*q =j;
// acquisisco index che è l'indice dell'elemento che
// voglio togliere. Ricordiamo che il primo elemento
// ha indice 0, il secondo ha indice 1 e così via..
// numero elementi della lista -1;
// in pratica n conta i 'salti' fra un elemento e l'altro.

cout<<"indice:";cin>>index;
while(q->y!=NULL){
     n++;
     q= q->y;
}
// che costituiscono la lista
// ...poi, se la lista non è vuota e se 0<=index<tot

if(!n){
// deve essere index=0, se no, non ha senso.
// j->x=0 (coda vuota) j->x<>0 (un solo elemento in coda)

     if(!index)
          if(j->x!=0)j->x=0;
}else{//se vi è più di un elemento in coda..
     if(index>0 && index<=n){//se non è il 1°elemento
     q =j;
     for(i=0;i<index-1;i++) q = q->y;
     //q punta ora all'elemento precedente da togliere
     p=q->y;
     //p punta ora all'elemento da togliere
     q->y=p->y;
     //l'elemento puntato da q punta all'elemento cui
     //punta l'elemento puntato da p
}//fine if(index>0 && index<=n)

if(!index)j=j->y;
}//fine if(!n)
return j;
}//fine pop

void print(T *j) {
T* p= j;
while(p != NULL) {
     if(p->x)cout<<p->x<<" ";
     p = p->y;
}//fine while
cout<<endl;
}//fine print

Come si nota l'intero programma è invariato rispetto ai casi precedenti, solo la funzione di estrazione (pop) è stata elaborata ulteriormente e non è escluso che possa essere riscritta in forma più semplice. La variabile n, non restituisce il numero di elementi di cui è dotata la coda, ma il numero di 'salti' fra un elemento e l'altro.

Se n=0 vuol dire che o la coda è vuota (j->x=0) e non bisogna fare niente; oppure che la coda è costituita da un solo elemento (j->x!=0) in tal caso se si deve cancellare questo unico elemento deve essere index=0 allora..
if(!index)
     if(j->x!=0) j->x=0;

se n è diverso da 0 e index è uno degli elementi successivi al primo, viene eseguito il task:
     q =j;
     for(i=0;i<index-1;i++) q = q->y;
     //q punta ora all'elemento precedente da togliere
     p=q->y;
     //p punta ora all'elemento da togliere
     q->y=p->y;
     //l'elemento puntato da q punta all'elemento cui
     //punta l'elemento puntato da p


sempre nel caso che si abbia n diverso da 0 se index=0, cioè se si sceglie di eliminare il primo elemento:
if(!index)j=j->y;





edutecnica