TDP004 Objektorienterad programmering

Förberedelseuppgifter Minneshantering och pekarstrukturer

Följande uppgifter handlar om pekare och hur de kan användas för att skapa pekarstrukturer, samt hur klasser kan stödja ansvaret för minneshatering.

Uppgift 1

Skriv den kod som behövs för att beskriva följande figur:

              /------------------\
              |                  |
     +-----+  |  +-------------+ |
first|  o-----\->|     +-----+ | |
     +-----+     |next |  o------/
       (*)       |     +-----+ |
                 |       (*)   |
                 |     +-----+ |
                 |data |  5  | |
                 |     +-----+ |
                 |      (int)  |
                 +-------------+
                    (Element)

I figuren pekar "first" på elementet, och elementets "next" pekar på elementet självt.

Uppgift 2

Givet figuren i uppgift (1) körs följande kod:


(*first->next).next->data = 10;
(*first->next).next->next = nullptr;

Förklara vad som händer när koden körs och hur samma sak går att göra med enklare kod.

Uppgift 3

Skriv den kod som behövs för att figuren i uppgift (1) skall bli som följer.

     +-----+     +-------------+      +-------------+
first|  o------->|     +-----+ |   /->|     +-----+ |
     +-----+     |next |  o-------/   |next |  0  | |
       (*)       |     +-----+ |      |     +-----+ |
                 |       (*)   |      |       (*)   |
                 |     +-----+ |      |     +-----+ |
                 |data |  5  | |      |data |  9  | |
                 |     +-----+ |      |     +-----+ |
                 |      (int)  |      |      (int)  |
                 +-------------+      +-------------+
                    (Element)            (Element)

I figuren pekar "first" på elementet som har "data"=5 och det elementets "next" pekar i sin tur på elementet med "data"=9 som i sin tur har "next"=nullptr. Antag att Element har en konstruktor Element(Element* next, int data).

Uppgift 4

Skriv den kod som behövs för att figuren i uppgift (3) skall bli som följer.

                                 /--------------------\
     +-----+     +-------------+ |    +-------------+ |  +-------------+
first|  o------->|     +-----+ | | /->|     +-----+ | \->|     +-----+ |
     +-----+     |next |  o------/ |  |next |  0  | |    |next |  o------\
       (*)       |     +-----+ |   |  |     +-----+ |    |     +-----+ | |
                 |       (*)   |   |  |       (*)   |    |       (*)   | |
                 |     +-----+ |   |  |     +-----+ |    |     +-----+ | |
                 |data |  5  | |   |  |data |  9  | |    |data |  8  | | |
                 |     +-----+ |   |  |     +-----+ |    |     +-----+ | |
                 |      (int)  |   |  |      (int)  |    |      (int)  | |
                 +-------------+   |  +-------------+    +-------------+ |
                    (Element)      |     (Element)          (Element)    |
                                   \-------------------------------------/

Elementet längst till höger är det "nya" jämfört med föregående figur. Det tidigare elementen ligger alltså kvar på sin tidigare plats i minnet. I figuren pekar "first" på elementet som har "data"=5 och det elementets "next" pekar i sin tur på nya elementet med "data"=8 som i sin tur har "next"=9 och till slut "next"=nullptr. Antag att Element har en konstruktor Element(Element* next, int data). Förenklat ritar vi ovan figur som följer:

      +-----+    +---+---+    +---+---+    +---+---+    
first |  o------>| 5 | o----->| 8 | o----->| 9 | 0 |
      +-----+    +---+---+    +---+---+    +---+---+    
        (*)      (Element)    (Element)    (Element)

I den förenklade figuren har vi även lagt elementen i den ordning som gör att figuren framstår som enkel (hur elementen egentligen ligger i minnet har vi abstraherat bort). ( Off-topic: Om du tycker figurerna verkar jobbiga att rita i emacs skall du först prova "rektangel"-kommandona i emacs, de låter dig klippa och klistra valfria rektanglar. )

Uppgift 5

