Göm menyn

Mer om datatyper

Förutom listor och strängar finns det en del andra användbara datatyper i Python. Vi kommer i detta dokument gå igenom datatyperna tuple och dictionary.

Tupler

En tupel är en konstant lista (eng. tuple). En tupel är, precis som en sträng, oföränderliga (immutable). Tupler ser ut och fungerar som vanliga listor, men initieras med parenteser istället för hakparenteser. Tupler kan också initieras utan parenteser, även om det inte är helt rekommenderat då det inte är lika tydligt.

Dokumentation

Här kommer några exempel på hur tupler fungerar.

Även om tupler i sig är oföränderliga så kan vi skapa nya tupler utifrån gamla. En tupel kan också innehålla data som i sig går att förändra.

Användning av tupler

Eftersom tupler aldrig ändras kommer de att ha samma storlek och innehåll. Detta gör att deras interna rutiner kan köras snabbare. Tupler är alltså mer effektiva än listor och lämpar sig för tillfällen då man har konstanta sekvenser, t.ex.:

En användbar konvention är att använda tupler där man har strukturerad data och informationen på olika positioner har olika roller, och listor när man har sekvenser med data av samma typ. Till exempel:

Dictionaries

Dictionaries är listor av par som man kan använda som uppslagstabeller. Varje par består av en nyckel och ett värde. Genom att ange en nyckel får man tillbaka parets värde (kan liknas vid listans index). I övrigt fungerar dictionaries ungefär som listor.

Dokumentation

Alla oföränderliga värden kan användas som nycklar i en dictionary. Samma nyckel kan dock inte förekomma två gånger. Ordningen mellan paren (så som de visas när man t.ex. skriver ut dem) är egentligen ointressant och därför lämnar Python inga garantier för att ordningen bevaras.

En mer allmän benämning på den här typen av datastruktur är hashtabell. Grundtanken är att det finns en algoritm som beräknar ett hashvärde för varje nyckel. Detta hashvärdet används sedan som ett internt index för att slå upp värdet snabbt.

Sammansatta datatyper

Datatyp Innehåll? Muterbar? Indexering?
str Text Nej Heltal
list Vad som helst Ja Heltal
tuple Vad som helst Nej Heltal
dict Vad som helst Ja Nästan vad som helst

Binära sökträd (BST)

Alt text

  • Binärt, d.v.s. varje nod har maximalt två grenar under sig.
  • Ordnade så att nyckeln i en viss nod är större än alla nycklar i vänstra grenen, och mindre än eller lika med alla nycklar i högra grenen.
  • Ofta lagras mer än enbart nyckeln i noden.
  • Ett lätt sätt att organisera datamängder för att lätt kunna söka upp information (om man redan känner till nyckeln).

Algoritm för sökning i ett binärt sökträd

Vi letar efter x i trädet t.

  1. Om t är ett tomt träd finns inte x i det.
  2. Om t är ett löv kollar vi om t == x.
  3. Om x < nyckeln i roten av t, fortsätt att söka i vänster gren.
  4. Om x > nyckeln i roten av t, fortsätt att söka i höger gren.
  5. Annars har vi en träff!

Hur kan vi använda dem i Python?

Det finns inga inbyggda binära sökträd i Python, det är en abstrakt datatyp (ADT). Om vi vill kunna arbeta med binära sökträd måste vi implementera dem själva, med andra ord skriva funktioner som gör allt det vi vill kunna göra med binära sökträd. För att kunna skriva dessa funktioner måste vi bestämma ett sätt att representera binära sökträd med hjälp av de inbyggda datatyperna i Python.

Representera binära sökträd med hjälp av listor

  • Det tomma trädet representeras av en tom lista.
  • Löv representeras med heltal
  • Inre noder representeras som [vänster gren, nyckel, höger gren]

Det finns många möjliga sätt att representera binära träd i Python, detta är endast ett av dem.

Här är vårt tidigare exempel representerat på detta vis.

Primitiva funktioner

De primitiva funktionerna hjälper oss att implementera representationen. Var för sig är de ganska enkla, men de fungerar som gränssnitt gentemot andra funktioner som vill arbeta med binära sökträd.

Rekursiv sökning i ett binärt sökträd

Vi implementerar nu den tidigare algoritmen i Python-kod. Notera att search() inte känner till representationen av trädet, utan endast de primitiva funktionerna.

Tillhörande quiz

Finnes här


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-15