TDIU08 Problemlösning och programmering

Handledning inlämningsuppgift 2

Uppgift

Se inlämningsuppgiften. Uppgiften består i att designa (rita och förklara) en datastruktur för att representera ett släktträd för ett släktforskningsprogram. För detta är det meningen att du skall använda de konstruktioner som presenterades på översiktsföreläsningen om datastrukter. Obs: Ingen kod krävs.

Datatyper/strukturer

En kortare genomgång av verktygen följer nedan. För en mer utförlig beskrivning hänvisar vi till kursens föreslagna literatur.

Grundläggande datatyper

De grundläggande datatyper vi kan använda för att representera olika data i våra program är:

  Integer      Heltal mellan ca -2*10^9 och +2*10^9 
  Float        Realla tal med begränsad precision
  Character    Enskilda tecken
  Boolean      Sanningsvärden
  String       Textsnuttar

Egentligen är ju string ett fält, men finns som inbyggd typ i språket och kommer väl till pass då man vill representera text.

Fält

Då man vill representera mycket data är det lämpligt att samla dessa i en sammansatt datatyp. Ett fält är ett exempel på ett sådant. Vill man lagra många data av samma typ är ett fält lämpligt att använda. För att komma åt ett enskilt data i fältet använder man sedan ett index d.v.s. numret på den plats där datat finns.

Poster

En annan form av sammansatt datatyp är en post. Poster skiljer sig från fält på så sätt att postens olika delar kan ha olika datatyper. Varje del av posten får också ett namn. Det är dessa namn som används då man vill komma åt postens enskilda delar. Självklart kan man kombinera poster och fält så att man kan ha fält med poster eller en post med ett fält som en av delarna.

Filer

Vi kommer att behandla filer mer grundligt i kursens c++-del. För nuvarande kan vi nöja oss med att veta att när man börjar få riktigt mycket data så kan det vara värt att representera detta på hårddisken istället för i datorns arbetsminne. Att lagra data på fil är också ett sätt att behålla information då programmet stängs av.

Pekare

För både poster och fält gäller det att man i förväg måste deklarera dessa, så att kompilatorn vet hur mycket minne som skall läggas ut. Man kallar därför dessa datastrukturer för statiskt minne. Det går alltså inte att variera storleken på dessa strukturer utan man måste ta till så att det räcker från början. Om man istället vill lägga upp det så att programmet kan begära mer minne när det har behov av det brukar man prata om dynamiskt minne. Vi kan i detta fall använda oss av pekare. En pekare är en variabel som inte i sig har något värdefullt data, utan innehåller en adress som leder någon annan stans i minnet. Pekaren kan också vara satt så att den inte leder något alls. Med en pekare kan man när som helst i sitt program begära mer minne från operativsystemet. Det minne man får då "tillhör" då ens program och måste explicit lämnas tillbaka innan programmet tar slut.

Länkade strukturer

Om man nu tänker sig att man har en pekare som pekar på en post. Posten har i sin tur två delar, en del som är något värdefullt data som man vill hålla reda på och en del som är en likadan pekare som den första. Pekaren i posten kan nu peka vidare på en ny post, o.s.v. Detta är vad man brukar kalla en enkellänkad lista och är en struktur som kan växa och krympa efter behov. Det finns varianter på detta självklart. T.ex. länkade strukturer som har pekare som leder både till nästa och till föregående post, de kallas för dubbellänkade listor. Man kan även tänka sig att ha en struktur där varje post får ha två pekare till nya element, då resulterar detta i en trädstruktur.

Sidansvarig: Torbjörn Jonsson
Senast uppdaterad: 2018-08-09