pages/Kapitel09-page-01.svg

pages/Kapitel09-page-02.svg

pages/Kapitel09-page-03.svg

pages/Kapitel09-page-04.svg

pages/Kapitel09-page-05.svg

pages/Kapitel09-page-06.svg

pages/Kapitel09-page-07.svg

pages/Kapitel09-page-08.svg

pages/Kapitel09-page-09.svg

pages/Kapitel09-page-10.svg

pages/Kapitel09-page-11.svg

pages/Kapitel09-page-12.svg

pages/Kapitel09-page-13.svg

pages/Kapitel09-page-14.svg

pages/Kapitel09-page-15.svg

pages/Kapitel09-page-16.svg

pages/Kapitel09-page-17.svg

pages/Kapitel09-page-18.svg

pages/Kapitel09-page-19.svg

pages/Kapitel09-page-20.svg

pages/Kapitel09-page-21.svg

pages/Kapitel09-page-22.svg

pages/Kapitel09-page-23.svg

pages/Kapitel09-page-24.svg

pages/Kapitel09-page-25.svg

pages/Kapitel09-page-26.svg

pages/Kapitel09-page-27.svg

pages/Kapitel09-page-28.svg

pages/Kapitel09-page-29.svg

pages/Kapitel09-page-30.svg

pages/Kapitel09-page-31.svg

pages/Kapitel09-page-32.svg

pages/Kapitel09-page-33.svg

pages/Kapitel09-page-34.svg

pages/Kapitel09-page-35.svg

pages/Kapitel09-page-36.svg

pages/Kapitel09-page-37.svg

pages/Kapitel09-page-38.svg

pages/Kapitel09-page-39.svg

pages/Kapitel09-page-40.svg

pages/Kapitel09-page-41.svg

pages/Kapitel09-page-42.svg

pages/Kapitel09-page-43.svg

pages/Kapitel09-page-44.svg

pages/Kapitel09-page-45.svg

pages/Kapitel09-page-46.svg

pages/Kapitel09-page-47.svg

pages/Kapitel09-page-48.svg

pages/Kapitel09-page-49.svg

pages/Kapitel09-page-50.svg

pages/Kapitel09-page-51.svg

pages/Kapitel09-page-52.svg

pages/Kapitel09-page-53.svg

pages/Kapitel09-page-54.svg

pages/Kapitel09-page-55.svg

pages/Kapitel09-page-56.svg

pages/Kapitel09-page-57.svg

pages/Kapitel09-page-58.svg

Live-Demo - Stack

#include <iostream>

using namespace std;

template <typename T>
class Stack{
private:
	static int constexpr maxSize = 100;
	T data[maxSize];  // Array mit Daten
	int sz;			  // Stapelzeiger
	void error(const char* s)	{
		cerr << s << endl;
		exit(1);
	}
public:
	Stack(): sz{-1} {
	}
	void push(T& x) {
		if (full()) {
			error("voll");
		}
		data[++sz] = x;
	}
	void pop() {
		if (empty()) {
			error("leer");
		}
		sz--;
	}
	T top() {
		if (empty()) {
			error("leer");
		}
		return data[sz];
	}
	bool empty() {
	   return (sz == -1);
	}
	bool full() {
	   return (sz == maxSize-1);
	}

};

int main() {
	Stack<int> s;

	int i = 1;
	while (!s.full()) {
		s.push(i);
		i++;
	}
	cout << s.top() << endl;

	for (int i = 1; i <= 90; ++i) {
		s.pop();
	}

	while (!s.empty()) {
		cout << s.top() << endl;
		s.pop();
	}

	s.pop();

	return 0;

}
compiler

pages/Kapitel09-page-59.svg

pages/Kapitel09-page-60.svg

pages/Kapitel09-page-61.svg

pages/Kapitel09-page-62.svg

pages/Kapitel09-page-63.svg

pages/Kapitel09-page-64.svg

pages/Kapitel09-page-65.svg

pages/Kapitel09-page-66.svg

pages/Kapitel09-page-67.svg

pages/Kapitel09-page-68.svg

pages/Kapitel09-page-69.svg

pages/Kapitel09-page-70.svg

pages/Kapitel09-page-71.svg

pages/Kapitel09-page-72.svg

pages/Kapitel09-page-73.svg

pages/Kapitel09-page-74.svg

pages/Kapitel09-page-75.svg

pages/Kapitel09-page-76.svg

pages/Kapitel09-page-77.svg

pages/Kapitel09-page-78.svg

pages/Kapitel09-page-79.svg

pages/Kapitel09-page-80.svg

pages/Kapitel09-page-81.svg

pages/Kapitel09-page-82.svg

pages/Kapitel09-page-83.svg

pages/Kapitel09-page-84.svg

pages/Kapitel09-page-85.svg

pages/Kapitel09-page-86.svg

pages/Kapitel09-page-87.svg

pages/Kapitel09-page-88.svg

pages/Kapitel09-page-89.svg

pages/Kapitel09-page-90.svg

