Post on 05-Apr-2015
transcript
29.05.2000
Universität Dortmund, Lehrstuhl Informatik 1dittrich@cs.uni-dortmund.de
EINI IIEinführung in die Informatik
für Naturwissenschaftler und Ingenieure II
Prof. Dr. Gisbert Dittrich
19 -2
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ziel 1
• Weitere Beiträge zur Wiederverwendbarkeit von Code --> Einführung an Beispielen.
• Frage: Wie kann man das Hashen von Integern für das Hashen von
- komplexen Zahlen - Wörtern
- Beschäftigten - ...
effizient verwenden?
19 -3
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ziel 2
• Antwort:
Verwendung von Templates/Schablonen (bedeutet:
Klassen können als Parameter in Klassen (-schablonen) zur Erzeugung von Klassen verwendet werden.)
Durchgeführt für Beispiele.
19 -4
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Gliederung 1
• Neuer Anwendungsbereich • Klasse komplexe Zahlen
• Einführung in Templates/Schablonen1. Am Beispiel (einfache) Liste:
– Schablone für (einfache) Liste.– Beispielanwendungen:
Einfache Liste für komplexe Zahlen Einfache Liste für Integer Einfache Liste für Beschäftigte
• Konsequenzen– Detail: Erzeugung anonymer Klassen
19 -5
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Gliederung 2
2. Beispiel: Hashing allgemein– Annahmen– Liste(nschablone)– Schablone Hashtafel– Vergleich : int <---> Nutzinfo *– Methoden dazu – Beispielanwendungen:
Hashing für komplexe Zahlen Hashing für Integer Hashing für Wörter Hashing für Beschäftigte nach Klassenzugehörigkeit Hashing für Beschäftigte nach Verdienststufe
19 -6
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Klasse: KomplexeZahl
class KomplexeZahl { private:
int Re, Im; public:
KomplexeZahl (int r, int i) {Re = r; Im = i;}
KomplexeZahl * Plus (KomplexeZahl * p); KomplexeZahl * Minus (KomplexeZahl * p); KomplexeZahl * Minus (); KomplexeZahl * Mal (KomplexeZahl * p); void Druck();bool Gleich (KomplexeZahl * p);
}; Liste kompl Zahlen
19 -7
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Komplexe Zahlen
• Deute (a, b) als a + i*b.
• Operationen sind dann klar.• Beispiel: Multiplikation, Methode Mal
KomplexeZahl * Mal (KomplexeZahl * p) {int r, i;r = Re * p->Re - Im * p->Im;i = Im * p->Re + Re * p->Im;return new KomplexeZahl(r, i);}
[(a+ib)*(c+id) = (ac-bd) + i(ad + bc) ; ]
i= (−1)
19 -8
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Nun aber
Suchverfahren für komplexe Zahlen.• Binäre Suchbäume: nicht möglich, denn
– auf der Menge der komplexen Zahlen ist keine Ordnung (direkt) definiert.
19 -9
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
• Hashing: im Prinzip möglich• Muß also:
– Klasse KomplexList zur Formulierung verketteter Listen für komplexe Zahlen definieren,– das Hashing-Verfahren anpassen.
• Das ist LANGWEILIG, da i.w. Gleichförmiges wiederholt wird.
• Alternative ? --> Klassen als Parameter
Nun aber (Forts.)
19 -10
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Integer_Hashing: Analyse 1
class IntListenEl { public:
int Element;
IntListenEl * weiter;
void NutzinfoDruck()};
class IntListe { protected:
IntListenEl * DieIntListe;
bool IstDa(IntListenEl *, int);
IntListenEl * WegDamit (IntListenEl *, int);
void DieserDruck(IntListenEl *);
19 -11
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Integer_Hashing: Analyse 2
// class IntListe Fortsetzung public:
IntListe()
IntListe(int r)
bool Testen(int r)
void Entfernen(int r)
void Einfuegen(int)
void Druck()};
....
bool IntListe::IstDa(IntListenEl * Liste, int r) {.......
else { if (Liste->Element == r) Gleichheit ???!!!
........
Int-Hash: Analyse 3
19 -12
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Analyseergebnis
• Analyse der Rolle der int-Größe (vorige Folien)
• Ganze Zahlen gehen bei der Klasse IntListe nur insofern ein, als
– die Komponente Element vom Typ int war,– beim Testen die Gleichheit ganzer Zahlen benutzt wurde– sie als Parameter in Methoden auftreten
--> Diese Stellen müssen bei einer abstrakteren Behandlung ("Parametrisierung") auf Änderung überprüft werden.
19 -13
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Aufgabe: Abstrakte Formulierung
• Listentyp definieren, der diese beiden Angaben (Typ, Gleichheit) als Parameter hat:
– ganze Zahlen als Typparameter,– die Gleichheit als Funktionsparameter
(Das geht mit Hilfe rein virtueller Funktionen. Wird zunächst zurückgestellt).
19 -14
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Dazu zu erledigen:
• Allgemeine Angaben zu Liste:• Annahme über den Typ der Listenelemente,• Angabe der Signaturen von Listenmethoden,• Angabe
– der Implementierung, soweit das möglich ist– der typspezifischen Eigenschaften oder Operationen.
• Formulierung in C++• [Zunächst Reduktion auf Liste_einfach:
– Initialisieren der Liste - Einfügen eines Elements– Drucken der Liste(nelemente) ]
19 -15
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
class ListenEl {
Nutzinfo * Element;ListenEl * weiter;void NutzinfoDruck(){ Element->Druck(); cout << endl;}};
Erste Formulierungen
• Annahme: • Der Typ der Listenelemente ist Zeiger auf Nutzinfo, wobei Nutzinfo beliebige Klasse.• Grundtyp also: Nutzinfo *.
Nutzinfo weiterElement
Nutzinfo
Achtung: Setzt Methode Druck() in Nutzinfo voraus !!!
19 -16
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Erste Formulierungen 2
class Liste {
ListenEl * DieListe;
void ListenDruck(ListenEl *);
Liste() {
DieListe = NULL;};
void Einfuegen(Nutzinfo *);
void Druck(){ListenDruck(DieListe);}
19 -17
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Fazit
• Fast alle Operationen ohne Kenntnisse des zugrundeliegenden Typs Nutzinfo formulierbar.
• Ausnahmen:• der Druck eines Elements• evtl: Gleichheit von Elementen (hier (noch) nicht betrachtet)
• Im folgenden: Formulierung als Klasse
19 -18
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Formulierung als Klasse 1
• Dazu auch berücksichtigen:• Angabe, daß der Typ eine Art Parameter der Listenklasse ist !!• Zugriffsspezifikationen
(private, protected, public)
• Methoden müssen ausformuliert werden
19 -19
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Erste Formulierungen (Ausschnitt)
class ListenEl {
Nutzinfo * Element;
ListenEl * weiter;
void NutzinfoDruck(){
Element->Druck();
cout << endl;
}
};
19 -20
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
class ListenEl {
public:
Nutzinfo * Element;
ListenEl * weiter;
void NutzinfoDruck(){
Element->Druck();
cout << endl;
}
};
Formulierung als Klasse 2
Das ist neutemplate <class Nutzinfo>
19 -21
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anmerkungen
• Durch template <class Nutzinfo > wird angekündigt, daß die folgende Konstruktion eine Klasse Nutzinfo als Parameter hat.
• Die nun folgende Klasse ist keine: • Sie ist vielmehr das Muster (oder die Schablone) einer Klasse. Aus der Schablone können dann Klassen erzeugt werden (Wie, werden wir gleich sehen).
• Schablonen können im Hinblick auf Vererbung wie Klassen behandelt werden.
19 -22
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anmerkungen (Forts.)
• Zugriffsspezifikationen• Element;
weiter;
NutzinfoDruck()
als public Komponenten, da wir (nur an dieser Stelle !!) faul sind.
Logisch wäre protected oder gar private besser.
Vgl. Vorgehen in früheren Beispielen.
19 -23
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Erste Formulierungen 2 (Wiederholung)
class Liste {
ListenEl * DieListe;
void ListenDruck(ListenEl *);
Liste() {
DieListe = NULL;};
void Einfuegen(Nutzinfo *);
void Druck(){ListenDruck(DieListe);}
19 -24
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Formulierung als Klasse 3
template <class Nutzinfo>
class Liste { protected:
ListenEl<Nutzinfo> * DieListe;
void ListenDruck(ListenEl<Nutzinfo> *);
public:
Liste() {
DieListe = NULL;};
void Einfuegen(Nutzinfo *);
void Druck(){ListenDruck(DieListe);}
};
Auch bei Parametern oder lokalen Variablen muß der
Typparameter stets mitgeteiltwerden.
19 -25
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
ListenEl<Nutzinfo> *
neu = new ListenEl<Nutzinfo>;
Realisierung der Methoden 1
template <class Nutzinfo> mußmuß vor der Definition jeder Methode stehen
Der Name des Typparameters
mußmuß bei der Angabe der Klasse
genannt werden
void Liste<Nutzinfo>::Einfuegen(Nutzinfo * r){template <class Nutzinfo>
Auch hier: Typparameter
neu->Element = r;neu->weiter = DieListe;DieListe = neu;}
19 -26
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Realisierung der Methoden 2
template <class Nutzinfo>
void Liste<Nutzinfo>::
ListenDruck(ListenEl<Nutzinfo> * K) {
if (K != NULL) {
K->NutzinfoDruck();
ListenDruck(K->weiter);
}
}
19 -27
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Realisierung der Methoden 3
template <class Nutzinfo>
void Liste<Nutzinfo>::Einfuegen(Nutzinfo * r){
......}
Die Konstruktion müßte jetzt klar sein:• Angabe, daß es sich um eine Schablone mit Typparameter Nutzinfo handelt,• Nennung des Typparameters bei der Definition der
Methode (hier: Einfuegen).Liste_einfach.cpp
19 -28
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Liste komplexer Zahlen
class KomplexL: public Liste<KomplexeZahl> { public:
KomplexL() : Liste<KomplexeZahl>() {};};
int main() {KomplexL * MeineKoZListe = new KomplexL();for (int i = 0; i< 10;i++){
MeineKoZListe->Einfuegen(new KomplexeZahl
(rand()%100, rand()%100));};MeineKoZListe->Druck();return 0;}
Komplexe Zahlen Programm Quelltext
19 -29
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Liste von Integer-Zahlen 1
Erzeuge Klasse zu Integer-Zahlen: class IntegerZahl { public:
int i;
IntegerZahl (int i1) { i = i1;}
void Druck() { cout << i; }
int Get_i() {return i;}
bool Gleich(IntegerZahl *p) {
return (i == p->i);}
};
Liste von Integern
Hashing von Integern
19 -30
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
class KomplexL: public Liste<KomplexeZahl> { public:
KomplexL() : Liste<KomplexeZahl>() {};};
Anwendung: Liste komplexer Zahlen Wdh
int main() {KomplexL * MeineKoZListe = new KomplexL();for (int i = 0; i< 10;i++){
MeineKoZListe->Einfuegen(new KomplexeZahl
(rand()%100, rand()%100));};MeineKoZListe->Druck();return 0;}
19 -31
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Liste von Integer-Zahlen 2
class IntL: public Liste<IntegerZahl> { public:
IntL() : Liste<IntegerZahl>() {};};
int main() {IntL * MeineIntListe = new IntL();for (int i = 0; i< 10;i++){
MeineIntListe->Einfuegen(new IntegerZahl
(rand()%100));};MeineIntListe->Druck();return 0;}
Integer Programm Quelltext
19 -32
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Liste von Beschäftigten
class BeschL: public Liste<Beschaeftigter> { public:
BeschL() : Liste<Beschaeftigter>() {};};
int main() {BeschL * MeineBeschListe = new BeschL();.....
MeineBeschListe-> Einfuegen(einBeschaeftigter);
..........MeineBeschListe->Druck();return 0;}
Klasse Beschäftigter Programm Quelltext
19 -33
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anmerkungen
• Die neue Klasse entsteht durch Konkretisie-rung des Typparameters. Das geschieht hier mittels Vererbung: class IntL: public Liste<IntegerZahl> {
........ };
• Die (konkrete) Klasse Liste<IntegerZahl> entsteht dabei aus der Klasse(nschablone) Liste < Nutzinfo>, indem der Typparameter Nutzinfo durch IntegerZahl substituiert wird.
19 -34
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Konsequenzen
• Code für Listen wurde nur einmal formuliert
• Für jeden Typ kann mit dieser Technik eine Liste formuliert werden.
• Dazu muß lediglich formuliert werden:• ein Konstruktor,• // die virtuelle Methode ELDruck, die typspezifisch ist.• Dies geschieht hier durch Vererbung.
19 -35
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Konsequenzen (Forts.)
• Für jeden konkreten Typ, der den Typpara-meter ersetzt, wird bei der Ersetzung eine Klasse erzeugt (s.o.).• Diese kann im wesentlichen wie jede andere Klasse verwendet werden.
• „Anonyme“ Klasse • Die Ersetzung des Typparameters kann auch dort geschehen, wo Klassen benutzt werden.
--> vgl. Beispiel nächste Folien.
19 -36
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
class KomplexL: public Liste<KomplexeZahl> { public:
KomplexL() : Liste<KomplexeZahl>() {};};
Anwendung: Liste komplexer Zahlen UKlasse
int main() {KomplexL * MeineKoZListe =
new KomplexL();for (int i = 0; i< 10;i++){
MeineKoZListe->Einfuegen(new KomplexeZahl
(rand()%100, rand()%100));};MeineKoZListe->Druck();return 0;}
19 -37
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
/*class KomplexL: public Liste<KomplexeZahl> { public:
KomplexL() : Liste<KomplexeZahl>() {};};*/
Anwendung: Liste komplexer Zahlen anonym
int main() {Liste<KomplexeZahl> * MeineKoZListe =
new Liste<KomplexeZahl>;for (int i = 0; i< 10;i++){
MeineKoZListe->Einfuegen(new KomplexeZahl
(rand()%100, rand()%100));};MeineKoZListe->Druck();return 0;}
Programm
19 -38
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Gliederung 1
• Neuer Anwendungsbereich • Klasse komplexe Zahlen
• Einführung in Templates/Schablonen1. Am Beispiel (einfache) Liste:
– Schablone für (einfache) Liste.– Beispielanwendungen:
Einfache Liste für komplexe Zahlen Einfache Liste für Integer Einfache Liste für Beschäftigte
• Konsequenzen– Detail: Erzeugung anonymer Klassen Erledigt !!
19 -39
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Gliederung 2
2. Beispiel: Hashing allgemein– Annahmen– Liste(nschablone)– Schablone Hashtafel– Vergleich : int <---> Nutzinfo *– Methoden dazu – Beispielanwendungen:
Hashing für komplexe Zahlen Hashing für Integer Hashing für Wörter Hashing für Beschäftigte nach Klassenzugehörigkeit Hashing für Beschäftigte nach Verdienststufe
19 -40
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Hashing für beliebige Datentypen
• Hashing (Wiederholung): • Bisher formuliert für ganze Zahlen.• Zentral: Feld von Listen ganzer Zahlen, in die eingefügt wurde.• Feldelement wurde ermittelt durch Hashfunktion.
19 -41
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Idee Hashfunktion (vgl. Kap. 18)
• Formal:• Sei U die (endliche) Menge aller Objekte, für die die Suchoperationen definiert werden sollen. • h: U -> {0, ..., m-1} sei eine Funktion --> Hash-Fkt.• U‘: Menge aller Elemente, die bereits verarbeitet sind.• U‘(j) := h -1(j) U‘ : Menge aller Elemente in U‘, die von h auf j abgebildet werden.
• Aufgabe: t U schon in U‘ ?
19 -42
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Bildchen
0
1
2
3
4
Listen
dasFeld
19 -43
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Hashing Verwendung
• Benutze die verketteten Listen, um:• Element t wird in der Liste zu h(t) abgespeichert.• Suche t? Schaue in der Liste zu h(t) nach.• Lösche t? Lösche t in der Liste zu h(t).
• Zentral: Hashfunktion h• Muß einfach zu berechnen sein• Sollte die Elemente (möglichst) gleichmäßig verteilen.
19 -44
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Zur Schablone für Listen mit Typ Nutzinfo
• Annahmen:• Für Objekte des Typs Nutzinfo ist eine Druck-Methode definiert.
– Also: für q vom Typ Nutzinfo ist q.Druck() aufrufbar.
• Objekte des Typs Nutzinfo können verglichen werden:
– Für p vom Typ Nutzinfo * und q vom Typ Nutzinfo * ist p->Gleich(q) definiert und gibt true oder false zurück.
19 -45
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Listen- Schablone 1
template <class Nutzinfo>
class ListenEl { public:
Nutzinfo * Element;
ListenEl * weiter;
void NutzinfoDruck(){
Element->Druck();
cout<<endl;
}
};
19 -46
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Listen- Schablone 2
template <class Nutzinfo>
class Liste { protected:
ListenEl<Nutzinfo> * DieListe;
bool IstDa(ListenEl<Nutzinfo>*, Nutzinfo*);
/* Testet, daß Nutzinfo in Liste */
ListenEl<Nutzinfo> * WegDamit
(ListenEl<Nutzinfo> *, Nutzinfo *);
/* Entfernt Nutzinfo, falls in Liste
enthalten*/
void ListenDruck(ListenEl<Nutzinfo> *);
19 -47
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Listen- Schablone 3
// class Liste Fortsetzung public:
Liste() {DieListe = NULL;};
Liste(Nutzinfo * r) {
DieListe -> Element = r;
DieListe -> weiter = NULL;};
bool Testen(Nutzinfo * r) {
return IstDa(DieListe, r);}
void Entfernen(Nutzinfo * r) {
DieListe = WegDamit(DieListe, r);}
void Einfuegen(Nutzinfo *);
19 -48
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Listen- Schablone 4
// class Liste Fortsetzung 2 void Druck(){ListenDruck(DieListe);}
int Gleich(Nutzinfo * p, Nutzinfo * q){
return p->Gleich(q);}
/* In Nutzinfo muß also
Gleich(Nutzinfo *)definiert sein.*/
int Laenge();
19 -49
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Methode IstDa
template <class Nutzinfo>
bool Liste<Nutzinfo>::IstDa(
ListenEl<Nutzinfo> * K, Nutzinfo * r) {
if (K == NULL)
return false;
else {
if (Gleich(K->Element, r))
return true;
else
return IstDa(K->weiter, r);
}
}
19 -50
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Methode Einfuegen
template <class Nutzinfo>
void Liste<Nutzinfo>::Einfuegen(Nutzinfo * r) {
if(!Testen(r)) {
ListenEl<Nutzinfo> * neu
= new ListenEl<Nutzinfo>;
neu->Element = r;
neu->weiter = DieListe;
DieListe = neu;
}}
• Zu Restlichen vgl. Implementierung im Quelltext
Hash-List.cpp
19 -51
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Integer_Hashing: Analyse 3
class AbstrakteHashTafel { private:
IntListe ** hT;
protected:
int maxBucket;
public:
AbstrakteHashTafel(int);
virtual int h(int) = 0;
int Testen(int r)
void Einfuegen(int r)
void Entfernen(int r)
void Druck();};
Int-Hash: Analyse 1
19 -52
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Integer_Hashing: Analyse 4
class NeueHashTafel : public AbstrakteHashTafel {public:
NeueHashTafel(int m) : AbstrakteHashTafel(m)
int h(int);
};
int main() {//}
19 -53
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Schablone: Hashtafel 1
template <class Nutzinfo>
class HashTafelSchablone {
private:
Liste< Nutzinfo > ** hT;
protected:
int maxBucket;
public:
HashTafelSchablone(int);
virtual int h(Nutzinfo *q) = 0;
int Testen(Nutzinfo *r) {
return hT[h(r)]->Testen(r);}
19 -54
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Schablone: Hashtafel 2
// class HashTafelSchablone Fortsetzung
void Einfuegen(Nutzinfo *r) {
hT[h(r)]->Einfuegen(r);}
void Entfernen(Nutzinfo *r){
hT[h(r)]->Entfernen(r);}
void Druck();
int Laenge(int j) {
return hT[j]->Laenge(); }
};
19 -55
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Vergleich: int vs. NI*
alt neuTyp der Tafel IntListe ** hT Liste<NI> ** hTHashfunktion virtual int h(int r) virtual int h(NI *q) Element schon da? int Testen(int r) int Testen(NI *r) Einfügen void Einfuegen(int r) void Einfuegen(NI *r) Entfernen void Entfernen(int r) void Entfernen(NI *r)Drucken void Druck(); void Druck();Länge der Liste j (nicht vorhanden) int Laenge(int j)
NI = NutzinfoBis auf die Signatur gute alte Bekannte.
19 -56
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Methode: Konstruktor HTSchablone
template <class Nutzinfo>
HashTafelSchablone<Nutzinfo>::
HashTafelSchablone(int m) {
maxBucket = m;
hT = new Liste<Nutzinfo> *[m];
for (int i = 0; i < m; i++)
hT[i] = new Liste<Nutzinfo>();
}
19 -57
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Methode: Konstruktor Druck
template <class Nutzinfo>
void HashTafelSchablone<Nutzinfo>::Druck() {
int i;
for (i = 0; i < maxBucket; i++) {
cout << "\nBucket für i = "
<< i << ":\n";
hT[i]->Druck();
}
}
19 -58
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für komplexe Zahlen 1
• Alle Vorbereitungen durchgeführt, jedoch
• Zwei Schritte noch notwendig:• Erzeugen einer Hashtafel für komplexe Zahlen
d.h. der Klassenparameter Nutzinfo wird durch KomplexeZahl ersetzt
• Bestimmung der Hash-Funktion (aus dem Real- und dem Imaginärteil)
19 -59
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für komplexe Zahlen 2
class KomplexeHashTafel: public HashTafelSchablone<KomplexeZahl> {
public:KomplexeHashTafel(int k):
HashTafelSchablone<KomplexeZahl>(k) {};int h(KomplexeZahl * q) {
int hash(int);return hash(
hash(q->_re()) + 1 +
hash(q->_im()) + 2 );
}};
19 -60
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Hashfunktion
Verwendet
int hash(int k) { return k%maxHash;}
Mit maxHash als Primzahl
hash ist nicht besonders gut: Beispiel gleich nach dem Hauptprogramm
19 -61
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Beispiel für main()
void main() {KomplexeHashTafel * khT =
new KomplexeHashTafel(maxHash);for (int i = 0; i < 431431; i++)
khT->Einfuegen(new KomplexeZahl(rand(), rand()));
khT->Druck();for(i = 0; i < maxHash; i++)
*ausgabe << khT->Laenge(i) << endl;
KoZ-Hash.cpp
19 -62
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ein wenig Statistik: KomplexeZahlen
0
5
10
15
20
25
30
35
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
19 -63
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für IntegerZahlen
class IntegerHashTafel: public HashTafelSchablone<IntegerZahl> {
public:
IntegerHashTafel(int k):
HashTafelSchablone<IntegerZahl>(k) {};
int h(IntegerZahl * q) {
return (q->Get_i())%maxHash;
}
};
Integer
19 -64
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für IntegerZahlen
int main() {
IntegerHashTafel * InthT =
new IntegerHashTafel(maxHash);
for (int i = 0; i < 431; i++)
InthT->Einfuegen(
new IntegerZahl(rand()));
InthT->Druck();
for(int i = 0; i < maxHash; i++)
*ausgabe << InthT->Laenge(i)
<< endl;
}Programm Quelltext
19 -65
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ein wenig Statistik: IntegerZahlen
0
5
10
15
20
25
30
35
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
19 -66
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für Wörter 1
#include <string.h>
class Wort {private:
char wort[70];
public:
Wort (char w[]) {
for (int i=0;i<70;i++)
wort[i] = w[i];
}
19 -67
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für Wörter 2
// class Wort Fortsetzungvoid Druck() {
cout << wort;}
bool Gleich(Wort *w) {
bool b;
b=strcmp(wort,w->wort);
if (b==0)
return true;
else
return false;}
char* Get (){ return wort;}};
19 -68
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für Wörter 3
class WoerterbuchHashTafel:
public HashTafelSchablone<Wort> {
public:
WoerterbuchHashTafel(int k):
HashTafelSchablone<Wort>(k) {};
int h(Wort * q) {
return hash (q->Get());
}
int hash(char *);
};
19 -69
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für Wörter 4
int WoerterbuchHashTafel::hash(char* k)
{
char c;
int z;
c=*k;
c=toupper(c);
if (c<65 || c>91)
z=26;
else
z=c-65;
return z;
}
19 -70
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für Wörter 5
int main() {
WoerterbuchHashTafel * Woerterbuch =
new WoerterbuchHashTafel(maxHash);
// Einlesen der Datei
ifstream * EingabeDatei;
EingabeDatei = new ifstream ("Beweis.txt");
char gelesen[maxLen];
*EingabeDatei >> gelesen;
19 -71
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für Wörter 6
// int main() Fortsetzungwhile (!((*EingabeDatei).eof())) {
Woerterbuch->Einfuegen(new Wort (gelesen));
* EingabeDatei >> gelesen;
}
Woerterbuch->Druck();
for(int i = 0; i < maxHash; i++)
*ausgabe << Woerterbuch->Laenge(i)
<< endl;
return 0;
} Programm Quelltext
19 -72
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ein wenig Statistik: Wörter
02
46
81012
1416
1820
19 -73
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für BeschBesGr 1
class BeschaeftigtenHashTafel:
public HashTafelSchablone<Beschaeftigter> {
public:
BeschaeftigtenHashTafel(int k):
HashTafelSchablone<Beschaeftigter>(k) {};
int h(Beschaeftigter *);};
int BeschaeftigtenHashTafel::
h(Beschaeftigter* B)
/* Klassifikation nach Zugehörigkeit zur Besoldungsart*/
{ return B->Get_Besoldungsgruppe();}
19 -74
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für BeschBesGr 2
const int maxHash = 5;
ofstream *ausgabe = new ofstream("Ausgabe.doc");
int main() {
BeschaeftigtenHashTafel * B_H_Tafel =
new BeschaeftigtenHashTafel(maxHash);
// Erzeugen der Listeneinträge analog Kap.17 !!
B_H_Tafel->Druck();
for(int i = 0; i < maxHash; i++)
*ausgabe << B_H_Tafel->Laenge(i)
<< endl;
return 0;
} Programm QuelltextBeschaeftigter
19 -75
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ein wenig Statistik: BeschaftgBesGr
0
10
20
30
40
50
60
1 2 3 4 5
19 -76
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Anwendung: Hashing für BeschBVerdie 1
class BeschaeftigtenHashTafel:
public HashTafelSchablone<Beschaeftigter> {
// wie vorher
int BeschaeftigtenHashTafel::
h(Beschaeftigter* B)
// Klassifikation nach Verdiensthöhe
{ int x = B->Gehalt();
if (x < 2000) return 0;
else {if (x < 4000) return 1;
else { if ( x < 6000)return 2;
else { if (x < 8000)return 3;
else return 4;};};};}; Programm
Quelltext
19 -77
Prof. Dr. G. Dittrich29.05.2000
EINI II Kap. 19: Schablonen/Templates
Ein wenig Statistik: BeschVerdienst
0
10
20
30
40
50
60
70
1 2 3 4 5