Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - [Esercizio sulle liste] Puntatori di puntatori
Forum - C/C++ - [Esercizio sulle liste] Puntatori di puntatori

Avatar
WinstonS (Normal User)
Newbie


Messaggi: 6
Iscritto: 12/12/2010

Segnala al moderatore
Postato alle 15:50
Domenica, 12/12/2010
Ciao a tutti, starei facendo questo esercizio:
Testo quotato

A Elettrolandia si va a votare per eleggere il nuovo Governatore. Si presentano quattro candidati: 1,2,3,4.
Le schede votate sono raccolte in una lista, in cui ogni elemento memorizza il numero del candidato votato e un'informazione
sulla validità della scheda (valida o nulla). Si deve procedere allo spoglio.
     (i)   Definire gli opportuni tipi di dato per rappresentare la lista delle schede votate
     (ii)  Progettare una funzione ricorsiva che, presa in input la lista delle schede votate, e un numero corrispondente
            ad uno dei candidati, proceda al conteggio dei voti validi relativi a quel candidato
     (iii) Progettare una funzione che, presa in input la lista delle schede votate, e il numero corrispondente ad uno dei candidati,
            elimini dalla lista iniziale le schede votate non valide di quel
            candidato e restituisca il numero di cancellazioni effettuate



Ora credo di aver risolto tutto, ma se nella funzione del punto iii (EliminaSchedeNulle()) uso f (parametro) al posto di first (puntatore dichiarato globalmente per comodità) nel momento in cui vado a stampare la lista ho elementi in più che non dovrebbero esserci (se ho capito bene perchè first viene passato alla funzione per valore);
Quindi sostanzialmente la domanda è questa: cosa devo modificare nel codice per fare in modo che quando cambio il valore di f (cioè l'indirizzo dell'inizio della lista) nella funzione, venga cambiato anche il valore di first? Come posso, cioè, passare per riferimento first a EliminaSchedeNulle()?