pages/Kapitel09-page-91.svg

pages/Kapitel09-page-92.svg

pages/Kapitel09-page-93.svg

pages/Kapitel09-page-94.svg

pages/Kapitel09-page-95.svg

pages/Kapitel09-page-96.svg

pages/Kapitel09-page-97.svg

pages/Kapitel09-page-98.svg

pages/Kapitel09-page-99.svg

pages/Kapitel09-page-100.svg

pages/Kapitel09-page-101.svg

pages/Kapitel09-page-102.svg

pages/Kapitel09-page-103.svg

pages/Kapitel09-page-104.svg

pages/Kapitel09-page-105.svg

pages/Kapitel09-page-106.svg

pages/Kapitel09-page-107.svg

pages/Kapitel09-page-108.svg

pages/Kapitel09-page-109.svg

pages/Kapitel09-page-110.svg

pages/Kapitel09-page-111.svg

pages/Kapitel09-page-112.svg

pages/Kapitel09-page-113.svg

pages/Kapitel09-page-114.svg

pages/Kapitel09-page-115.svg

pages/Kapitel09-page-116.svg

pages/Kapitel09-page-117.svg

pages/Kapitel09-page-118.svg

pages/Kapitel09-page-119.svg

pages/Kapitel09-page-120.svg

pages/Kapitel09-page-121.svg

pages/Kapitel09-page-122.svg

pages/Kapitel09-page-123.svg

pages/Kapitel09-page-124.svg

pages/Kapitel09-page-125.svg

pages/Kapitel09-page-126.svg

pages/Kapitel09-page-127.svg

pages/Kapitel09-page-128.svg

pages/Kapitel09-page-129.svg

pages/Kapitel09-page-130.svg

pages/Kapitel09-page-131.svg

pages/Kapitel09-page-132.svg

pages/Kapitel09-page-133.svg

pages/Kapitel09-page-134.svg

pages/Kapitel09-page-135.svg

pages/Kapitel09-page-136.svg

pages/Kapitel09-page-137.svg

pages/Kapitel09-page-138.svg

pages/Kapitel09-page-139.svg

pages/Kapitel09-page-140.svg

pages/Kapitel09-page-141.svg

pages/Kapitel09-page-142.svg

pages/Kapitel09-page-143.svg

pages/Kapitel09-page-144.svg

pages/Kapitel09-page-145.svg

pages/Kapitel09-page-146.svg

pages/Kapitel09-page-147.svg

pages/Kapitel09-page-148.svg

pages/Kapitel09-page-149.svg

pages/Kapitel09-page-150.svg

pages/Kapitel09-page-151.svg

pages/Kapitel09-page-152.svg

pages/Kapitel09-page-153.svg

pages/Kapitel09-page-154.svg

pages/Kapitel09-page-155.svg

Live-Demo - Queue

#include <iostream>

using namespace std;

template <typename T>
class Queue {
private:
	struct Element {
		T data;
		Element *next;
	} *head, *tail;
	void error(char const *info) {
		cerr << info << endl;
		exit(1);
	}
public:
	Queue() {
		head = tail = nullptr;
	}
#ifndef NOCOPY
	Queue(Queue<T> const & list) {
		head = tail = nullptr;
		for (Element* e = list.head; e != nullptr; e = e->next) {
			enqueue(e->data);
		}
	}
#endif
	T front() {
		if (empty()) {
			error("leer");
		}
		return head->data;
	}
	void enqueue(T& x) {
		Element* e = new Element{x, nullptr};
		if (empty()) {
			head = tail = e;
		} else {
			tail->next = e;
			tail = e;
		}
	}
	void dequeue() {
		if (empty()) {
			error("leer");
		}
		Element *e = head;
		head = head->next;
		if (head == nullptr) {
			tail = nullptr;
		}
		delete e;
	}
	void debug_print(const char* name) {
		cout << name << ": ";
		cout << "head = " << head << ", tail = " << tail << endl;
	}
	void print(const char* name) {
		cout << name << ": ";
		Element* e = head;
		while (e != nullptr){
			cout << e->data << "->";
			e = e->next;
		}
		cout << "nullptr" << endl;
	}
	bool empty() {
		return (head == nullptr);
	}
	bool is_elem(T& x) {
		Element* e = head;
		while (e != nullptr){
			if (e->data == x) {
				return true;
			}
			e = e->next;
		}
		return false;
	}
	void clear() {
		while (head != nullptr){
			Element * e = head;
			head = head->next;
			delete e;
		}
		tail = nullptr;
	}
	Queue<T>& operator=(Queue const & q){
		if (this == &q) {
			return *this;
		}
		clear();
		Element *e = q.head;
		while (e != nullptr) {
			enqueue(e->data);
			e = e->next;
		}
		return *this;
	}
	bool operator==(Queue const & q) {
		if (this == &q) {
			return true;
		}
		Element *e1 = head;
		Element *e2 = q.head;
		// vergleiche alle Elemente:
		while (e1 != nullptr && e2 != nullptr) {
			if (e1->data != e2->data) {
				return false;
			}
			e1 = e1->next;
			e2 = e2->next;
		}
		return (e1 == e2); // beide müssen nullptr sein
	}
	Queue<T>& operator+=(Queue const & q){
		if (this == &q) {
			return *this;
		}
		Element *e = q.head;
		while (e != nullptr) {
			enqueue(e->data);
			e = e->next;
		}
		return *this;
	}
	~Queue(){
		clear();
	}
};

