[C]Pila. Pollo io o pollo prof?

[The-Revenge]

Ciao ragazzi. Vorrei farvi questa domanda su un queisto che è uscito nel compito di informatica, sulle strutture dati, precisamente pila. Non mi convince la correzione che il prof ha dato alla mia risoluzione, se vogliamo tralasciare, inoltre, che ha dato la mia medesima soluzione a un problema simile nella dispensa che ci ha fornito.

Comunque veniamo al problema.
La traccia era semplice : data una pila di caratteri già generata (non c'è necessita di generare la pila) scrivere una funzione che abbia in ingresso il puntatore alla testa della pila, e che ritorni il puntatore alla testa della pila epurata da tutti gli elementi contenti il campo informazione B. Si scriva inoltre la dichiarazione della struct.

Mia soluzione : (ometto la dichiarazione della struct e tutto il pezzo delle dichiarazione di puntatori ausiliari per semplicità).

p2=NULL;
While(puntatesta!=NULL){
if(puntatesta->car=='B')puntatesta=puntatesta->pun;
 else{
         paus=puntatesta;
         puntatesta=puntatesta->pun;
         paus->pun=p2;
         p2=paus;
         }
          }
While(p2!=NULL){

         paus=p2;
         p2=p2->pun;
         paus->pun=puntatesta;
         puntatesta=paus;
         }

dove car è il campo informazioni char, e pun è il puntatore alla struttura successiva, nelle struct.
Il codice non ha bisogno di commento, nel primo pezzo trasferisco ogni singolo elemento in un altra pila (p2) eliminando gli elementi con campo finroamzioni B, nel secondo pezzo ricostruisco la pila iniziale.

Veniamo al dunque, il problema è dove ho messo in grassetto : secondo il prof quel comando fa perdere il puntatore alla testa della pila, e quindi la pila stessa. Secondo lui avrei dovuto fare l'if di controllo una volta estratto ogni singolo elemento, cioè quando l'elemento si trova, da solo, puntato dal puntatore ausiliario paus.

Secondo voi chi ha ragione? Io continuo a pensare che, concettualmente, è giusto come ho scritto, anche perchè mi sembra che c'è scritto anche sul libro, se non erro

[wingman87]

Ma non potevi usare push e pop?
A parte questo mi sembra giusto. Solo non deallochi gli elementi eliminati, ma forse era richiesto così.

[The-Revenge]

Originariamente inviato da wingman87

Ma non potevi usare push e pop?
A parte questo mi sembra giusto. Solo non deallochi gli elementi eliminati, ma forse era richiesto così.

ho saltato volutamente la deallocazione, che comunque nel compito ho fatto, anche se forse sbagliando. IN pratica io deallocavo paus con free DENTRO il while (anche se questo non me lo ha contato come errore), che sarebbe inutile dato che paus ad ogni ciclo while viene messo uguale a puntatesta, casomai a fine di tutto potevo deallocare p2 e paus (che comunque dovrebbe puntare a NULL, quindi cosa devo deallocare? XD).

Comunque apparte questo, che diavolo è il push e pop? COn un prof che mi corregge le cose inesistenti, non vi stupite se non sò che vuol dire.
Pensate che non è riuscito a capire questo pezzo di codice :

void primalita(int num){
        int i=3;
        if((num==0)||(num==1))printf("\nIl numero non e' primo");
         else if(num==2)printf("\nIl numero e' primo");
          else if(num%2==0)printf("\nIl numero non e' primo");
           else {
                while(i<num){
                    if(num%i==0)break;
                    i=i+2;
                }

                 if(i==num)printf("\nIl numero e' primo");
                  else printf("\nIl numero non e' primo");
           }
           return;
    }

cioè, ditemi se uno cosi può insegnare all'università. Me lo ha segnato come errore, non capiva perchè i partiva da 3, non capiva perchè incrementavo i di 2 , non capiva perchè non ho usato un for al posto del while.
Io rifarò l'esame per il 23 che ho preso, ma mi sa che visto il prof potrei anche essere bocciato

[mindwings]

Originariamente inviato da The-Revenge

ho saltato volutamente la deallocazione, che comunque nel compito ho fatto, anche se forse sbagliando. IN pratica io deallocavo paus con free DENTRO il while (anche se questo non me lo ha contato come errore), che sarebbe inutile dato che paus ad ogni ciclo while viene messo uguale a puntatesta, casomai a fine di tutto potevo deallocare p2 e paus (che comunque dovrebbe puntare a NULL, quindi cosa devo deallocare? XD).

Comunque apparte questo, che diavolo è il push e pop? COn un prof che mi corregge le cose inesistenti, non vi stupite se non sò che vuol dire.
Pensate che non è riuscito a capire questo pezzo di codice :

void primalita(int num){
        int i=3;
        if((num==0)||(num==1))printf("\nIl numero non e' primo");
         else if(num==2)printf("\nIl numero e' primo");
          else if(num%2==0)printf("\nIl numero non e' primo");
           else {
                while(i<num){
                    if(num%i==0)break;
                    i=i+2;
                }

                 if(i==num)printf("\nIl numero e' primo");
                  else printf("\nIl numero non e' primo");
           }
           return;
    }

cioè, ditemi se uno cosi può insegnare all'università. Me lo ha segnato come errore, non capiva perchè i partiva da 3, non capiva perchè incrementavo i di 2 , non capiva perchè non ho usato un for al posto del while.
Io rifarò l'esame per il 23 che ho preso, ma mi sa che visto il prof potrei anche essere bocciato

Non capisco il senso di un corso di algoritmi e strutture dati che utilizzi il C/C++ quando poi uno studente non conosce nemmeno gli operatori del dato astratto pila... L'operatore push inpila un elemento, pop invece toglie l'elemento dalla pila(sottointeso che e' dalla testa).
EDIT:
Il tuo codice potrebbe essere piu' esplicito con l'uso di costanti e nomi piu' espliciti, l'algoritmo mi sembra un po' naive

[cionci]

Originariamente inviato da mindwings

L'operatore push inpila un elemento, pop invece toglie l'elemento dalla pila(sottointeso che e' dalla testa).

Dipende se li hanno definiti o meno questi operatori. Poi a me sinceramente più che una pila mi sembra una semplice lista.

Il puntatore alla testa lo perdi però dipende da come quel codice è integrato all'interno del resto.

Ad esempio:

void tuafunzione(struct lista * puntatesta)
{
  /*qui ci va il tuo codice*/
}

In questo caso non perdi assolutamente niente.
Se io chiamo:

struct lista * testa;
/* qui riempio la lista */
tuafunzione(lista);
/*qui lista non cambia valore */

[The-Revenge]

Originariamente inviato da cionci

Dipende se li hanno definiti o meno questi operatori. Poi a me sinceramente più che una pila mi sembra una semplice lista.

Il puntatore alla testa lo perdi però dipende da come quel codice è integrato all'interno del resto.

Ad esempio:

void tuafunzione(struct lista * puntatesta)
{
  /*qui ci va il tuo codice*/
}

In questo caso non perdi assolutamente niente.
Se io chiamo:

struct lista * testa;
/* qui riempio la lista */
tuafunzione(lista);
/*qui lista non cambia valore */

push e pop non li ho fatti, come non ho fatto qualsiasi operatore che agisca tramite funzione prestabilita in una pila/coda/lista.

Cionci, avevo già detto che ho omesso le varie parti del codice per arrivare al problema. ovviamente ho scritto il codice dentro la funzione che tu stesso hai scritto, ovvero

struct pila *elimina(struct pila *) {   }

ovvero alla funzione elimina entra il puntatore alla testa della pila, e esce un puntatore alla testa della pila.
Comunque perchè dici che è una lista? Io elimino sempre il primo elemento e , nella pila ausiliaria, impilo sempre dal primo elemento, e poi faccio l'inverso, quindi direi che non ho "violato" il concetto di pila se non per quell'errore che ha segnato il prof, che ancora sono in dubbio se è sbagliato ralmente o meno.
Se poi ho un brutto concetto di pila, non è colpa mia , ma sua

[cionci]

push e pop sono le operazioni di inserimento in testa ed estrazione dalla testa.

Riguardo al codice che hai omesso: ci serviva per capire se effettivamente perdervi il puntatore.

Comunque:

if(puntatesta->car=='B')puntatesta=puntatesta->pun;

Qui non è che perdi il puntatore alla testa, perdi il puntatore a qualsiasi elemento della lista che ha B nel campo informazione.

Tu stai usando la pila come se fosse una lista. In teoria le operazioni disponibili sulle liste dovrebbero essere solo push e pop. Quindi non dovresti poter accedere al contenuto interno.
Una ricerca come quella che hai fatto si fa con una pila di appoggio in cui andare a mettere tutti gli elementi estratti dalla prima pila (ad esclusione di quelli da rimuovere) per poi rimetterli nella pila originaria.

[The-Revenge]

Originariamente inviato da cionci

push e pop sono le operazioni di inserimento in testa ed estrazione dalla testa.

Riguardo al codice che hai omesso: ci serviva per capire se effettivamente perdervi il puntatore.

Comunque:

if(puntatesta->car=='B')puntatesta=puntatesta->pun;

Qui non è che perdi il puntatore alla testa, perdi il puntatore a qualsiasi elemento della lista che ha B nel campo informazione.

Tu stai usando la pila come se fosse una lista. In teoria le operazioni disponibili sulle liste dovrebbero essere solo push e pop. Quindi non dovresti poter accedere al contenuto interno.
Una ricerca come quella che hai fatto si fa con una pila di appoggio in cui andare a mettere tutti gli elementi estratti dalla prima pila (ad esclusione di quelli da rimuovere) per poi rimetterli nella pila originaria.

ho capito. Allora ha ragione il prof. Tu e il prof state dicendo una cosa simile, in un modo diverso, e tu non hai capito bene cioè che ho fatto io, ma io ho capito l'errore.
In pratica io ho fatto cioè che hai detto tu (usato una pila ausiliaria che poi vado a ricostruire), che ho chiamato appunto p2, ma come hai detto tu ho usato un elemento interno nella pila, cosa che è illegale (nell'asegnazione puntatesta=puntatesta->pun, puntatesta->pun si riferisce al secondo elemento della pila, cosa che è improbabile dato che la pila può aver accesso solo al primo elemento).
Era la stessa cosa che intendeva il professore quando diceva che perdo la testa, voleva dire che non posso accedere al secondo elemento per la struttura stessa della pila.

Grazie mille, mi avete aiutato a capire che cavolo voleva dire il prof con quel "perdi la testa della pila", se me lo avrebbe spiegato come ha fatto cionci, cioè che semplicemente non posso assegnare al secondo elemento, questo 3d non l'avrei nemmeno aperto

[The-Revenge]

Quindi ricapitolando, il codice giusto per ottenere una pila epurata dai caratteri B (scusate se non uso questi operatori push e pop, ma come vi ho detto non li ho studiati)

struct pila{
               char car;
               struct pila *pun;
               };



struct pila *elimina(struct pila *puntatesta){
struct pila *paus=NULL, *p2=NULL;
while(puntatesta!=NULL){
                                  paus=puntatesta;
                                  puntatesta=puntatesta->pun;
                                  if(paus->car=='B')free(paus);
                                   else{
                                         paus->pun=p2;
                                         p2=paus;
                                         }
                                  }
                                  
while(p2!=NULL){
                       paus=p2;
                       p2=p2->pun;
                       paus->pun=puntatesta;
                       puntatesta=paus;
                      }

}

[cionci]

Avevo capito che p2 era la pila ausiliaria...
In questi frangenti si definiscono le due operazioni di push e pop da fare sulla pila in modo da lasciare fare tutto il lavoro a loro.

struct stack
{
   char info;
   struct stack * next;
};


void push(struct stack ** s, char info)
{
   struct stack * new_head = (struct stack *)malloc(sizeof(struct stack));
   new_head->next = *s;
   new_head->info = info;
   *s = new_head;
}

char pop(struct stack ** s)
{
   struct stack * old_head;
   char ret;

   if(!*s)
     return -1;
   
   old_head = *s;
   *s = old_head->next;
   ret = old_head->info;
   free(old_head);
   return ret;
}

A quel punto il tuo problema sarebbe diventato una banalità...

Semplicemente così:

while((ret = pop(&s)) > 0)
{
   if(ret != 'B') push(&s2, ret);
}

while((ret = pop(&s)) > 0) push(&s, ret);

[Furla]

solitamente (almeno per quanto riguarda la mia esperienza) esercizi del genere vengono assegnati per operare efficientemente ed a basso livello su una struttura dati, non per astrarre tipi da usare con funzioni indipendenti dall'implementazione. appare abbastanza evidente che The-Revenge (e probabilmente, cosa ancor più grave, il suo professore) usi il termine pila per indicare una lista monodirezionale.

una soluzione semplice potrebbe essere questa:

struct stack
{
   char info;
   struct stack * next;
};

void togliB(struct stack ** s) {
  struct stack * olds;
  while (*s) {
    while (*s->info=='B') {
      olds=*s;
      *s=*s->next;
      delete olds;
    }
    s=&(*s->next);
  }
}

[cionci]

Originariamente inviato da Furla

struct stack
{
   char info;
   struct stack * next;
};

void togliB(struct stack ** s) {
  struct stack * olds;
  while (*s) {
    if (*s->info=='B') {
      olds=*s;
      *s=*s->next;
      delete olds;
    }
    s=&(*s->next);
  }
}

Però fai uso della struttura interna a lista dello stack...non è secondo me un approccio da stack E' un approccio da lista. Cosa cambierebbe nel tuo codice se quella fosse una semplice lista e non uno stack ? Assolutamente niente.
E' lo stesso appunto che farei sul secondo codice postato dall'autore del thread, anzi lui si trova in uno stato ancora più incoerente perché usa due pile e poi trasferisce fra le due pile strutture interne della rappresentazione della pila.
E' chiaro che fra i due trovo più corretto il tuo approccio, alla fine deve essere uno dei due approcci o quello con l'astrazione (insegna ad usare le pile) o quello che sfrutta la struttura interna a lista (insegna ad usare le liste). Però non è detto che una pila sia organizzata con le liste


In ogni caso perdi la testa della lista...scorri usando *s, quindi alla fine del ciclo *s sarà NULL, ma tale variazione si rifletterà anche sul chiamante. Se vuoi fare una cosa del genere o fai una chiamata ricorsiva o fai un while prima per eliminare gli elementi in testa e poi un altro per gli elementi successivi a quelli in testa.

[Furla]

Originariamente inviato da cionci

Però fai uso della struttura interna a lista dello stack...non è secondo me un approccio da stack E' un approccio da lista. Cosa cambierebbe nel tuo codice se quella fosse una semplice lista e non uno stack ? Assolutamente niente.
In ogni caso perdi la testa della lista...scorri usando *s, quindi alla fine del ciclo *s sarà NULL, ma tale variazione si rifletterà anche sul chiamante. Se vuoi fare una cosa del genere o fai una chiamata ricorsiva o fai un while prima per eliminare gli elementi in testa e poi un altro per gli elementi successivi a quelli in testa.

ho spiegato sopra perché opero sulla struttura.
*s alla fine del ciclo punterà all'ultimo elemento, che giustamente deve avere next a zero. ovviamente esiste una ricorsiva equivalente, ma non è necessario il doppio ciclo, se si fa uso del puntatore a puntatore.

[cionci]

Originariamente inviato da Furla

ho spiegato sopre perché opero sulla struttura.
*s alla fine del ciclo punterà all'ultimo elemento, che giustamente deve avere next a zero. ovviamente esiste una ricorsiva equivalente, ma non è necessario il doppio ciclo, se si fa uso del puntatore a puntatore.

Per quale motivo deve essere a zero ? Se io passo un puntatore alla testa a quella funzione io mi devo aspettare di riavere un puntatore alla testa. Altrimenti passo semplicemente *s e ritorno il puntatore alla nuova testa.

PS: scusa, ma ho modificato il post sopra

[Furla]

uso tipico:
(scusate se c'è qualche errore ma sono senza compilatore al momento)

//bla blah
void main()
{
  struct stack * testa;
  struct stack * app;
  char i =127;
  while(--i) { // riempio la lista
    app=(struct stack *)malloc(sizeof(struct stack));
    app->info=i;
    app->next=testa;
    testa=app;
  }
  togliB(&testa); //passo l'indirizzo, non il puntatore alla lista
  app=testa;
  while(app){
    printf("%c ",app->info);
    app=app->next;
  }
  while(--i) { // riempio la lista
    app=(struct stack *)malloc(sizeof(struct stack));
    app->info=i;
    app->next=testa;
    testa=app;
  }
  togliB(&testa); //passo l'indirizzo, non il puntatore alla lista
  app=testa;
  while(app){
    printf("%c ",app->info);
    app=app->next;
  }
}

[cionci]

Certo, dopo la chiamata testa vale NULL, hai quindi perso il puntatore alla testa.

[Furla]

*s non corrisponde più a testa, alla fine del ciclo.

l'unica possibilità che ho di cambiare testa si verifica quando (e finché, ho fixato) il primo elemento della lista abbia info = B, caso in cui entro nel while interno e assegno a *s (cioè a testa) l'indirizzo dell'elemento successivo. dopodiché s punterà ad un altro puntatore (il next di un elemento successivo) e testa rimarrà invariato. non so se son riuscito a spiegarmi , ti torna?

comunque se hai la possibilità provalo, si vede subito se ho cannato ...

[cionci]

Originariamente inviato da Furla

*s non corrisponde più a testa, alla fine del ciclo

Stampami il nuovo stack dopo la chiamata ad eliminaB.

[The-Revenge]

cionci, mi potresti spiegare perchè il mio codice è sbagliato senza usare push e pop genitlmente? perchè come vi ho detto non li ho studiati, abbiate pazienza con me, anche voi vi siete accorti che chi mi insegna la materia non è il massimo, il libro per la pila ha 2 pagine....
L'unica informazione che vi posso dare è che io uso la pila come una lista da cui si può accedere solo al primo elemento, e anche sul libro fa la stessa cosa.
MI potresti dire perchè il codice (il secondo) è sbagliato?

[cionci]

Non è sbagliato, il codice funziona.
Diciamo che si trova a metà fra le due strade che si adottano solitamente.
Pensa alla tua funzione come appartenente ad una libreria che implementa una pila. In tal caso sicuramente non adotterai il metodo usato da te, ma quello cercherai di sfruttare la struttura a lista andando ad eliminare direttamente gli elementi.

Pensa invece alla tua funzione esterna ad un libreria. La libreria ti mette a disposizione un tipo di dato stack e le operazioni di push e pop. Dovrai sfruttare quelle operazioni per andare a risolvere il problema, indipendentemente dalla struttura interna della pila.

Il tuo metodo di risoluzione si trova a metà perché trasferisci da una pila all'altra elementi (anche se solo della testa) della struttura interna della pila. Quindi sfrutti e non sfrutti la struttura interna della pila.

Sicuramente non mi sembra il miglior approccio di studio.
Prova a pensare ad implementare uno stack con un vettore.