Informatik I - Übung 10

Pascal Schärli

pascscha@student.ethz.ch

10.05.2019

Was gibts heute?

  • Best-Of Vorlesung
    • Klassen
    • Headerfiles
    • Pointers
    • New / Delete
  • Vorbesprechung
    • Quicksort

Pascal Schärli 10.05.2019

Vorlesung

Pascal Schärli 10.05.2019

Klassen

Pascal Schärli 10.05.2019

  • Klassen sind wie Structs, nur dass ihre Members standardmässig private sind.
  • Sie können sowohl Variablen als auch Funktionen beinhalten.
  • Klassennamen sind aus Konvention gross geschrieben.

Klassen

Pascal Schärli 10.05.2019

#include <iostream>

class Wallet{
    unsigned int money;
    std::string owner;

public:
    Wallet(std::string o, unsigned int m){
        money = m;
        owner = o;
    }

    unsigned int money_left(){
        return money;
    }

    bool pay(unsigned int amount){
        if(money >= amount){
            money -= amount;
            return true;
        }
        else{
            return false;
        }
    }

    std::string get_owner(){
        return owner;
    }
};
main(){
    Wallet w(100, "Pascal");

    std::cout << w.money_left() << " ";
    w.money += 100;
    std::cout << w.pay(150)

    std::cout << w.owner << "/n";
    w.get_owner() = "Eve";
    std::cout << w.owner << "/n";

}

Findet die 10 Fehler

Klassen

Pascal Schärli 10.05.2019

#include <iostream>

class Wallet{
    unsigned int money;
    std::string owner;

public:
    Wallet(std::string o, unsigned int m){
        money = m;
        owner = o;
    }

    unsigned int money_left(){
        return money;
    }

    bool pay(unsigned int amount){
        if(money >= amount){
            money -= amount;
            return true;
        }
        else{
            return false;
        }
    }

    std::string get_owner(){
        return owner;
    }
};
int main(){
    Wallet w("Pascal",100);
    std::cout << w.money_left() << " " 
              << w.get_owner() << "\n";

    // Pay 50.-
    bool success1 = w.pay(50);
    std::cout << success1 << " " 
              << w.money_left() << " " 
              << w.get_owner() << "\n";

    // Pay 100.-
    bool success2 = w.pay(75);
    std::cout << success2 << " " 
              << w.money_left() << " "
              << w.get_owner() << "\n";
    return 0;
}
100 Pascal
1 50 Pascal
0 50 Pascal

Klassen

Pascal Schärli 10.05.2019

Wallet(std::string o, unsigned int m){
    money = m;
    owner = o;
}
Wallet(std::string o, unsigned int m): owner(o), money(m){}

Headerfiles (.h)

Pascal Schärli 10.05.2019

  • Um grössere Projekte besser strukturieren zu können werden "Headerfiles" verwendet.
  • Sie definieren was eine C++ Klasse macht, aber noch nicht wie.
  • Zu den Header Files kreiert man dann ein .cpp File, welches die Klasse implementiert.

Headerfiles (.h)

Pascal Schärli 10.05.2019

#ifndef WALLET_H
#define WALLET_H

#include <iostream>

class Wallet{
    unsigned int money;
    std::string owner;

public:
    // POST: initializes new wallet
    Wallet(std::string, unsigned int);
    
    // POST: returns how much money 
    //        is left in wallet
    unsigned int money_left();

    // POST: Pays an amount of money if
    //        there's enough available
    bool pay(unsigned int amount);

    // POST: returns the owner of 
              the wallet
    std::string get_owner();
};

#endif

wallet.h

Include Guard stellt sicher, dass Funktionen nicht mehrmals deklariert werden

Ende Include Guard

Funktionen werden deklariert aber nicht implementiert

Dokumentation (Pre/Post Conditions) schreibt man schon im Header file.

Header Files (.h)

Pascal Schärli 10.05.2019

Headerfile wird included

Funktionen werden implementiert

Keine Pre/Post Conditions mehr nötig

#include "wallet.h"

Wallet::Wallet(std::string o, unsigned int m){
    money = m;
    owner = o;
}

unsigned int Wallet::money_left(){
    return money;
}

bool Wallet::pay(unsigned int amount){
    if(money >= amount){
        money -= amount;
    return true;
    }
    else{
        return false;
    }
}

std::string Wallet::get_owner(){
    return owner;
}

