16 Samlingar

För att strukturera upp flera variabler av samma typ har vi hittills uteslutande använt arrayer (fält). Detta är långt ifrån det enda sättet att strukturera sina data i ett program, det finns massvis av så kallade datastrukturer. I C# finns många av dessa tillgängliga i ett paket som heter Collections - därav namnet samlingar på svenska. Vill man prata i mer generella termer använder man dock ofast datastrukturer.

Det finns alldeles för många samlingar att lära oss för att vi ska hinna inom ramen för Programmering 1 men tre av de vanligaste/enklast eller mest grundläggande är några som väldigt mycket liknar en array - nämligen List, Stack och Queue.

16.1 List

En lista (List) fungerar ungefär som en array men den har en del tillhörande, färdiga metoder som underlättar vårt arbete en hel del. Det är dock fortfarande fråga om att organisera flera data i led efter varandra och vi indexerar fortfarande med hjälp av heltal (räknat från 0). Vi använder fortfarande samma terminologi för innehållet på respektive plats - element. Den data vi väljer att organisera kan fortfarande vara av flera olika typer: int, char, string osv. Med andra ord har vi en List av olika typer (vi säger att vi specificerar en typparameter). Är det fråga om heltal kan vi illustrera listan som nedan - dvs. precis som en array.

En List av typen heltal.

En egenskap som skiljer List och array åt är dock att en listas storlek är dynamisk. Vi specificerar inte vilken storlek vi behöver på en lista när vi skapar den utan storleken kan växa och krympa under tiden programmet körs. Med andra ord är List väldigt användbar när vi ska lagra okänt antal data i en lista.

När vi skapar en List så ser den generella syntaxen ut såhär

List<datatyp> variabelnamn = new List<datatyp>();

där datatyp givetvis ersätts med den typ av data vi vill lagra och variabelnamn med ett beskrivande namn för det vi lagrar. Om vi exempelvis ska lagra poäng som heltal använder vi följande:

List<int> poang = new List<int>();

Till denna variabeln poang följer sedan en hel del metoder vi direkt kan använda för att bland annat lägga till, ta bort, hämta ut och rensa i listan.

16.1.1 `List`-metoder

