Informatik II - Ãœbung 5

Pascal Schärli

PascalCase@pascscha.ch

23.10.2020

Nachbesprechung

Pascal Schärli 23.10.2020

Ein wachsender Stack

public Stack(int capacity) {
    size = 0;
    buffer = new int[capacity];
}

Pascal Schärli 23.10.2020

Ein wachsender Stack

public String toString() {
    StringBuffer buf = new StringBuffer();
    buf.append("[");
    for (int i = 0; i < size; i++) {
        if (i != 0) buf.append(", ");
        buf.append(Integer.toString(buffer[i]));
    }
    buf.append("]");
    return buf.toString();
}

Pascal Schärli 23.10.2020

Ein wachsender Stack

private void grow() {
    int[] new_buffer = new int[2 * buffer.length];
    for (int i = 0; i < size; i++) {
        new_buffer[i] = buffer[i];
    }
    buffer = new_buffer;
}

Pascal Schärli 23.10.2020

Ein wachsender Stack

public void push(int number) {
   if (size == buffer.length) {
        grow();
    }
    buffer[size] = number;
    size += 1;
}

Pascal Schärli 23.10.2020

Ein wachsender Stack

public int pop() throws EmptyStackException {
    if (size == 0) throw new EmptyStackException();
    size -= 1;
    return buffer[size];
}

Pascal Schärli 23.10.2020

Ein wachsender Stack

public int peek() throws EmptyStackException {
    if (size == 0) throw new EmptyStackException();
    return buffer[size - 1];
}

Pascal Schärli 23.10.2020

Ein wachsender Stack

public boolean empty() {
    return size == 0;
}

public int size() {
    return size;
}

public int capacity() {
    return buffer.length;
}

Pascal Schärli 23.10.2020

Ackermann-Funktion

A(2,1)
  A(2,0)
    A(1,1)
      A(1,0)
        A(0,1)
        <- 2
      <- 2
      A(0,2)
      <- 3
    <- 3
  <- 3
  A(1,3)
    A(1,2)
      A(1,1)
        A(1,0)
          A(0,1)
          <- 2
        <- 2
        A(0,2)
        <- 3
      <- 3
      A(0,3)
      <- 4
    <- 4
    A(0,4)
    <- 5
  <- 5
<- 5

Pascal Schärli 23.10.2020

Ackermann-Funktion als Stack

public int A(int n, int m) {
    Stack stack = new Stack(10);
    stack.push(n);
    stack.push(m);

    while (stack.size() != 1) {
        System.out.println(stack);
        final int cm = stack.pop();
        final int cn = stack.pop();
        if (cn == 0) {
            stack.push(cm + 1);
        } 
        else if (cm == 0) {
            stack.push(cn - 1);
            stack.push(1);
        } 
        else {
           stack.push(cn - 1);
            stack.push(cn);
            stack.push(cm - 1);
        }
    }
    System.out.println(stack);
    return stack.pop();
}

\(A(0,m) = m + 1\)

\(A(n,0) = A(n-1,1)\)

\(A(n,m) = A(n-1,A(n,m-1))\)

Pascal Schärli 23.10.2020

Ackermann-Bytecode

0: iload_1  
1: ifne 8  
4: iload_2  
5: iconst_1  
6: iadd  
7: ireturn  
8: iload_2  
9: ifne 21  
12: aload_0  
13: iload_1  
14: iconst_1  
15: isub  
16: iconst_1  
17: invokevirtual #16; //Method A:(II)I  
20: ireturn  
21: aload_0  
22: iload_1  
23: iconst_1  
24: isub  
25: aload_0  
26: iload_1  
27: iload_2  
28: iconst_1  
29: isub  
30: invokevirtual #16; //Method A:(II)I  
33: invokevirtual #16; //Method A:(II)I  
36: ireturn  
public int A(int n, int m) {
    if (n == 0){
        return m + 1;
    }
    if (m == 0){
        return A(n - 1, 1);
    }
    return A(n - 1, A(n, m - 1));
}

Pascal Schärli 23.10.2020

Vorlesung

Pascal Schärli 23.10.2020

Swap

 public static void swap(StringBuffer sbf1, StringBuffer sbf2)   {
	StringBuffer temp = sbf1;
	sbf1 = sbf2;
	sbf2 =temp;
 }
 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);
 
 
 Hello World
 
 Hello World
 Hello World

Output:

Pascal Schärli 23.10.2020