int main() {
	Queue<int> q;

	for (int i = 2; i <= 11; ++i) {
		q.enqueue(i);
	}

	for (int i = 1; i <= 5; ++i) {
		cout << q.front() << endl;
		q.dequeue();
	}
	while (!q.empty()) {
		cout << q.front() << endl;
		q.dequeue();
	}
	if (q.empty()) {
		cout << "q ist leer" << endl;
	}

	return 0;

}
compiler

Live-Demo - Queue defekt

#include <iostream>
#define NOCOPY

using namespace std;

template <typename T>
class Queue {
private:
	struct Element {
		T data;
		Element *next;
	} *head, *tail;
	void error(char const *info) {
		cerr << info << endl;
		exit(1);
	}
public:
	Queue() {
		head = tail = nullptr;
	}
#ifndef NOCOPY
	Queue(Queue<T> const & list) {
		head = tail = nullptr;
		for (Element* e = list.head; e != nullptr; e = e->next) {
			enqueue(e->data);
		}
	}
#endif
	T front() {
		if (empty()) {
			error("leer");
		}
		return head->data;
	}
	void enqueue(T& x) {
		Element* e = new Element{x, nullptr};
		if (empty()) {
			head = tail = e;
		} else {
			tail->next = e;
			tail = e;
		}
	}
	void dequeue() {
		if (empty()) {
			error("leer");
		}
		Element *e = head;
		head = head->next;
		if (head == nullptr) {
			tail = nullptr;
		}
		delete e;
	}
	void debug_print(const char* name) {
		cout << name << ": ";
		cout << "head = " << head << ", tail = " << tail << endl;
	}
	void print(const char* name) {
		cout << name << ": ";
		Element* e = head;
		while (e != nullptr){
			cout << e->data << "->";
			e = e->next;
		}
		cout << "nullptr" << endl;
	}
	bool empty() {
		return (head == nullptr);
	}
	bool is_elem(T& x) {
		Element* e = head;
		while (e != nullptr){
			if (e->data == x) {
				return true;
			}
			e = e->next;
		}
		return false;
	}
	void clear() {
		while (head != nullptr){
			Element * e = head;
			head = head->next;
			delete e;
		}
		tail = nullptr;
	}
	Queue<T>& operator=(Queue const & q){
		if (this == &q) {
			return *this;
		}
		clear();
		Element *e = q.head;
		while (e != nullptr) {
			enqueue(e->data);
			e = e->next;
		}
		return *this;
	}
	bool operator==(Queue const & q) {
		if (this == &q) {
			return true;
		}
		Element *e1 = head;
		Element *e2 = q.head;
		// vergleiche alle Elemente:
		while (e1 != nullptr && e2 != nullptr) {
			if (e1->data != e2->data) {
				return false;
			}
			e1 = e1->next;
			e2 = e2->next;
		}
		return (e1 == e2); // beide müssen nullptr sein
	}
	Queue<T>& operator+=(Queue const & q){
		if (this == &q) {
			return *this;
		}
		Element *e = q.head;
		while (e != nullptr) {
			enqueue(e->data);
			e = e->next;
		}
		return *this;
	}
	~Queue(){
		clear();
	}
};

int main() {
	Queue<int> q;
	for (int i = 1; i <=5; ++i) {
		q.enqueue(i);
	}
	Queue<int> q2 = q;

	cout << "q.front() = " << q.front() << ", q2.front() = " << q2.front() << endl;

	q.debug_print("q ");
	q2.debug_print("q2");
	cout << endl;

	q.dequeue();

	cout << "q.front() = " << q.front() << ", q2.front() = " << q2.front() << endl;

	q.debug_print("q ");
	q2.debug_print("q2");

	return 0;

}
compiler

pages/Kapitel09-page-156.svg

pages/Kapitel09-page-157.svg

pages/Kapitel09-page-158.svg

pages/Kapitel09-page-159.svg

pages/Kapitel09-page-160.svg

pages/Kapitel09-page-161.svg

pages/Kapitel09-page-162.svg

pages/Kapitel09-page-163.svg

pages/Kapitel09-page-164.svg

pages/Kapitel09-page-165.svg

pages/Kapitel09-page-166.svg

pages/Kapitel09-page-167.svg

pages/Kapitel09-page-168.svg

pages/Kapitel09-page-169.svg

pages/Kapitel09-page-170.svg

pages/Kapitel09-page-171.svg

pages/Kapitel09-page-172.svg

pages/Kapitel09-page-173.svg