Ecco il link al codice: http://pastebin.com/vJLEgzb1

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef enum {false, true} boolean;
  4.  
  5.         struct nodo {
  6.                 int candidato;
  7.                 boolean valida;
  8.                 struct nodo *next;
  9.         };
  10.  
  11. typedef struct nodo scheda;
  12. scheda *first; //puntatore al primo elemento della lista
  13. /* prototipi delle funzioni */
  14. void InizializzaLista();
  15. void AggiungiScheda(int candidato, boolean validita);
  16. void ScriviSchede();
  17. int ConteggioVotiValidi(int candidato, scheda* f);
  18. int EliminaSchedeNulle(int candidato, scheda *f);
  19. /* ## */
  20.  
  21. int main()
  22. {
  23.  
  24.                 //Variabili varie:
  25.                 int scelta; //Per la scelta del menu
  26.                 int candidato; //tiene un intero 1<=n<=4 riferito al candidato n
  27.                 int validita;//validità della scheda
  28.                 int jolly;
  29.                 int termina=0;
  30.         InizializzaLista();
  31.         while(termina==0){
  32.         //Presento un menu di scelta
  33.                 printf("\n\n\nElezioni del nuovo Governatore di Elettolandia\n I candidati sono: '1', '2', '3', '4'\n");
  34.                 printf("Scegli fra le seguenti opzioni:\n\
  35.                         1) Aggiungi scheda\n\
  36.                         2) Vedi schede\n\
  37.                         3) Svuota Lista Schede\n\
  38.                         4) Conteggia Voti validi per un candidato\n\
  39.                         5) Elimina schede nulle per un candidato\n\
  40.                         6) Termina\n");
  41.  
  42.                 //Faccio in modo che l'utente scelga un n 1<=n<=6 prima di continuare l'esecuzione
  43.                 do {
  44.                 printf("\nDigita la tua scelta: ");scanf("%d",&scelta);
  45.                 } while (scelta < 1 || scelta >6);
  46.  
  47.                 switch (scelta) {
  48.                         case 1: //scelta==1
  49.                                 printf("\nVoto per il candidato numero: ");scanf("%d",&candidato);
  50.                                 printf("\nScrivi 0 se la scheda è nulla, 1 se valida: ");scanf("%d",&validita);
  51.                                 AggiungiScheda(candidato, validita);
  52.                                 printf("Aggiunto un nuovo voto %s per il candidato %d\n\
  53. Premere invio per continuare...", \
  54.                                 first->valida?("valido"):("NON valido"), first->candidato);
  55.                                 getchar();
  56.                                 getchar();
  57.                                 break;
  58.                         case 2:
  59.                                 printf("** Inizio della lista **\n\
  60. Indirizzo - Candidato - Validità - Successiva\n");
  61.                                 ScriviSchede();
  62.                                 printf("** Fine della lista **\n\
  63. Premere invio per continuare...");getchar();getchar();
  64.                                 break;
  65.                         case 3:
  66.                                 InizializzaLista();
  67.                                 printf("Lista svuotata!\nPremere un tasto per continuare");getchar();getchar();
  68.                                 break;
  69.                         case 4:
  70.                                 printf("\nInserire il numero del candidato di cui conteggiare i voti validi:");scanf("%d",&candidato);
  71.                                 jolly=ConteggioVotiValidi(candidato,first);
  72.                                 printf("\nI voti validi per il candidato %d sono: %d",candidato,jolly);
  73.                                 printf("\nPremi invio per continuare...");getchar();getchar();
  74.                                 break;
  75.                         case 5:
  76.                                 printf("\nInserire il numero del candidato di cui eliminare i voti nulli:");scanf("%d",&candidato);
  77.                                 jolly=EliminaSchedeNulle(candidato,first);
  78.                                 printf("\nEliminate %d schede",jolly);
  79.                                 printf("\nPremi invio per continuare...");getchar();getchar();
  80.                                 break; 
  81.                         case 6:
  82.                                 termina=1;
  83.                 }
  84.         }
  85.         return (0);
  86. }
  87. //Inizializzazione della lista: si libera la memoria sfruttata precedentemente per la lista
  88. void InizializzaLista()
  89. {
  90.         scheda *temp;
  91.         while (first!=NULL)
  92.         {
  93.                 temp = first;
  94.                 first = first->next;
  95.                 free(temp);
  96.         }
  97.         //first=(scheda*) malloc(sizeof(scheda));
  98.         return;
  99. }
  100.  
  101. //Funzione per l'aggiunta di schede alla lista
  102. void AggiungiScheda(int candidato, boolean validita)
  103. {
  104.         scheda *nuova;
  105.         nuova = (scheda*) malloc(sizeof(scheda));
  106.         nuova->candidato=candidato;
  107.         nuova->valida=validita;
  108.         nuova->next=first;
  109.         first=nuova;
  110.         return;
  111. }
  112. //Stampa la lista
  113. void ScriviSchede() {
  114.         scheda *temp=first;
  115.         while (temp!=NULL)
  116.         {
  117.                 printf("%p           %d    -    %d   %p \n",temp,temp->candidato,temp->valida,temp->next);
  118.                 temp=temp->next;
  119.         }
  120. }
  121.  
  122. //Punto (ii)
  123. int ConteggioVotiValidi (int candidato, scheda* f) //sto passando come parametro la lista solo perchè è richiesto esplicitamente nell'esercizio, ne farei a meno sfruttando il puntatore first che è dichiarato globalmente
  124. {
  125.         if (f==NULL) return 0; //controlla che la lista non sia vuota
  126.         if (f->candidato==candidato && f->valida==true)
  127.                         return 1+ConteggioVotiValidi(candidato, f->next);              
  128.         else
  129.                         return 0+ConteggioVotiValidi(candidato,f->next);
  130. }
  131. //Fine Punto (ii)
  132.  
  133. // punto (iii)
  134. int EliminaSchedeNulle(int candidato, scheda *f) //vedi commento a riga 132
  135. {
  136.  
  137.         if (first == NULL) return 0; //Se la lista è vuota esce dalla funzione tornando 0
  138.         if (first->next==NULL && first->candidato==candidato && first->valida==false) {InizializzaLista(); return 1;} //Nel caso in cui ci sia un solo elemento nella lista e questo elemento va eliminato, è necessario chiamare inizializzalista(); torna 1 perchè è coem fare una cancellazione
  139.         int cancellazioni=0;
  140.         scheda *temp, *prec;
  141.         //Il primo ciclo fa in modo che f non sia un voto nullo al candidato passato come parametro
  142.         while (first->candidato==candidato && first->valida==false) { //fin quando la prima scheda è un voto nullo a candidato
  143.                 temp=first->next;  //il primo elemento diviene quello successivo
  144.                 free(first); //libero la memoria del vecchio primo elemento
  145.                 first=temp;
  146.                 cancellazioni++; //incremento il numero di cancellazioni
  147.         }
  148.         prec=first; //ho gia verificato che f non è una scheda nulla a candidato
  149.         temp=prec->next; //controllo della scheda successiva alla prima "rimasta"
  150.         while(temp!=NULL) {
  151.                 if (temp->candidato==candidato && temp->valida==false) {
  152.                         prec->next=temp->next; //Se la scheda puntata da temp non è valida allora la scheda precedente a temp (con prec->next=temp) dovrà puntare alla scheda successiva a temp (temp->next)
  153.                         free(temp); //Libero la memoria
  154.                         cancellazioni++; //incremento il numero di cancellazioni
  155.                         temp=prec->next;
  156.                 } else
  157.                 {
  158.                         prec=temp; //incremento prec
  159.                         temp=temp->next; //incremento temp
  160.                 }
  161.         };
  162.         return cancellazioni; //torna in output il numero delle cancellazioni effettuate
  163. }
  164. // punto (iii)


