Kodprov 2018-08-30

Inlämning går till så här: ställ dig i katalogen kodprov180830. Om du har tappat bort dig i filsystemet kan du skriva cd; cd kodprov180830. Nu kan du skriva make handin för att lämna in kodprovet. När du kör detta kommando skapas en zip-fil med de filer som du har uppmanats att ändra i (inga andra), och denna fil sparas sedan på en plats där vi kan rätta provet. Vid behov kan du köra make handin flera gånger – endast den sista inlämningen räknas.

Den automatiska rättningen kommer att gå till så att vi kör dina inlämningar mot omfattande testfall. Du har fått ut mindre omfattande testfall eller motsvarande i detta prov som du kan använda som ett stöd för att göra en korrekt lösning. Experiment med att lämna ut mer omfattande tester har visat sig skapa mer stress än hjälp (tänk fler testfall som fallerar)¹.

Om du har löst uppgifterna på rätt sätt och testfallen som du får ut passerar är du förhoppningsvis godkänd.

• Samma regler som för en salstenta gäller: inga mobiltelefoner, inga SMS, inga samtal med någon förutom vakterna oavsett medium.
• Du måste kunna legitimera dig.
• Du får inte på något sätt titta på eller använda gammal kod som du har skrivit.
• Du får inte gå ut på nätet.
• Du får inte använda någon annan dokumentation än man-sidor och böcker.
• Det är tillåtet att ha en bok på en läsplatta, eller skärmen på en bärbar dator. Inga andra program får köra på dessa maskiner, och du får inte använda dem till något annat än att läsa kurslitteratur.
• Du måste skriva all kod själv, förutom den kod som är given.
• Du får använda vilken editor som helst som finns installerad på institutionens datorer, men om 50 personer använder Eclipse samtidigt så riskerar vi att sänka servrarna.

Vi kommer att använda en blandning av automatiska tester och granskning vid rättning. Du kan inte förutsätta att den kod du skriver enbart kommer att användas för det driver-program som används för testning här. Om du t.ex. implementerar en länkad lista av strängar kan testningen ske med hjälp av ett helt annat driver-program än det som delades ut på kodprovet.

I mån av tid har vi ofta tillämpat ett system där vi ger rest för mindre fel. Det är oklart om detta system tillämpas för detta kodprov men det betyder att det är värt att lämna in partiella lösningar, t.ex. en lösning som har något mindre fel.

Denna uppgift går ut på att implementera en cirkulärlänkad, dubbellänkad lista.

En dubbellänkad lista är en lista där varje nod har en pekare, inte bara till sitt nästa element, utan också till sitt föregående. En sådan lista är lämplig att använda när man vill kunna traversera listan i “båda riktningar”.

En cirkulärlänkad lista är en lista som inte termineras genom att den sista länkens next-pekare pekar på NULL, utan där den sista länken pekar på den första länken. Följande loop skulle i en cirkulärlänkad lista, alltså inte terminera:

while (cursor)
  {
    printf("%d", cursor->element); // Skriv ut elementet
    cursor = cursor->next; // Gå vidare till nästa element
  }

while%20%28cursor%29%0A%20%20%7B%0A%20%20%20%20printf%28%22%25d%22%2C%20cursor-%3Eelement%29%3B%20%2F%2F%20Skriv%20ut%20elementet%0A%20%20%20%20cursor%20%3D%20cursor-%3Enext%3B%20%2F%2F%20G%C3%A5%20vidare%20till%20n%C3%A4sta%20element%0A%20%20%7D%0A

En lista som är både dubbellänkad och cirkulärlänkad går alltså att traversera åt båda hållen och termineras icke av NULL i någondera riktning. För enkelhets skull kommer listans element att vara heltal.

Din uppgift är att skriva färdigt programmet list.c så att det implementerar alla funktionerna i list.h och passerar testerna i driver.c. Vad du måste göra är klart markerat med ///TODO i list.c.

#ifndef __kodprov__
#define __kodprov__

#include <stdbool.h>

typedef struct list list_t;

/// Skapar en tom lista 
list_t *ioopm_list_create(); 

/// Tar bort en lista ur minnet
void ioopm_list_destroy(list_t *list); 

/// Stoppar in ett element FÖRST i listan
void ioopm_list_prepend(list_t *list, int element);

/// Stoppar in ett element SIST i listan
void ioopm_list_append(list_t *list, int element);

/// Tar bort elementet på plats index. Negativa
/// index räknas bakifrån, dvs. -1 är sista elementet.
/// Valida index är [-N,-1] och [0,N) för en lista med N element.
/// \returns true om elementet togs bort.
bool ioopm_list_remove(list_t *list, int index); 

