Föreläsning 2 Abstrakta datatyper

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, dictionaryI den här kursen ska vi titta på datastrukturena:¶ ObjektLänkade listor bestående av noder (objekt) med referens till nästa nodStackKöDequeue (double-ended queue)Allmänna trädBinära trädHashtabellerBooleska hashtabeller och bloomfilterTrappa/heapPrioritetskö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.¶