Ultima modifica effettuata da WinstonS il 12/12/2010 alle 22:49
PM
Avatar
Alex (Ex-Member)
Expert


Messaggi: 441
Iscritto: 15/08/2005

Up
0
Down
V
Segnala al moderatore
Postato alle 18:17
Domenica, 12/12/2010
per passare un valore per riferimento invece che per valore usa un puntatore a un puntatore...così puoi modificare il puntatore facendolo puntare da qualche altra parte...


Alex=)
PM
Avatar
WinstonS (Normal User)
Newbie


Messaggi: 6
Iscritto: 12/12/2010

Up
0
Down
V
Segnala al moderatore
Postato alle 21:12
Domenica, 12/12/2010
Mai usati puntatori a puntatori; vediamo
il prototipo della funzione di questo tipo?
int EliminaSchedeNulle(int candidato, scheda **f)

e la chiamata alla funzione così? EliminaSchedeNulle(candidato,&first)[\code], dove candidato è un int e first è dichiarato come scheda *first[\code]...


E fin qui il programma va ma poi come opero all'interno di EliminaSchedeNulle?? *f->, *f., **f->, **f., (per fare un esempio di cose che non funzionano)?


PM
Avatar
WinstonS (Normal User)
Newbie


Messaggi: 6
Iscritto: 12/12/2010

Up
0
Down
V
Segnala al moderatore
Postato alle 22:46
Domenica, 12/12/2010
Ecco così sembra andare (mi suggeriva lumo_e che si potrebbe semplificare la funzione EliminaSchedeNulle(...) ad un solo while, ma non sono arrivato a come fare).
Lo metto qui così che il post possa servire a qualcun altro.