/// Returnerar elementet på plats index. Negativa
/// index räknas bakifrån, dvs. -1 är sista elementet.
/// Valida index är [-N,-1] och [0,N) för en lista med N element.
/// \returns en pekare till int:en i listan -- NULL om den inte fanns
int *ioopm_list_get(list_t *list, int index); 

/// Kontrollerar om en lista innehåller ett viss element
/// \returns true om elementet finns i listan.
bool ioopm_list_contains(list_t *list, int element); 

/// OBS! Implementeras i O(n) tid, inte O(1). 
/// \returns antalet element i listan. 
int ioopm_list_size(list_t *list); 
#endif

%23ifndef%20__kodprov__%0A%23define%20__kodprov__%0A%0A%23include%20%3Cstdbool.h%3E%0A%0Atypedef%20struct%20list%20list_t%3B%0A%0A%2F%2F%2F%20Skapar%20en%20tom%20lista%20%0Alist_t%20%2Aioopm_list_create%28%29%3B%20%0A%0A%2F%2F%2F%20Tar%20bort%20en%20lista%20ur%20minnet%0Avoid%20ioopm_list_destroy%28list_t%20%2Alist%29%3B%20%0A%0A%2F%2F%2F%20Stoppar%20in%20ett%20element%20F%C3%96RST%20i%20listan%0Avoid%20ioopm_list_prepend%28list_t%20%2Alist%2C%20int%20element%29%3B%0A%0A%2F%2F%2F%20Stoppar%20in%20ett%20element%20SIST%20i%20listan%0Avoid%20ioopm_list_append%28list_t%20%2Alist%2C%20int%20element%29%3B%0A%0A%2F%2F%2F%20Tar%20bort%20elementet%20p%C3%A5%20plats%20index.%20Negativa%0A%2F%2F%2F%20index%20r%C3%A4knas%20bakifr%C3%A5n%2C%20dvs.%20-1%20%C3%A4r%20sista%20elementet.%0A%2F%2F%2F%20Valida%20index%20%C3%A4r%20%5B-N%2C-1%5D%20och%20%5B0%2CN%29%20f%C3%B6r%20en%20lista%20med%20N%20element.%0A%2F%2F%2F%20%5Creturns%20true%20om%20elementet%20togs%20bort.%0Abool%20ioopm_list_remove%28list_t%20%2Alist%2C%20int%20index%29%3B%20%0A%0A%2F%2F%2F%20Returnerar%20elementet%20p%C3%A5%20plats%20index.%20Negativa%0A%2F%2F%2F%20index%20r%C3%A4knas%20bakifr%C3%A5n%2C%20dvs.%20-1%20%C3%A4r%20sista%20elementet.%0A%2F%2F%2F%20Valida%20index%20%C3%A4r%20%5B-N%2C-1%5D%20och%20%5B0%2CN%29%20f%C3%B6r%20en%20lista%20med%20N%20element.%0A%2F%2F%2F%20%5Creturns%20en%20pekare%20till%20int%3Aen%20i%20listan%20--%20NULL%20om%20den%20inte%20fanns%0Aint%20%2Aioopm_list_get%28list_t%20%2Alist%2C%20int%20index%29%3B%20%0A%0A%2F%2F%2F%20Kontrollerar%20om%20en%20lista%20inneh%C3%A5ller%20ett%20viss%20element%0A%2F%2F%2F%20%5Creturns%20true%20om%20elementet%20finns%20i%20listan.%0Abool%20ioopm_list_contains%28list_t%20%2Alist%2C%20int%20element%29%3B%20%0A%0A%2F%2F%2F%20OBS%21%20Implementeras%20i%20O%28n%29%20tid%2C%20inte%20O%281%29.%20%0A%2F%2F%2F%20%5Creturns%20antalet%20element%20i%20listan.%20%0Aint%20ioopm_list_size%28list_t%20%2Alist%29%3B%20%0A%23endif%0A

For enkelhets skull skall alla element i mängden att lagras i en array (kallad elements) vars storlek är fix – dvs. när man skapar en mängd bestäms hur många element den maximalt kan rymma.

Elementen i arrayen skall vara ordnade dvs. följande skall alltid gälla för i >= 0 och i+1 < elements.length:

T a = elements[i];
T b = elements[i+1];
a.compareTo(b) < 0; /// är alltid sant 