pages/Kapitel09-page-174.svg

pages/Kapitel09-page-175.svg

pages/Kapitel09-page-176.svg

pages/Kapitel09-page-177.svg

pages/Kapitel09-page-178.svg

pages/Kapitel09-page-179.svg

pages/Kapitel09-page-180.svg

pages/Kapitel09-page-181.svg

pages/Kapitel09-page-182.svg

pages/Kapitel09-page-183.svg

pages/Kapitel09-page-184.svg

pages/Kapitel09-page-185.svg

Ankündigungen

🤓 Probeklausur 🥵

  • Dienstag, 17.12., von 14:15 Uhr bis 15:45 Uhr
  • Anmeldung bis Donnerstag, 12.12. um 12 Uhr notwendig
  • Die Bearbeitung und Abgabe ist freiwillig
  • Es können bis zu 25 zusätzliche Punkte erworben werden

🎅 Weihnachtsvorlesung 🎄

  • Donnerstag, 19.12.
  • Inhalt
    • Rekapitulation Kapitel 1 - 9
    • Live-Beispiele und Experimente
    • Wichtig: Bereit Euch bitte mit konkreten Fragen vor!
  • Festliche Stimmung
    • Wir bringen Punsch (und vielleicht auch Glühwein) mit
    • Ihr bringt bitte gute Laune, Tasse und ggf. Gebäck mit

Wissensspeicher 13

Abstrakte Datentypen

  • Beschreibt das Layout von Datenstrukturen
  • Deffiniert die zugehörigen Operationen
  • Wichtig: Es wird nur der Effekt eine Operation definiert
  • Die Umsetzung spielt erst mal keine Rolle

Beispiele

  • Stack
    • Beispiel: ein Stapel von Tellern
    • push legt etwas auf den Stapel, pop entfernt oberstes Element
    • LIFO-Prinzip: last in, first out
  • Schlange
    • Beispiel: Warteschlange an der Kasse
    • enqueue hängt etwas hinten an, dequeue entfernt vorne etwas
    • FIFO-Printip: first in, first out

pages/Kapitel09-page-186.svg

pages/Kapitel09-page-187.svg

pages/Kapitel09-page-188.svg

pages/Kapitel09-page-189.svg

pages/Kapitel09-page-190.svg

pages/Kapitel09-page-191.svg

pages/Kapitel09-page-192.svg

pages/Kapitel09-page-193.svg

pages/Kapitel09-page-194.svg

pages/Kapitel09-page-195.svg

pages/Kapitel09-page-196.svg

pages/Kapitel09-page-197.svg

pages/Kapitel09-page-198.svg

pages/Kapitel09-page-199.svg

pages/Kapitel09-page-200.svg

pages/Kapitel09-page-201.svg

pages/Kapitel09-page-202.svg

pages/Kapitel09-page-203.svg

pages/Kapitel09-page-204.svg

pages/Kapitel09-page-205.svg

pages/Kapitel09-page-206.svg

pages/Kapitel09-page-207.svg

pages/Kapitel09-page-208.svg

pages/Kapitel09-page-209.svg

pages/Kapitel09-page-210.svg

pages/Kapitel09-page-211.svg

pages/Kapitel09-page-212.svg

pages/Kapitel09-page-213.svg

pages/Kapitel09-page-214.svg

pages/Kapitel09-page-215.svg

pages/Kapitel09-page-216.svg

pages/Kapitel09-page-217.svg

pages/Kapitel09-page-218.svg

Live-Demo - Queue mit Operatoren

#include <iostream>

using namespace std;

template <typename T>
class Queue {
private:
	struct Element {
		T data;
		Element *next;
	} *head, *tail;
	void error(char const *info) {
		cerr << info << endl;
		exit(1);
	}
public:
	Queue() {
		head = tail = nullptr;
	}
#ifndef NOCOPY
	Queue(Queue<T> const & list) {
		head = tail = nullptr;
		for (Element* e = list.head; e != nullptr; e = e->next) {
			enqueue(e->data);
		}
	}
#endif
	T front() {
		if (empty()) {
			error("leer");
		}
		return head->data;
	}
	void enqueue(T& x) {
		Element* e = new Element{x, nullptr};
		if (empty()) {
			head = tail = e;
		} else {
			tail->next = e;
			tail = e;
		}
	}
	void dequeue() {
		if (empty()) {
			error("leer");
		}
		Element *e = head;
		head = head->next;
		if (head == nullptr) {
			tail = nullptr;
		}
		delete e;
	}
	void debug_print(const char* name) {
		cout << name << ": ";
		cout << "head = " << head << ", tail = " << tail << endl;
	}
	void print(const char* name) {
		cout << name << ": ";
		Element* e = head;
		while (e != nullptr){
			cout << e->data << "->";
			e = e->next;
		}
		cout << "nullptr" << endl;
	}
	bool empty() {
		return (head == nullptr);
	}
	bool is_elem(T& x) {
		Element* e = head;
		while (e != nullptr){
			if (e->data == x) {
				return true;
			}
			e = e->next;
		}
		return false;
	}
	void clear() {
		while (head != nullptr){
			Element * e = head;
			head = head->next;
			delete e;
		}
		tail = nullptr;
	}
	Queue<T>& operator=(Queue const & q){
		if (this == &q) {
			return *this;
		}
		clear();
		Element *e = q.head;
		while (e != nullptr) {
			enqueue(e->data);
			e = e->next;
		}
		return *this;
	}
	bool operator==(Queue const & q) {
		if (this == &q) {
			return true;
		}
		Element *e1 = head;
		Element *e2 = q.head;
		// vergleiche alle Elemente:
		while (e1 != nullptr && e2 != nullptr) {
			if (e1->data != e2->data) {
				return false;
			}
			e1 = e1->next;
			e2 = e2->next;
		}
		return (e1 == e2); // beide müssen nullptr sein
	}
	Queue<T>& operator+=(Queue const & q){
		if (this == &q) {
			return *this;
		}
		Element *e = q.head;
		while (e != nullptr) {
			enqueue(e->data);
			e = e->next;
		}
		return *this;
	}
	~Queue(){
		clear();
	}
};

