C++ - sortowanie elementów listy jednokierunkowej

Dla specjalistów Programowanie
#1

Witam serdecznie,

Mam problem ze zrealizowaniem zadanego polecenia. Mój program ma wczytywać z pliku do listy jednokierunkowej współrzędne par punktów, będących punktami początkowymi i końcowymi odcinków. I z tą częścią sobie poradziłam. Jednak teraz dysponuję listą jednokierunkową, zawierającą elementy o polach „x1”, „y1”, „x2”, „y2” oraz wskaźnik na element następny i muszę napisać funkcję, która dokonałaby posortowania elementów listy względem współrzędnej x końca odcinka (czyli pola “x2”) w porządku rosnącym, jednak niestety nie bardzo wiem jak to zrobić. Próbowałam coś wymyślić, ale chyba jednak nie doszłam do niczego sensownego. Bardzo proszę o pomoc. Na innym forum znalazłam taki schemat postępowania.

Rozumiem co należy robić krok po kroku, ale nie potrafię tego zapisać. Przy próbach realizacji w końcu gubię się w tym co piszę. Patrząc na punkt 6 rozumiem, że to ma działać rekurencyjnie, tak? Bardzo proszę o pomoc, potrzebuję tego na jutro, a już nie bardzo wiem jak to rozpisać. Może istnieje jakiś inny, dość przystępny sposób wykonania tego sortowania?

Pozdrawiam i z góry dziękuję za ewentualną pomoc

#2

Rozdziel problem na mniejsze problemy.

Najpierw sobie dopisz do swojej struktury danych (listy jednokierunkowej) metodę zamiany elementów na liście.

Jak będziesz miał taką metodę to pozostaje Ci tylko zaimplementować algorytm sortowania, który używa swapowania, pamiętając, że wartością jest x2 z elementu listy.

#3

Mógłbyś to jakoś bardziej rozwinąć, tak bardziej łopatologicznie? Bo nie do końca chyba rozumiem co mam zrobić, to moje początki z programowaniem.

#4

Masz jakąś strukturę do przechowywania listy jednokierunkowej. Na początek dodaj do tej struktury operację zamiany elementów.

Jeśli masz to zrobione jako klasę - dodaj metodę.

Jeśli masz to na funkcjach - dodaj funkcję.

#5

Nie uważasz, że naukę lepiej zaczynać od początku a nie środka? :wink:

#6

Powiem tak, na zajęciach mieliśmy podstawy podstaw. Teraz dostajemy do zrealizowania programy, które nijak mają się do tego, co robiliśmy wcześniej. Dlatego szukam pomocy, bo sama nie jestem w stanie zastosować pewnych algorytmów.

#7

Pokaż jak implementujesz listę jednokierunkową.

#8 
struct SLista

            {

                int x1;

                int y1;

                int x2;

                int y2;

                SLista *next;

            };


void wczytaj (string nazwa)

{

    ifstream dane;

    ofstream wsp_x ("wsp_x.txt");

    ofstream wsp_y ("wsp_y.txt");

    dane.open (nazwa.c_str());

    if( !dane.good() )

            cout << "Otwarcie pliku nie powiodlo sie" << endl;


    string wiersz;

    int x1, y1, x2, y2;



    while (!dane.eof())

            {

                dane >> x1 >> y1 >> x2 >> y2;

                wsp_x << x1 << endl << x2 << endl;

                wsp_y << y1 << endl <
            }

    dane.close();

}



void tworzliste(SLista *&glowa)

{

        SLista *aktualny;

        SLista *ogon;

        int x, y;

        ifstream wsp_x;

        wsp_x.open ("wsp_x.txt");

        ifstream wsp_y;

        wsp_y.open ("wsp_y.txt");

        aktualny=NULL;

        glowa=NULL;

        wsp_x >> x;

        wsp_y >> y;

        while(!wsp_x.eof() && !wsp_y.eof())

        {

                ogon=aktualny;

                aktualny=new SLista;

                aktualny->x1=x;

                aktualny->y1=y;

                wsp_x >> x;

                wsp_y >> y;

                aktualny->x2=x;

                aktualny->y2=y;

                if(ogon==NULL)

                glowa=aktualny;

                else

                ogon->next=aktualny;

                aktualny->next=NULL;

                wsp_x >> x;

                wsp_y >> y;

        }

        wsp_x.close();

        wsp_y.close();

}



void drukujliste(SLista *glowa)

{ SLista *aktualny;

    aktualny=glowa;

    while(aktualny!=NULL)

    {

        cout<x1<<" "<y1<<"\t"<x2<<" "<y2<
        aktualny=aktualny->next;

    }

}