Call by Value / Reference

  • Call by value:
    • an Funktion übergebenen Daten werden kopiert
    • keine Verbindung mehr zwischen den Daten beim Aufrufer und den Daten in der Funktion
       
  • Call by reference:
    • Anstatt Daten zu kopieren werden Referenzen (Pointer) auf die Daten übergeben
    • Methodenaufrufe an einem so übergebenen Objekt arbeiten also auf demselben Objekt, das auch außerhalb sichtbar ist

Pascal Schärli 23.10.2020

Call by Value / Reference

  • In C++ war beides möglich:
    • Call by value: Daten werden kopiert und übergeben
    • Call by reference: Referenz auf die Daten wird übergeben


  • Java ist IMMER call by value!!
    • Bei der Ãœbergabe einer Referenz auf ein Objekt wird die Adresse in eine lokale Variable kopiert!
    • Bei Ãœbergabe eines primitiven Typs (char, int, float) wird der Wert in eine lokale Variable kopiert!

Pascal Schärli 23.10.2020

What went wrong?

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }
 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);

Output:

sbf1
address1
address1
"Hello"
address2
"World"
sbf2
address2
 
 
 Hello World

Pascal Schärli 23.10.2020

What went wrong?

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }
 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);
 
 
 Hello World

Output:

sbf1
address1
address1
"Hello"
address2
"World"
sbf2
address2
s1
address1
s2
address2
swap

Pascal Schärli 23.10.2020

What went wrong?

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }
 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);
 
 
 Hello World

Output:

sbf1
address1
address1
"Hello"
address2
"World"
sbf2
address2
s1
address2
s2
address1
swap

Pascal Schärli 23.10.2020

What went wrong?

 public static void swap(StringBuffer s1, StringBuffer s2){
	StringBuffer temp = s1;
	s1 = s2;
	s2 =temp;
 }
 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);
 
 
Hello World

Output:

sbf1
address1
address1
"Hello"
address2
"World"
sbf2
address2
Hello World
Hello World

Pascal Schärli 23.10.2020

Fix

public static void swap(StringBuffer s1, StringBuffer s2) {
    StringBuffer temp = new StringBuffer(s1);
    
    s1.delete(0, s1.length());
    s1.append(s2);
	
    s2.delete(0, s2.length());
    s2.append(temp);
}
 StringBuffer sbf1 = new StringBuffer("Hello");
 StringBuffer sbf2 = new StringBuffer("World");
		
 System.out.println(sbf1+" "+sbf2);
 swap(sbf1,sbf2);
 System.out.println(sbf1+" "+sbf2);
 
 
Hello World

Output:

sbf1
address1
address1
"Hello"
address2
"World"
sbf2
address2
Hello World
World Hello
s1
address1
s2
address2
swap
"Hello"
"World"

\(\rightarrow\) Man kann das zu Grunde liegende Objekt verändern!

Pascal Schärli 23.10.2020

Pakete - Beispiel

package node;

public class Node {
  public int value;
  public Node next;
  public Node(int value, Node next) {
    this.value = value;
    this.next = next;
  }  
}

Node.java

package u5a1;
import node.Node;

public class Lists {	
    public static String toString(Node node) {
        if (node == null) return "null";

        StringBuffer buf = new StringBuffer();
        buf.append(node.value).append(", ").append(toString(node.next));
        return buf.toString();
    }
}

Lists.java

{1, 4, 21, 8}
→ “1, 4, 21, 8, null“

Pascal Schärli 23.10.2020

How do you call that?

public class Impedance {
    private final String name;
    protected double real, imag;
    
    public Impedance(String name, double real, 
            double imag) {
        this.name = name;
        this.real = real;
        this.imag = imag;
    }

    public static Impedance add(String name, 
            Impedance z1, Impedance z2) {
        double real = z1.getReal() + z2.getReal(); 
        double imag = z1.getImag() + z2.getImag();
        return new Impedance(name, real, imag);
    }

    public String toString() {
        return getName() + " = " + getReal() + 
            " + i" + getImag();
    }

    public String getName() {
        return this.name;
    }

    public double getImag() {
        return this.imag;
    }

    public double getReal() {
        return this.real;
    }
}

Attribute

Konstruktor

Klassenmethoden

Instanzmethoden (nicht static)

Pascal Schärli 23.10.2020

Java Keywords

public class Impedance {
    private final String name;
    protected double real, imag;
    