Det finns som sagt en mängd olika metoder att använda när man arbetar med en List (komplett dokumentation på docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=netframework-4.7.2#methods) men vi väljer här att ta en titt på några av dessa.

Add(element): Lägger till ett element längst bak i listan (storleken ökar).
Clear(): Rensar/tömmer hela listan (alla element försvinner).
Contains(element): Returnerar true om element existerar i listan, annars false.
ElementAt(position): Hämtar elementet på index position.
First(): Hämtar det första elementet i listan.
IndexOf(element): Returnerar ett heltal som är index för den position där element befinner sig i listan. Om elementet inte finns alls returneras -1.
Insert(position, element): Stoppar in element på index position. Alla efterföljande element flyttas ett steg i ordningen, dvs. inga element skrivs över (listans storlek ökar).
Last(): Hämtar det sista elementet i listan.
Remove(element): Tar bort element från listan. Om flera element kan matchas tas det första i ordningen bort. Efter att ett element plockats bort flyttas alla efterföljande element framåt ett steg (listans storlek krymper).
RemoveAt(position): Tar bort det element som finns på index position och flyttar/krymper listan sedan enligt ovanstående punkt.

Kom ihåg att skilja på element och index.

I samtliga ovanstående punkter är position ett heltal och element ett element av den datatyp man använde när man skapade listan. Dessutom finns en egenskap Count som innehåller antalet element listan har just nu. Med andra ord är detta List-motsvarigheten till Length i en array.

Många av dessa metoder gör det väldigt mycket enklare för oss som programmerare men man ska alltid ha effektivitet i åtanke när man använder någon datastruktur. Läs igenom Listoperationer och effektivitet på sidan 206 i boken för att få en bättre uppfattning om detta i fallet List.

Ett exempelprogram som nyttjar några av ovanstående metoder kan se ut såhär:

static void Main(string[] args)
{
    List<string> kurser = new List<string>();
    kurser.Add("Programmering 1");
    kurser.Add("Programmering 2");
    kurser.Add("Webbutveckling 1");
    kurser.Add("Webbutveckling 2");

    SkrivUt(kurser);

    Console.Write("Ange ny kurs att lägga till: ");
    string nyKurs = Console.ReadLine();
    kurser.Add(nyKurs);

    SkrivUt(kurser);

    Console.Write("Vilken kurs i ordningen vill du ta bort? ");
    int index = int.Parse(Console.ReadLine());
    kurser.RemoveAt(index);

    Console.WriteLine("Det finns nu " + kurser.Count + " kurser i listan.");
    Console.WriteLine("Först i ordningen ligger '" + kurser.First() + "'.");
    Console.WriteLine("Sist i ordningen ligger '" + kurser.Last() + "'.");
}

static void SkrivUt(List<string> kurser)
{
    for (int i = 0; i < kurser.Count; i++)
    {
        Console.Write(i + ": " + kurser.ElementAt(i) + " ");
        Console.WriteLine();
    }
}

16.2 Stack

Den andra samligen vi tar en titt på heter Stack. En Stack liknar en List i ganska stor utsträckning, den kan lagra olika datatyper och gör det en och en efter varandra (så kallad diskret linjär ordning). Men i samband med en Stack nämner man sällan index eftersom att samltiga operationer på en Stack görs i en och samma ände.

Man kan likna en Stack med en trave papper på ett bord. Om vi ska lägga till ett papper till traven gör vi det längst upp. Pappret längst upp är också de enda vars innehåll vi kan se. Vill vi se innehåll på pappret under måste vi lyfta bort det översta pappret. Dessa tre operationer kallar man för Push, Peek och Pop när man talar om en Stack.

Push, peek och pop på en Stack.

Lite mer formellt kan vi beskriva dessa tre Stack-metoder såhär:

Push(element): Lägger till element på toppen av stacken.
Peek(): Läser det översta elementet på stacken.
Pop(): Läser och plockar bort det översta elementet på stacken.

Utöver dessa finns även metoder Clear() som (precis som med List) rensar hela datastrukturen och egenskapen Count som anger hur många element som finns på stacken.

För att skapa en Stack skriver vi generellt följande kod:

Stack<datatyp> variabelnamn = new Stack<datatyp>();

Om vi t.ex. vill skapa en stack som lagrar strängar med namn ser koden ut såhär:

Stack<string> namn = new Stack<string>();

Med variabelnamnet namn kan vi sedan alltså använda Stack-metoderna. Exempelvis såhär:

Stack<string> namn = new Stack<string>();
namn.Push("Martin");
namn.Push("Andreas");
namn.Peek(); // --> "Andreas"
namn.Pop(); // --> "Andreas"
namn.Peek(); // --> "Martin"
namn.Push("Andrew");
namn.Count; // --> 2
namn.Clear();
namn.Count; // --> 0 (tom stack)

Märk väl att om vi vill behålla det element vi plockar ut från en Stack så får vi se till att lagra detta i en egen variabel. Se nedanstående exempel:

Stack<string> namn = new Stack<string>();
namn.Push("Martin");
string martin = namn.Pop();

Efter att ovanstående kod har körts är stacken tom men elementet "Martin" finns lagrat i variabeln martin.

När man illustrerar en Stack är det vanligt att man ritar den på höjden (och inte liggande som List och array) för att behålla analogin med en trave. Och precis som nämnts tidigare så utelämnar man index eftersom det ändå bara är det överstra elementet man kan arbeta med. Datastrukturer som beter sig på detta vis (sist in, först ut) brukar man benämna som LIFO från engelskans last in first out.

En Stack ritar vi på höjden, utan index.

Vanliga användningsområden för Stack är olika former av att stega tillbaka eller när man vill åt något i omvänd ordning. Vi kan t.ex. skriva ett ord baklänges genom att sätta in alla bokstäver i en stack och sedan plocka ut dom igen. Ett annat användningsområde man kan tänka sig är att vandra tillbaka samma väg man gått på en spelplan. Detta genom att placera varje position man besöker på stacken och sedan plocka ut dom och därmed besöka dom i omvänd ordning.

16.3 Queue

Den tredje datastrukturen vi tittar på är Queue. När vi nu känner till Stack som en LIFO-lista är det väldigt enkelt att beskriva Queue som en FIFO-lista, first in first out. Här handlar det alltså om att det element som först lades till är det som först kommer plockas ut.

En Queue har linjärt ordnade element men vi kan bara lägga till element i ena änden och plocka bort från den andra. Med andra ord precis som en vanlig kö i en matbutik eller liknande. Peek(), Clear() och Count för Queue är identiska med metoderna med samma namn för Stack. För att lägga till och ta bort använder vi följande:

Enqueue(element): Lägger till ett element till kön (i slutet).
Dequeue(): Läser och plockar bort det element som ligger först i kön.

De unika metoderna för Queue.

Precis som med List och Stack kan Queue lagra vilken datatyp som helst och syntaxen för att skapa en kö är likadan som för de tidigare datastrukturerna:

Queue<datatyp> variabelnamn = new Queue<datatyp>();

För personer i en kö skulle det alltså bli:

Queue<string> personer = new Queue<string>();

Med variabeln personer kan jag sedan använda metoderna vi beskrev ovan.

Queue<string> personer = new Queue<string>();
personer.Enqueue("Martin");
personer.Enqueue("Andreas");
personer.Enqueue("Andrew");
string forstIKon = personer.Dequeue(); // "Martin" försvinner från kön men lagras i variabeln.

16.4 Andra samlingar

För den som vill fördjupa sig inom samlingar/collections/datastrukturer finns massor att lära sig. En bra ingång är Microsofts egna dokumentation på docs.microsoft.com/en-us/dotnet/api/system.collections.generic?view=netframework-4.7.2#classes bara för att få en överblick över vad som finns.

Letar man efter mer genomarbetad litteratur finns en uppsjö av C#-böcker på engelska, men vill man åt något på svenska finns boken Datatyper och algoritmer av Janlert och Wiberg. Den handlar inte om C# i sig utan tar upp datastrukturer (och algoritmer) på ett generellt, något mer abstrakt plan.

16.5 Övningar

I denna, lite större övning ska du skapa ett program som hanterar en att göra-lista. Programmet ska kunna visa, lägga till och ta bort inlägg i listan. Dessutom ska man kunna ta bort och lägga till inlägg på en viss position. Till hjälp får du en grundstruktur med bland annat en do-while-sats att utgå ifrån. Detta upplägg är ofta lämpligt när man skriver någon form av “menyprogram” i konsollmiljö. Den List som hela programmet skall jobba mot finns i form av variabeln todo och tanken är att du delar upp programmet i metoder enligt kommentarerna i skelettkoden.

static List<string> todo = new List<string>();

static void Main(string[] args)
{
    int option;

    do
    {
        Console.Clear();
        PrintMenu();
        Console.Write("Enter option: ");
        option = int.Parse(Console.ReadLine());

        if (option == 0)
        {
            //Anropa metod som skriver ut listan
        }
        else if (option == 1)
        {
            //Anropa en metod som lägger till i lista
        }
        else if (option == 2)
        {
            //Anropa metod som tar bort översta i lista
        }
        else if (option == 3)
        {
            //Anropa metod som tar bort på viss position
        }
        else if (option == 4)
        {
            //Anropa metod som lägger till på viss position
        }

    } while (option != -1);
}

static void PrintMenu()
{
    Console.WriteLine("********* Menu *********");
    Console.WriteLine("* 0. View ToDo-list    *");
    Console.WriteLine("* 1. Add item          *");
    Console.WriteLine("* 2. Remove item       *");
    Console.WriteLine("* 3. Remove item #n    *");
    Console.WriteLine("* 4. Insert at #n      *");
    Console.WriteLine("* -1. Exit             *");
    Console.WriteLine("************************");
}

Skapa ett program som har två listor som innehåller följande heltal: 5, 6, 20, 19, 5, 16, 20, 13, 1, 11 och 16, 19, 6, 1, 8, 17, 11, 1, 20, 13. Du kan skapa variabler av typen list och sätta in värdet direkt vid deklaration såhär:
```
int[] tal = { 6, 19, 6, 1, 8, 17, 11, 1, 20, 13 };
List<int> lista = new List<int>(tal);
```
En array skapas visserligen i onödan men ditt kodande blir något enklare. Din uppgift är sedan att ta bort alla tal ur respektive lista som inte finns i den andra - dvs. endast unika tal skall finnas kvar. Dessa skall sedan kopieras in till en ny, gemensam lista som skrivs ut till användaren.
Skapa ett program som läser in en sträng och sedan kontrollerar om detta är en palindrom. Uppgiften skall lösas med hjälp av en Stack.

Skriv ett program som kontrollerar att en uppsättning paranteser är korrekt. Användaren skall kunna skriva in paranteserna och programmet svarar sedan med "OK" eller "FEL". Du skall lösa programmet med hjälp av en Stack och kan till hjälp ta denna pseudokod (ej färdigt program):

så länge tecken kan läsas in och fel saknas i parantesföljden
    om det inlästa tecknet är en vänsterparantes
        lägg det på stacken
    om det inlästa tecknet är en högerparantes
        om stacken är tom
            parantesföljden är felaktig
        annars
            ta bort topp-elementet från stacken
om stacken inte är tom
    parantesföljden är felaktig

Du kan testköra med följande korrekta följder ()(), (()) och dessa två felaktiga ())(), (().

Skriv ett program som hanterar en enkel kö med personnamn. Återanvänd tänket/upplägget från uppgiften med ToDo-listan.
- Programmet skall ha en meny med alternativen “Lägg till i kön”, “Ta bort från kön” och “Avsluta”.
- Programmet ska fortsätta köra kontinuerligt tills dess att användaren avslutar.
- När man lägger till i kön får man skriva in namnet på den person man vill lägga till.
- När man tar bort någon ifrån kön skrivs dennes namn ut.
- I menyn skrivs även alltid antalet personer i kön ut.
- Använd datastrukturen Queue och dess metoder för att lösa kösystemet.

15 Sökning