Codice sorgente - presumibilmente C++

  1. /*
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. typedef enum {false, true} boolean;
  5. struct nodo {
  6.         int candidato;
  7.         boolean valida;
  8.         struct nodo *next;
  9. }; typedef struct nodo scheda;
  10.  
  11. /* prototipi delle funzioni */
  12. void InizializzaLista(scheda** f);
  13. void AggiungiScheda(int candidato, boolean validita, scheda** f);
  14. void ScriviSchede(scheda *f);
  15. int ConteggioVotiValidi(int candidato, scheda* f);
  16. int EliminaSchedeNulle(int candidato, scheda** f);
  17.  
  18. int main()
  19. {
  20.         //Variabili varie:
  21.         int scelta; //Per la scelta del menu
  22.         int candidato; //tiene un intero 1<=n<=4 riferito al candidato n
  23.         int validita;//validità della scheda
  24.         int jolly;
  25.         int termina=0;
  26.         scheda *first; //puntatore al primo elemento della lista
  27.         InizializzaLista(&first);
  28.         while(termina==0){
  29.         //Presento un menu di scelta
  30.                 printf("\n\n\nElezioni del nuovo Governatore di Elettolandia\n I candidati sono: '1', '2', '3', '4'\n");
  31.                 printf("Scegli fra le seguenti opzioni:\n\
  32.                         1) Aggiungi scheda\n\
  33.                         2) Vedi schede\n\
  34.                         3) Svuota Lista Schede\n\
  35.                         4) Conteggia Voti validi per un candidato\n\
  36.                         5) Elimina schede nulle per un candidato\n\
  37.                         6) Termina\n");
  38.  
  39.                 //Faccio in modo che l'utente scelga un n 1<=n<=6 prima di continuare l'esecuzione
  40.                 do {
  41.                 printf("\nDigita la tua scelta: ");scanf("%d",&scelta);
  42.                 } while (scelta < 1 || scelta >6);
  43.  
  44.                 switch (scelta) {
  45.                         case 1:
  46.                                 printf("\nVoto per il candidato numero: ");scanf("%d",&candidato);
  47.                                 printf("\nScrivi 0 se la scheda è nulla, 1 se valida: ");scanf("%d",&validita);
  48.                                 AggiungiScheda(candidato, validita, &first);
  49.                                 printf("Aggiunto un nuovo voto %s per il candidato %d\n\
  50. Premere invio per continuare...", \
  51.                                 first->valida?("valido"):("NON valido"), first->candidato);
  52.                                 getchar();
  53.                                 getchar();
  54.                                 break;
  55.                         case 2:
  56.                                 printf("** Inizio della lista **\n\
  57. Indirizzo - Candidato - Validità - Successiva\n");
  58.                                 ScriviSchede(first);
  59.                                 printf("** Fine della lista **\n\
  60. Premere invio per continuare...");getchar();getchar();
  61.                                 break;
  62.                         case 3:
  63.                                 InizializzaLista(&first);
  64.                                 printf("Lista svuotata!\nPremere un tasto per continuare");getchar();getchar();
  65.                                 break;
  66.                         case 4:
  67.                                 printf("\nInserire il numero del candidato di cui conteggiare i voti validi:");scanf("%d",&candidato);
  68.                                 jolly=ConteggioVotiValidi(candidato,first);
  69.                                 printf("\nI voti validi per il candidato %d sono: %d",candidato,jolly);
  70.                                 printf("\nPremi invio per continuare...");getchar();getchar();
  71.                                 break;
  72.                         case 5:
  73.                                 printf("\nInserire il numero del candidato di cui eliminare i voti nulli:");scanf("%d",&candidato);
  74.                                 jolly=EliminaSchedeNulle(candidato,&first);
  75.                                 printf("\nEliminate %d schede",jolly);
  76.                                 printf("\nPremi invio per continuare...");getchar();getchar();
  77.                                 break; 
  78.                         case 6:
  79.                                 termina=1;
  80.                 }
  81.         }
  82.         return (0);
  83. }
  84. //Inizializzazione della lista: si libera la memoria sfruttata precedentemente per la lista
  85. void InizializzaLista(scheda **f)
  86. {
  87.         scheda *temp;
  88.         while ((*f)!=NULL)
  89.         {
  90.                 temp = (*f);
  91.                 (*f) = (*f)->next;
  92.                 free(temp);
  93.         }
  94.         return;
  95. }
  96.  
  97. //Funzione per l'aggiunta di schede alla lista
  98. void AggiungiScheda(int candidato, boolean validita,scheda **f)
  99. {
  100.         scheda *nuova = (scheda*) malloc(sizeof(scheda));
  101.         nuova->candidato=candidato;
  102.         nuova->valida=validita;
  103.         nuova->next=(*f);
  104.         (*f)=nuova;
  105.         return;
  106. }
  107. //Stampa la lista
  108. void ScriviSchede(scheda *f) {
  109.         while (f!=NULL)
  110.         {
  111.                 printf("%p           %d    -    %d   %p \n",f,f->candidato,f->valida,f->next);
  112.                 f=f->next;
  113.         }
  114. }
  115.  
  116. //Punto (ii)
  117. int ConteggioVotiValidi (int candidato, scheda* f)
  118. {
  119.         if (f==NULL) return 0; //controlla che la lista non sia vuota
  120.         if (f->candidato==candidato && f->valida==true)
  121.                         return 1+ConteggioVotiValidi(candidato, f->next);              
  122.         else
  123.                         return 0+ConteggioVotiValidi(candidato,f->next);
  124. }
  125. //Fine Punto (ii)
  126.  
  127.  
  128. int EliminaSchedeNulle(int candidato, scheda** f)
  129. {
  130.  
  131.         if ((*f) == NULL) return 0; //Se la lista è vuota esce dalla funzione tornando 0
  132.         if ((*f)->next==NULL && (*f)->candidato==candidato && (*f)->valida==false) {InizializzaLista(f); return 1;} //Nel caso in cui ci sia un solo elemento nella lista e questo elemento va eliminato, è necessario chiamare inizializzalista(); torna 1 perchè è coem fare una cancellazione
  133.         int cancellazioni=0;
  134.         scheda *temp, *prec;
  135.         //Il primo ciclo fa in modo che f non sia un voto nullo al candidato passato come parametro
  136.         while ((*f)->candidato==candidato && (*f)->valida==false) { //fin quando la prima scheda è un voto nullo a candidato
  137.                 temp=(*f)->next;  //il primo elemento diviene quello successivo
  138.                 free((*f)); //libero la memoria del vecchio primo elemento
  139.                 (*f)=temp;
  140.                 cancellazioni++; //incremento il numero di cancellazioni
  141.         }
  142.         prec=(*f); //ho gia verificato che f non sia una scheda nulla a candidato
  143.         temp=prec->next; //controllo della scheda successiva alla prima "rimasta"
  144.         while(temp!=NULL) {
  145.                 if (temp->candidato==candidato && temp->valida==false) {
  146.                         prec->next=temp->next; //Se la scheda puntata da temp non è valida allora la scheda precedente a temp (con prec->next=temp) dovrà puntare alla scheda successiva a temp (temp->next)
  147.                         free(temp); //Libero la memoria
  148.                         cancellazioni++; //incremento il numero di cancellazioni
  149.                         temp=prec->next;
  150.                 } else
  151.                 {
  152.                         prec=temp; //incremento prec
  153.                         temp=temp->next; //incremento temp
  154.                 }
  155.         };
  156.         return cancellazioni; //torna in output il numero delle cancellazioni effettuate
  157. }
  158. // punto (iii)