na razie mam coś takiego

#9

No to teraz napisz funkcję swap_elements(SLista element1, SLista element2) po prostu zamieniając pole next w obu listach pamiętając o szczególnych przypadkach (pierwszym i ostatnim elemencie).

Potem już tylko implementujesz sortowanie używając funkcji swap_elements do zamiany miejsc.

#10

czyli ta funkcja swap_elements ma zamieniać ze sobą jedynie pola next elementu1 i elementu2? przepraszam, jeśli źle to rozumiem, ale nigdy nie używałam funkcji swap

#11

Tak - tylko zwróć uwagę na te rzeczy o których pisałem.

I takie pytanie, po co Ci zmienna adres? Nie używasz jej.

#12

Dobrze, zaraz będę próbować zrealizować Twoje wskazówki, dziękuję.

Fakt, oczywiście jest tam niepotrzebna, wpisałam ją przy abstrakcyjnym kombinowaniu z tym sortowaniem i po prostu zapomniałam potem usunąć.

#13

Witam,

Poczytaj sobie o bubble sort, przy liście jednokierunkowej powinno to być łatwe w realizacji, tak jak już koledzy pisali potrzebujesz funkcji która zamienia kolejnością elementy na liście.

Pozdrawiam,

mr-owl

#14

Najprościej chyba będzie zrobić sortowanie przez wybór. Najpierw tworzysz sobie pustą listę posortowaną, potem wyszukujesz największy element, usuwasz z początkowej listy i dodajesz na początek posortowanej, powtarzasz dopóki początkowa lista nie będzie pusta.

Przykład:

void sortuj(SLista*& l)

{

	SLista* n = 0;

	while(l)

	{

		SLista *max = l, *pmax = 0;

		for(SLista *p = l, *i = l->next; i; p = i, i = i->next)

			if(i->x2 >= max->x2)

				max = i, pmax = p;

		if(pmax)

			pmax->next = max->next;

		else

			l = max->next;

		max->next = n;

		n = max;

	}

	l = n;

}

Jeśli rzeczywiście dostajecie zadania znacznie przekraczające to czego was uczyli to lepiej żebyś nauczyła się programować we własnym zakresie. Polecam:

W kilka tygodni powinnaś ogarnąć najważniejsze rzeczy :slight_smile:

#15

Czyli funkcja swap, którą ma potem wykorzystywać algorytm sortowania ma wyglądać tak, dobrze rozumiem? Czy powinna zawierać coś jeszcze?

void swap_elements(SLista *element1, SLista *element2)

{

    swap (element1->next, element2->next);

}

Mogłabym prosić o pomoc z zaimplementowaniem algorytmu sortowania? Nie mogę się w tym połapać, tzn jeśli chodzi o sortowanie bąbelkowe, to jak to jest, na samym początku muszę zliczyć ilość elementów listy do posortowania i potem zastosować pętlę for? Czy jakoś inaczej to trzeba zrobić? Staram się to zrozumieć i ogólnie ćwiczę sobie pisanie różnych programów w oparciu o różne materiały pomocnicze, ale ten muszę zrobić akurat na jutro, a nigdy nie stosowałam tego typu algorytmów.

#16

Olej powyższe porady poza tą udzieloną przez @Rolek0. Znajdujesz max i przenosisz do pustej listy (łatwy, indukcyjny dowód, że działa).

PS

struct SLista

            {

                int x1;

                int y1;

                int x2;

                int y2;

                SLista *next;

            };

Co znaczą u ciebie inty, bo mi to wygląda na jakieś odcinki/wektory. Musisz w ogóle zacząć od zdefiniowania porządku to jest aby posortować jakiś zbiór musisz wiedzieć kiedy element jest mniejszy od innego.

#17

To są współrzędne punktów: (x1,y1) - początek odcinka, (x2, y2) - koniec odcinka. Czyli w ogóle źle to rozumiem?

#18

Tu nie ma co rozumieć, to ja ciebie pytam co chcesz reprezentować.

Jeśli odcinki, to powiedz mi jak chcesz ustalić porządek odcinków? To znaczy kiedy odcinek AB jest mniejszy w sensie relacji porządku od odcinka CD?

#19

Ale to jest konieczne? Moim zadaniem jest posortować te pary punktów (tzn. odcinki) względem współrzędnej x-owej końca odcinka (czyli w moim przypadku x2).

#20

Ach, nie zwróciłem uwagi w pierwszym poście, że masz zdefiniowany porządek (własnie jako x2). No to w sumie pozostaje użyć kodu który podał ci @Rolek0.