Jak napisać funkcję/procedurę wstawiającą węzeł przed węzłem o podanym kluczu
Będzie mi ona potrzebna później do napisania innej funkcji
Chodzi mi o rozbicie tej funkcji na przypadki oraz o sposób powiązania nowego węzła z węzłami już istniejącymi na liście w każdym z tych przypadków
Wstawianie węzła przed węzłem o podanym kluczu
potrzebne mi jest do następującej funkcji
Utwórz nowy węzeł (zarezerwuj pamięć i przypisz dane)
Wyszukaj na liście węzeł o kluczu większym niż podany
Wstaw nowy węzeł przed wyszukanym węzłem
U Cormena znalazłem taki pseudokod otoczki
1. Let p0 be the point in Q with minimum y-coordinate,
or the leftmost such point in case of a tie
2. Let <p1,p2,...,pm> be remaining points in Q,
sorted by polar angle in counterclockwise order around p0
(if more than one point has the same angle, remove all but
the one that is farthest from p0)
3. Let S be an empty stack
4. PUSH(p0,S)
5. PUSH(p1,S)
6. PUSH(p2,S)
7. for i = 3 to m
8. do while the angle formed by points NEXT-TO-TOP(S),TOP(S)
and pi makes nonleft turn
9. do POP(S)
10. PUSH(pi,S)
11. return S
Jeśli chodzi o punkt pierwszy to musimy szukać minimum ale
ze względu na obydwie współrzędne
Tutaj największy problem może być z punktem 2.
bo trzeba napisać funkcję porównującą zarówno kąty jak i odległość punktu od p0
Kąty można porównywać ze wzoru na pole równoległoboku (rozpisać sobie wyznacznik)
aby uniknąć funkcji cyklometrycznych oraz porównywać kwadraty odległości aby uniknąć pierwiastków
Funkcja porównująca powinna zwracać podobne wartości jak ta np funkcja porównująca łańcuchy w C
problem w tym że powinna porównywać obie wartości na raz
A jeśli chodzi o usuwanie punktów współliniowych to wolałbym je przesunąć na koniec listy
i zwrócić wskaźnik na ostatni węzeł tej części listy bez powtórzeń
Jeśli będziemy umieli stwierdzić czy punkt jest na lewo bądź prawo wektora (tutaj chyba nie jest na lewo)
to nie będziemy mieli problemu z dalszymi punktami
Z punktem 1. chyba sobie poradzę
Największe problemy może stworzyć punkt 2.
Przydałoby się też przypomnieć jak zrealizować warunek dla pętli while w punkcie 8.
Nie chcę korzystać z gotowców z STL