[C] Invertire Stack In Place (Senza Vettore di Appoggio)

[Skull260287]

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]

Nessuno ha qualche idea?

[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

[Skull260287]

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"