Programmieren, Algorithmen und Datenstrukturen 2 (Vorlesung 14)

Binärer Suchbaum

• Wie wäre ein binärer Suchbaum mit den sechs Knoten aus dem vorigen Beispiel maximal unvorteilhaft aufgebaut? → Ein komplett einseitig balancierter Baum

Ternärer Suchbaum

• Es müssen maximal log₃( N ) Knoten besucht werden

Klausur

• STL-Container kommen dran

Beispiel für map

/*
 * File:   main.cpp
 * Author: maximilian.krieg
 *
 * Created on 15. Mai 2012, 14:44
 */

#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>

using namespace std;

    double value_product(const pair<string, double>& a, const pair<string, double>& b)
    {
	return a.second * b.second;
    }

int main() {
    // Deutscher Aktienindex, 3-Jan-2012
    map<string, double> dax; // pair(symbol,price)
    dax["DAI"] = 36.11;
    dax["DTE"] = 9.13;
    dax["VOW"] = 122.10;
    // …
    map<string, double> dax_weight; // pair(symbol,weight)
    dax_weight.insert(make_pair("DAI", 5.7727));
    dax_weight.insert(make_pair("DTE", 5.3815));
    dax_weight.insert(make_pair("VOW", 3.3586));
    // …
    map<string, string> dax_name; // pair(symbol,name)
    dax_name["DAI"] = "Daimler";
    dax_name["DTE"] = "Deutsche Telekom";
    dax_name["VOW"] = "Volkswagen";
    // …

    double daimler_price = dax["DAI"]; // Werte aus der map lesen
    double volkswagen_price = dax["VOW"];

    if (dax.find("SOW") != dax.end()) // Eintrag suchen
	cout << "Software AG ist im DAX!\n";
    // über die map Elemente iterieren:

    typedef map<string, double>::const_iterator dax_iterator;

    for (dax_iterator p = dax.begin(); p != dax.end(); ++p) {
	const string& symbol = p->first; // das Symbol im "Ticker"
	cout << symbol << '\t' << p->second << '\t'
		<< dax_name[symbol] << '\n';
    }

    double dax_index =
	    inner_product(dax.begin(), dax.end(), // alle Firmen im DAX
	    dax_weight.begin(), // deren Gewichtung
	    0.0, // Initialisierung mit 0.0
	    plus<double>(), // addieren
	    value_product // zuerst multiplizieren
	    );

    cout << dax_index;
}