TDDD86 Datastrukturer, algoritmer och programmeringsparadigm
Labb 3 FAQ
Labb 3 FAQ
- Q: Måste jag skriva en destruktor? Vad ska den göra i så fall? När ska jag anropa destruktorn?
-
A: Ja, i det behövs en destruktor. Den ska frigöra allt dynamiskt allokerat minne din lista använder (minne som initialiserats med
new
). Du ska inte anropa destruktorn explicit, klientprogrammet gör det automatiskt när en listvariabels definitionsområde tar slut. -
Q: Jag har hört talas om något som kallas för "smarta pekare" som frigör sitt eget minne och inte kräver minneshantering med
new
/delete
. Får jag använda smarta pekare? - A: Nej. Vi vill att du ska öva på att manuellt allokera och frigöra minne i den här uppgiften. Vi vill att du bygger upp vissa färdigheter innan du blir beroende av funktionalitet i bibliotek för att hjälpa dig.
- Q: Vad ska programmet göra om turen har 0 punkter?
-
A:
size()
ska returnera 0,distance()
ska returnera 0.0,show()
ska inte skriva ut någonting ochdraw()
ska inte rita någonting. - Q: Hur representerar jag oändligheten?
-
A: Använd
std::numeric_limits
från::infinity() limits
. -
Q: När ska jag skapa en ny länkad list-nod med
new
? -
A: För att skapa en tur med N noder ska du använda
new
påNode
exakt N gånger. Det är onödigt (och betraktat som dålig stil) att användanew
med tillfälliga variabler som används för att traversera listan. - Q: Går det skapa en animation för att se hur heuristikerna beter sig?
-
A: Ja. Se instruktionerna i
tsp.cpp
. - Q: Mitt program tar väldigt lång tid på sig. Går det att fixa?
-
A: Detta beror vanligen på ett problem i smallest insertion-heuristiken. Du har antagligen en loop som undersöker vad som skulle hända vid insättning av den nya punkten vid varje möjligt insättningsställe. Det är helt ok. Om du däremot anropar
distance()
-metoden för att beräkna den nya turens längd vid varje möjlig insättningspunkt lägger du egentligen till en loop inuti din första loop, vilket blir för långsamt. Du behöver inte beräkna om hela turens längd för varje möjlig insättningspunkt; det räcker att beräkna förändringen i turlängd och hålla reda på vilken insättningspunkt som ger den minsta förändringen. - Q: Hur vet jag att mitt program gör rätt?
-
A: För
usa13509.txt
får vi längderna77449.9794
och45074.7769
för nearest insertion respektive smallest insertion. Förcircuit1290.txt
får vi25029.7905
respektive14596.0971
. - Q: Måste jag använda en länkad lista i E4?
- A: Ja. Man får dock ändra på noderna (bara i E4), kanske lägga till data eller skapa dubbel länkade eller priotitet listor. Det ska dock alltid vara länkade listor som ni ska implementera själva. Man ska hantera minnet och inte skapa garbage. Programmet ska följa samma stil som för resten av labbarna (namn, referens, kommentarer etc).
Sidansvarig: Ahmed Rezine
Senast uppdaterad: 2024-08-29