wallet.cpp

Funktionsname nach dem Schema ClassName::functionName

Header Files (.h)

Pascal Schärli 10.05.2019

main.cpp

#include <iostream>
#include "wallet.h"

int main(){
    Wallet w("Pascal",100);
    std::cout << w.money_left() << " "
              << w.get_owner() << "\n";

    // Pay 50.-
    bool success1 = w.pay(50);
    std::cout << success1 << " "
              << w.money_left() << " "
              << w.get_owner() << "\n";

    // Pay 100.-
    bool success2 = w.pay(75);
    std::cout << success2 << " "
              << w.money_left() << " "
              << w.get_owner() << "\n";
}

Header File wird included

Falls ein .cpp File mitkompiliert wurde, welches:

  1. das Headerfile ebenfalls importiert und
  2. die Klasse implementiert,

kann die Klasse hier verwendet werden.

References Recap

Pascal Schärli 10.05.2019

int a = 1;
int b = 2;
int& x = a;
int& y = x;
y = b;
std::cout << a << " " << b << " " << x << " " << y << std::endl;
2 2 2 2

Pointers

Pascal Schärli 10.05.2019

  • Der Speicher in Computern ist in Bytes (8 Bit) aufgeteilt.
  • Jedes Byte hat eine Adresse
  • Ein Pointer speichert nicht einen Wert sondern die Adresse von einem Wert.

Beispiel

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

Pascal Schärli 10.05.2019

int a = 5;
int* x = &a;

char c = 'd';
char* z = &c;

5

840

int a

int* x

d

char c

char* z

850

x

z

Operatoren

Pascal Schärli 10.05.2019

&

  1. Bitwise AND
     
  2. Variabel als Referenz deklarieren
     
  3. Adresse einer Variabel herausfinden

*

  1. Multiplikation
     
  2. Variabel als Pointer deklarieren
     
  3. Inhalt von einem Pointer herausfinden
z = x & y;
int& y = x;
int* ptr_a = &a;
z = x * y;
int* ptr_a = &a;
int a = *ptr_a;

New & Delete

Pascal Schärli 10.05.2019

  • Mit dem Keyword new kann man Pointer erstellen, welche auf Daten zeigen die niemals out of scope gehen.
  • Im Gegenzug muss man selber die Daten mit dem Keyword delete löschen falls man diese nicht mehr braucht.

New & Delete

Pascal Schärli 10.05.2019

#include <iostream>

int* create_value(){
    int x = 5;
    return &x;
}

int main(){
    int* ptr = create_value();

    std::cout << *ptr << "\n";
    return 0;
}
warning: address of local variable ‘x’ returned

Segmentation fault (core dumped)
#include <iostream>

int* create_value(){
    int* x = new int(5);
    return x;
}

int main(){
    int* ptr = create_value();

    std::cout << *ptr << "\n";

    delete ptr;

    return 0;
}

5

New & Delete (Arrays)

Pascal Schärli 10.05.2019

#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        *(a + i) = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << *a << " ";
    std::cout << *(a + 1) << " ";
    std::cout << *(a + 2) << " ";
    std::cout << *(a + 3) << " ";
    std::cout << *(a + 4) << " ";

    delete[] a;

    return 0;
}

Stellt speicher für 5 Integer bereit

Pointer dereferenzieren um den dort gespiecherten Wert zu ändern

Pointer dereferenzieren um den dort gespiecherten Wert zu lesen

0 1 2 3 4

Output:

Arrays - Syntaktischer Zucker

Pascal Schärli 10.05.2019

*(a + 1)
a[1]
#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        *(a + i) = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << *a << " ";
    std::cout << *(a + 1) << " ";
    std::cout << *(a + 2) << " ";
    std::cout << *(a + 3) << " ";
    std::cout << *(a + 4) << " ";

    delete[] a;

    return 0;
}

#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        a[i] = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << a[0] << " ";
    std::cout << a[1] << " ";
    std::cout << a[2] << " ";
    std::cout << a[3] << " ";
    std::cout << a[4] << " ";

    delete[] a;

    return 0;
}

Beispiel

Pascal Schärli 10.05.2019

int* a = new int[5]{0, 8, 7, 2, -1};
int* ptr = a;         // pointer assignment
++ptr;                // Shift pointer to right
int my_int = *ptr;    // read target
ptr += 2;             // shift by 2 elements
*ptr = 18;            // overwrite target
int* past = a+5;
std::cout << my_int << " " << (ptr < past) << "\n";
delete[] a;