int main() {
	Queue<int> q;

	for (int i = 1; i <=5; ++i) {
		q.enqueue(i);
	}
	
	q.print("q");
	
	Queue<int> q2{q};
	
	q2.print("q2");
	cout << "q == q2: " << (q == q2) << endl;
	cout << endl;
	
	q2 += q;
	q2.print("q2 += q");
	
	cout << "q == q2: " << (q == q2) << endl;
	cout << endl;
	
	q2 = q;
	q2.print("q2 = q");
	

	return 0;
}
compiler

pages/Kapitel09-page-219.svg

pages/Kapitel09-page-220.svg

pages/Kapitel09-page-221.svg

pages/Kapitel09-page-222.svg

pages/Kapitel09-page-223.svg

pages/Kapitel09-page-224.svg

pages/Kapitel09-page-225.svg

Live-Demo - Automatisch erzeugte Methoden

#include <iostream>

using namespace std;

class MyClass {
    int m_x;
public:
    MyClass() = default;
    MyClass(int y): m_x(y) {}
    MyClass(MyClass const & mc) : m_x(mc.m_x + 3) {}
    MyClass& operator=(MyClass const &mc) {
        m_x = mc.m_x + 10;
        return *this;
    }
    ~MyClass() = default;
    int getX() { return m_x;}
};

int main() {
    MyClass a(3);
    cout << a.getX() << endl;

    MyClass b(3);
    b = a;
    cout << b.getX() << endl;

	return 0;
}
compiler

pages/Kapitel09-page-226.svg

pages/Kapitel09-page-227.svg

pages/Kapitel09-page-228.svg

pages/Kapitel09-page-229.svg

pages/Kapitel09-page-230.svg

pages/Kapitel09-page-231.svg

pages/Kapitel09-page-232.svg

pages/Kapitel09-page-233.svg

pages/Kapitel09-page-234.svg

pages/Kapitel09-page-235.svg

pages/Kapitel09-page-236.svg

pages/Kapitel09-page-237.svg

pages/Kapitel09-page-238.svg

pages/Kapitel09-page-239.svg

pages/Kapitel09-page-240.svg

pages/Kapitel09-page-241.svg

pages/Kapitel09-page-242.svg

pages/Kapitel09-page-243.svg

pages/Kapitel09-page-244.svg

pages/Kapitel09-page-245.svg

pages/Kapitel09-page-246.svg

pages/Kapitel09-page-247.svg

pages/Kapitel09-page-248.svg

pages/Kapitel09-page-249.svg

pages/Kapitel09-page-250.svg

pages/Kapitel09-page-251.svg

pages/Kapitel09-page-252.svg

pages/Kapitel09-page-253.svg

pages/Kapitel09-page-254.svg

pages/Kapitel09-page-255.svg

pages/Kapitel09-page-256.svg

pages/Kapitel09-page-257.svg

pages/Kapitel09-page-258.svg

pages/Kapitel09-page-259.svg

pages/Kapitel09-page-260.svg

pages/Kapitel09-page-261.svg

pages/Kapitel09-page-262.svg

pages/Kapitel09-page-263.svg

pages/Kapitel09-page-264.svg

pages/Kapitel09-page-265.svg

pages/Kapitel09-page-266.svg

pages/Kapitel09-page-267.svg

pages/Kapitel09-page-268.svg

pages/Kapitel09-page-269.svg

pages/Kapitel09-page-270.svg

pages/Kapitel09-page-271.svg

pages/Kapitel09-page-272.svg

pages/Kapitel09-page-273.svg

pages/Kapitel09-page-274.svg

pages/Kapitel09-page-275.svg

pages/Kapitel09-page-276.svg

pages/Kapitel09-page-277.svg

pages/Kapitel09-page-278.svg

pages/Kapitel09-page-279.svg

pages/Kapitel09-page-280.svg

