Ordinare stack

5 Risposte

• B

  bottomap

  Utente Attivo

  Iscritto da

  mar, 2004

  Messaggi:

  312

  Re: Ordinare stack

  14 dic 2007, 20:14

  Ciao,
  
  Caso mai in maniera decrescente... ad ogni modo dovresti specificare meglio:
  1) Di che tipo di stack stai parlando
  2) Con cosa è implementato (liste, vettori o altro)
  3) Che senso ha volerlo ordinare (lo stack è una struttura nata per determinate operazioni FIFO. Se trovi necessario ordinarne il contenuto, con buona sicurezza hai sbagliato nella scelta della struttura).
  4) Che significato dai a "ordinato in maniera decrescente". Dipende da che "direzione" dai allo stack, ovvero se pensi che gli elementi minori debbano stare in testa o in coda.
  
  Nel caso sia implementato con liste o vettori è comunque sufficiente un qualsiasi algoritmo di ordinamento che operi su di essi (hai l'imbarazzo della scelta).
  
  Ciaociao
• H

  half

  Pochi posts

  Iscritto da

  ott, 2007

  Messaggi:

  22

  Re: Ordinare stack

  14 dic 2007, 20:19

  Lo stack implementato con un arrray di MAX caratteri.. il senso di ordinarlo non c'e'...
  e solo un esercizio dato dal prof ad un compito..
  e dice solo di ordinare lo stack in maniera non descrescente.
• B

  bottomap

  Utente Attivo

  Iscritto da

  mar, 2004

  Messaggi:

  312

  Re: Ordinare stack

  15 dic 2007, 11:18

  Ciao,
  
  Beh, allora come detto (un vettore di MAX caratteri) è sufficiente un qualsiasi algoritmo di base per l'ordinamento dei vettori...
  
  Dal selection sort, all'insertion sort, al bubble sort al quicksort (il qsort l'hai direttamente tra le funzioni di libreria, gli altri puoi trovare indicazioni sull'implementazione praticamente dappertutto - da internet a qualsiasi libro di programmazione).
  
  Nell'implementazione più semplice (farai N*N confronti e scambi - le prestazioni non sono buone, ma per vettori "piccoli" può ancora andare) farai una doppia for (indici i e j diciamo)... confronti l'elemento i con tutti gli elementi j>i, se l'elemento i è maggiore di j li scambi e continui. In questo modo in i avrai sempre l'elemento minore tra i successivi.
  Visto che i parte da 0, porterai in posizione 0 il minore di tutti i j>=0 (quindi il minore di tutti), quindi passi ad 1 e ci inserisci il minore tra i j>=1, e così via... al termine delle iterazioni avrai il vettore ordinato (in 0 il minore in N-1 il maggiore).
  
  Ciaociao
• H

  half

  Pochi posts

  Iscritto da

  ott, 2007

  Messaggi:

  22

  Re: Ordinare stack

  15 dic 2007, 11:36

  Si ma nn posso effettuare scambi..perche posso usare solo le funzioni di libreria stack(pop,push..).gli accessi diretti all array vengono considerati errori..e posso utilizzare solo un numero costante di stack d appoggio...
• B

  bottomap

  Utente Attivo

  Iscritto da

  mar, 2004

  Messaggi:

  312

  Re: Ordinare stack

  15 dic 2007, 12:23

  Ciao,
  
  Beh... queste informazioni le dovevi dare nel primo post... usando degli stack di appoggio e solo le operazioni sugli stack la cosa si può complicare non poco (oltre ad essere un'operazione inutile, ma questo l'abbiamo già appurato).
  
  Per uno spunto dai un'occhiata all'algoritmo di risoluzione delle torri di hanoi... cerca di immaginare su quali basi lavora (non tanto quello che fa, ma come ottiene di spostare n cerchi utilizzando 3 paletti soltanto).
  In più dai un'occhiata anche a come funziona lo stack nel calcolo delle espressioni in notazione polacca inversa.
  
  Ciaociao