[C] Esercizio su pile/code

[kily_2001]

ciao a tutti, come risolvereste questo esercizio?

Considerate una sequenza di interi letti da input e definite una funzione C che li stampa
in modo tale che tutti i pari precedano i dispari, nello stesso ordine in cui vengono letti.
Ad esempio, se la sequenza è:
1 , 20 , 35 , 40 , 62 , 51 , 66
La stampa che si vuole ottenere e'
20 , 40 , 62 , 66 , 1 , 35 , 51
La funzione deve utilizzare come struttura dati di appoggio una pila o una coda.


grazie mille!!!

[Skywalker87]

Beh innazi tutto definisci la struttura e le funzioni che gestiscono la pila-coda. E dopo questo scrivi una semplice funzione per riordidare la pila-coda secondo l'ordine che vuoi tu, facendogli rispettare le condizioni di FILO per la pila e FIFO per la coda. L'esercizio non e' complicato ma un po' "lunghetto", quindi ti invito a fare almeno un tentativo dopo di che a postare il codice cosi' vediamo di risolvere insieme eventuali dubbi!!

[kily_2001]

la pila-coda volevo implementarla con delle liste concatenate, ma innanzitutto cosa mi conviene usare? una pila o una coda?

[Skywalker87]

la pila-coda volevo implementarla con delle liste concatenate

Perfetto...

ma innanzitutto cosa mi conviene usare? una pila o una coda?

Assolutamente idifferente!

[kily_2001]

void ordina(stack *stk)
{
     if(IsEmpty(stk)) return;
     {
       int y=pop(stk);
       ordina(stk);
       if (y%2==0) printf("%d ",y);
       else push(stk,y);
     }
} 

in questo modo mi stampa i pari e lascia i dispari nello stack, ora come faccio a fare in modo che dopo i pari mi stampa i restanti elementi dello stack (che sono nell'ordine esatto per essere stampati)?

[kily_2001]

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 50

struct elem
{ 
   int d;
   struct elem* next;
};

typedef struct elem elem;

typedef struct stack
{
   int cnt;
   elem* top;
}stack;

void init(stack*);
void push(stack*,int); 
int pop(stack*);
int top(stack*);
int IsEmpty(stack*);
int IsFull(stack*);
void stampa(stack*);

void init(stack* stk)
{
     stk->cnt=0;
     stk->top=NULL;
}

void push(stack* stk, int d)
{
     elem* tmp=malloc(sizeof(elem));
     tmp->d=d;
     tmp->next=stk->top;
     stk->top=tmp;
     stk->cnt++;
}

int pop(stack* stk)
{
    int dato=stk->top->d;
    elem *tmp=stk->top;
    stk->top=stk->top->next;
    stk->cnt--;
    free(tmp);
    return dato;
}

int top (stack* stk)
{
    return stk->top->d;
}

int IsEmpty(stack* stk)
{
    return (stk->cnt==0);
}

int IsFull(stack* stk)
{   
    return (stk->cnt==MAXSIZE);
}

void stampa(stack* stk)
{
  if(stk->cnt==0) return;
  else
  {
    int tmp=pop(stk);
    printf("%d ",tmp);
    stampa(stk);
  }    
} 

questo è il mio stack.h

[kily_2001]

ho risolto cosi va bene? dal main chiamo stampa_in_ordine.

void stampa_in_ordine(stack *stk)
{
     stampa_pari(stk);
     stampa(stk);
}

void stampa_pari(stack *stk)
{
     if(IsEmpty(stk)) return;
     {
       int y=pop(stk);
       stampa_pari(stk);
       if (y%2==0) printf("%d ",y);
       else push(stk,y);
     }
}

void stampa(stack* stk)
{
  if(stk->cnt==0) return;
  else
  {
    int tmp=pop(stk);
    stampa(stk);
    printf("%d ",tmp);
    push(stk,tmp);
  }    
} 

c'è un modo un po piu "compatto" per fare un programma del genere? magari usando una sola funzione. L'ideale sarebbe ordinare i valori nello stack come vuole l'esercizio e poi stamparli normalmente.

[Skywalker87]

Io avrei strutturato una funzione ordina() che scorre tutta la lista e controlla se l'elemento in considerazione e' pari o dispari. Se e' pari viene prelevato dalla lista e posto in una nuova, creata apposta per ospitare gli elementi pari; se invece e' dispari viene prelevato dalla lista e posto in una altra lista ancora creata per ospitare gli elementi dispari. A questo punto ci si ritrova con la lista originale vuote e due nuove liste una contenete gli elementi pari e una contenente quelli dispari. Ora basta riversare le nuove liste create nella lista madre, in modo da riempirla prima con gli elementi pari o dispari e poi con quelli rimanenti. Poi potrai utilizzare sempre la stessa funzione stampa, visto che la lista e' ora ordinata.

[kily_2001]

nn credo che si possa fare, il testo dice che si ha in input una sequenza di interi e che si puo usare o una coda o uno stack, non credo siano ammesse altre strutture d'appoggio!

[Skywalker87]

nn credo che si possa fare, il testo dice che si ha in input una sequenza di interi e che si puo usare o una coda o uno stack, non credo siano ammesse altre strutture d'appoggio!

Ah ok questo lo so adesso, beh al posto delle liste potresti utilizzare un array, insomma un qualcosa che ti permetta dimemorizzare temporaneamente i valori della coda.