Programmeringsmetodik: Inlämningsuppgift 3

Den här uppgiften går ut på att arbeta med länkade listor, och öva lite både på tidskomplexitet och verkliga körtider.

Uppgiften

Skriv ett program som frågar efter ett filnamn, läser heltal från den filen, och lagrar dem i en länkad lista. Inga dubbletter ska tas med, så innan man lägger in ett nytt tal måste man kolla att det inte redan finns med. Som avslutning ska programmet skriva ut talen i listan, som nu alltså innehåller unika tal. Ordningen spelar ingen roll.
Prova sen att dela upp i två olika länkade listor. Lägg alla jämna tal i den ena listan, och alla udda tal i den andra. Man kan använda uttrycket x % 2 == 0 för att avgöra om talet x är jämnt eller inte.
Svara nu på dessa frågor:
- Hur mycket snabbare kan man räkna med att versionen med två listor blir?
- Vad är tidskomplexiteterna för de två versionerna? Motivera svaret.
- Mät tiden. Hur mycket snabbare blev det?

Exempel

En exempelfil med 10 tal:

17 16 20 17 18 16 17 18 16 17

Exempel på utmatning:

(Ordningen spelar ingen roll.)

Tips

Man kan använda programmet skapa-tal.c för att skapa en textfil med tal.

Redovisning

Provkör programmet med olika indata för att säkerställa att det fungerar som det ska. (Ni kommer väl ihåg testning, som i inlämningsuppgift 1 och 3 i Programmering grundkurs?)
Redovisning sker genom att programmet därefter uppvisas och provkörs för labbhandledaren. Skriv ner svaren på frågorna, och visa och förklara för handledaren.

Om samarbete på inlämningsuppgifterna: Varje grupp (som normalt består av en eller två studenter) ska göra en egen lösning, och skicka in den, men det är inte förbjudet att samarbeta eller fråga andra studenter om hjälp. Däremot ska man i så fall tydligt ange vilka som man samarbetat med. Varje lösning måste ange namnet på alla som bidrog i arbetet. Samarbete är alltså tillåtet, men måste redovisas.

Godkänd rapport utgör en del av delkurs 2 i kursen Programmeringsmetodik.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 12 september 2012