[C/C++] Sortowanie listy jednokierunkowej


(Rdrfear) #1

Witam. Następny problem pojawił się na mojej drodze podczas pisania kolejnego programu.

Zadaniem jest napisanie listy jednokierunkowej, która będzie wczytywała nowy obiekt: liczbę i literę, aż wpiszemy 0.

Potem ma posortować listę według kolejności liczb, a jeśli liczby są takie same to według kolejności liter w alfabecie (i z tą funkcją mam największy problem).

Potem wyświetla listę i zwalnia zajętą pamięć.

Proszę o delikatną pomoc z sortowaniem i sprawdzeniem programu.

Dzięki z góry.


(Kubakuderski) #2

Jeżeli może być na zwykłych listach i parach, tak na szybko:

#include 

#include 

#include 


using namespace std; 


int main()

{ 

   list > jakasnazwa;

   int i;

   char u;


   while(1)

   {

      cin >> i;

      if(i!=0)

      {

         cin >> u;

         jakasnazwa.push_back(make_pair(i,u));

      } else {

         break;

      }

   }

   jakasnazwa.sort();


   for(list >::iterator it = jakasnazwa.begin(); it != jakasnazwa.end(); it++)

      cout << it->first << " " << it->second << endl;


   jakasnazwa = list >(0);

   return 0; 

}

Jeżeli koniecznie muszą być kolejki, to po prostu przepisałbym listę do kolejki, bo kolejkę trudno posortować.


(Rdrfear) #3

Problem w tym, że nie wolno mi stosować tablic ani pojemników z biblioteki standardowej (z tego względu zabronione są „słowa” [,], vector, set, map, list).


(Kubakuderski) #4

Jak dokładnie brzmi treść zadania?


(Rdrfear) #5

Program wczytujący z klawiatury pary złożone z dodatniej liczby całkowitej oraz małej litery i tworzący z każdej podanej pary element listy pojedynczo wiązanej (przechowuje on powyższe dane oraz odnośnik do następnego elementu listy). Kresem wczytywania danych jest podanie jako liczby wartości zerowej, a wtedy litera nie jest już wczytywana i ostatnią daną dołożoną do listy jest ostatnia pełna para złożona z liczby dodatniej i małej litery. Lista ma być tak budowana, by kolejność elementów w liście była rosnąca względem liczby, a przy równych liczbach względem litery. Na koniec program wypisuje otrzymaną listę w pojedynczych liniach umieszczając najpierw liczbę a po spacji literę, a następnie zwalnia całą użytą pamięć.


(Drobok) #6

Jeśli sprawdzasz następny element to sprawdzaj też null następnego bo się sypnie przy końcu sortowania. Zamieniaj wskaźniki a nie dane. Jeśli if się nie sprawdzi, zmieniaj na następny element, bo się będzie zapętlać, dlaczego dajesz next do head ?? :slight_smile:

Tyle na pierwszy rzut oka, pewnie coś jeszcze wyjdzie w praniu :slight_smile:


(Rdrfear) #7

Rozumiem, że head nie powinno się zmieniać, ale w poszczególnych funkcjach będzie się zmieniało tylko lokalnie prawda?

Wziąłem pod uwagę porady i oto poprawiony kod(tylko nie wiem czy dobrze zrozumiałem aluzje)


(Drobok) #8

Wywaliłbym ten wskaźnik z argumentów wszystkich funkcji, twój while(1) jest bez sensu. Wystarczy użyć:

do

{

   cin >> i;

   cin >> u;

   Dodaj(i, u);

}while(i!=0);

Nie masz żadnego wskaźnika na początek listy (więc jej nie posortujesz, bo nie masz od czego zacząć). Właśnie jego powinieneś przypisać do wskaźnika tymczasowego, po czym to nim poruszać się po liście przy sortowaniu. Jeśli warunek obecny->next->next==null przerywasz. A jeśli nie sprawdzasz jak się mają do siebie. Musisz sprawdzać 2 do przodu, bo nie będziesz miał jak zamienić wskazywanego elementu.

Sprawdzasz 2 i 3 będąc na 1:

1 2 3 4

1 ma wskazywać na 3

2 ma wskazywać na 4

3 ma wskazywać na 2

Zamieniasz wszystko korzystając z z zmiennej temp dla 3. Jak nie pomieszać adresów pozostawiam tobie :slight_smile: Btw teraz tylko raz przechodzisz listę, musisz to zrobić tyle razy, aż wszystko będzie posortowane :slight_smile:


(Rdrfear) #9

Poprawiłem sortowanie i usunąłem wskaźnik z argumentów, utworzyłem także wskaźnik na pierwszy element i w funkcjach posługuje się wskaźnikiem pomocniczym. Żeby sortowanie listy przebiegało więcej razy, muszę chyba użyć pętli for. W funkcji "Dodaj" policzyć ile mam danych, a potem w "Sort" wrzucić przed pętlę while, pętlę for, dla i<(n-1) elementów.


(Drobok) #10

Nie masz używać for'a, tylko do, while 2x z jakąś zmienną bool. Co robi to ile w funkcji dodaj ? Nie trzeba nic liczyć. Nie obsługujesz pierwszego dodania :slight_smile: Funkcja usuń, nie usuwa jednego elementu, więc nie ma sensu, musisz podmienić wskaźniki (coś jak w sortowaniu). Czyszczenie pamięci robisz robisz za pomocą destruktora.


(Rdrfear) #11

Poprawiłem sortowanie w kodzie:

Teraz została już tylko funkcja 'Usuń'.

I tu mam pytanie, którego elementu nie usuwa ta funkcja? Ostatniego? Muszę przemyśleć to jeszcze.

Możliwe, że zaraz na coś wpadnę to podam gotowy kod do sprawdzenia.

Dzięki wielkie.

Mam prośbę, żeby ktoś sprawdził czy program działa poprawnie i kompiluje się. U mnie na windzie za każdym razem (od jakichś 3 dni) na Geany z MinGW podczas kompilacji Geany się wiesza. Dzięki.

Jeszcze jedna rzecz: to pierwszy element się nie kasuje. Czy w funkcji 'Usun' nie wystarczy po pętli napisać "delete poczatek;"?


(Drobok) #12

Usuwać ma ci wszystko po zakończeniu korzystania z programu (ponieważ zostawiasz wszystko w pamięci). Musisz usuwać wszystko od pierwszego elementu, zapisując z zmiennej tymczasowej adres następnego elementu do usunięcia :slight_smile:

A co do kompilacji mylisz wskaźniki ze stringami, więc nie ma prawa do działania :slight_smile:


(Rdrfear) #13

Funkcja Usuń usuwa teraz wszystkie węzły listy.

Sortowanie wskaźnikami mi nie wychodziło, więc po prostu zmieniam wartości danych w sortowaniu.

Poprawiłem też funkcję dodającą kolejne węzły. Teraz wszystko działa elegancko.

Dzięki!

brobok, dzięki za podpowiedzi, piwko bym postawił.