    public Impedance(String name, double real, 
            double imag) {
        this.name = name;
        this.real = real;
        this.imag = imag;
    }

    public static Impedance add(String name, 
            Impedance z1, Impedance z2) {
        double real = z1.getReal() + z2.getReal(); 
        double imag = z1.getImag() + z2.getImag();
        return new Impedance(name, real, imag);
    }

    public String toString() {
        return getName() + " = " + getReal() + 
            " + i" + getImag();
    }

    public String getName() {
        return this.name;
    }

    public double getImag() {
        return this.imag;
    }

    public double getReal() {
        return this.real;
    }
}
  • final: Darf nicht verändert werden
  • public: Für alle Sichtbar
  • private: In der Klasse Sichtbar
  • protected: in abgeleiteten Klassenund im package Sichtbar
  • static: unabhängig von der Klasseninstanz, existiert nur einmal für alle Objekte dieser Klasse

Pascal Schärli 23.10.2020

Naming Conventions

  • Pakete:
    • Alles Kleinbuchstaben (lowercase)
    • Beispiel: mypackage, u4a2
  • Klassen:
    • Erster Buchstabe Gross (PascalCase)
    • Beispiel: RandomArray, StringBuffer
  • Funktionen & Variabeln
    • Erster Buchstabe klein (camelCase)
    • Beispiel: toString(), myFunction(), myVar
  • Konstanten (Static):
    • Alles Gross, Wörter mit _ getrennt (UPPER_SNAKE_CASE)
    • Beispiel: MY_CONSTANT, SPEED_OF_LIGHT

Pascal Schärli 23.10.2020

Linked List

package list;

public class List {
	public int val;
	public List next;

	public List(int val, List next) 
	{
		this.val = val;
		this.next = next;
	}	
}

1

[1, 21, 4]

Pascal Schärli 23.10.2020

val  =
next =

21

val  =
next =

4

val  =
next =
null

Pascal Schärli 23.10.2020

Vorbesprechung

Pascal Schärli 23.10.2020

Einfach verkettete Listen

package list;

public class List {
    public int val;
    public List next;

    public List(int val, List next) {
        this.val = val;
        this.next = next;
    }
}
  • Implementiert eine Linked-List
  • Achtung: Spezielle Namensgebung
    • List \(\rightarrow\) Eine Node/Knoten aus der Liste
    • Lists \(\rightarrow\) Helperfunktionen um die Liste zu verändern
  • Ihr müsst die Funktionen rekursiv implementieren!
package u5a1;

import java.util.NoSuchElementException;
import list.List; 


public class Lists {  
	// TODO
}

Pascal Schärli 23.10.2020

Einfach verkettete Listen

public static String toString(List list){
    if (list == null) return "null";
    
    StringBuffer buf = new StringBuffer();
    buf.append(list.value).append(", ").append(toString(list.next));
    return buf.toString();
}
val  =
next =

1

val  =
next =

9

val  =
next =

4

null
"1, " + toString(list.next)
"9, " + toString(list.next)
"4, " + toString(list.next)
"null"
= "null"
= "4, null"
= "9, 4, null"
= "1, 9, 4, null"

Pascal Schärli 23.10.2020

Einfach verkettete Listen

add \(\rightarrow\) Neuer Wert am Anfang anhängen

list1 \(\widehat{=}\) [1, 21]

add(list1, 4);

\(\Rightarrow\) list1 \(\widehat{=}\) [4, 1, 21]

size \(\rightarrow\) Bestimmt die Grösse einer Liste

list1 \(\widehat{=}\) [4, 1, 21]

size(list1);

\(\Rightarrow\) 3

Pascal Schärli 23.10.2020

Einfach verkettete Listen

sum \(\rightarrow\) Bestimmt Summe aller Elemente

list1 \(\widehat{=}\) [4, 1, 21]

sum(list1);

\(\Rightarrow\) 26

last \(\rightarrow\) Bestimmt den letzten Knoten einer Liste

list1 \(\widehat{=}\) [4, 1, 21]

list2 = last(list1);

\(\Rightarrow\) list2 \(\widehat{=}\) [21]

Pascal Schärli 23.10.2020

Einfach verkettete Listen

sublist \(\rightarrow\) Schneidet den Anfang einer Liste ab

list1 \(\widehat{=}\) [4, 1, 21]

list2 = sublist(list1,1);

\(\Rightarrow\) list2 \(\widehat{=}\) [1, 21]

valueAt \(\rightarrow\) Bestimmt den Wert von einem bestimmten Element