0

8

7

2

-1

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

ptr

ptr

my_int = 8

ptr

18

past

8 1

Output:

Findet die 3 Fehler

Pascal Schärli 10.05.2019

#include <iostream>
int main(){
    int* a = new int[7]{0, 6, 5, 3, 2, 4, 1};
    int* b = new int[7];
    int* c = b;

    // copy a into b using pointers
    for(int* p = a; p <= a + 7; ++p){
        *c++ = *p;
    }

    // cross-check
    for(int i = 0; i <= 7; ++i){
        if(a[i] != c[i]){
            std::cout << "Oops, copy error...\n";
        }
    }
    return 0;
}
#include <iostream>
int main(){
    int* a = new int[7]{0, 6, 5, 3, 2, 4, 1};
    int* b = new int[7];
    int* c = b;

    // copy a into b using pointers
    for(int* p = a; p < a + 7; ++p){
        *c++ = *p;
    }

    // cross-check
    for(int i = 0; i < 7; ++i){
        if(a[i] != b[i]){
            std::cout << "Oops, copy error...\n";
        }
    }
    return 0;
}

Aufgabe

Pascal Schärli 10.05.2019

// PRE: [b, e) and [o, o+(e-b)) are disjoint and valid ranges
void f (int* b, int* e, int* o) {
    while (b != e) {
        --e;
        *o = *e;
        ++o;
    }
}

1

3

-8

1

5

b

4

e

o

e

3

o

e

1

o

Aufgabe

Pascal Schärli 10.05.2019

// PRE: [b, e) and [o, o+(e-b)) are disjoint and valid ranges
// POST: 
//       
void f (int* b, int* e, int* o) {
    while (b != e) {
        --e;
        *o = *e;
        ++o;
    }
}
// PRE: [b, e) and [o, o+(e-b)) are disjoint and valid ranges
// POST: The range [b, e) is copied in reverse order into the
//        range [o, o+(e-b))
void f (int* b, int* e, int* o) {
    while (b != e) {
        --e;
        *o = *e;
        ++o;
    }
}

Aufgabe

Pascal Schärli 10.05.2019

// PRE: [b, e) and [o, o+(e-b)) are disjoint and valid ranges
void f (int* b, int* e, int* o) {
    while (b != e) {
        --e;
        *o = *e;
        ++o;
    }
}

Welche dieser Funktionsaufrufe ist valid?

f(a, a+5, a+5);
int* a = new int[5];
f(a, a+2, a+3);
f(a, a+3, a+2);

Out of bounds

Ranges not disjoint

Vorbesprechung

Pascal Schärli 10.05.2019

4: Quick Sort - input

Pascal Schärli 10.05.2019

void input(std::istream& is, int*& begin, int*& end)

Input:

5

3

2

1

4

5

5

3

2

1

4

5

  1. Speicher Allozieren
     
  2. Speicher Füllen
a = new int[size]

3

2

1

4

5

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

begin

end

end

end

end

end

end

4: Quick Sort - output

Pascal Schärli 10.05.2019

void output(std::ostream& os,const int* begin,const int* end)

Output:

3

2

1

4

5

3

2

1

4

5

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

begin

end

it

it

it

it

it

it

4: Quick Sort - pivot

Pascal Schärli 10.05.2019

int* pivot(int* begin, int* end)

3

2

3

4

5

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

begin

end

p

e

b

Wähle ein non-pivot Element (b)
Swappe entweder mit dem ersten (p) oder letzten (e) Element von der Range
Schrumpf die Range so dass das neu platzierte Element nicht mehr darin vorkommt.

3

2

b

p

2

3

1

1

p

1

3

b

5

4

e

5

4

b

5

5

e

return p

4: Quick Sort - quicksort

Pascal Schärli 10.05.2019

3

2

1

4

5

pivot

2

1

3

5

4

pivot

2

1

pivot

5

4

2

1

5

4

3

4: Quick Sort - main

Pascal Schärli 10.05.2019

int main () {
    int* begin;
    int* end;
    input(std::cin,begin,end);
    quicksort(begin,end);
    output(std::cout,begin,end);
    delete[] begin;
    return 0;
}

Viel Spass!

Pascal Schärli 10.05.2019