Znajdź błąd w kodzie Mariusz: struct node{ int key; struct node *next; }; void ListInsert(struct node **L,int x) { struct node *px; struct node *y; struct node *z; px=(struct node *)malloc(sizeof(struct node)); px−>data=x; if((*L)==NULL) { (*L)=px; x−>next=NULL; } else { y=(*L); z=NULL; while(y!=NULL && x−>key>y−>key) { z=y; y=y−>next; } px−>next=y; z−>next=px; } }

a: a na samym poczatku w definicji to nie powinno byc juz node *next ? zamiast struct node *next?

Mariusz: oczywiście x−>next=NULL to literówka i powinno tam być px−>next=NULL

Mariusz: a: myśl dalej Jeden błąd to literówka , wyżej go wypisałem Jako podpowiedź co jest nie tak mogę dodać że węzły z kluczem większym od klucza w węźle wskazywanym przez głowę zdaje się wstawiać poprawnie a: możesz nie pisać stale słówka struct jeśli dasz typedef

jc: Co to jest "data" ? czy to też literówka? Dlaczego nie napiszesz po prostu 0, tylko NULL?

Mariusz: data to jest pozostałość po starej nazwie pola danych To też łatwo wychwycić

Sawyer: A gdzie jest inicjalizowana wartość klucza którą porównuje pętla while?

Sawyer: Jeśli Twój kod ma za zadanie wstawiać elementy na przykład na środku listy i nadawać im unikalny klucz wewnętrzny, to przecież należy po wstawieniu elementu pozmieniać wszystkie klucze węzłów znajdujących się za właśnie wstawionym węzłem. Jeśli natomiast ma po prostu wstawiać w dane miejsce np. a−>b−>c−>d, wstaw literę "e" na 2 pozycji: a−>b−>e−>c−>d, to zmienna klucz jest do niczego. Nie ma sensu aktualizować jej, wystarczy zliczać obroty pętli przy przechodzeniu przez listę, a potem zmieniać wskaźniki węzła poprzedniego i następnego. No i dlaczego zmienna L jest wskaźnikiem na wskaźnik to ja nie wiem. Jeśli chcesz zamknąć całą listę w jednym obiekcie to stwórz strukturę listy wewnątrz której jest zagnieżdżona struktury węzłów. Teraz jest tak że zmienna L wskazuje na miejsce w pamięci wskaźnika który wskazuje na obiekt typu node, nie do końca wiem czemu. Możliwe że gadam niestworzone głupoty, jeśli tak proszę mnie poprawić.

Sawyer: W C++ widziałbym to tak: #include <iostream> #include <new.h> #include <conio.h> using namespace std; struct node{ node *next; int data; }; void ListInsert(node *&ListHead, int insertPosition, int data) { /* Stworzenie nowego węzła */ node *newNode; newNode = new node; newNode−>data = data; //utworzenie głowy jeśli nie istnieje if (ListHead == NULL) { newNode−>next = NULL; ListHead = newNode; // tworzy głowę } else { if (insertPosition == 0){ // trzeba zmienić głowę newNode−>next = ListHead; ListHead = newNode; return; } node *iterator; // aktualnie sprawdzana pozycja na liście iterator = ListHead; // ustawia sie na głowie /* jeżeli następna pozycja NULL to koniec listy, lub za pomocą insertposition zliczamy na którym miejscu jesteśmy*/ while (iterator−>next != NULL && insertPosition > 1) { // przy każdym obrocie pętli zostaje nam o jeden mniej mniejsc do przesunięcia iteratora insertPosition−−; iterator = iterator−>next; } /*znaleźlismy miejsce, iterator jest w miejscu gdzie 1 miejsce za nim jest nasze docelowe do wstawienia węzła*/ if (insertPosition <= 1){ /*aby zachować ciągłość listy i nie stracić połączeń tymczasowo stwarzamy wskaźnik na listę za miejscem wstawiania*/ node *bufforNode; bufforNode = iterator−>next; iterator−>next = newNode; // wstawiamy węzeł za iterator newNode−>next = bufforNode; // a całą reszę listy za właśnie wstawiony węzeł } else{ // wyszliśmy poza listę iterator−>next = newNode; newNode−>next = NULL; } } } int main(){ node *Head = NULL; ListInsert(Head, 0, 100); ListInsert(Head, 1, 11); ListInsert(Head, 2, 12); ListInsert(Head, 3, 114); ListInsert(Head, 1, 8); ListInsert(Head, 10, 90); ListInsert(Head, 3, 3); ListInsert(Head, 0, 3); ListInsert(Head, 9, 5); ListInsert(Head, 0, 59); node *displayPointer = Head; while (displayPointer!=NULL){ cout << displayPointer−>data << endl; displayPointer = displayPointer−>next; } getch(); }

