Alfabetyczne sortowanie listy w drzewie
Ostatnio zmodyfikowano 2018-01-07 23:19
4ever4 Temat założony przez niniejszego użytkownika |
Alfabetyczne sortowanie listy w drzewie » 2018-01-07 17:45:27 Witam mam problem, z którym nie potrafię sobie poradzić. Chodzi o to,aby wczytać dane z pliku do listy, sortując ją alfabetycznie. przykładowy plik wejściowy: gr1 kokos wlasciwy gr2 mamutowiec olbrzymi gr5 jesion wyniosly gr8 dab japonski gr4 wawrzyn szlachetny gr2 baobab afrykanski gr1 jodla pospolita gr1 sosna wejmutka plik wyjściowy powinien być postaci: gr1 jodla pospolita kokos wlasciwy sosna wejmutka gr2 baobab afrykanski mamutowiec olbrzymi gr4 wawrzyn szlachetny gr5 jesion wyniosly gr8 dab japonski Napisałem program wykorzystujący drzewo i listę. Wczytując zawartość pliku do listy, jeśli program napotka wyraz mniejszy od pierwszego na liście, to dany wyraz dokłada na początek listy. Natomiast, jeśli napotka większy od pierwszego na liście, to dokłada go na koniec listy. Przy takich warunkach program działa poprawnie. Natomiast jeśli dołożę warunek, aby lista była sortowana alfabetycznie-program nie działa(kompiluje się, ale crashuje). Prosiłbym o wskazanie przyczyny występowania takiej sytuacji i jak można temu zapobiec, ponieważ nie mam pomysłu jak to zrobić. Poniżej przesyłam mój kod: #include <iostream> #include <conio.h> #include <Windows.h> #include <fstream> #include <string>
using namespace std; fstream plik;
struct lista { string dana_reszta1; string dana_reszta2; lista * nastepna; };
struct wezel { string dana; lista * glowa; wezel * lewe; wezel * prawe; };
void drukuj_drzewo( wezel * korzen ) { if( korzen != nullptr ) { drukuj_drzewo( korzen->lewe ); cout << korzen->dana << endl; lista * wsk = korzen->glowa; while( wsk != nullptr ) { cout << wsk->dana_reszta1 << " " << wsk->dana_reszta2 << endl; wsk = wsk->nastepna; } cout << endl; drukuj_drzewo( korzen->prawe ); } }
void wstaw_drzewo_i_liste( wezel *& korzen, string zdanie1, string zdanie2, string zdanie3 ) { if( korzen == nullptr ) { korzen = new wezel; korzen->dana = zdanie1; korzen->lewe = nullptr; korzen->prawe = nullptr; korzen->glowa = new lista; korzen->glowa->dana_reszta1 = zdanie2; korzen->glowa->dana_reszta2 = zdanie3; korzen->glowa->nastepna = nullptr; } else if((( zdanie1.length() > korzen->dana.length() ) ||(( zdanie1 > korzen->dana ) &&( zdanie1.length() >= korzen->dana.length() ) ) ) &&( zdanie1 != korzen->dana ) ) { wstaw_drzewo_i_liste( korzen->prawe, zdanie1, zdanie2, zdanie3 ); } else if((( zdanie1.length() < korzen->dana.length() ) ||(( zdanie1 < korzen->dana ) &&( zdanie1.length() <= korzen->dana.length() ) ) ) &&( zdanie1 != korzen->dana ) ) { wstaw_drzewo_i_liste( korzen->lewe, zdanie1, zdanie2, zdanie3 ); } else { if( korzen->dana == zdanie1 ) { lista * nowa = new lista; nowa->dana_reszta1 = zdanie2; nowa->dana_reszta2 = zdanie3; if(( nowa->dana_reszta1 ) <( korzen->glowa->dana_reszta1 ) ) { nowa->nastepna = korzen->glowa; korzen->glowa = nowa; } else { lista * wsk = korzen->glowa->nastepna; nowa->nastepna = korzen->glowa; while((( wsk->dana_reszta1 ) <( nowa->dana_reszta1 ) ) &&( wsk != nullptr ) ) { wsk = wsk->nastepna; nowa->nastepna = nowa->nastepna->nastepna; } nowa->nastepna->nastepna = nowa; nowa->nastepna = wsk; } } else if( korzen->dana > zdanie1 ) wstaw_drzewo_i_liste( korzen->lewe, zdanie1, zdanie2, zdanie3 ); else wstaw_drzewo_i_liste( korzen->prawe, zdanie1, zdanie2, zdanie3 ); } }
int main() { string zdanie1; string zdanie2; string zdanie3; plik.open( "dane.txt", ios::in ); wezel * korzen = nullptr; while( !plik.eof() ) { plik >> zdanie1 >> zdanie2 >> zdanie3; wstaw_drzewo_i_liste( korzen, zdanie1, zdanie2, zdanie3 ); } drukuj_drzewo( korzen ); _getch; system( "pause" ); return 0; }
|
|
pekfos |
» 2018-01-07 19:37:19 while((( wsk->dana_reszta1 ) <( nowa->dana_reszta1 ) ) &&( wsk != nullptr ) )
|
Kolejność warunków ma znaczenie. Te wsk != nullptr w tym momencie nic nie robi. |
|
4ever4 Temat założony przez niniejszego użytkownika |
» 2018-01-07 23:15:02 Dzięki za odpowiedź. Po zamianie warunków program działa prawidłowo. Nie wiedziałem, że kolejność warunków ma znaczenie. Po przeanalizowaniu doszedłem do wniosku, że masz racje. Program sprawdzając pierwszy warunek chciał odczytać wartość z pod nieprzydzielonej pamięci, więc stąd ten błąd. Zamieniając kolejność warunków program sprawdza pierwszy warunek (wsk != nullptr) który jest nieprawdziwy, więc zatrzymuje się sprawdzanie warunków pętli while, dzięki czemu nie zostaje odczytana nieprzydzielona pamięć. Czy dobrze to rozumuje? |
|
pekfos |
» 2018-01-07 23:19:52 Tak. |
|
« 1 » |