Utgå från den förenklade figuren i uppgift (4) men antag att antalet element ("lådor") är okänt. Skriv en while-loop som letar upp sista elementet (det med next == nullptr). Efter while-loopen skall adressen till sista elementet finnas i en pekarvariabel.

Uppgift 6

Utgå från den förenklade figuren i uppgift (4) men antag att antalet element ("lådor") är okänt. Skriv en rekursiv funktion som letar upp sista elementet (det med next == nullptr). Funktionen skall returnera adressen till sista elementet som en pekarvariabel.

Uppgift 7

Utgå från den förenklade figuren i uppgift (4) och följande funktion:


void insert(Element* e, int i)
{
  e = new Element(e->next, i);
}

Förklara vad som händer när följande kod kör och hur det ser ut efteråt:

insert(first, 2);

I denna uppgift gäller det att noga rita upp vad som händer för att få fram rätt (eller fel beroende på hur man ser det) slutresultat.

Uppgift 8

Rita en figur som visar resultatet av följande kod:


void insert(Element* e, int i)
int* data[3];
for (int i = 0; i < 3; ++i)
{
  data[i] = new int(i);
}

Tips: Deklarationer med pekare läses bäst baklänges. T.ex. kan "int* data[3]" läsas ut som "skapa ett fält med storlek 3 som heter 'data' och lagrar pekare till heltal".

Uppgift 9

Antag att ett Element i uppgift 4 har en destruktor:


void insert(Element* e, int i)
Element::~Element()
{
   delete next;
}

Visa steg för steg vad som händer när satsen "delete first" körs på strukturen i uppgift 4?

Uppgift 10

Klasser har speciella funktioner som aktiveras "automatiskt" i vissa lägen. En programmerare har använd dessa för att bygga en enkel pekarklass för heltal. Klassen håller reda på en pekare till heltal som tas emot via konstruktor. Det finns:

en medlemsfunktion för att ta reda på om pekaren är giltig (skild från nullptr)
en medlemsfunktion som låter dig komma åt en referens (alltså ändringsbar!) till minnet som pekas ut
en destruktor som avallokerar pekarens minne
en kopieringskonstruktor som /flyttar/ pekaren från det objekt som kopieras till det nya objektet. Pekaren i gamla objektet sätts till nullptr.


class Int_Pointer
{
public:
   Int_Pointer(int* ip = nullptr) : p{ip} {}
   Int_Pointer(Int_Pointer& rhs) : p{rhs.p} { rhs.p = nullptr; }
   ~Int_Pointer() { delete p; }
   bool is_valid() { return p != nullptr; }
   int& content_of() { retrun *p; }
   
private:
   int* p;
};

Redovisa hur följande kod skulle fungera:


Int_Pointer p{ new int };
Int_Pointer q{ p };

q.content_of() = 5;
if ( p.is_valid() )
{
  p.content_of() = 7;
}

Uppgift 11

Utgå från klassen i uppgift 10. Redovisa hur följande kod skulle fungera:


Int_Pointer p{ new int };
Int_Pointer p{ new int };

if ( p.is_valid() )
{
  Int_Pointer q{ new int };
  p = q;
}

if ( p.is_valid() )
{
  p.content_of() = 7;
}

Tips: Det går inte så speciellt bra.

Uppgift 12

Utgå från klassen i uppgift 10, men anta att pekaren pekar på 1GB data (datatyp GB_Data) istället för ett heltal. Redovisa hur följande kod skulle fungera:


GB_Pointer do_some_work(GB_Pointer data)
{
  // do some work
  return data;
}

GB_Pointer untreated_data{ new GB_Data; }
GB_Pointer treated_data{ do_some_work( untreated_data ) };

Finns någon fördel med detta jämfört med följande kod?


GB_Data do_some_work(GB_Data data)
{
  // do some work
  return data;
}
GB_Data untreated_data{}
GB_Data treated_data{ do_some_work( untreated_data ) };

Sidansvarig: Eric Ekström
Senast uppdaterad: 2016-10-27

IDA - Institutionen för datavetenskap