Mariusz: Sawyer dlaczego jest wskaźnik na wskaźnik ? W C nie ma referencji , referencja pojawia się dopiero w C++ Funkcja ma wstawiać elementy do listy w ten sposób aby wartości wyróżnionego pola zwanego kluczem były uporządkowane (w tym wypadku rosnąco) Gdybyśmy chcieli nadać węzłom unikalny klucz funkcję trzeba by trochę zmodyfikować Dopisałem funkcje wypisująca dane i wyszukująca węzeł struct node{ int key; struct node *next; }; void ListInsert(struct node **L,int x) { struct node *px; struct node *y; struct node *z; px=(struct node *)malloc(sizeof(struct node)); px−>key=x; if((*L)==NULL) { (*L)=px; px−>next=NULL; } else { y=(*L); z=NULL; while(y!=NULL && x−>key>y−>key) { z=y; y=y−>next; } px−>next=y; z−>next=px; } } void ListPrint(struct node *L) { struct node *p; p=L; while(p!=NULL) { printf("%d−>",p−>key); } printf("NULL\n"); } struct node* ListSearch(struct node *L,int k) { struct node *p; p=L; while(p!=NULL && p−>key!=k) p=p−>next; return p; } Sawyer przeczytałeś chociaż kod tej funkcji linia po linii ? Co według ciebie mogłoby powodować niepoprawne działanie tej funkcji wstawiającej ? Gdyby ktoś z was znalazł błąd to moglibyśmy przejść do usuwania elementów

Mariusz: Przydałaby się edycja oczywiście po wypisaniu wartości klucza czy wyświetlania danych w węźle iterujemy także wskaźnik p=p−>next;

Sawyer: To powinno rozwiązać Twój problem void ListInsert(struct node **L,int x) { struct node *px; struct node *y; struct node *z; px=(struct node *)malloc(sizeof(struct node)); px−>key=x; if((*L)==NULL) { (*L)=px; px−>next=NULL; } else { y=(*L); z=NULL; do{ z=y; y=y−>next; } while(y!=NULL && x−>key>y−>key) ; px−>next=y; z−>next=px; } }

Sawyer: Ah wybacz, nie wziąłem jeszcze jednej rzeczy pod uwagę.

Sawyer: Ponieważ tak na prawdę problem jest taki. Powiedzmy że tworzysz głowę z kluczem 3. Następnie dodajesz węzeł o kluczu 3. To zauważ że jeśli masz while(state) to wskaźnik Z jest NULL. wskaźnik Y jest głową, pętla while nie wykonuje się ani razu, ponieważ 3>3 = false zostawiając wskaźnik Z na NULL, a później chcesz odczytać wartość z−>next ze wskaźnika który nie istnieje. Czyli problem wystąpi zawsze wtedy gdy dodasz wartość mniejszą bądź równą od głowy. Z wartością równą głowie można poradzić sobie ustawiając Z na samym początku na głowę lub stosując pętlę do−while. Ale z wartością mniejszą od głowy to zaraz pomyślę.

Sawyer: Wydaje mi się że tak powinno być dobrze. Sprawdziłem i działa, na wszystkich przypadkach. void ListInsert(struct node **L,int x) { struct node *px; struct node *y; struct node *z; px=(struct node *)malloc(sizeof(struct node)); px−>key=x; if((*L)==NULL) { (*L)=px; px−>next=NULL; } else { y=(*L); z=NULL; while(y!=NULL && x−>key>y−>key) { z=y; y=y−>next; } if (z == NULL){ px−>next = L; L = px; } else{ px−>next = y; z−>next = px; } } } } Dodałem jedną If−kę która po prostu sprawdza z której strony głowy należy wartość wstawić jeśli z "prawej" (instrukcja dla else) to nic sie nie zmienia Jeśli natomiast z lewej to nowy węzeł wskazuje na starą głowę i sam staje się głową, czy dobrze myślę?

Sawyer: Oczywiście tam powinno być px−>next = (*L) oraz (*L) = px. Ale zwykle piszę w C++ i tak z przyzwyczajenia taka literówka.

