Opgaver - Modul 11 - Programmeringsopgaver

Til de første opgaver herunder er der lavet en projektskabelon der indeholder test. Skabelonen findes på GitHub-repositoriet under / modul11 / LinkedList /.

I skabelonen kan du bruge følgende kommandoer:

$ dotnet test
$ dotnet run

Med “dotnet test” kører alle testene, og du kan se hvad der fejler. Med “dotnet run” kører du filen “Program.cs”, som indeholder eksempelkode der viser, hvordan man bruger “UserLinkedList”-klassen.

Opgave 1 - Kig i koden

Start med at kigge i “UserLinkedList.cs”. Kig på de operationer der allerede er implementeret (AddFirst, GetFirst, RemoveUser, …). For hver af dem, sammen med din gruppe, gør følgende:

• Forklar hvordan det virker. Brug papir og blyant, hvor du tegner en liste, og viser operationen.
• Forklar hvad størrelsesordenen af tidskompleksiteten er for hver operation med “Big O”.

Opgave 2 - Implementer de manglende operationer

Flere metoder i “UserLinkedList.cs” mangler at blive implementeret. For at hjælpe dig er der stillet følgende til rådighed:

• Test du kan køre, for at se hvad der fejler.
• Filen “Program.cs” indeholder koder, der viser hvordan operationerne skal bruges. Du kan tilføje yderligere koden i filen, hvis du har brug for det - fx mere Console.WriteLine().

Jeg anbefaler at du angriber opgaven i følgende rækkefølge:

1. Implementer RemoveFirst()
2. Implementer GetLast();
3. Implementer CountUsers();

Opgave 3 - Contains

Det kunne være rigtigt smart hvis man nemt kunne tjekke om noget allerede er i listen. Du skal derfor gøre følgende:

1. Tilføje en metode “public bool Contains(User user)” til klassen “UserLinkedList”. Start med bare at lave en “return null!;” i metoden.
2. Tilføj en ny testmetode i “LinkedList_Tests” (i filen "UserLinkedList.Tests.cs) som tester metoden. Testen skal selvfølgelig fejle da Contains ikke er lavet færdig.
3. Gå tilbage til Contains og lav den færdig.
4. Tilføje kode i Program.cs der viser hvordan man bruger Contains.

Opgave 4 - SortedUserLinkedList

Med inspiration fra “UserLinkedList”, skal du lave en ny udgave, “SortedUserLinkedList”, hvor listen altid er sorteret. Det betyder at du ikke længere må have en “AddFirst”, men nu blot skal have en “Add” der indsætter det rigtige sted.

Du skal også skrive nogle nye test-metoder der sikrer, at koden er korrekt ift. sortering.

Opgave 5 - Udfordring - DoublyLinkedList

Her er en udfordring. Du skal nu lave en ny udgave af UserLinkedList som er dobbeltkædet, dvs. at hver node nu både har en “next” og en “previous”. Du skal derudover sikre at der både er en “AddFirst”, “AddLast”, “RemoveFirst” og en “RemoveLast”.

Fordelen ved en dobbelkædet liste er, at man kan indsætte og fjerne i begge ender af listen i konstant tid. Dette er smart hvis man vil bruge listen til både køer og stakke.