Witam.
Lista którą się sugerowałem : http://www.p-programowanie.pl/cpp/lista-jednokierunkowa-c/
Mam pewne pytanie co do wskazników w liście jednokierunkowej.
Dlaczego muszę uzyć zapisu TEMP->NASTEPNY = TEMP->NASTEPNY->NASTEPNY
Aby Element nie był już widoczny w liście ( wiem, że nie jest usunięty )
A nie działa zapis TEMP = TEMP->NASTEPNY lub TEMP = TEMP->Nastepny->Nastepny ?
który wg. mnie też powinien nadpisać poprzedni węzeł, a wiem że działa tak, ze tylko przesuwa wskaźnik.
Dlaczego muszę uzyć zapisu TEMP->NASTEPNY = TEMP->NASTEPNY->NASTEPNY
Aby Element nie był już widoczny w liście ( wiem, że nie jest usunięty )
No a co się stanie, jak Elementowi 1 ustawisz wskaznik by wskazywał na Element 3? Nic nie bedzie wskazywalo juz na element 2.
A nie działa zapis TEMP = TEMP->NASTEPNY lub TEMP = TEMP->Nastepny->Nastepny ?
A co nie działa? Pokaż kod.
void Lista::Delete(int k)
{
if (First->key == k)
{
Node * Tmp = First;
First = First->Next;
delete Tmp;
}
else
{
Node * Tmp = First;
while (Tmp->Next)
{
if (Tmp->key == k-1)
{
//Node * Tmp2 = Tmp->Next;
//Tmp->Next = Tmp->Next->Next;
//delete Tmp2;
void Lista::Delete(int k)
{
if (First->key == k)
{
Node * Tmp = First;
First = First->Next;
delete Tmp;
}
else
{
Node * Tmp = First;
while (Tmp->Next)
{
if (Tmp->key == k-1)
{
//Node * Tmp2 = Tmp->Next;
//Tmp->Next = Tmp->Next->Next;
//delete Tmp2;
Tmp = Tmp->Next->Next;
return;
}
Tmp = Tmp->Next;
}
}
}
return;
}
Tmp = Tmp->Next;
}
}
}
Tak wygląda moja funkcja do usuwania.
Kod wyłączony z użytku działał prawidłowo, natomiast przy użyciu
Tmp = Tmp->Next->Next;
Funkcja wyświetlająca, nadal pokazuje element, którego wg. mnie być nie powinno.
Przepraszam źle mi się wklieło :
void Lista::Delete(int k)
{
if (First->key == k)
{
Node * Tmp = First;
First = First->Next;
delete Tmp;
}
else
{
Node * Tmp = First;
while (Tmp->Next)
{
if (Tmp->key == k-1)
{
//Node * Tmp2 = Tmp->Next;
//Tmp->Next = Tmp->Next->Next;
//delete Tmp2;
Tmp = Tmp->Next->Next;
return;
}
Tmp = Tmp->Next;
}
}
}
Spójrz ponownie na rysunek. Załóżmy, że tmp oznacza nam w danej chwili wskaźnik na Element1, a chcemy usunąć Element2. Jeżeli ustawisz wskaźnik który pokazuje w tej chwili na Element1 (nasza zmienna tmp) na Element 3 to lista zacznie rozpoczynać się od Elementu3, z pominięciem Element1 i Element2. A chcieliśmy tylko skasować Element2. Dlatego jest ważne by nadpisać wskaźnik, który pokazuje na Element2, a nie na ten przy którym jesteśmy. A ten wskaźnik znajduje się w tmp->next
viader napisał(a):
Spójrz ponownie na rysunek. Załóżmy, że tmp oznacza nam w danej chwili wskaźnik na Element1, a chcemy usunąć Element2. Jeżeli ustawisz wskaźnik który pokazuje w tej chwili na Element1 (nasza zmienna tmp) na Element 3 to lista zacznie rozpoczynać się od Elementu3, z pominięciem Element1 i Element2. A chcieliśmy tylko skasować Element2. Dlatego jest ważne by nadpisać wskaźnik, który pokazuje na Element2, a nie na ten przy którym jesteśmy. A ten wskaźnik znajduje się w tmp->next
No właśnie o to chodzi.. a ja nie rozumiem dlaczego mimo tego, funkcja "Pokaz" nadal pokazuje element 1 i element 2, mimo że nie powinna
void Lista::Print()
{
Node * Tmp = First;
while (Tmp)
{
cout << Tmp->key << endl;
Tmp = Tmp->Next;
}
}
void Lista::Insert(int k)
{
if (First == 0)
{
First = new Node;
First->key = k;
}
else
{
Node * Tmp = First;
while (Tmp->Next)
{
Tmp = Tmp->Next;
}
Tmp->Next = new Node;
Tmp->Next->key = k;
Tmp->Next->Next = 0;
}
}
Ponieważ jeżeli zmieniasz początek listy to powinieneś pamiętać o odpowiednim ustawieniu wskaźnika First. Zauważ, że od niego zaczyna się wyświetlanie, nie ma znaczenia co ustawisz w tmp czyli zmiennej lokalnej. Inna sprawa gdy tmp pokazuje ci na jakiś sensowny obiekt i przez wskaźnik dobierasz się do ustawiania już wskaźnika na kolejny element.
viader napisał(a):
Ponieważ jeżeli zmieniasz początek listy to powinieneś pamiętać o odpowiednim ustawieniu wskaźnika First. Zauważ, że od niego zaczyna się wyświetlanie, nie ma znaczenia co ustawisz w tmp czyli zmiennej lokalnej. Inna sprawa gdy tmp pokazuje ci na jakiś sensowny obiekt i przez wskaźnik dobierasz się do ustawiania już wskaźnika na kolejny element.
Super, myślę że w końcu łapie w czym jest problem dzięki koledze.
W takim razie zapis
Tmp = Tmp->Next->Next;
Praktycznie nic nie zmienia w liście, tylko lokalnie "przemieszcza się" z elementu 1 do 3,
zaś
Tmp->Next = Tmp->Next->Next;
Wskazuje na jakiś konkretny obiekt i go nadpisuje ?
Tego właśnie nie mogę zrozumieć, bo wydawało mi się że działanie powyższych jest podobne lub takie samo..
Dawid90dd napisał(a):
O jejku jejku. Funkcja Delete. 1.:
Masz tam w jednym miejscu sprawdzenie czy pierwszy klucz == k, a jezeli nie to dla innych elementow sprawdzasz juz czy klucz == k-1. Wątpię, że to jest zamierzone.
2.:
Tmp = Tmp->Next->Next; oznacza przeskoczenie o dwa elementy, przy czym prosisz się w tym momencie o kłopoty, dlatego że jeżeli Tmp->Next->Next będzie nullem, to w kolejnym cyklu while sprawdzisz, czy Tmp->next bedzie nullem, w momencie, gdy sam Tmp bedzie sie rownal nullowi.
3.:
Tmp->Next = Tmp->Next->Next; Rowniez oznacza przeskoczenie o dwa elementy, i znowu sie prosisz o klopoty, jezeli Tmp->Next->Next bedzie nullem.
Dziekuje za odp.
W takim razie jak "po Bożemu" zrealizować usuwanie ?
AndrjuWron napisał(a):
W takim razie zapis
Tmp = Tmp->Next->Next;
Praktycznie nic nie zmienia w liście, tylko lokalnie "przemieszcza się" z elementu 1 do 3,
Ten zapis zmienia ci ustawienie wskaźnika tmp na dwa obiekty w przód, ale po wyjściu z funkcji obiekt tmp jest usuwany.
AndrjuWron napisał(a):
zaś
Tmp->Next = Tmp->Next->Next;
Wskazuje na jakiś konkretny obiekt i go nadpisuje ?
Ten zapis oznacza mniej więcej. Pójdź do obiektu na który pokazuje tmp i ustaw w nim wskaźnik, który obecnie pokazuje na następny element. Ustaw go na element, który jest następnym elementem następnego elementu. (dwa w przód)
AndrjuWron napisał(a):
W takim razie jak "po Bożemu" zrealizować usuwanie ?
if(tmp!=First) {
tmp->next = tmp->next->next;
}
else {
First = First->next;
}
Coś takiego od strony ustawienia wskaźników. Ten kod wymaga jeszcze poprawki, zwolnienia pamięci i czy czasem nie kasujemy ostatniego elementu, wtedy trzeba ustawić na null wskaźnik.
tmp->next
Ale wszystko tu zależy od twojego podejścia, możesz na kilka sposobów sprawdzić czy chcesz skasować pierwszy lub ostatni wskaźnik i się zabezpieczyć wedle uznania.
Źle napisałem, zapomniałem że masz tam instrukcje return, Jeszcze raz.
1.: Pozostaje tak jak jest.
Zmień te Tmp->key == k-1 na Tmp->key == k
2.: Jeżeli odkomentujesz to co zakomentowałeś, i ta część będzie wyglądać tak:
Node * Tmp2 = Tmp->Next;
Tmp->Next = Tmp->Next->Next;
delete Tmp2;
Tmp = Tmp->Next->Next;
a. Tworzysz kopie pointera na nastepny element, ok.
b. Ustawiasz tmp->next na tmp->next->next. tmp->next moze wskazywac teraz na jakis element, lub na null. ok
c. Zwalniasz z pamięci już odłączony z listy element. ok
d. tmp = tmp->next->next przeskakuje jeszcze o dwa kolejne elementy, ta linia jest potrzebna. Jeżeli tmp->next będzie się równał nullptrowi to tmp->next->next jest zlym pomyslem.
Zwróć jeszcze uwagę na to, że w Twojej linked liście możesz umieścić kilka elementów z takimi samymi wartościami-kluczami. W takim przypadku funkcja delete usunie ci tylko ten który jest najbliżej początku listy.
Dawid90dd napisał(a):
Źle napisałem, zapomniałem że masz tam instrukcje return, Jeszcze raz.
1.: Pozostaje tak jak jest.
Zmień teTmp->key == k-1naTmp->key == k2.: Jeżeli odkomentujesz to co zakomentowałeś, i ta część będzie wyglądać tak:
Node * Tmp2 = Tmp->Next;
Tmp->Next = Tmp->Next->Next;
delete Tmp2;
Tmp = Tmp->Next->Next;
a. Tworzysz kopie pointera na nastepny element, ok.
b. Ustawiasz tmp->next na tmp->next->next. tmp->next moze wskazywac teraz na jakis element, lub na null. ok
c. Zwalniasz z pamięci już odłączony z listy element. ok
d. tmp = tmp->next->next przeskakuje jeszcze o dwa kolejne elementy, ta linia jest potrzebna. Jeżeli tmp->next będzie się równał nullptrowi to tmp->next->next jest zlym pomyslem.Zwróć jeszcze uwagę na to, że w Twojej linked liście możesz umieścić kilka elementów z takimi samymi wartościami-kluczami. W takim przypadku funkcja delete usunie ci tylko ten który jest najbliżej początku listy.
A dlaczego tmp->key == k ?
W moim przypadku usuwa to wtedy element k+1 zamiast k.
"W moim przypadku". Ja nie wiem jaki jest Twój przypadek, Jeżeli masz tablice z kluczami {12, 253, 33, 23}, i chcesz usunąć element z kluczem 33 to sprawdzasz po kazdym elemencie czy jego wartosc == 33, a nie 33 - 1.