Mariusz: z−>next=px; Ja opakowałem powyższą instrukcję instrukcją warunkową if i też mi działało Ciekaw byłem czy wyłapiecie błąd no i czy nie ma innych błędów Sawyer może zastanówmy się teraz nad usuwaniem elementów np void ListDelete(struct node **L,struct node * x) { // Tu jest nasz kod } Jakie są warunki brzegowe ? Co może powodować błędy ? W jakim miejscu zwalniać pamięć

Sawyer: dostajemy na argumencie od razu węzeł do usunięcia? Fajniej by było z kluczem Tak więc na samym początku sprawdzamy czy węzłem jest czy nie jest głowa. Jeśli tak to tworzymy buffor przetrzymujący głowa−>next, następnie usuwamy miejsce w pamięci od głowy, a później ustawiamy na nową głowę buffor. Jeśli węzeł to nie głowa na samym początku ustawiamy iteratorFront na głowie, natomiast iteratorBack na NULL potem przesuwamy się w pętli iteratorFront na iteratorFront−>next a iteratorBack staje się iteratorFront, pętla działa aż do znalezienia klucza, czy węzła który przeznaczony jest do usunięcia. Oznacza to że iteratorBack jest teraz na węźle poprzedzającym, przypadek brzegowy gdy chcemy usunąć głowę został rozpatrzony wcześniej ale jeśli by nie został to teraz iteratoBack były NULL i powodowałoby to błędy. IteratorFront wskazuje na nasz element do usunięcia natomiast IteratorFront−>next na resztę listy. Tworzymy buffor przechowujący wartość IteratorFront−>next, usuwamy miejsce w pamięci pod adresem z iteratoFront, ustawiamy iteratorBack−>next na buffor. Przypadek gdy iteratorFront−>next jest NULL nic nie zmiania bo to oznacza po prostu że iteratorBack−>next staje się NULL, co oznacza koniec listy.

Mariusz: Spróbuje na podstawie tego opisu napisać funkcje usuwającą węzeł W razie czego poprawisz ?

Sawyer: w C++ to będzie tak, wydaje mi się że wszystko przewidziałem, czy nie? Sprawdziłem i działa, dla usuwania głowy, usuwania, wewnątrz i usuwania z końca. void deleteNode(node *&L, node *x) { struct node *y; struct node *z; if (x == L) { node *headNext = L−>next; delete L; L = headNext; } else { y = (L); z = NULL; while (y != NULL && y!=x){ z = y; y = y−>next; } node *buffor; buffor = y−>next; delete y; z−>next = buffor; } }

Sawyer: Czy w ogóle jest sens rozpatrywać przypadek w który mamy sobie węzeł "wolny" nie należący do naszej listy nie połączony w żaden sposób z całością, i chcemy go usunać, bo wtedy oczywiście kod nie zadziała. Ale to chyba w ogóle przeczy idei usuwania obiektu z listy, bo przecież go na liście nie ma.

Mariusz: Myślę że takie przypadki też trzeba rozważyć bo jeżeli użytkownik poda wskaźnik który nie pokazuje na węzeł listy albo gdy poda NULL to program się "rozsypie"

Sawyer: no to na samym początku funkcji będzie if (x == NULL)return; A po pętli while if (y == NULL) { delete y; return; }, czyli while (y != NULL && y!=x){ z = y; y = y−>next; } if (y == NULL) { delete y; return; } czyli jeśli przeszlismy całą pętlę i nasz iteratorFront jest NULL znaczy doszliśmy do końca pętli nie znajdując naszego węzła, ergo go tam po prostu nie ma, usuwamy go wiec tak po prostu i wychodzimy z funkcji.

Mariusz: Znalazłem taki oto pseudokod List−Del(L,x) if head[L]! =NIL then if head[L] =x then head[L] :=next[x]; else y:=head[L]; while(next[y]! =x) do y:=next[y]; end while next[y] :=next[x]; end if end if i wygląda na to że ma więcej błędów niż ten pseudokod do wstawiania elementu do listy

Sawyer: W ogóle Mariusz, jeśli to nie tajemnica mogę zapytać czym się zajmujesz ? Przeglądałem Twoje posty i jestem ciekaw co robisz. A co do pseudokodu, to zacznijmy od tego że tu nie ma w ogóle zwalniania pamięci, nie rozważa przypadków gdy element jest spoza listy, ale sam kod jest troszkę inny, zauważ że tutaj dane są przechowywane w tablicy, więc nadpisując miejsce w tablicy powiedzmy "next" nie tracimy informacji o tym co jest ZA nextem bo po prostu będzie to kolejne pole w tablicy, dlatego i buffor dodatkowy przechowujący tymczasowy wskaźnik (jak w moim kodzie), jest niepotrzebny, kod jest spoko, ale po pierwsze, to nie jest dynamiczna alokacja pamięci, to jest tablica z komórkami które mogą być wskaźnikami na obiekty lub coś w ten deseń, ale wciąż komórki same z siebie istnieją. Tutaj nie potrzebujesz też dwóch wskaźników (y, z) ponieważ, wiesz co będzie dalej, wystarczy odnieść się do komórki w tablicy. Lista wygląda tak O2−>O1−>O3−>O4−>NULL W tym przypadku to działa tak że powiedzmy mamy tablice next: zastosuje taki zapis numer_obiektu−>pole w tablicy które jest kolejne. Tablica tak: |NULL|O1−>3|NULL|O3−>5|O2−>1|O4−>null| Chcemy usunąć obiekt o indeksie 3. Więc wystarczy że zaczniemy od głowy(pole tablicy 4) O1 ma ona indeksNext = 1, więc wejdziemy do tablicy o indeksie 1 która z kolei skieruje nas na indeks 3 itp itd. Jeśli zauważmy że tablica chce nas skierować na komórkę w której jest nasz obiekt do usunięcia to znaczy że czas na usuwanie. Jesteśmy w komórce numer [1], wiemy że w komórce do której nas skieruje [3] jest interesujący nas obiekt. Nie chcemy żeby z komórki [1] nas kierowało do [3], chcemy niejako obejść ten obiekt. Czyli robimy taką operację next[1](miejsceDoSkierowania) = next[3](miejsceDoSkierowania) I dostajemy wtedy taką tablicę: |NULL|O1−>5|NULL|O3−>5|O2−>1|O4−>null| O2−>O1−>O4−>NULL No przynajmniej ja tak rozumiem ten pseudokod. Czyli lista na tablicy, jakoś nie widzę w tym sensu.

Sawyer: http://codepad.org/WWsdWfwp Napisałem Ci Mariusz bibliotekę takiej listy od zera w C++, może coś Ci się przyda jak sobie przeczytasz, jeśli masz jakieś pytania to śmiało. Potem możemy ją zamienić bardzo prosto na coś ala vector, kontener, za pomocą operatora [], ale już nie chciałem komplikować sprawy.

Mariusz: Gdyby mi programowanie jakoś wychodziło to pewnie bym coś robił http://eduinf.waw.pl/inf/alg/001_search/0083.php Przeglądałem też tę stronę ale tutaj koleś się nie kryje z tym że w jego opisach algorytmów mogą błędy Gdy zwróciłem na to uwagę na innym forum to gimbusy próbowały mnie wyśmiać Starsze środowiska Pascala nie obsługują dynamicznych tablic oraz korzystają z DOSowego modelu pamięci i tam lista przydaje się bardziej Jeżeli mamy usuwanie gdy dany jest wskaźnik to przydaje się też odpowiednio napisana funkcja wyszukująca

Mariusz: http://codepad.org/3o61eBO9 Znalazłem w sieci taki kod funkcji sortującej przez scalanie z trzema wersjami funkcji scalającej Przydałoby się sprawdzić czy ta wersja z tzw fałszywym węzłem jest poprawna (nie spowoduje jakichś błędów) a także opisać te procedury Jak przerobić te funkcje sortujące przez scalanie tak aby nadawały się także do sortowania listy dwukierunkowej Przypuśćmy że chcielibyśmy napisać program do całkowania funkcji wymiernych Korzystamy z takiego schematu 1. deg L(x)>=deg M(x) Dzielimy wielomiany z resztą

	L(x)		R(x)
∫		dx=∫W(x)dx+∫		dx
	M(x)		M(x)

2. gcd(M(x),M'(x))≠const Stosujemy sposób Ostrogradskiego wydzielenia części wymiernej całki

	R(x)		R1(x)		R2(x)
∫		dx=		+∫		dx
	M(x)		M1(x)		M2(x)

M₁(x)=GCD(M(x),M'(x)) M(x)=M₁(x)M₂(x) deg R₁(x)<deg M₁(x) deg R₂(x)<deg M₂(x) Wielomiany z liczników znajdujemy korzystając z współczynników nieoznaczonych 3. gcd(M(x),M'(x))=const Stosujemy rozkład na sumę ułamków prostych Rozkład ten będzie jednak łatwiejszy bo mianownik nie ma pierwiastków wielokrotnych Trójmiany kwadratowe występujące w rozkładzie mianownika zapisujemy w postaci kanonicznej Wielomian można przechowywać na liście aby nie przechowywać zer jeśli się pojawią Przydatne operacje na wielomianach 1. Dodawanie wielomianów 2. Odejmowanie wielomianów 3. Mnożenie wielomianów 4. Dzielenie wielomianów z resztą 5. NWD wielomianów (wykorzystujemy funkcję z punktu 4.) 6. Schemat Hornera 7. Pierwiastki wielomianu bądź rozkład wielomianu na czynniki (Tutaj musimy zadowolić się metodami numerycznym, najlepsza byłaby taka która znajdowałaby najpierw czynniki kwadratowe)

Mariusz: Do twojej listy dopisałem funkcję zwracającą pozycje wyszukiwanego węzła o danym kluczu

Sawyer: Jeśli piszemy program stricte do wielomianów to nie trzeba pisać funkcji wstawiania w dowolnym miejscu, każdorazowo dodanie nowego elementu będzie przez funkcję sortującą (tam w moim kodzie to jest insertSortedByValue), która będzie przyrównywać stopnie X w wyrazach wprowadzanych, czyż nie?

Mariusz: Twoja liste na razie testowalem piszac sito Eratostenesa Widzialem ze niektorzy proponuja uzyc listy do przechowywania wielomianu W przypadku wielomianu na liscie przydaloby sie napisac wymienione funkcje Ja na tablicy mialem funkcje dodawanie wielomianow, mnozenie wielomianow, dzielenie wielomianow z reszta (z Numerical recipes in C) schemat Hornera pierwiastki tylko do czwartego stopnia wlacznie gdzie nie trzeba bylo metod numerycznych http://codepad.org/zvWnqSsy Tutaj mamy liste z sortowaniem przez scalanie oraz z odwracaniem kolejnosci Jesli chodzi o sortowanie listy przez scalanie to czy scalanie w tzw falszywym wezlem (dummy node) jest napisane bez bledow Przydaloby sie tez porownanie tych funkcji scalajacych jedna jest napisana rekurencyjnie, druga wykorzystuje falszywy wezel (dummy node) trzecia jest napisana iteracyjnie bez zadnych udziwnien Jak przerobić te funkcje sortujące przez scalanie tak aby nadawały się także do sortowania listy dwukierunkowej Wstawienie n wezlow w sposob uporzadkowany to ∑₁ⁿk czyli O(n²) Wstawienie n wezlow a pozniej posortowanie scalaniem O(nlog n) pod warunkiem ze wezly wstawiamy na poczatek listy Tak wiec jesli chcemy miec liste stale posortowana to lepiej uzyc wstawiania jezeli potrzebujemy posortowac liste raz na jakis czas lepsze bedzie sortowanie przez scalanie Ostatnio na podstawie pseudokodow Cormena napisalem kopiec na tablicy Moze gdy w przyszlosci przejdziemy do drzew to napiszemy go dynamicznie na drzewie

Mariusz: Jeśli chodzi o sortowanie tablic to kody można znaleźć Sortowanie bąbelkowe // Wirth p 66 Sortowanie przez wstawianie // CLRS p 18,26 Sortowanie przez wybór // Wirth p 64 Sortowanie przez kopcowanie // CLRS p 154,157,160 // Wirth p 75 Sortowanie przez scalanie // CLRS p 31,34 Sortowanie przez podział // Wirth p 79 Jeśli chodzi o sortowanie plików to kod łączenia naturalnego znalazłem w jakimś hiszpańskojęzycznym pdf o programowaniu w Pascalu Co do wyszukiwań to mamy funkcje function LinearSearch(A:TArray;n:integer;x:TElem):integer; var i:integer; begin i:=1; while((i<=n)and(A[i]<>x))do i:=i+1; if(i>n) then LinearSearch:=0; (*kazda wartosc poza przedzialem dla indeksów tablicy będzie dobra*) else LinearSearch:=i; end; function BinarySearch(A:TArray;n:integer;x:TElem):integer; var p,q,r:integer; found:boolean; begin p:=1; r:=n; found:=false; while((p<=r)and(not found))do begin q:=(p+r) div 2; if(A[q]=x) then found:=true else if(A[q]>x)then r:=q−1 else p:=q+1; end; if (not found) then BinarySearch:=0 else BinarySearch:=q end; Tak jak wspomniałem napisałem też tablicową wersję kopca bazując na pseudokodach Cormena i teraz czas na listy na których można napisać stos a także kolejkę