[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]

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? :stordita: 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]

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? :stordita: 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 :D

[cionci]

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]

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 :doh:

[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]

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]

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]

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]

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 :D, ti torna?

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

[cionci]

*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.

[The-Revenge]

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.

forse finalmente (e miracolosamente direi, dato che è più sottile di quello che psnavo) ho capito cosa vuoi dire : in pratica stai dicendo che io so che nella pila non posso prelevare elementi interni quindi uso una pila ausiliaria dalla quale trasferisco solo elementi alla testa; ma nel fare questo di fatto "maneggio" gli elementi interni della pila, trasferendoli da una pila all'altra, quindi violo l'essenza della pila di non poter toccare gli elementi interni, anche se comunque rispetto la regola di estrarli dalla testa. Invece con il push e pop che dici tu sono funzioni che permettono di non toccare completamente la struttura interna senza avere bisogno di pila ausiliaria ma solo di queste due funzioni.
E' giusto come ho interpretato? se è giusto vabbene, sennò ci rinuncio :doh: :stordita:
Cmq non avendo fatto il push e pop e tutte queste precisazioni, direi che la mia soluzione è comunque quella adottata dal prof :doh:

[cionci]

E' giusto come ho interpretato? se è giusto vabbene, sennò ci rinuncio :doh: :stordita:
Cmq non avendo fatto il push e pop e tutte queste precisazioni, direi che la mia soluzione è comunque quella adottata dal prof :doh:
Tutto esatto ;)
Comunque ricordati che le pile si possono fare anche con i vettori. Prova ad implementarne una ed implementa magari anche le operazioni di push e pop ;)

[cionci]

Ritornando alla funzione di eliminazione di Fulra... La funzione ricorsiva è sicuramente la più semplice:

struct stack * eliminaB(struct stack * s)
{
struct stack * aux;

if(!s) return NULL;

s->next = eliminaB(s->next)

if(s->info == 'B')
{
aux = s->next;
free(s);
return aux;
}

return s;
}
Ovviamente credo sappiate che una funzione ricorsiva si può simulare guarda caso con una pila :D

struct stack * eliminaB(struct stack * s)
{
struct stack * aux, stack;
while(s)
{
push(stack, s);
s = s->next;
}

aux = NULL;
while(size(stack))
{
s = pop(stack);
s->next = aux;
aux = s;
if(s->info == 'B')
{
aux = s->next;
free(s);
}
}
return aux;
}

Ovviamente tutto non compilato e sensibile a possibili errori...

[Furla]

#include "stdio.h"
#include "stdlib.h"

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;
free(olds);
}
s=&((*s)->next);
}
}

void riempi(struct stack ** testa) {
struct stack * app;
char i =127;
while(--i) { // riempio la lista
app=(struct stack*)malloc(sizeof(struct stack));
app->info= i%3?'B':i;
app->next=*testa;
*testa=app;
}

}
void stampa(struct stack * app) {
while(app){
printf("%c ",app->info);
app=app->next;
}
printf("%s","\n\n");
}

void main() {
struct stack * testa = 0;
riempi(&testa);
stampa(testa);
togliB(&testa); //passo l'indirizzo, non il puntatore alla lista
stampa(testa);
scanf("%d",testa);
}

testata, perfettamente funzionante. ho solo aggiunto qualche parentesi perché * e -> bisticciavano ( :Prrr: ) e cambiato delete in free (svista da c++ista).
notare che nel main mi ero scordato di inizializzare la lista in uno stato consistente: errore imperdonabile.

[cionci]

In effetti funziona, *s cambia per tutte le estrazioni in testa e di conseguenza cambia anche *testa nel main. Poi dopo vai a cambiare l'indirizzo puntato da s quindi le modifiche che vai a fare successivamente non influiscono sul valore di *testa nel main. Bello.