dana jest lista 2 kier. Na której 1 element wskazuje zmienna wskaźnikowa head. Lista przechowuje wartosci float. Napsiz fukcje która usunie z listy pierwszy znaleziony element którego wartość przechowywana spełnia nierowność: -1,5<wartosc elem<5. Argumentem funkcji jest tylko wskaźnik head funkcja zwraca pozycje usuniętego elementu.
Jak na razie twoja funkcja zwolniłaby pamięć zajmowaną przez głowę listy (skoro masz przekazać wskaźnik do niej jako argument), gdyby w ogóle miała szansę zadziałać, bo zaraz potem usiłuje porównać floata ze wskaźnikiem na Element_t.
Zacznij może od napisania funkcji, która wyszuka w liście dwukierunkowej pierwszy element o danej wartości klucza (i zwróci wskaźnik do niego). Jako argument niech przyjmie szukaną wartość klucza oraz wskaźnik do głowy listy. Potem pomyślimy, co dalej.
Masz listę dwukierunkową. Jest to struktura, która u Ciebie składa się z następujących elementów:
klucz (czyli w praktyce - to, co w danym elemencie przechowujemy, np. wartość typu float)
wskaźnik do następnego elementu listy
wskaźnik do poprzedniego elementu listy
Szczególnymi elementami listy są głowa i ogon. Wskaźnik do poprzedniego elementu listy w głowie ma wartość NULL, podobnie jak wskaźnik do następnego elementu listy w ogonie.
Do danego elementu listy nie możemy dostać się bezpośrednio (nie możemy powiedzieć: "zmienię teraz wartość klucza piątego elementu listy" i natychmiast się do tego elementu dostać, tak jak w tablicy: t[5]=3). Do listy mamy dostęp sekwencyjny: wiemy gdzie jest głowa, głowa udostępnia nam wskaźnik, który pokazuje, gdzie jest drugi element listy; jak dostaniemy się do drugiego elementu, to on nam "pokaże", gdzie jest trzeci element itd.
Załóżmy, ze mamy typ Element_t zdefiniowany tak jak u Ciebie. Funkcja, która dostaje jako argument wskaźnik na głowę listy i "przechodzi" po kolejnych elementach listy, wygląda mniej więcej tak:
Czyli "dopóki nie okaże się, że wskaźnik o nazwie glowa pokazuje na ogon (czyli: na element, który we wskaźniku next ma wpisane NULL), przesuwaj go do przodu po liście (czyli: przypisuj mu wartość wskaźnika next, odczytaną z elementu, na który dotychczas wskazywał).
Łatwo zmodyfikować tę funkcję, żeby wykonywała jakąś konkretną akcję na wszystkich elementach listy, np. zwiększyła wartość wszystkich kluczy o 1:
Spróbuj zastąpić linijkę piątą tak, żeby funkcja w tym miejscu sprawdzała, czy wartość klucza danego elementu mieści się w przedziale \(\displaystyle{ (-1,5;5)}\). Jeśli tak, funkcja ma w tym właśnie miejscu zwrócić wskaźnik do tego elementu (na co trzeba zmienić słówko void rozpoczynające definicję funkcji?)
# include <stdio.h>
# include <stdlib.h>
typedef struct Element_t
{
float element;
Element_t *next;
Element_t *prev;
};
Element_t *head,*ptr;
float przeszukaj(Element_t *glowa)
{
while(glowa->next != NULL)
{
if ((prev<5 )&& (-1,5<next) ) //jeśli spełnia warunki to musi zwrócić wskaźnik na ten element i usunąc go
{
ptr=element;
free(element);
return ptr ;
}
glowa=glowa->next; // a jeśli nie to szuka dalej takiego elementu
}
}
Ok. Jest już dużo lepiej. Teraz jest jeszcze problem z obsługą listy.
Rozumiem, że funkcja free zwalnia pamięć zajmowaną przez to, na co pokazuje wskaźnik ptr. Twoja funkcja zapisuje zatem zawartość wskaźnika element do wskaźnika ptr, następnie zwalnia pamięć. Od tego momentu wskaźniki ptr i element pokazują na losowe miejsce w pamięci, niezwiązane z listą, w którym być może znalazły się już dane innego programu. Nie ma żadnego sensu zwracanie wskaźnika do usuniętego elementu (myślę, że w zadaniu nie chodziło o zwrócenie adresu, tylko informacji, którym z kolei elementem w liście był ten usunięty; tym zajmiemy się może później).
Jeszcze większym problemem jest rozerwanie listy. Element poprzedni w liście pokazuje na losowe miejsce w pamięci, a powinien pokazać na następny element w liście (po operacji usuwania jest nim ten element, który był w liście po usuniętym elemencie). Podobny problem jest właśnie z tym kolejnym elementem, którego wskaźnik prev po usunięciu powinien wskazywać gdzie indziej.
Jeśli zostawimy funkcję w takim kształcie, jaki ma obecnie, to cała część listy po usuniętym elemencie staje się śmieciem (bo nie zwolniliśmy pamięci, którą zajmuje, ale nie mamy do niej dostępu, bo zgubiliśmy do niej wszystkie wskaźniki).
Spróbuj teraz dodać po linijce 20. kod, który spowoduje, że przed usunięciem elementu lista będzie już poprawnie "połączona" (na takiej zasadzie):
Wskazówka: nie ma problemu, żeby skorzystać z z konstrukcji typu wskaznik->prev->next itp.
No właśnie niestety tak się nie da. W wyniku tego, co napisałaś ptr->prev pokazuje teraz na to, na co pokazywał ptr->next, a nie o to chodziło. Próbujesz zresztą scalić w jeden dwa elementy, które mają pozostać w liście (nie można z nich zrobić jednego - mamy usunąć ten element, który jest pomiędzy).
ptr->prev->next=prt->next; //pole next elementu pokazywanego przez ptr->prev ma pokazać element następny po ptr
ptr->next->prev=ptr->prev; //pole prev elementu następnego po ptr ma pokazać element przed ptr
(porównaj z rysunkiem z mojego poprzedniego posta)
Teraz zastanów się, czy funkcja zadziała poprawnie, kiedy okaże się, że do usunięcia jest głowa lub ogon listy.
ptr->prev->next // a to nie jest tak ptr --(prev)--> przed peterem--(next)-->wracam do ptr ??
czy to nie mogło być po prostu ptr ?
Jeżeli będzie to głowa lub ogon to chyba nie zadziała bo np jest ogon to :
ptr->prev->next=prt->next; tutaj trzeba zmienić bo po tym nie będzie już elementu tlyko będzie NULL?
Gdyby ptr->prev->next było po prawej stronie przypisania, to rzeczywiście do wskaźnika po lewej stronie przypisałabyś adres ptr.
Tu jednak chcesz zmienić wartość pola next, należącego do elementu przed ptr. Gdybyś miała osobny wskaźnik, powiedzmy ptr2, pokazujący na element przed ptr, to mogłabyś napisać:
ptr2->next=ptr->next (czyli: do wskaźnika ptr2->next - bo to pole jest jakimśtam wskaźnikiem - przypisz adres, na który pokazuje wskaźnik ptr->next)
Żeby ptr2 pokazywał istotnie na poprzedni element, mogłabyś napisać \(\displaystyle{ ptr2=ptr->prev}\).
Mam nadzieję, że w miarę jasno to wytłumaczyłem. Zasadniczą różnicą jest to, czy dana zmienna (wskaźnik) stoi po lewej czy po prawej stronie operatora przypisania. Jeśli nie jest to dość jasne to:
Ukryta treść:
Zauważ różnicę pomiędzy:
b=6; ("nie obchodzi mnie, co jest w zmiennej b, ale teraz ma się tam znaleźć wartość 6")
a=b; ("teraz bardzo mnie obchodzi, co jest w zmiennej b; masz odczytać jej wartość i wpisać ją do zmiennej a)
Tak samo jest tutaj:
ptr->prev->next=ptr->next; ("nie obchodzi mnie, na co pokazuje pole next elementu, na który pokazuje ptr->prev; ale teraz masz zrobić tak, żeby pokazywało na to samo, na co pokazuje pole ptr->next)
ptr2=ptr->prev->next ("teraz bardzo mnie obchodzi, na co pokazuje pole pole next elementu, na który pokazuje ptr->prev; masz sprawdzić, na co pokazuje - okaże się, ze na to, na co pokazuje ptr - i sprawić, żeby na to samo pokazywał ptr2")
Masz jakiś pomysł, jak poprawić funkcję, żeby oprawnie działała także dla głowy/ogona listy? Podpowiem, że wystarczy każdą z dwóch linijek, które Ci podpowiedziałem ostatnim razem, poprzedzić if-em.-- 23 września 2010, 16:40 --Może jeszcze taka sprawa: napisałaś, że z tym będzie problem:
ptr->prev->next=prt->next;
a ja mówię, z tym nie będzie problemu, jeśli ptr jest ogonem; bo pole (ptr->prev)->next po wykonaniu tej instrukcji zacznie pokazywać na to, na co pokazywało pole ptr->next, czyli na NULL (i bardzo dobrze - w ten sposób stanie się nowym ogonem). Problem z tą właśnie instrukcją będzie wtedy, kiedy ptr będzie głową (dlaczego?)
Ja wcale nie myślę, ze to śmieszne. Tak długo człowiek nie umie, dopóki nie usiądzie i się nie nauczy . Może na wszelki wypadek napiszę cały kod, żeby nie było wątpliwości:
Tak na dobrą sprawę zmienna ptr jest tu średnio potrzebna, można by cały czas korzystać ze zmiennej glowa. Dodałem tu zmienną pozycja, która zlicza, ile razy "przeszliśmy" do kolejnego elementu listy, zanim dotarliśmy do elementu, który trzeba usunąć (czyli w praktyce: na której pozycji w liście był usunięty element).