pages/Kapitel09-page-281.svg

pages/Kapitel09-page-282.svg

pages/Kapitel09-page-283.svg

pages/Kapitel09-page-284.svg

pages/Kapitel09-page-285.svg

pages/Kapitel09-page-286.svg

pages/Kapitel09-page-287.svg

pages/Kapitel09-page-288.svg

pages/Kapitel09-page-289.svg

pages/Kapitel09-page-290.svg

pages/Kapitel09-page-291.svg

pages/Kapitel09-page-292.svg

pages/Kapitel09-page-293.svg

pages/Kapitel09-page-294.svg

pages/Kapitel09-page-295.svg

pages/Kapitel09-page-296.svg

pages/Kapitel09-page-297.svg

pages/Kapitel09-page-298.svg

pages/Kapitel09-page-299.svg

pages/Kapitel09-page-300.svg

pages/Kapitel09-page-301.svg

pages/Kapitel09-page-302.svg

pages/Kapitel09-page-303.svg

pages/Kapitel09-page-304.svg

pages/Kapitel09-page-305.svg

pages/Kapitel09-page-306.svg

pages/Kapitel09-page-307.svg

pages/Kapitel09-page-308.svg

pages/Kapitel09-page-309.svg

pages/Kapitel09-page-310.svg

pages/Kapitel09-page-311.svg

pages/Kapitel09-page-312.svg

pages/Kapitel09-page-313.svg

pages/Kapitel09-page-314.svg

pages/Kapitel09-page-315.svg

pages/Kapitel09-page-316.svg

pages/Kapitel09-page-317.svg

pages/Kapitel09-page-318.svg

pages/Kapitel09-page-319.svg

pages/Kapitel09-page-320.svg

pages/Kapitel09-page-321.svg

pages/Kapitel09-page-322.svg

pages/Kapitel09-page-323.svg

pages/Kapitel09-page-324.svg

Wissensspeicher 14

Listenimplementierungen

  • Einfluss der Implementierung auf die Laufzeit
  • Hier: sz vs. sz, ez
  • Schnellere Einfügeoperation auf Kosten von zusätzlichem Zeiger

Binärbaum

  • Bestandteile: Knoten und Kanten
  • Jeder Knoten hat 0, 1 oder 2 Kindknoten
  • Jeder Knoten hat genau einen Elternknoten

Suchbäume

  • Spezialfall von binären Bäumen
  • Linker Teilbaum ist kleiner als der aktuelle Knoten
  • Rechter Teilbaum ist größer als der aktuelle Knoten

pages/Kapitel09-page-325.svg

pages/Kapitel09-page-326.svg

pages/Kapitel09-page-327.svg

pages/Kapitel09-page-328.svg

pages/Kapitel09-page-329.svg

pages/Kapitel09-page-330.svg

pages/Kapitel09-page-331.svg

pages/Kapitel09-page-332.svg

pages/Kapitel09-page-333.svg

pages/Kapitel09-page-334.svg

pages/Kapitel09-page-335.svg

pages/Kapitel09-page-336.svg

pages/Kapitel09-page-337.svg

pages/Kapitel09-page-338.svg

pages/Kapitel09-page-339.svg

pages/Kapitel09-page-340.svg

pages/Kapitel09-page-341.svg

pages/Kapitel09-page-342.svg

pages/Kapitel09-page-343.svg

pages/Kapitel09-page-344.svg

pages/Kapitel09-page-345.svg

pages/Kapitel09-page-346.svg

pages/Kapitel09-page-347.svg

pages/Kapitel09-page-348.svg

pages/Kapitel09-page-349.svg

pages/Kapitel09-page-350.svg

pages/Kapitel09-page-351.svg

pages/Kapitel09-page-352.svg

pages/Kapitel09-page-353.svg

pages/Kapitel09-page-354.svg

pages/Kapitel09-page-355.svg

pages/Kapitel09-page-356.svg

pages/Kapitel09-page-357.svg

pages/Kapitel09-page-358.svg

pages/Kapitel09-page-359.svg

pages/Kapitel09-page-360.svg

pages/Kapitel09-page-361.svg

pages/Kapitel09-page-362.svg

pages/Kapitel09-page-363.svg

pages/Kapitel09-page-364.svg

pages/Kapitel09-page-365.svg

Live-Demo - Höhe binärer Suchbaum

#include <iostream>

using namespace std;

