Informatik W11

Levin Ceglie

---

Outine

• Quiz
• Pointers
• Datenstrukturen und Iteratoren

Pointers

Ein Pointer oder auch Zeiger ist ein C++ Objekt, das auf eine Speicheradresse zeigt. Die Adresse eines Objekts a können wir immer mit &a ausgeben (nicht verwechseln mit Referenz).

Initialisierung

Ein Pointer wird im Allgemeinen mit

Typ* name;

initialisiert, wobei der Typ dem Typen der Adresse entsprechen muss.

Dereferenzierung

Um das tatsächliche Objekt zu erhalten, auf welches ein Pointer zeigt, dereferenziert man den Pointer. Dies geschieht mitters dem * Operator. Zum Beispiel wie folgt falls p ein Pointer auf ein Objekt ist, für welches die Ausgabe mittels << definiert ist:

std::cout << *p;

Nullpointer

Mit Typ* p = nullptr lässt sich ein Pointer erstellen, der “ins Nichts” zeigt, das heisst er zeigt auf keine Speicheradresse.
Achtung: Das dereferenzieren eines nullptr führt zu einem Error.

Die Symbole & und * in C++

In C++ hat das Symbol & drei verschiedene Bedeutungen, abhängig davon, wo es steht:

1. Der logische UND-Operator.
   Beispiel: bool valid = a && b;
2. Deklaration einer Variable als Referenz.
   Beispiel: int& x = a;
3. Zugriff auf Adresse einer Variablen.
   Beispiel: int* p = &a;

Das Symbol * hat ebenso drei verschiedene Bedeutungen, abhängig davon, wo es steht:

1. Arithmetischer Multiplikationsoperator.
   Beispiel: int x = 3 * a;
2. Deklaration einer Pointer Variable.
   Beispiel: int* p = &a;
3. Dereferenzierungsoperator eines Pointers, um auf die Speicherstelle zuzugreifen.
   Beispiel: int a = *p;

Constness

Wie bei den üblichen Datentypen, gibt es auch die Möglichkeit konstante Pointer zu definieren. Dies geschieht mit Typ* const p;. Als Faustregel, kann man den Datentyp von rechts nach links lesen, so würde man int* const p; lesen als “konstanter (const) pointer (*) auf einen Integer (int). Weitere Beispiele:

int* p;                        // => dynamischer Pointer auf dynamischen Wert
const int* p;              // => dynamischer Pointer auf konstanten Wert
int const* p;              // => dynamischer Pointer auf konstanten Wert
int* const p;              // => konstanter Pointer auf dynamischen Wert
const int* const p;    // => konstanter Pointer auf konstanten Wert

Datenstrukturen und Iteratoren

Aufgabe (our_list::init)

Zusammen our_list.h durchgehenund Fragen klären. Danach individuel Aufgabe lösen.

Lösung:

our_list::our_list(our_list::const_iterator begin, our_list::const_iterator end) {
  this->head = nullptr;
  if (begin == end) {
    return;
  }
  // Let's add the first element from the iterator.
  our_list::const_iterator it = begin;
  this->head = new lnode { *it, nullptr };
  ++it;
  lnode *node = this->head;
  // Let's add all the remaining elements.
  for (; it != end; ++it) {
    node->next = new lnode { *it, nullptr };
    node = node->next;
  }
}

Aufgabe (our_list::swap)

Lösung:

void our_list::swap(unsigned int index) {
 
  lnode* prev = nullptr;
  lnode* curr = this->head;
  bool swap_head = index==0;
  
  // Find the element.
  while (index > 0) {
    prev = curr;
    curr = curr->next;
    --index;
  }
  
  assert(curr != nullptr);
  assert(curr->next != nullptr);
  
  // Swap with the next one.
  lnode* tmp = curr->next;
  curr->next = curr->next->next;
  tmp->next = curr;
  
  if(swap_head){
    this->head = tmp;
  }
  else{
    prev->next = tmp;
  }
}

Aufgabe (our_list::extend)

Lösung:

void our_list::extend(our_list::const_iterator begin, our_list::const_iterator end) {
  if (begin == end) {
    return;
  }
  our_list::const_iterator it = begin;
  if (this->head == nullptr) {
    this->head = new lnode { *it, nullptr };
    ++it;
  }
  lnode *n = this->head;
  while (n->next != nullptr) {
    n = n->next;
  }
  for (; it != end; ++it) {
    n->next = new lnode { *it, nullptr };
    n = n->next;
  }
}