PDA

Visualizza la versione completa : [C] Invertire Stack In Place (Senza Vettore di Appoggio)


Skull260287
19-10-2008, 14:59
Ciao a tutti sono alle prese con un algoritmo che utilizza la ricorsione per invertire gli elementi di uno stack in place, ovvero senza utilizzare altre strutture di appoggio. Ho scritto un codice che, testato, pare abbia l'unico problema che non "scarica" gli elementi salvati nella variabile temp in fase di Push. L'lagoritmo è semplificato, indico le semplificazioni in testa al programma. Qualcuno ha qualche idea?



/* = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

Nome File: Inverti_Stack_Ricorsione.c

Funzionalità:
L'algoritmo Inverte i valori presenti nello stack utilizzando la
ricorsione.

Semplificazione: Implemento lo Stack come Vettore ed effettuo le
operazioni su di esso direttamente in questo algoritmo, andrebbe diviso

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

#include <stdio.h>

void Inverti(int S[],int Elem,int Dim,int Flag,int Top,int ToBotto,int temp);

int main(int argc, char *argv[])
{

int Stack[64];
int i=0;
int n;
int Top=0;

int c;

printf("Quanti Numeri Vuoi Inserire?");
c=getch();

c=c-'0';

do{
printf("\n\nInserire Un Elemento da Tastiera ");
n=getch();

n=n-'0';

printf("%i",n);

Stack[i]=n;
i++;
}while(i<c);

Top=i-1;

printf("\n\n\n");

for(i=0;i<=Top;i++) printf("%i\t",Stack[i]);

printf("\n\n\n");

Inverti(Stack,Top,Top,0,Top,0,0);

printf("\n\n\n");

for(i=0;i<=Top;i++) printf("%i\t",Stack[i]);

fflush(stdin);
printf("Premere Un Tasto Per Uscire...\n");
_getch();
return 0;

}

void Inverti(int S[],int Elem,int Dim,int Flag,int Top,int ToBottom,int temp)
{
printf("\n\nDentro inverti\n");
system("pause");
printf("\n\nVariabili In Testa Alla Funzione: \n");
printf("Elem %i, Dim %i,Flag %i, Top %i, Stack[Top] %i, ToBottom %i\n\n",Elem,Dim,Flag,Top,S[Top],ToBottom);
if(Top>=Dim-Elem && Flag==0)
{
if(Dim==Top) ToBottom=S[Top];


else{
temp=S[Top];
printf("S[Top] Pop %i\n\n",temp);
system("pause");
}

Inverti(S,Elem,Dim,Flag,Top-1,ToBottom,temp);
}

else if(Elem>=0)
{
Flag=1;
if(Top==-1) Top=0;

if(Top==Dim-Elem)
{
S[Top]=ToBottom;
printf("S[Top] ToBottom %i\n\n",S[Top]);
system("pause");
}
else if(Top<=Dim)
{
S[Top]=temp;
printf("S[Top] Inserito %i\n\n",S[Top]);
system("pause");
if(Top==Dim) Top--;
}
else
{
Flag=0;
Elem--;
Top--;
int i;
for(i=0;i<=Top;i++) printf("%i\t",S[i]);
}
Inverti(S,Elem,Dim,Flag,Top+1,ToBottom,temp);
}
}

Skull260287
20-10-2008, 09:36
Nessuno ha qualche idea?

Edgar89
20-10-2008, 22:13
scusa... forse sarò scemo io che non ho cenato ancora e la fame mi dà le allucinazioni ma praticamente tu da uno stack [0,1,2,3,4] devi ottenere [4,3,2,1,0]? se è così basta fare così:


void reverse(int* first, int* end){
if (first>=end) return;
//scambia i due valori
int tmp=0;
tmp=*first;
*first=*end;
*end=tmp;
first++;
end--;
reverse(first,end);
}

ovviamente devi calcolare end a parte scorrendo l'array una volta

Skull260287
21-10-2008, 20:44
Originariamente inviato da Edgar89
scusa... forse sarò scemo io che non ho cenato ancora e la fame mi dà le allucinazioni ma praticamente tu da uno stack [0,1,2,3,4] devi ottenere [4,3,2,1,0]? se è così basta fare così:


void reverse(int* first, int* end){
if (first>=end) return;
//scambia i due valori
int tmp=0;
tmp=*first;
*first=*end;
*end=tmp;
first++;
end--;
reverse(first,end);
}

ovviamente devi calcolare end a parte scorrendo l'array una volta

In questo modo però si oltrepassa il limite imposto dal fatto che lo stack sia una struttura LIFO, ovvero che l'ultimo elemento inserito sia il primo a dover essere estratto ed è anche l'unico che può essere estratto. Al penultimo non puoi accedere, quindi neppure al primo come nel tuo esempio, se non hai estratto prima tutti quelli "che erano sopra di lui"

Loading