list1 \(\widehat{=}\) [4, 1, 21]

valueAt(list1,2);

\(\Rightarrow\) 21

Pascal Schärli 23.10.2020

Einfach verkettete Listen

index \(\rightarrow\) bestimmt den ersten Index bei dem ein bestimmter Wert in der Liste gespeichert ist

list1 \(\widehat{=}\) [4, 1, 21]

index(list1,21);

\(\Rightarrow\) 2

Pascal Schärli 23.10.2020

Modifizierung von Listen

  • Klasse MutableLists erweitert die Klasse Lists mit Methoden zum Bearbeiten von Listen
     
  • Rekursive Implementation
     
  • Benützt eure Methoden in Lists aus der vorherigen Aufgabe

Pascal Schärli 23.10.2020

append \(\rightarrow\) Neuer Wert am Ende anhängen

list1 \(\widehat{=}\) [4, 1]

append(list1,21);

\(\Rightarrow\) list1 \(\widehat{=}\) [4, 1, 21]

concat \(\rightarrow\) Verbindet zwei Listen

list1 \(\widehat{=}\) [4, 1], list2 \(\widehat{=}\) [21, 8]

concat(list1,list2);

\(\Rightarrow\) list1 \(\widehat{=}\) [4, 1, 21, 8]

Modifizierung von Listen

Pascal Schärli 23.10.2020

insertAt \(\rightarrow\) Wert an bestimmter Stelle einfügen

list1 \(\widehat{=}\) [4, 1]

insertAt(list1,1,3);

\(\Rightarrow\) list1 \(\widehat{=}\) [4, 3, 1]

list1 \(\widehat{=}\) [4, 1], list2 \(\widehat{=}\) [9, 10]

insertAt(list1,1,list2);

\(\Rightarrow\) list1 \(\widehat{=}\) [4, 9, 10, 1]

Modifizierung von Listen

insertAt \(\rightarrow\) Liste an bestimmter Stelle einfügen

Pascal Schärli 23.10.2020

remove \(\rightarrow\) Wert an bestimmter Stelle entfernen

list1 \(\widehat{=}\) [4, 1, 21, 8]

remove(list1,2);

\(\Rightarrow\) list1 \(\widehat{=}\) [4, 1, 8]

Modifizierung von Listen

Pascal Schärli 23.10.2020

Sortieren von Listen

  • Klasse SortedLists erweitert die Klasse Lists mit Methoden zum Bearbeiten von Listen
     
  • Rekursive Implementation

  • Zuerst funkiton insertSorted() machen, welche einen Wert in einen bereits sortierten Array einfügt.

  • list.next sortieren, dann list.value mit insertSorted in den sortierten Rest einfügen

Pascal Schärli 23.10.2020

Sortieren von Listen

insertSorted \(\rightarrow\) Fügt einer Sortierten Liste einen weiteren Wert hinzu

list1 \(\widehat{=}\) [1, 4, 21]

insertSorted(list1,8);

\(\Rightarrow\) list1 \(\widehat{=}\) [1, 4, 8, 21]

Pascal Schärli 23.10.2020

Noch ein wachsender Stack

  • Klasse Stack hat eine Private Variable vom Typ List, welches die Daten im Stack speichert.
     
  • Implementiert damit einen Stack, Ihr könnt eure Lists Hilfsfunktionen verwenden.
     
  • Falls ihr etwas neu Schreibt \(\rightarrow\) Rekursive Implementation

Pascal Schärli 23.10.2020

Noch ein wachsender Stack

push \(\rightarrow\) Wert oben auf den Stack legen

list \(\widehat{=}\) [1, 21]

push(4);

\(\Rightarrow\) list \(\widehat{=}\) [4, 1, 21]

list \(\widehat{=}\) [4, 1, 21]

pop();

\(\Rightarrow\) list \(\widehat{=}\) [1, 21]

\(\Rightarrow\) return 4

pop \(\rightarrow\) Element oben vom Stack wegnehmen

Pascal Schärli 23.10.2020

Noch ein wachsender Stack

peek \(\rightarrow\) Oberster Wert vom Stack lesen

list \(\widehat{=}\) [1, 21]

peek();

\(\Rightarrow\) return 1

empty \(\rightarrow\) True falls Liste leer ist

size \(\rightarrow\) Grösse der Liste

Pascal Schärli 23.10.2020

Viel Spass!

Pascal Schärli 23.10.2020