Hilfe Hashfunktion Telefonbuch

Jockelx

Ja, dann leg mal los

Also es ist so wie ich vorher gesagt habe.

Dein Telefonbuch-Container sollte also so aussehen:

Eintrag telbuch[26][5];  // 26 Zeilen, da die Hash-Fkt einen Wert zwischen 0 und 25 liefert
// 5 Spalten, weil = max laut Aufgabenstellung

~~Eintrag ist telnummer nicht unbedingt als int speichern (+495345345, 040/54545,...) sind nicht so gut dafür geeignet.~~
Jetzt willst du einen neuen Eintrag einfügen:
- holst dir den Hash des Eintrags => weisst in welche Zeile er muss
- guckst nach, wieviel Einträge dort vorhanden sind
- ist noch Platz?
ja: einfügen
nein: fehler

Soweit kannst das ja schonmal machen.

Edit: Man Gott, was für ein Satz.
Ignoriere vielleicht erstmal so 'Feinheiten', dass int als Datentyp für Telefonnummern ungeeignet ist oder das dir 'Kim Ho' um die Ohren fliegen würde.

Jacqueline

Hallo Jockelx,

vielen Dank für deine Hilfestellung
Nach etlichen Tagen des Probierens bin ich hoffentlich schon einen Schritt weiter in die richtige Richtung gekommen.
Allerdings hat die Suchfunktion noch einen Haken und bei der Sortierung bin ich mir auch nicht sicher.

Vielleicht könntest du mir noch einen Ratschlag geben, was noch geändert werden muss? Ich bin gerade mal wieder mit dem Latein am Ende. Buuh ist ganz schön kompliziert

Viele Grüsse und Tausend Dank

#include <iostream>

#include <string>
using namespace std;

struct Eintrag          //Eintrag fuer eine Person mit Nachname, Vorname und Telefonnummer
{
    string familienname;
    string vorname;
    int telefonnummer;
    int sortierwert;
};

int hashing(string familienname)    //Hashfunktion bezugnehmend auf Familienname, welcher einen bestimmten Wert zurueckgibt
{
int hashwert;
hashwert=(familienname[0]*100 + familienname[1]*10 + familienname[2])%26;
return hashwert;
}

int main()
{
    int anzahl = 0;     //mehr als 130 Eintraege koennen nicht angenommen werden
    char yn = 'y';
    int i;
    int j;
    Eintrag telbuch[26][5];     //Speichertabelle fuer die Eintraege
    Eintrag eingabe;            //Eingabe eines Eintrags für das Telefonbuch

    for (i=0;i<26;i++)
       for(j=0;j<5;j++)
          telbuch[i][j].telefonnummer=0;    //Initialisierung aller Eintraege auf Telefonnummer=0

    while (yn == 'y')
    {
        cout << "Name, Vorname, Telefonnummer eingeben:"<<endl;
        cin >> eingabe.familienname >> eingabe.vorname >> eingabe.telefonnummer;
        cout << "Length: " << eingabe.familienname.length() << endl; //Laenge des Strings Familienname

         i = hashing(eingabe.familienname);

        cout << "Hashwert: " << i << endl;      //Anzeige, welcher Hashwert zugeordnet wurde

        if (eingabe.familienname.length()>=3)       //Pruefung ob mindestens 3 Zeichen eingegeben wurden
        {
            cout<<"Eingabe korrekt"<<endl;

           while(j<5)
           {
                if(telbuch[i][j].telefonnummer==0)
                {
                    telbuch[i][j].familienname=eingabe.familienname;
                    telbuch[i][j].vorname=eingabe.vorname;
                    telbuch[i][j].telefonnummer=eingabe.telefonnummer;
                    telbuch[i][j].sortierwert=hashing(eingabe.familienname);
                   // break;
                }
                else
                    j++;
           }
            anzahl++;
        }

        else
        {
            cout<<"Familienname zu kurz"<<endl;
        }

        if (anzahl<130)     //falls noch nicht die Maximalanzahl erreicht ist koennen weitere Eintraege eingegeben werden
        {
            cout << "weitere Daten? (y/n) ";
            cin >> yn;
        }
        else
            yn='f';

    }

// Nach Eintraegen im Telefonbuch suchen

    string familienname;
    int index;
    do
    {
        cout << "Name: "<<endl;
        cin >> familienname;
        int fach=hashing(familienname);     //Anzeige, welcher Hashwert zugeordnet wurde

       // index = -1;

        for (int i=0; i<anzahl; i++)
        {
           //while(j<5)
            {
                if (telbuch[i][j].sortierwert == fach)         // Telefonbuch nach Familienname durchsuchen
                {
                    // Gefunden bei index i
                    index = i;
                    //break;
                }
            }
        }
        if (index == -1)
        {
            cout << "kein Eintrag gefunden"<<endl;
        }
        else
        {
            cout << "Eintrag gefunden: "<<endl;
            cout << "Name: "<<telbuch[index][j].familienname <<endl;
            cout << "Vorname: "<<telbuch[index][j].vorname <<endl;
            cout << "Telefonnummer "<<telbuch[index][j].telefonnummer <<endl;
        }
        cout << "weitere Anfragen? (y/n) ";
        cin >> yn;
    }
    while (yn == 'y');

    return 0;
}

