Dr. Andreas F. Borchert Institut für Angewandte Informationsverarbeitung 9. Dezember 2008
Wolfgang Kaifler Blatt 7






Objektorientierte Programmierung mit C++ (WS 2008)


Abgabetermin: 16. Dezember 2008

13 Templates (10 Punkte)

Die Interpolations- oder Intervallsuche ist ein auf der binären Suche aufbauendes Suchverfahren. (http://de.wikipedia.org/wiki/Interpolationssuche) Bei diesem Verfahren wird versucht, den Such-Algorithmus bei einem günstigeren Punkt als der Mitte zu starten.

13.1 Suche (3 Punkte)

Ihre Aufgabe ist es, ein Template interpolSearch() zu erstellen, mit dem ein vorgegebenes Element in einem numerischen sortierten Vector gesucht werden soll. (den Algorithmus finden Sie unter http://de.wikipedia.org/wiki/Interpolationssuche). Die Vektorelemente besitzen den Typ des Template-Parameters T.

Das Template soll drei Parameter besitzen: Einen Zeiger auf das erste Element, das zu suchende Element vom Typ T und die Anzahl der Elemente.

Die Funktion soll den Wert den Index des gesuchten Elementes zurückliefern, falls die Suche erfolgreich verläuft, andernfalls -1.

13.2 Sortierung (2 Punkte)

Definieren Sie weiterhin ein Template insertionSort, welches einen numerischen Vektor aufsteigend sortiert. Als Parameter soll dabei ein Zeiger auf das erste Element sowie die Anzahl der Elemente genügen.

13.3 Anzeige (2 Punkte)

Weiterhin soll noch ein Template display definiert werden, das den Vektor auf dem Bildschirm anzeigt. Auch hier soll ein Zeiger auf das erste Element sowie die Anzahl der Elemente ausreichen.

13.4 Test (3 Punkte)

Zuletzt testen Sie Ihre bisherigen Templates. Erzeugen Sie dafür aus Ihren Templates nun konkrete Objekte vom Typ short und double Definieren Sie je einen zugehörigen Vektor und lassen Sie sich die sortierten Vektoren anzeigen.

Viel Erfolg!