Esercizio 9     

Scrivi un programma che memorizzi una lista a puntatori di interi, dotata delle tre funzioni push, pop e print (per stampare) che permetta di togliere un elemento basandosi su un indice e assumendo che il primo elemento abbia indice 0.

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