C++ linked list class. Lyckas inte med Remove funktion.

Permalänk
Medlem

C++ linked list class. Lyckas inte med Remove funktion.

Tjena! Jag försöker skapa en list class baserad på sammankopplade noder. Så här ser Remove funktionen ut:

void Sorted_List::remove(int value)
{
Node* tmp = first;
Node* old = tmp;
if (first->data == value)
{
tmp = first->next;
delete first;
first = tmp->next;
}
else
{
while (tmp->data != value)
{
if (tmp->next == nullptr)
{
return;
}
old = tmp;
tmp = tmp->next;
}
old->next = tmp->next;
delete tmp;
}
size_of_list -= 1;
}

Den fungerar så länge jag inte försöker ta bort det första objektet i listan, då går den inte att köra. Vad gör jag fel?

Visa signatur

Case: Lian Li PC-O11 Dynamic - Motherboard: MSI MAG X570 TOMAHAWK WIFI - CPU: AMD Ryzen 5 3600 - GPU: Gainward GeForce RTX 3080 Phantom 10G - RAM: G.Skill 32GB DDR4 3600MHz CL18 Trident Z Neo - PSU: Corsair RM750X - SSD: Kingston A2000 1TB

Permalänk
Medlem

Du sätter början av listan till näst-nästa element när du tar bort första.

Permalänk
Medlem
Skrivet av perost:

Du sätter början av listan till näst-nästa element när du tar bort första.

Det fungerar tyvärr ändå inte

Visa signatur

Case: Lian Li PC-O11 Dynamic - Motherboard: MSI MAG X570 TOMAHAWK WIFI - CPU: AMD Ryzen 5 3600 - GPU: Gainward GeForce RTX 3080 Phantom 10G - RAM: G.Skill 32GB DDR4 3600MHz CL18 Trident Z Neo - PSU: Corsair RM750X - SSD: Kingston A2000 1TB

Permalänk
Medlem
Skrivet av Murvar:

Det fungerar tyvärr ändå inte

Du har ju inte riktigt förklarat vad som faktiskt går fel... Vad menar du med "går inte att köra"?

Lägg även din kod mellan code-taggar:
[code]
// Din kod här
[/code]

så att indenteringen bibehålls och gör det lättare att läsa koden.

Visa signatur

AMD Ryzen 7 1700X 3.8 GHz 20MB | ASUS PRIME X370-PRO | MSI GeForce GTX 1080 Gaming X 8GB | G.Skill 16GB DDR4 3200 MHz CL14 Flare X | Corsair RM650x 650W

Permalänk
Hedersmedlem

Kan starkt rekommendera att rita upp din länkade lista på papper och gå igenom för hand varje operation du gör. Fann det själv väldigt effektivt när jag hade svårt att förstå.

Permalänk
Medlem
Skrivet av Shimonu:

Kan starkt rekommendera att rita upp din länkade lista på papper och gå igenom för hand varje operation du gör. Fann det själv väldigt effektivt när jag hade svårt att förstå.

Nu är jag ingen vidare bra på just C++, men för egen del fungerade det väldigt bra att skriva kommentarer för varje sats, som beskriver varje operation

Visa signatur

AMD Ryzen 7 5800X3D | EVGA GeForce RTX 3080 10GB FTW3 ULTRA | ASUS ROG Strix B450-F Gaming | Corsair RM750X V2 | Crucial Ballistix Sport LT 3200MHz 16GB | Samsung 980 Pro 1TB | Crucial MX500 2TB | NZXT H500

Permalänk
Hedersmedlem
Skrivet av Cenorida:

Nu är jag ingen vidare bra på just C++, men för egen del fungerade det väldigt bra att skriva kommentarer för varje sats, som beskriver varje operation

Svårheten för mig är att hålla hur listan ser ut i huvudet för varje operation. När man har det ritat så behöver man inte komma ihåg vilka effekter som tidigare operation lämnade efter sig och saknar man någon operation så blir det tydligt när det saknas en pil till exempel. Men alla tänker vi olika så det gäller att hitta vad som passar en bäst.

Permalänk
Medlem

Hur vet funktionen om listan? Jag ser inte att du skickar med den som argument.
F.ö om du skall ändra på huvudet till funktionen så behöver du antingen skicka med en dubbelpekare till listan alternativt returnera den (och just nu har du en void-funktion).

// jag kan C men inte C++, men det bör vara lika gällande det (?)

Visa signatur

10700K | NVIDIA RTX 3080

Permalänk
Medlem
Skrivet av Murvar:

if (first->data == value) { tmp = first->next; delete first; first = tmp->next; }

Några antaganden om din class: konstruktorn som skaper tom lista sätter first till nullptr? Eller finns bara konstruktor som skapar lista med en nod?

I första fallet så får du segfault redan i if-satsen om man testar med tom lista. I fallet när man har endast en nod i listan så pekar first->next på null,
så tmp == nullptr. Då får du segfault när du försöker göra tmp->next.

Fundera igenom vad som händer med din kod om:
- det finns inget i listan
- det finns en nod i listan
vilka checkar behöver du göra innan du försöker följa en pekare?

Permalänk
Medlem
Skrivet av kwame:

Hur vet funktionen om listan? Jag ser inte att du skickar med den som argument.
F.ö om du skall ändra på huvudet till funktionen så behöver du antingen skicka med en dubbelpekare till listan alternativt returnera den (och just nu har du en void-funktion).

// jag kan C men inte C++, men det bör vara lika gällande det (?)

Han gör en class (det som är den stora skillnaden mellan c och c++). Tänk att en class är lite som en struct fast den inte bara innehåller variabler utan även funktioner. De två :: betyder att remove är en funktion som kan användas på object av typen sorted_list. Remove kan använda argument variabler och medlemsvariabler från klassobjectet (dvs som finns i "structen" ).

