jappoz92
Newbie
Karma: +0/-0
 Scollegato
Messaggi: 8
|
 |
« inserita:: Giugno 20, 2012, 11:41:55 am » |
|
Salve, sto creando una lista in C++ e dovrei creare anche un metodo di sort (a piacere, non importa la complessità) Ho elaborato una cosa del genere ma quando eseguo mi si blocca il programma (non sono sicuro per giunta che la sintassi sia corretta). Qualcuno potrebbe aiutarmi a capire dove è sbagliato ed eventualmente a metterla a posto? Posto il codice void List::Sort( void ){
if( IsEmpty() ){
cout << "Lista VUOTA" << endl;
return;
}
ListNode *currentPtr = firstPtr -> nextPtr;
while( currentPtr != 0 ){
if( currentPtr -> data > currentPtr -> nextPtr -> data ){
int aux = currentPtr -> data;
currentPtr -> data = currentPtr -> nextPtr -> data;
currentPtr -> nextPtr -> data = aux;
}
currentPtr = currentPtr -> nextPtr;
}
return;
}
e qui i prototipi delle classi List e ListNode
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h" //il file dove è definita la classe ListNode (ovvero il singolo nodo della lista)
class List{
public:
List(); // costruttore
~List(); // distruttore
void InserisciCima( const int& ); // inserisce un elemento in cima alla lista
void InserisciFondo( const int& ); // inserisce un elemento in fondo alla lista
bool IsEmpty( void ) const; // restituisce true se la lista è vuota
void Print( void ) const; // stampa a video la lista
bool RimuoviCima( int& ); // rimuove un elemento dalla cima, copia il valore nel nodo passato a parametro e restituisce true se l' operazione va a buon fine
bool RimuoviFondo( int& ); // rimuove un elemento dal fondo, copia il valore nel nodo passato a parametro e restituisce true se l' operazione va a buon fine
bool Search( const int& ); // ricerca il valore passato al metodo e restituisce true se lo trova
void Sort( void ); // algoritmo di sort a piacere
private:
ListNode *firstPtr; // puntatore al primo nodo
ListNode *lastPtr; // puntatore all' ultimo nodo
ListNode *getNewNode( const int& ); // funzione che alloca memoria (facoltativa, per comodità)
};
#endif
#ifndef LISTNODE_H
#define LISTNODE_H
class ListNode{
friend class List; // dichiaro la classe friend di List in modo che la classe List possa aver accesso ai dati memmnro privati di listNode
public:
ListNode( const int& ); // costruttore con parametro un intero per inizializzare il dato membro
int getData( void ) const; // metodo get per recuperare il dato contenuto all' interno del nodo
void setData( int& ); // metodo set per impostare il dato membro del nodo
private:
int data; // dato membro principale (può essere di qualunque tipo, anche una classe)
ListNode *nextPtr; // puntatore al nodo successivo, tipico della struttura ricorsiva (indispensabile)
};
#endif
|
|
|
|
|
Registrato
|
|
|
|
jSte75
Jr. Member
Karma: +4/-0
Scollegato
Messaggi: 71
|
|
« Risposta #1 inserita:: Giugno 20, 2012, 03:01:25 pm » |
|
Ciao, ad uno sguardo veloce (mooolto veloce) direi che c'è un errore nel pezzo di codice: while( currentPtr != 0 ){
if( currentPtr -> data > currentPtr -> nextPtr -> data ){ Il test del while non da' alcuna garanzia che currentPtr -> nextPtr sia valorizzato, quindi quando raggiungi la fine lista nextPtr è nullo e quindi si genera un errore. Stefano |
|
|
|
|
Registrato
|
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #2 inserita:: Giugno 20, 2012, 03:08:09 pm » |
|
Intanto grazie della risposta, ho capito quello che vuoi dire, però se fosse così non mi darebbe l' errore alla fine del programma? (Io nel main dopo il metodo sort chiamo il metodo print per vedere la lista ordinata e a quel punto si blocca proprio il programma e windows mi da un errore.) Se fosse così almeno la lista fino a n - 1 me la dovrebbe far vedere no? Secondo te come posso fare per ovviare a questa cosa? Grazie ancora per l'attenzione, saluti  |
|
|
|
|
Registrato
|
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #3 inserita:: Giugno 22, 2012, 02:13:10 pm » |
|
Nessuna idea? Tra l' altro dovrei anche calcolarne la complessità che così a naso mi sembra O(n^2)...
|
|
|
|
|
Registrato
|
|
|
|
|
pancry777
|
|
« Risposta #4 inserita:: Giugno 22, 2012, 02:21:22 pm » |
|
 tutte le strutture sequenziali come le liste, file ecc.. si ordinano solo con il merge sort
|
|
|
|
|
Registrato
|
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #5 inserita:: Giugno 22, 2012, 02:34:40 pm » |
|
Nel esercizio del mio esame la consegna era di implementare una lista con vari metodi, di cui uno di sort a piacere e di calcolarne la complessità... forse te volevi dire che il migliore dal punto di vista computazionale è il merge sort?
|
|
|
|
|
Registrato
|
|
|
|
|
Roberto Allegra
|
|
« Risposta #6 inserita:: Giugno 22, 2012, 02:48:54 pm » |
|
Se fosse così almeno la lista fino a n - 1 me la dovrebbe far vedere no? Direi di no: se la stampa la fai dopo l'ordinamento, l'errore avverrà prima del primo messaggio. Il problema è molto probabilmente quello evidenziato da jSte75. Come ovviare è semplice: verifica anche che il successore non sia nullo, nella condizione di uscita del ciclo while. Il suggerimento è comunque di usare un debugger qualsiasi per verificare cosa succede durante l'esecuzione La complessità computazionale è quella tipica del bubble sort, che viene spiegato - spesso per primo, dato che è semplice e notoriamente inefficiente - in tutti i testi di Algoritmi e Strutture dati. Studia bene come funziona, perché l'implementazione che hai realizzato nel codice è solo parziale. |
|
|
|
|
Registrato
|
I moderatori invitano tutti gli utenti a prendere visione del REGOLAMENTO e a rispettarlo.
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #7 inserita:: Giugno 22, 2012, 05:24:27 pm » |
|
Grazie per l' aiuto, ho modificato il while come segue ed effettivamente ora non si blocca e stampa tutto while( ( currentPtr != 0 ) && ( currentPtr -> nextPtr != 0 ) )
C'è comunque ancora un problema che non riesco a identificare per il quale il metodo mi mette in ordine solo l' elemento più piccolo e il più grande ma gli altri non li scambia, è come se facesse solo un ciclo. Per esempio se io immetto nella lista 9 2 7 3 6 6 5 6 Chiamando il metodo sort e stampando la lista dopo mi restituisce una lista fatta così: 2 7 3 6 6 5 6 9 Ho controllato sul libro e mi sembra che il concetto (per quanto riguarda il bubblesort) sia giusto, non è un algoritmo per nulla complicato eppure mi sta dando diversi problemi. |
|
|
|
|
Registrato
|
|
|
|
|
Roberto Allegra
|
|
« Risposta #8 inserita:: Giugno 23, 2012, 06:15:03 pm » |
|
Ho controllato sul libro e mi sembra che il concetto (per quanto riguarda il bubblesort) sia giusto, non è un algoritmo per nulla complicato eppure mi sta dando diversi problemi. Come ti ho scritto, l'implementazione che hai fornito è solo parziale. Come hai già capito, il problema è che svolgi un solo "passaggio" di ordinamento, mentre il tutto dev'essere messo in un ciclo che continui finché non si verificano più scambi. Leggi bene l'implementazione del bubble sort, sul tuo libro di testo o su una qualunque fonte decente. |
|
|
|
|
Registrato
|
I moderatori invitano tutti gli utenti a prendere visione del REGOLAMENTO e a rispettarlo.
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #9 inserita:: Giugno 24, 2012, 12:06:41 pm » |
|
Ho controllato sul libro e mi sembra che il concetto (per quanto riguarda il bubblesort) sia giusto, non è un algoritmo per nulla complicato eppure mi sta dando diversi problemi. Come ti ho scritto, l'implementazione che hai fornito è solo parziale. Come hai già capito, il problema è che svolgi un solo "passaggio" di ordinamento, mentre il tutto dev'essere messo in un ciclo che continui finché non si verificano più scambi. Leggi bene l'implementazione del bubble sort, sul tuo libro di testo o su una qualunque fonte decente. Allora io so che il bubblesort di solito viene implementato (per gli array) con due cicli for. Il problema è che qua io ho una lista, e non so a priori quanto è grande questa lista essendo una struttura dinamica. Ho pensato di fare un secondo while più esterno, perchè il primo mi assicura solo un giro, però non saprei proprio quale condizione potrei inserire all' interno di questo secondo while... |
|
|
|
|
Registrato
|
|
|
|
|
pancry777
|
|
« Risposta #10 inserita:: Giugno 24, 2012, 01:57:42 pm » |
|
metti una metodo che ti dice se è l'ultimo elemento della lista e lo fai di tipo boolean
|
|
|
|
|
Registrato
|
|
|
|
|
Roberto Allegra
|
|
« Risposta #11 inserita:: Giugno 24, 2012, 01:57:55 pm » |
|
Non importa se siano vettori, liste, o quant'altro, né se la dimensione è nota o meno. Ripeto: il tutto dev'essere messo in un ciclo che continui finché non si verificano più scambi. Una volta detto questo l'implementazione è veramente banale. Rinnovo l'invito a leggere almeno lo pseudocodice dato da una qualunque fonte decente, perfino wikipedia italiana (che comunque, a quanto vedo, non si smentisce. Ci sono almeno tre strafalcioni, solo nella sezione che ho guardato...  ). |
|
|
|
|
Registrato
|
I moderatori invitano tutti gli utenti a prendere visione del REGOLAMENTO e a rispettarlo.
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #12 inserita:: Giugno 24, 2012, 03:25:48 pm » |
|
Intanto grazie per la pazienza e la disponibilità Roberto, però io proprio non ci arrivo anche se è una banalità. Ho capito quello che vuoi dire, ovvero che il ciclo deve continuare finchè si effettuano scambi, ma non saprei come mettere questa condizione in un while. Mi spiego meglio... Col codice in questa forma while( ){
while( ( currentPtr != 0 ) && ( currentPtr -> nextPtr != 0 )){
if( (currentPtr -> data) > (currentPtr -> nextPtr) -> data ){
int aux = currentPtr -> data;
currentPtr -> data = currentPtr -> nextPtr -> data;
currentPtr -> nextPtr -> data = aux;
}
currentPtr = currentPtr -> nextPtr;
}
currentPtr = firstPtr;
}
return;
}
ho pensato di aggiungere un while più esterno (con argomento ignoto per adesso ) che azzeri il puntatore in modo da scorrere sempre dall' inizio il ciclo. Quello che non capisco è come imporre la condizione che continui a farlo finchè scambia. Guiardando lo pseudocodice di wikipedia mi è venuto in mente di mettere il corpo dell' if all' interno di una funzione "scambio" che ritorni true se fa qualcosa e false se non fa niente, e in questo modo potrei scrivere while(scambio) ecc però volevo cercare di capire come fare senza usare questo escamotage... |
|
|
|
|
Registrato
|
|
|
|
|
Roberto Allegra
|
|
« Risposta #13 inserita:: Giugno 24, 2012, 04:55:13 pm » |
|
Guiardando lo pseudocodice di wikipedia mi è venuto in mente di mettere il corpo dell' if all' interno di una funzione "scambio" che ritorni true se fa qualcosa e false se non fa niente Non serve una funzione: è sufficiente dichiarare una variabile booleana all'esterno del ciclo (tipo "bool haFinito"), che viene posta a true all'inizio del ciclo più interno e a false quando avviene uno scambio. Non è un escamotage: è l'implementazione più classica dell'algoritmo di bubble-sort. Poiché un'iterazione dev'essere fatta per forza, puoi usare un do..while(!haFinito). |
|
|
|
|
Registrato
|
I moderatori invitano tutti gli utenti a prendere visione del REGOLAMENTO e a rispettarlo.
|
|
|
jappoz92
Newbie
Karma: +0/-0
Scollegato
Messaggi: 8
|
|
« Risposta #14 inserita:: Giugno 24, 2012, 05:22:26 pm » |
|
Guiardando lo pseudocodice di wikipedia mi è venuto in mente di mettere il corpo dell' if all' interno di una funzione "scambio" che ritorni true se fa qualcosa e false se non fa niente Non serve una funzione: è sufficiente dichiarare una variabile booleana all'esterno del ciclo (tipo "bool haFinito"), che viene posta a true all'inizio del ciclo più interno e a false quando avviene uno scambio. Non è un escamotage: è l'implementazione più classica dell'algoritmo di bubble-sort. Poiché un'iterazione dev'essere fatta per forza, puoi usare un do..while(!haFinito). Eureka finalmente mi funziona! Grazie mille ancora, per dovere di cronaca posto il codice finale... magari un domani potrebbe servire a qualcuno void List::Sort( void ){
bool fine;
if( IsEmpty() ){
cout << "Lista VUOTA" << endl;
return;
}
ListNode *currentPtr = firstPtr;
do{
fine = true;
while( ( currentPtr != 0 ) && ( currentPtr -> nextPtr != 0 )){
if( (currentPtr -> data) > (currentPtr -> nextPtr) -> data ){
int aux = currentPtr -> data;
currentPtr -> data = currentPtr -> nextPtr -> data;
currentPtr -> nextPtr -> data = aux;
fine = false;
}
currentPtr = currentPtr -> nextPtr;
}
currentPtr = firstPtr;
}while(!fine);
return;
}
|
|
|
|
|
Registrato
|
|
|
|
|
Messaggi recenti
