Hallo!!
Soll dieses Mal eine Liste für Studenten mit Matrikelnummer, Name und eMail über Hashing erzeugen.
Die Matrikelnummer ist der Schlüssel.
Die beiden Hash-Methoden (also mit Weiterstreufunktion) sind gegeben:
int hash(int k){return k%m;} //m == Laenge des arrays
int hash2(int k){return 1+k%(m-2);} //fuer Sondierfolge
Wenn 75 % erreicht sind soll das Array vergrößert werden, hierfür ist eine Folge von Primzahlen gegeben:
1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573
Soweit so gut. Ich bin mir jetzt nicht ganz sicher ob ich das mit dem Hashing richtig verstanden habe ... Aber beim hinzufügen bzw. löschen versuche ich das zuerst mit der normalen hash-Funktion, wenn der Platz aber belegt (bzw frei beim löschen) ist, versuche ich mit der hash2 funktion etwas zu finden. ich bin mir aber noch nicht sicher, was ich mache, wenn ich auch damit nichts finde.
naja, wie auch immer, mein programm hätte ich soweit fertig, aber allein das hinzufügen von studenten funktioniert schon nicht, ich erhalte immer die Ausgabe "Student konnte nicht hinzugefügt werden". Aber einen Fehler in der add-Methode kann ich nicht finden???:L
ich weiß es ist ein seeehr langer code. aber ich wäre froh wenn jemand drüber schauen könnte. insbesondere über die add-methode ...
danke!
Soll dieses Mal eine Liste für Studenten mit Matrikelnummer, Name und eMail über Hashing erzeugen.
Die Matrikelnummer ist der Schlüssel.
Die beiden Hash-Methoden (also mit Weiterstreufunktion) sind gegeben:
int hash(int k){return k%m;} //m == Laenge des arrays
int hash2(int k){return 1+k%(m-2);} //fuer Sondierfolge
Wenn 75 % erreicht sind soll das Array vergrößert werden, hierfür ist eine Folge von Primzahlen gegeben:
1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573
Soweit so gut. Ich bin mir jetzt nicht ganz sicher ob ich das mit dem Hashing richtig verstanden habe ... Aber beim hinzufügen bzw. löschen versuche ich das zuerst mit der normalen hash-Funktion, wenn der Platz aber belegt (bzw frei beim löschen) ist, versuche ich mit der hash2 funktion etwas zu finden. ich bin mir aber noch nicht sicher, was ich mache, wenn ich auch damit nichts finde.
naja, wie auch immer, mein programm hätte ich soweit fertig, aber allein das hinzufügen von studenten funktioniert schon nicht, ich erhalte immer die Ausgabe "Student konnte nicht hinzugefügt werden". Aber einen Fehler in der add-Methode kann ich nicht finden???:L
Java:
public class StudList {
private int[] primzahlen = {1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573};
private StudListNodes[] tabelle;
private int anzahlStuds;
private int aktuelleLaenge;
public StudList() {
aktuelleLaenge = 0;
tabelle = new StudListNodes[primzahlen[aktuelleLaenge]];
}
public void add(int matrNr, String name, String email) {
/** neuer Eintrag; ueberschreibt evtl. schon vorhandenen Eintrag mit gleicher matrNr;
requires: matrNr positiv, name und email nichtleer **/
int place = hash(matrNr);
StudListNodes n = tabelle[place];
if (getStand(n) == 0 && n.matrikelnummer == matrNr || getStand(n) != 0) {
// wenn belegt: Matrikelnummer gleich, oder unbelegt
tabelle[place] = new StudListNodes(matrNr, name, email);
anzahlStuds++;
}
else { // sonst weiterstreuen
place = hash2(matrNr);
n = tabelle[place];
if (getStand(n) == 0 && n.matrikelnummer == matrNr || getStand(n) != 0) {
// muss wieder unbelegt oder gleiche MatrNr sein
tabelle[place] = new StudListNodes(matrNr, name, email);
anzahlStuds++;
}
else {
System.out.println("Student konnte nicht eingefuegt werden");
}
}
if ((tabelle.length * 0.75) <= anzahlStuds) { // > 75% eingefügt
aktuelleLaenge++;
StudListNodes[] tabelle2 = new StudListNodes[primzahlen[aktuelleLaenge]];
for (int i = 0; i < tabelle.length; i++) {
StudListNodes x = tabelle[i];
if (getStand(x) == 0) { // belegt, muss kopiert werden
int platz = hash(getNr(x));
if (getStand(tabelle2[platz]) == 0) { // wenn neuer Platz schon belegt wäre, finde anderne Platz
platz = hash(getNr(x));
}
tabelle2[platz] = new StudListNodes(matrNr, name, email);
}
}
this.tabelle = tabelle2;
}
}
public void delete(int matrNr) {
/** loescht Eintrag; keine Wirkung, falls matrNr nicht vorkommt; **/
int place = hash(matrNr);
StudListNodes n = tabelle[place];
if (getStand(n) == 0) { // belegt
n = new StudListNodes(); // leerer Knoten
anzahlStuds--;
}
}
public String giveName(int matrNr) {
/** liefert Namen zu Matrikelnummer; leerer String falls matrNr nicht vorkommt; **/
int place = hash(matrNr);
StudListNodes n = tabelle[place];
if (getStand(n) == 0) {
return getName(n);
}
else {
place = hash2(matrNr);
n = tabelle[place];
if (getStand(n) == 0) {
return getName(n);
}
else {
return " ";
}
}
}
public String giveMail(int matrNr) {
/** liefert email-Adresse zu Matrikelnummer; leerer String falls matrNr nicht vorkommt; **/
int place = hash(matrNr);
StudListNodes n = tabelle[place];
if (getStand(n) == 0) {
return getMail(n);
}
else {
place = hash2(matrNr);
n = tabelle[place];
if (getStand(n) == 0) {
return getMail(n);
}
else {
return " ";
}
}
}
private int hash(int k) {
return k%(tabelle.length);
}
private int hash2(int k) {
return 1+k%(tabelle.length-2);
}
private String getName(StudListNodes n) {
return n.name;
}
private String getMail(StudListNodes n) {
return n.mail;
}
private int getNr(StudListNodes n) {
return n.matrikelnummer;
}
private int getStand(StudListNodes n) {
if (n == null) {
return -1;
}
else {
return n.stand;
}
}
private class StudListNodes {
int matrikelnummer;
String name;
String mail;
int stand; // 0, belegt, -1 leer, -2 gelöscht
StudListNodes () { // leerer Node wird erzeugt, wenn gelöscht wird
stand = -2;
}
StudListNodes (int nr, String name, String mail) {
matrikelnummer = nr;
this.name = name;
this.mail = mail;
stand = 0; // 0 ... belegt
}
}
}ich weiß es ist ein seeehr langer code. aber ich wäre froh wenn jemand drüber schauen könnte. insbesondere über die add-methode ...
danke!