template <typename T>
class BinTree {
private:
	struct Node{
		T data;
		Node *left, *right;
	} *root;
	Node* insert(Node *node, T x) {
		if (node == nullptr) {
			Node *node = new Node{x, nullptr, nullptr};
			return node;
		}
		if (node->data > x) {
			node->left = insert(node->left, x); 
		} else if (node->data < x) {
			node->right = insert(node->right, x);
		}
		return node;
	}
	bool is_elem(Node *node, T x) {
		if (node == nullptr) {
			return false;
		}
		if (node->data == x) {
			return true;
		}
		if (node->data > x) {
			return is_elem(node->left, x);
		}
		return is_elem(node->right, x);
	}
	void clear(Node *node) {
		if (node == nullptr) {
			return;
		}
		clear(node->left);
		clear(node->right);
		delete node;
	}
	void print(Node *node) {
		if (node == nullptr) {
			return;
		}
		print(node->left);
		cout << node->data << " ";
		print(node->right);
	}
    int height(Node *node) {
        if (node == nullptr) {
            return 0;
        }
        int left = height(node->left);
        int right = height(node->right);
        if (left > right) {
            return left + 1;
        } else {
            return right + 1;
        }
    }
public:
	BinTree() {
		root = nullptr;
	}
	void insert(T x) {
		root = insert(root, x);
	}
	bool is_elem(T x) {
		return is_elem(root, x);
	}
	void clear() {
		clear(root);
		root = nullptr;
	}
	void print() {
		print(root);
		cout << endl;
	}
    int height() {
        return height(root);
    }
	~BinTree() {
		clear();
	}
};

int main() {
	BinTree<int> tree;

    tree.insert(20);
    tree.insert(40);
    tree.insert(42);
    tree.insert(55);
    tree.insert(25);
    tree.insert(11);
    tree.insert(18);
    tree.insert(19);
    tree.insert(8);
    tree.insert(9);
    tree.insert(5);
    cout << "Höhe des Baums: " << tree.height() << endl;
    tree.print();

	return 0;

}
compiler

pages/Kapitel09-page-366.svg

pages/Kapitel09-page-367.svg

pages/Kapitel09-page-368.svg

pages/Kapitel09-page-369.svg

pages/Kapitel09-page-370.svg

pages/Kapitel09-page-371.svg

pages/Kapitel09-page-372.svg

pages/Kapitel09-page-373.svg

pages/Kapitel09-page-374.svg

pages/Kapitel09-page-375.svg

pages/Kapitel09-page-376.svg

pages/Kapitel09-page-377.svg

pages/Kapitel09-page-378.svg

pages/Kapitel09-page-379.svg

pages/Kapitel09-page-380.svg

pages/Kapitel09-page-381.svg

pages/Kapitel09-page-382.svg

pages/Kapitel09-page-383.svg

pages/Kapitel09-page-384.svg

pages/Kapitel09-page-385.svg

pages/Kapitel09-page-386.svg

pages/Kapitel09-page-387.svg

pages/Kapitel09-page-388.svg

pages/Kapitel09-page-389.svg

pages/Kapitel09-page-390.svg

pages/Kapitel09-page-391.svg

pages/Kapitel09-page-392.svg

pages/Kapitel09-page-393.svg

pages/Kapitel09-page-394.svg

pages/Kapitel09-page-395.svg

pages/Kapitel09-page-396.svg

pages/Kapitel09-page-397.svg

pages/Kapitel09-page-398.svg

pages/Kapitel09-page-399.svg

pages/Kapitel09-page-400.svg

pages/Kapitel09-page-401.svg

pages/Kapitel09-page-402.svg

pages/Kapitel09-page-403.svg

pages/Kapitel09-page-404.svg

pages/Kapitel09-page-405.svg

pages/Kapitel09-page-406.svg

pages/Kapitel09-page-407.svg

pages/Kapitel09-page-408.svg

pages/Kapitel09-page-409.svg

pages/Kapitel09-page-410.svg

pages/Kapitel09-page-411.svg

pages/Kapitel09-page-412.svg

pages/Kapitel09-page-413.svg

pages/Kapitel09-page-414.svg

pages/Kapitel09-page-415.svg

pages/Kapitel09-page-416.svg

pages/Kapitel09-page-417.svg

pages/Kapitel09-page-418.svg

pages/Kapitel09-page-419.svg

pages/Kapitel09-page-420.svg

pages/Kapitel09-page-421.svg

pages/Kapitel09-page-422.svg

pages/Kapitel09-page-423.svg

pages/Kapitel09-page-424.svg

pages/Kapitel09-page-425.svg

pages/Kapitel09-page-426.svg

pages/Kapitel09-page-427.svg

pages/Kapitel09-page-428.svg

pages/Kapitel09-page-429.svg

pages/Kapitel09-page-430.svg

pages/Kapitel09-page-431.svg

pages/Kapitel09-page-432.svg

pages/Kapitel09-page-433.svg

pages/Kapitel09-page-434.svg

pages/Kapitel09-page-435.svg

pages/Kapitel09-page-436.svg

pages/Kapitel09-page-437.svg

pages/Kapitel09-page-438.svg

pages/Kapitel09-page-439.svg

pages/Kapitel09-page-440.svg

pages/Kapitel09-page-441.svg

pages/Kapitel09-page-442.svg

pages/Kapitel09-page-443.svg

pages/Kapitel09-page-444.svg

pages/Kapitel09-page-445.svg

pages/Kapitel09-page-446.svg

pages/Kapitel09-page-447.svg

pages/Kapitel09-page-448.svg