Ex:

Sorted_List minLista; //skapa/deklarera ny tom lista minLista.remove(4711);

exempelkod blev fel 😬
Permalänk
Medlem

@magjan: Sorted_List minLista(); är en funktionsdeklaration, du måste ta bort parenteserna för att deklarera ett objekt. Det är ett så känt problem med C++ att det har en egen Wikipedia-sida: Most vexing parse.

Permalänk
Medlem
Skrivet av Murvar:

Tjena! Jag försöker skapa en list class baserad på sammankopplade noder. Så här ser Remove funktionen ut:

void Sorted_List::remove(int value) { Node* tmp = first; Node* old = tmp; if (first->data == value) { tmp = first->next; delete first; first = tmp->next; } else { while (tmp->data != value) { if (tmp->next == nullptr) { return; } old = tmp; tmp = tmp->next; } old->next = tmp->next; delete tmp; } size_of_list -= 1; }

Den fungerar så länge jag inte försöker ta bort det första objektet i listan, då går den inte att köra. Vad gör jag fel?

Som tidigare sagt så hoppar du över en nod när du tar bort huvudet.

void Sorted_List::remove(int value) { Node* tmp = first; //Toppen Node* old = tmp; //Vad är tmp? Har du definierat Node *tmp i class Sorted_List? Inte ett bra namn, och onödigt i de flesta fall if (first->data == value) { tmp = first->next; //Nu har du 'first' som nod 0 och 'tmp' som nod 1 delete first; //Nu tar du bort nod 0 ('first') first = tmp->next; //Nu sätter du nod 2 som 'first'. Det skall stå first = tmp; } else { while (tmp->data != value) { if (tmp->next == nullptr) { return; //Här vill du antingen lägga till en error funktion eller "return false;" för att indikera att inget togs bort. //Det kräver att du ändrar void till bool naturligtvis. Om det är kritiskt att du tar bort något skall det vara en error //funktion istället så att allting går sönder efter en plan istället för att du får felsöka i timmar. } old = tmp; tmp = tmp->next; } old->next = tmp->next; delete tmp; } size_of_list -= 1; //Detta är att be om problem när du ändrar saker senare eller lägger ytterligare funktioner //för att modifiera din LL. Gör hellre en funktion //GetLength() { //int nLength = 0; //Node* index = first; //while (index->data != nullptr) { //++nLength; //index = index->next; //} //return nLength} för att få en absolut värdering varje gång. }

Om jag kan föreslå att göra saker något enklare för dig:

//I class Sorted_List{ //Node *_head; //_head->next pekar alltid på första elementet. _head används inte självt. bool Sorted_List::remove(int value) //bool så vi kan se hur det går. { Node* tmp = _head; while (tmp->next->data != value) { if (tmp->next == nullptr) { return false; } tmp = tmp->next; } Node* kill = tmp->next; tmp->next = tmp->next->next; delete kill; size_of_list = GetLength(); return true; } int GetLength() { int nLength = 0; Node* index = _head->next; while (index->data != nullptr) { ++nLength; index = index->next; } return nLength; }

Permalänk
Medlem
Skrivet av perost:

@magjan: Sorted_List minLista(); är en funktionsdeklaration, du måste ta bort parenteserna för att deklarera ett objekt. Det är ett så känt problem med C++ att det har en egen Wikipedia-sida: Most vexing parse.

Haha. Ja. Jag gör ofta det felet. Det är så förvirrande. List initiering har inte gjort det lättare heller.

Permalänk
Medlem
Skrivet av Fey:

Om jag kan föreslå att göra saker något enklare för dig:

//I class Sorted_List{ //Node *_head; //_head->next pekar alltid på första elementet. _head används inte självt. bool Sorted_List::remove(int value) //bool så vi kan se hur det går. { Node* tmp = _head; while (tmp->next->data != value) { if (tmp->next == nullptr) { return false; } tmp = tmp->next; } Node* kill = tmp->next; tmp->next = tmp->next->next; delete kill; size_of_list = GetLength(); return true; } int GetLength() { int nLength = 0; Node* index = _head->next; while (index->data != nullptr) { ++nLength; index = index->next; } return nLength; }

Jag gillar att du inte gjorde ett helt färdigt exempel. Om det är en skoluppgift så ska man få vägledning men inte lösning.
En fråga bara (i samma anda som mitt tidigare svar) vad händer om listan är tom... Dvs om _head inte har något att peka på? (_head->next = = nullptr ?). Vad händer då med din (och TS) while loop?

förtydligande
Permalänk
Medlem
Skrivet av Fey:
Skrivet av magjan:

Tack för tipsen! Jag försökte faktiskt räkna elementen med en funktion tidigare men fick rådet att bara spara det som en int istället då funktionen inte fungerade. Feys implementation fungerade tyvärr inte heller (till att börja med).

Mitt problem var brist på konstruktor till Node samt att jag behövde ta in fallet där first == nullptr. Nu fungerar koden som tänkt, inklusive size() funktionen. Tack så mycket för att ni tog er tid till att hjälpa mig! Fastnade med det här alldeles för länge.

Visa signatur

Case: Lian Li PC-O11 Dynamic - Motherboard: MSI MAG X570 TOMAHAWK WIFI - CPU: AMD Ryzen 5 3600 - GPU: Gainward GeForce RTX 3080 Phantom 10G - RAM: G.Skill 32GB DDR4 3600MHz CL18 Trident Z Neo - PSU: Corsair RM750X - SSD: Kingston A2000 1TB