Ultima modifica effettuata da WinstonS il 12/12/2010 alle 22:50
PM
Avatar
Alex (Ex-Member)
Expert


Messaggi: 441
Iscritto: 15/08/2005

Up
0
Down
V
Segnala al moderatore
Postato alle 19:40
Lunedì, 13/12/2010
Testo quotato

Postato originariamente da WinstonS:

Mai usati puntatori a puntatori; vediamo
il prototipo della funzione di questo tipo?
int EliminaSchedeNulle(int candidato, scheda **f)

e la chiamata alla funzione così? EliminaSchedeNulle(candidato,&first)[\code], dove candidato è un int e first è dichiarato come scheda *first[\code]...


E fin qui il programma va ma poi come opero all'interno di EliminaSchedeNulle?? *f->, *f., **f->, **f., (per fare un esempio di cose che non funzionano)?



mi pare che devi usare (*f)->
in quanto l'operatore -> ha la precedenza su *...


Alex=)
PM
Avatar
WinstonS (Normal User)
Newbie


Messaggi: 6
Iscritto: 12/12/2010

Up
0
Down
V
Segnala al moderatore
Postato alle 21:57
Lunedì, 13/12/2010
Si infatti ho fatto così :) Grazie mille

PM
Avatar
ramy (Normal User)
Newbie


Messaggi: 1
Iscritto: 06/01/2011

Up
0
Down
V
Segnala al moderatore
Postato alle 23:09
Giovedì, 06/01/2011
Un altro modo sarebbe di tenere un puntatore numerico che conitene il numero di strutture allocate e un bool che dice se la struttura va salvata o no.
Una volta creata la funzione di input sembre di programmare in python,basta solo liberare l' area di memoria (io non lo faccio perchè è un programma breve).

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdio.h>
  3. #include <stdbool.h>
  4. #include <string.h>
  5. #include <malloc.h>
  6. #include <time.h>
  7.  
  8.  
  9. typedef struct
  10. {
  11.     bool save;
  12.     char *nome;
  13.     char *cognome;
  14. }persona;
  15.  
  16.  
  17.  
  18. char *input(FILE *fp);
  19. void add(persona *ptr,int *num);
  20.  
  21. int main(int argc,char **argv)
  22. {
  23.     persona *lista;
  24.     int *num,i;
  25.     num=(int*)malloc(sizeof(int));
  26.     lista=(persona*)malloc(sizeof(persona));
  27.     *num=0;
  28.     for(i=0;i<3;i++)
  29.       add(lista,num);
  30.     printf("Output:\n");
  31.     for(i=0;i<*num;i++)
  32.       puts(lista[i].cognome);
  33.     return 0;
  34. }
  35.  
  36. char *input (FILE *fp)
  37. {
  38.     char *string;
  39.     char check;
  40.     string=(char*)malloc(sizeof(char));
  41.     int i=1;
  42.     while((check=fgetc(fp))!=10)
  43.     {
  44.         string[i-1]=check;
  45.         i++;
  46.         string=(char*)realloc(string,i*sizeof(char));
  47.     }
  48.     string[i-1]='\0';
  49.     fflush(stdin);
  50.     return string;
  51. }
  52.  
  53. void add(persona *ptr,int *num)
  54. {
  55.     if(*num>1)
  56.       ptr=(persona*)realloc(ptr,sizeof(persona));
  57.     printf("Inserire nome:-->");
  58.     ptr[*num].nome=input(stdin);
  59.     printf("Inserire cognome:-->");
  60.     ptr[*num].cognome=input(stdin);
  61.     ptr[*num].save=true;
  62.     (*num)++;
  63. }



Ovviamente se non hai tempo di cambiarlo ti conviene lasciarlo così,molti usando il puntatore alla prossima struttura.
Ma in questo modo per aggiungerne una basta digitare (add,num),per cancellarne una basta mettere a falso il bool che dice di salvarla o no.
Alla fine del programma solo quelle col bool true vengono salvate sul file.




PM