pages/Kapitel09-page-449.svg

pages/Kapitel09-page-450.svg

pages/Kapitel09-page-451.svg

pages/Kapitel09-page-452.svg

pages/Kapitel09-page-453.svg

pages/Kapitel09-page-454.svg

pages/Kapitel09-page-455.svg

pages/Kapitel09-page-456.svg

pages/Kapitel09-page-457.svg

pages/Kapitel09-page-458.svg

pages/Kapitel09-page-459.svg

pages/Kapitel09-page-460.svg

pages/Kapitel09-page-461.svg

pages/Kapitel09-page-462.svg

pages/Kapitel09-page-463.svg

pages/Kapitel09-page-464.svg

pages/Kapitel09-page-465.svg

pages/Kapitel09-page-466.svg

pages/Kapitel09-page-467.svg

pages/Kapitel09-page-468.svg

pages/Kapitel09-page-469.svg

pages/Kapitel09-page-470.svg

pages/Kapitel09-page-471.svg

pages/Kapitel09-page-472.svg

pages/Kapitel09-page-473.svg

pages/Kapitel09-page-474.svg

pages/Kapitel09-page-475.svg

pages/Kapitel09-page-476.svg

pages/Kapitel09-page-477.svg

pages/Kapitel09-page-478.svg

pages/Kapitel09-page-479.svg

pages/Kapitel09-page-480.svg

pages/Kapitel09-page-481.svg

pages/Kapitel09-page-482.svg

pages/Kapitel09-page-483.svg

pages/Kapitel09-page-484.svg

pages/Kapitel09-page-485.svg

pages/Kapitel09-page-486.svg

pages/Kapitel09-page-487.svg

pages/Kapitel09-page-488.svg

pages/Kapitel09-page-489.svg

pages/Kapitel09-page-490.svg

pages/Kapitel09-page-491.svg

pages/Kapitel09-page-492.svg

pages/Kapitel09-page-493.svg

pages/Kapitel09-page-494.svg

pages/Kapitel09-page-495.svg

pages/Kapitel09-page-496.svg

pages/Kapitel09-page-497.svg

pages/Kapitel09-page-498.svg

pages/Kapitel09-page-499.svg

pages/Kapitel09-page-500.svg

pages/Kapitel09-page-501.svg

pages/Kapitel09-page-502.svg

pages/Kapitel09-page-503.svg

pages/Kapitel09-page-504.svg

pages/Kapitel09-page-505.svg

pages/Kapitel09-page-506.svg

pages/Kapitel09-page-507.svg

pages/Kapitel09-page-508.svg

pages/Kapitel09-page-509.svg

pages/Kapitel09-page-510.svg

pages/Kapitel09-page-511.svg

pages/Kapitel09-page-512.svg

pages/Kapitel09-page-513.svg

pages/Kapitel09-page-514.svg

pages/Kapitel09-page-515.svg

pages/Kapitel09-page-516.svg

pages/Kapitel09-page-517.svg

pages/Kapitel09-page-518.svg

pages/Kapitel09-page-519.svg

pages/Kapitel09-page-520.svg

pages/Kapitel09-page-521.svg

pages/Kapitel09-page-522.svg

pages/Kapitel09-page-523.svg

pages/Kapitel09-page-524.svg

pages/Kapitel09-page-525.svg

pages/Kapitel09-page-526.svg

pages/Kapitel09-page-527.svg

pages/Kapitel09-page-528.svg

pages/Kapitel09-page-529.svg

pages/Kapitel09-page-530.svg

pages/Kapitel09-page-531.svg

pages/Kapitel09-page-532.svg

pages/Kapitel09-page-533.svg

pages/Kapitel09-page-534.svg

pages/Kapitel09-page-535.svg

pages/Kapitel09-page-536.svg

pages/Kapitel09-page-537.svg

pages/Kapitel09-page-538.svg

pages/Kapitel09-page-539.svg

pages/Kapitel09-page-540.svg

pages/Kapitel09-page-541.svg

pages/Kapitel09-page-542.svg

pages/Kapitel09-page-543.svg

pages/Kapitel09-page-544.svg

pages/Kapitel09-page-545.svg

pages/Kapitel09-page-546.svg

pages/Kapitel09-page-547.svg

pages/Kapitel09-page-548.svg

pages/Kapitel09-page-549.svg

pages/Kapitel09-page-550.svg

pages/Kapitel09-page-551.svg

pages/Kapitel09-page-552.svg

pages/Kapitel09-page-553.svg

pages/Kapitel09-page-554.svg

pages/Kapitel09-page-555.svg

pages/Kapitel09-page-556.svg

pages/Kapitel09-page-557.svg

pages/Kapitel09-page-558.svg

pages/Kapitel09-page-559.svg

pages/Kapitel09-page-560.svg

pages/Kapitel09-page-561.svg

pages/Kapitel09-page-562.svg

pages/Kapitel09-page-563.svg

pages/Kapitel09-page-564.svg

pages/Kapitel09-page-565.svg