T%20a%20%3D%20elements%5Bi%5D%3B%0AT%20b%20%3D%20elements%5Bi%2B1%5D%3B%0Aa.compareTo%28b%29%20%3C%200%3B%20%2F%2F%2F%20%C3%A4r%20alltid%20sant%20%0A

Eftersom det är lite meckigt att skapa en array av generisk typ i Java ger jag ut den koden här:

T[] elements = (T[]) new Comparable[maxCapacity];

T%5B%5D%20elements%20%3D%20%28T%5B%5D%29%20new%20Comparable%5BmaxCapacity%5D%3B%0A

Detta leder dock till klagomål från kompilatorn: Note: Set.java uses unchecked or unsafe operations. Det är OK. Det går förstås också bra – eller bättre! – att ha en array av Comparable[].

Klassen Set är deklarerad enligt följande:

public class Set<T extends Comparable<T>>

public%20class%20Set%3CT%20extends%20Comparable%3CT%3E%3E%0A

dvs. typen Set<Foo> betyder en mängd av element av typen Foo sådana att Foo instanceof Comparable<Foo> alltid gäller. Interfacet CompareTo definierar en metod, int compareTo(T o) sådan att:

• a.compareTo(b) returnerar ett negativt tal om a kommer före b i den ordning som implementeras
• a.compareTo(b) returnerar 0 om a och b är lika
• a.compareTo(b) returnerar ett positivt tal om a kommer efter b i den ordning som implementeras

(Alltså ekvivalent med t.ex. hur strcmp() fungerar i C.)

Eftersom Foo instanceof Comparable<Foo> alltid gäller så kan instanser av Foo endast jämföras med andra instanser av Foo med hjälp av compareTo().

Du behöver alltså minst en array och en maxkapacitet.

Mängden skall stödja följande operationer:

1. Konstruktor som tar som argument maximalt antal element
2. Konstruktor som inte tar några argument utan delegerar till den första konstruktorn med 16 som maximalt antal element
3. public boolean add(T elem) som lägger till elem i mängden om utrymme finns och elem inte redan är medlem. Huruvida ett element är medlem eller inte avgörs med hjälp av compareTo().
4. private int indexOf(T elem) som returnerar platsen i arrayen där elem finns, alternativt borde ha funnits om elementet fanns med. För att kunna skilja mellan finns och borde ha funnits använder vi negativa index för det senare, och eftersom 0 är varken positivt eller negativt ökar vi negativa index med 1. Alltså: -5 betyder att “om det sökta elementet hade funnits i arrayen skulle det ha funnits på index 4” medan 4 betyder att “det sökta elementet finns på plats 4”. På samma sätt betyder -1 “skulle ha funnits först i arayen”, och 0 “finns först i arrayen”.
5. public boolean contains(T elem) som returnerar true om elem finns i mängden, annars false.
6. int size() som returnerar antalet element i mängden, initialt 0.
7. En jämförelsemetod (vanlig equals()). a.equals(b) skall returnera true om a och b är alias, eller om a och b innehåller identiska objekt. Observera att det inte går att göra en typsäker version av denna metod! Kompilatorn kommer att klaga på Note: Set.java uses unchecked or unsafe operations.. Bry dig inte om detta.
8. Plus alla andra privata metoder som du kan tänkas behöva.

1. Enda sättet ändra i mängden skall vara genom add().
2. Ett försök att skapa en mängd med negativ maxkapacitet, eller anropa add() eller contains() med null skall kasta undantaget IllegalArgumentException. (Detta är ett standard-exception som finns.)
3. Vid överskridande av maxkapaciteten skall ett SetFullException kastas. (OBS! Detta måste du själv skriva! Gör det i Set.java och “fort” – annars kan inte ens Driver.java kompilera.) Observera att anrop till add() med element som redan är medlemmar i mängden inte växer mängden!
4. Du skall använda dig av indexOf() i implementationen av add() för att ta reda på om det nya elementet redan finns och om inte – var det skall placeras.

Du kan testa din inlämning med hjälp av make. Då körs programmet i Driver.java som skapar några mängder och utför några få operationer på dem. Vid eventuella fel skrivs ett meddelande ut.

make test kör alla test utan att avbryta vid fel. make test-hard kör alla test och avbryter vid fel.

Questions about stuff on these pages? Use our Piazza forum.

Want to report a bug? Please place an issue here. Pull requests are graciously accepted (hint, hint).

Nerd fact: These pages are generated using org-mode in Emacs, a modified ReadTheOrg template, and a bunch of scripts.

Ended up here randomly? These are the pages for a one-semester course at 67% speed on imperative and object-oriented programming at the department of Information Technology at Uppsala University, ran by Tobias Wrigstad.