• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Prioritet och associativitet hos operatorerna i C

Scenario

Stålmannen har en textfil som heter platser.txt, och som innehåller data om platser. Varje plats anges med en rad, bestående av tre tal: först ett (unikt) heltal som är platsens nummer, och sen platsens latitud och longitud:

17 59.2466 15.2448 3 59.2549 15.2463 421609 59.3326 18.0651 25 37.421987 -122.084067 och så vidare

Filen innehåller flera miljoner platser. Platsnumren är alltså unika, men det är inte säkert att de kommer i nummerordning i filen, eller att det inte finns luckor i numreringen. (Om det finns tre platser, kan de alltså ha numren 4711, 3000000000 och 17.)

Stålmannen har en annan textfil som heter mosade.txt, och som innehåller data om de myggor han slagit ihjäl.

17 3 25 1 17 1 421609 47 17 2 och så vidare

Varje rad i filen innehåller två heltal: ett platsnummer och ett myggantal. Enligt filen har han först varit på plats 17 och slagit ihjäl 3 myggor. Sen flög han till plats 25 och slog ihjäl en ensam mygga. Därefter flög han tillbaka till plats 17, och dödade ännu en ensam mygga. Sen flög han till plats 421609 och slog ihjäl inte mindre än 47 myggor, innan han igen flög tillbaka till plats 17 och dödade 2 myggor.

Filen innehåller flera miljarder sådana platsbesök.

Uppgift (30 p)

Man måste alltså på något sätt summera ihop antalet dödade myggor för varje plats, och sen välja ut den plats som har högst summa.

Om det är flera platser som delar på förstaplatsen, dvs har samma summa av dödade myggor, spelar det ingen roll vilken av dem man skriver ut.

Om man väljer olämpliga datastrukturer, till exempel osorterade länkade listor, kan det ta mycket lång tid att köra programmet med de stora datamängder som det handlar om. Välj därför datastrukturer så att programmet går att köra på en normal, modern dator utan att ta orimligt lång tid, och utan att krascha på grund av minnesbrist.

För att ett program ska vara lätt att förstå och arbeta vidare med, bör man dela upp det i mindre delar, så kallad modularisering. Modularisera programmet så det består av flera filer (.c- och .h-filer). Modulariseringen gäller även de viktigaste datatyperna i programmet, där man bör använda abstrakta datatyper. En abstrakt datatyp är gjord så att implementationsdetaljerna är dolda, och därför går att ändra utan att man behöver ändra i resten av programmet.

Poängbedömning:

• Ett korrekt program som ger rätt svar, ger 10 poäng på uppgiften, även om det skulle ta mycket lång tid att köra programmet.
• Lämpligt valda, och korrekt implementerade, datastrukturer ger ytterligare 10 poäng.
• Lämpligt vald och väl genomförd programkonstruktion, med filer och abstrakta datatyper, ger ytterligare 10 poäng.