Merlin
18-05-2004, 13:33
Angabe:
Gegeben ist eine Hashtabelle in Form eines Arrays table mit der festgelegten Größe n. Jedes Element table[i], i = 0......n-1, dieses Arrays besteht aus folgenden Komponenten:
table[i]:key enthält den Schlüssel des Datensatzes;
table[i]:data enthält die eigentlichen Daten;
table[i]:status enth¨alt einen der folgenden Werte:
______ used: table[i] enthält einen gültigen Datensatz;
______ unused: table[i] ist frei und war nie besetzt;
______ reusable: table[i] war schon besetzt, ist aber wieder frei.
Nehmen Sie an, dass eine Hashfunktion a(k) existiert, die aus einem Schlüssel k einen Hashindex in der (oben) deklarierten Tabelle berechnet. Schreiben Sie eine Prozedur in Pseudocode, die feststellt, ob ein Datensatz mit dem Schl¨ussel searchkey in der Tabelle enthalten ist. Bei Erfolg soll der Index des Datensatzes zurückgeliefert werden, bei Misserfolg der Wert ¡1. Zur Behandlung von Kollisionen ist die konstante Schrittweite c1 zu verwenden. __________________________________________________ ___
Ich hab das folgendermassen gemacht:
Suche_key(T,m,searchkey) {
pos = a(searchkey); // Position ermitteln
solange (T[pos].status == used v T[pos] == reuseable) {
//Solange es nicht frei ist
falls T[pos].key != searchkey {
pos = (pos + c1) mod m
}
sonst return T[pos].key;
}
return -1;
hoffe dass das auch stimmt ;)
_________________________________
Angabe zu c:
Die oben genannten Schlüssel sind Zeichenketten in der Form, dass Sie auf die einzelnen Elemente eines Schlüssels key als Zeichen
key.char[j], j = 0......m - 1, zugreifen können.
Es existiert eine Funktion ord(ch), welche den numerischen Wert eines Zeichens ch liefert.
Schreiben Sie eine Hashfunktion a'(k) in Pseudocode, welche nach der Divisions-Rest-Methode vorgeht, um aus den Zeichen des Schlüssels k einen Hashindex zu berechnen. Was die Lösung betrifft, bin ich mir da selber nicht sicher.
Ich habs so probiert:
a'(k) = (T[a(k)].key) mod m
bitte um Kritik
Wahrscheinlich ist eher a'(k) = [ ord(T[a(k)].key) ] mod m gemeint?
Gegeben ist eine Hashtabelle in Form eines Arrays table mit der festgelegten Größe n. Jedes Element table[i], i = 0......n-1, dieses Arrays besteht aus folgenden Komponenten:
table[i]:key enthält den Schlüssel des Datensatzes;
table[i]:data enthält die eigentlichen Daten;
table[i]:status enth¨alt einen der folgenden Werte:
______ used: table[i] enthält einen gültigen Datensatz;
______ unused: table[i] ist frei und war nie besetzt;
______ reusable: table[i] war schon besetzt, ist aber wieder frei.
Nehmen Sie an, dass eine Hashfunktion a(k) existiert, die aus einem Schlüssel k einen Hashindex in der (oben) deklarierten Tabelle berechnet. Schreiben Sie eine Prozedur in Pseudocode, die feststellt, ob ein Datensatz mit dem Schl¨ussel searchkey in der Tabelle enthalten ist. Bei Erfolg soll der Index des Datensatzes zurückgeliefert werden, bei Misserfolg der Wert ¡1. Zur Behandlung von Kollisionen ist die konstante Schrittweite c1 zu verwenden. __________________________________________________ ___
Ich hab das folgendermassen gemacht:
Suche_key(T,m,searchkey) {
pos = a(searchkey); // Position ermitteln
solange (T[pos].status == used v T[pos] == reuseable) {
//Solange es nicht frei ist
falls T[pos].key != searchkey {
pos = (pos + c1) mod m
}
sonst return T[pos].key;
}
return -1;
hoffe dass das auch stimmt ;)
_________________________________
Angabe zu c:
Die oben genannten Schlüssel sind Zeichenketten in der Form, dass Sie auf die einzelnen Elemente eines Schlüssels key als Zeichen
key.char[j], j = 0......m - 1, zugreifen können.
Es existiert eine Funktion ord(ch), welche den numerischen Wert eines Zeichens ch liefert.
Schreiben Sie eine Hashfunktion a'(k) in Pseudocode, welche nach der Divisions-Rest-Methode vorgeht, um aus den Zeichen des Schlüssels k einen Hashindex zu berechnen. Was die Lösung betrifft, bin ich mir da selber nicht sicher.
Ich habs so probiert:
a'(k) = (T[a(k)].key) mod m
bitte um Kritik
Wahrscheinlich ist eher a'(k) = [ ord(T[a(k)].key) ] mod m gemeint?