Föreläsning 2

Redigering pågår...

Datastrukturer

En datastruktur är till för att lagra data (som en variabel), men med plats för flera värden. Exempel som du sett:

I Python: lista, sträng, dictionary
I den här kursen ska vi titta på datastrukturena:

Objekt
Länkade listor bestående av noder (objekt) med referens till nästa nod
Stack
Kö
Dequeue (double-ended queue)
Allmänna träd
Binära träd
Hashtabeller
Booleska hashtabeller och bloomfilter
Trappa/heap
Prioritetskö
Abstraktion

Anta att vi vill skriva ett kalenderprogram.
Data: Olika typer av händelser kopplade till datum och tid.

Exempel på operationer:
find_events(start_date, end_date)
add_appointment( parametrar? )
delete_item( parametrar? )

Man behöver inte veta exakt hur data lagras för att använda operationerna.

Likadant i Python - vi vet inte hur strängar, listor och uppslagslistor är definierade, ändå kan vi använda dom. Det här är ett exempel på abstraktion. Om implementationen av listans metoder ändras (i en ny Python-version) behöver vi inte bekymra oss, alla våra program som använder listor fungerar ändå. Vi använder listan som en abstrakt datastruktur.