Hilfe Hashfunktion Telefonbuch



  • 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.



  • 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;
    }
    


  • 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.



  • 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😕 😞



  • 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.



  • 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



  • Du hast recht, ich hatte überlesen

    Jacqueline schrieb:

    Informatik für Geisteswissenschaftler

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



  • 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



  • 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.



  • Danke Furble Wurble für den Tipp 😉

    Code Tags wurden sofort gesetzt 👍


Anmelden zum Antworten