Belli

Dein Code ist ohne Code-Tags sehr schwer zu lesen. Beim Überfliegen scheint mir allerdings, dass Deine Matrix schon gar nicht gefüllt wird.

Ich habe den Eindruck, dass an dieser Stelle:

while(j<5)  // <=====
{
  if(telbuch[i][j].telefonnummer==0)
  {
    telbuch[i][j].familienname=eingabe.familienname;
    telbuch[i][j].vorname=eingabe.vorname;
    telbuch[i][j].telefonnummer=eingabe.telefonnummer;
    telbuch[i][j].sortierwert=hashing(eingabe.familienname);

j schon immer den Wert 5 hat, und die Schleife deshalb gar nicht betreten wird.

Jacqueline

Hallo Belli,

vielen Dank für Deine Antwort und sorry für die vergessenen Code-Tags, ich bin ziemlich neu hier.

Ich habe wohl wirklich nicht den richtigen Plan, kannst du mir vielleicht sagen was ich ändern muss, damit die Matrix richtig gefüllt wird?
Egal was ich mache, ich komme maximal zu einer Endlosschleife, aber nicht mehr oder annähernd in die richtige Richtung

Wutz

Du hast das Prinzip der Hashtables nicht verstanden, deine Implementierung von telbuch als 2-dimensional und sortierwert lässt keinen anderen Schluss zu.
Außerdem ist Familienname als Hash-Key völlig unsinnig, was machst du z.B. bei mehrfachem Vorkommen desselben Familiennames?
Welchen der mehrfach vorkommenden Einträge soll die Suchfunktion dann finden?
Außerdem bietet C++ mit unordered_map bereits eine Hashtable an, für Strings sogar mit integrierter Hashfunktion.

Marc-O

Wutz schrieb:

Du hast das Prinzip der Hashtables nicht verstanden, deine Implementierung von telbuch als 2-dimensional und sortierwert lässt keinen anderen Schluss zu.
Außerdem ist Familienname als Hash-Key völlig unsinnig, was machst du z.B. bei mehrfachem Vorkommen desselben Familiennames?
Welchen der mehrfach vorkommenden Einträge soll die Suchfunktion dann finden?
Außerdem bietet C++ mit unordered_map bereits eine Hashtable an, für Strings sogar mit integrierter Hashfunktion.

Natürlich hast du damit recht, aber es ist so in der Aufgabenstellung definiert, siehe Post 3 und dann muss man sich leider dran halten.

Jacqueline das Problem mit der While-Schleife liegt an deiner nicht vorher richtig initaliseren Variable "j". Diese ist noch durch durch das erste beschreiben auf 5 gesetzt:

for (i=0;i<26;i++) 
  for(j=0;j<5;j++) // <== hier wird sie immer passen belegt, aber am Ende steht eine 5 drin
    telbuch[i][j].telefonnummer=0; //Initialisierung aller Eintraege auf Telefonnummer=0

Also am besten vor deiner While-Schleife mit 0 belegen, dann geht wird die Schleife auch durchlaufen.

Als 2tes, zuerst führst du das Hashing durch, und danach prüfst du die Anzahl der Zeichen passt, ist in der falsch Reihenfolge.

Das "break" in der While solltest du wieder einkommentieren und die Erhöhung der Anzahl mit in den If-Block nehmen, also in der Art:

if (eingabe.familienname.length()>=3) { //Pruefung ob mindestens 3 Zeichen eingegeben wurden 
  i = hashing(eingabe.familienname); 
  cout << "Hashwert: " << i << endl; //Anzeige, welcher Hashwert zugeordnet wurde 
  cout<<"Eingabe korrekt"<<endl; 

  j = 0; // Edit und dann auch noch selbst vergessen obwohl man es auch noch schreibt ;-)
  while(j<5) { 
    if(telbuch[i][j].telefonnummer==0) { 
      telbuch[i][j].familienname=eingabe.familienname; 
      telbuch[i][j].vorname=eingabe.vorname; 
      telbuch[i][j].telefonnummer=eingabe.telefonnummer; 
      telbuch[i][j].sortierwert=hashing(eingabe.familienname); 
      anzahl++; 
      break; 
    }
    else
      j++; 
  }
  // TODO: Ausgabe fehlt noch, das der Eintrag erfolgreich war oder nicht
} 
else
  cout<<"Familienname zu kurz"<<endl;

Edit: Bei deiner Suchfunktion arbeitest du wieder ganz anders als beim Eintragen, dass sollte dir selbst zu denken geben, das hier etwas nicht passt.
Auch hier ist der hashwert der erste Index im telbuch-Array und du musst nur noch den 2ten Index durchlaufen und nach den passenden Nachnamen suchen.
In etwa so:

i = hashwert(nachname);
while(j < 5) {
  if(telbuch[i][j].telefonnummer != 0 && telbuch[i][j].Nachname == nachname) {
    // Ausgabe der Informationen bzw. Index speichern und später ausgeben...
    break;
  }
}

MfG Marco

Wutz

Du hast recht, ich hatte überlesen

Jacqueline schrieb:

Informatik für Geisteswissenschaftler

Offensichtlich darf sich bei den Philosophen der Bodensatz der Informatiklehrer ungestraft tummeln.

Jacqueline

Vielen Dank Marco!!!!

Ich denke dank deiner Hilfe habe ich es jetzt endlich hin bekommen

Ganz schön schwierig am Anfang, aber nochmal tausend Dank für die Hilfe

Mfg Jacqueline

Jacqueline

Hallo wutz,

ja lustig, aber eigentlich sind in der Vorlesung alle versammelt.
Von Maschinenbau bis Physik

Naja kann ja nur noch besser werden

Mfg Jacqueline

Ich würde das sortiertwert Member weglassen. Warum sollte man das speichern, wenn man's doch leicht wieder berechenen kann?

Die einzelnen Member von Eingabe einzeln zu kopieren ist insofern unnötig, als das Du damit den Zuweisungsoperator von Eingabe händisch nachprogrammierst.
Du kannst ja zum Beispiel einfach schreiben:

Eingabe a, b;
a=b; // das = ist der sog. Zuweisungsoperator

anstatt

Eingabe a,b;
a.name=b.name;
a.vorname=b.vorname;
...

Es wird übrigens einfacher, wenn Du nicht alles in die main() Funktion klatscht, sondern in einzelne Funktionen aufteilst - wie z.B. hashing() .

Übrigens kannst Du Deinen Fauxpas mit den fehlenden Codetags noch berichtigen, indem Du Deine Beiträge editierst.

Jacqueline

Danke Furble Wurble für den Tipp

Code Tags wurden sofort gesetzt