Programmieren, Algorithmen und Datenstrukturen 2 (Vorlesung 11)

Semester-Plan

• Quicksort implementieren
• Binärer Suchbaum implementieren

Polymorphie (Mehrdeutigkeit)

• Auflösung  von Templates und Parametern zur Build-time
• Auflösung von Klassen und virtuellen Methoden zur Run-time („ad-hoc“)

Templates

• Was nicht geht:
  • Template<Basis> != Template<Abgeleitet>
  • Zuweisung schlägt fehl (Klassen und auch Zeiger)

STL

• Standard Template Library (besser: Standard Container Library)
• Container = Sequenzen von Daten (Bsp.: vector<typ>)
• Anwendung von Standard-Funktionen erleichtern die Arbeit
  • schnell, sicher, standardisiert, portabel und weniger Selbstaufwand

Beispiel Summe:

• double s( 0.0 ); = Konstruktorinitialisierersyntax
• Feldgröße bei Arrays immer mitgeben
• while( first ) { first = first->next; }  // Schleife bis Null erreicht wird

#include <iostream>
using std::cout;
using std::endl;

template<class I, class T> T sum( I first, I last, T s ) // T=Typ
{
	while( first != last )
	{
		s += *first;
		++first;
	}
return s;
}

int main()
{
double a[] = { 2.1, 4.2, 6.3, 1.4, 3.5, 5.6 }; // a=Adresse des Arrays und 1. Elements
double d = sum( a, a+sizeof(a)/sizeof(*a), double() );
cout << a << endl;
cout << sizeof(a) << endl;
cout <<sizeof(*a) << endl;
cout << a+sizeof(a)/sizeof(*a);
}

Ein Programm für die Summe von double Werten, die in einem Datenfeld gespeichert wird.

double sum( double array[], int n ) {
double s( 0.0 );
for( int i( 0 ); i<n; ++i ) s += array[i];
return s;
}

Ein Programm für die Summe von int Werten, die in einer einfach verketteten Liste gespeichert sind.

struct Node { Node* next; int data; };
  int sum( Node* first ) {
  int s( 0 );
  while( first ) {
    s += first->data;
    first = first->next;
  }
  return s;
}

Allgemeines  Programm zur Berechnung von Summen (Pseudo-Code).

sum( data_sequence ) {
  s = 0;                       // Initialisierung
  while( not_at_end( ) ) {     // Iterationsbedingung
    s += get_current_value( );
    get_next_element( );       // Iteration
  }
  return s;                    // Ergebnisrückgabe
}

Bestimmen des höchsten Wertes (Pseudo-Code).

highest( data_sequence ) {
  s=0, tmp=0;                  // Initialisierung
  while( not_at_end( ) ) {     // Iterationsbedingung
    tmp = get_current_value( );
    if( s < tmp ) s = tmp;
    get_next_element( );       // Iteration
  }
  return s;                    // Ergebnisrückgabe
}

Einfacher ist es, die STL zu verwenden. So sieht es in der STL aus:

template<class I, class T> T sum( I first, I last, T s ) {
  while( first != last ) { s += *first; ++first; }
  return s;
}

Anwendung: z.B.

double a[] = { 2.1, 4.2, 6.3, 1.4, 3.5, 5.6 };
double d = sum( a, a+sizeof(a)/sizeof(*a), double() );

• sizeof(*a) = Größe eines doubles

Funktionen:

• #include
  • accumulate
  • inner_product
  • partial_sum
  • adjacent_differenze

Wichtige Iteratoren:

• begin ( Ist Teil der Sequenz )
• end (Steht 1 Element hinter dem letzten Element → nicht mehr Teil der Sequenz)
• Mathematisch: [ b; e [

Sequenzen und Iteratoren

• Sequenz:
  • hat einen Anfang und ein Ende
  • Werte der Elemente können gelesen/geschrieben werden
• Iterator:
  • Zeiger mit zusätzlichen Eigenschaften
  • können einzelnen Elemente innerhalb von Sequenzen identifizieren
  • „begin“ identifiziert den Anfang der Sequenz
  • „end“ identifiziert das Ende der Sequenz (zeigt auf 1 Element nach dem letzten!!!)

• Bedingungen gemäß Seite 8 müssen erfüllt sein, damit man von einem Iterator sprechen kann
  • ==
  • !=
  • a*
  • a* = b
  • b=a*
  • ++a

Template: Doppelt verkettete Liste

• Konstruktor mit nur 1 Argument führt ohne Explicit eine Typumwandlung durch!

template<class Elem> struct myNode { // "für alle Typen Elem"
    Elem val; // der Wert vom Typ Elem
    myNode<Elem>* pre; // Zeiger auf vorhergehenden Knoten (predecesor)
    myNode<Elem>* suc; // Zeiger auf nachfolgenden Knoten (successor)
    explicit myNode(const Elem&, myNode<Elem>*, myNode<Elem>*) // Konstruktor
};
// Definition des Konstruktors

template<class Elem>
myNode<Elem>::myNode(const Elem& v = Elem(),
myNode<Elem>* p = 0, myNode<Elem>* s = 0)
: val(v), pre(p), suc(s) {
}

Nested Class

• Eingebette Klassen benötigen mehrfache Namensauflösung
• bool myList<Elem>::myIterator::operator==
• bool myList<Elem>::myIterator::operator!=

Algorithmen

• manipulieren Daten in Containern, ohne sich darum zu kümmern, wie die Container diese Daten spiechern
• In der STL gibt es ca. 10 Container
  • + Iteratoren
  • + ca. 60 Algorithmen