Hilfe Hashfunktion Telefonbuch

[Jacqueline]

Hallo liebe Forum Gemeinde,

ich bin ziemlich neu hier und möchte mich kurz vorstellen.
Ich heiße Jacqueline und bin gerade im 1. Semester Master in Informatik für Geisteswissenschaftler.
Hier versuche ich mich gerade kämpfend in die Programmiersprachen C und C++ einzuarbeiten. Mal mehr und mal weniger erfolgreich.

Zur Zeit sitze ich, an einer für mich als Anfänger, ziemlich harten Nuss.

Vielleicht könnte mir einer von euch etwas helfen oder einen kleinen Tipp geben.

Wir sollen in C++ ein Telefonbuch mittels Hashfunktion programmieren Eine Matrix soll ein Telefonbuch repräsentieren. Die Elemente der Matrix sind Datensätze bestehend aus dem Familiennamen, Vornamen und einer Telefonnummer. Jede Matrixzeile enthält 5 solcher Einträge und das Menü soll mindestens 10 mal aufgerufen werden.
Soweit so gut

Ich habe das Gefühl mit meinem bisherigen Code total falsch zu liegen, ich kann zwar die Namen eingeben, aber wenn ich dann einen bestimmten Namen suchen will wird mir nur der jeweils erste geliefert.Ich steh gerade total auf dem Schlauch.

Für ein bisschen Hilfe wäre ich überaus dankbar!

Hier erst einmal mein bisher geschriebener Code

#include <iostream>
#include <string>

using namespace std;

struct Eintrag          //Eintrag für eine Person mit Nachname, Vorname und Telefonnummer
{
    string familienname;
    string vorname;
    int telnummer;
};

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

return hashwert;
}

int main()
{
    const int N = 130;      //maximal 5 Einträge in jedem Hashfach = 130 Einträge maximal
    int anzahl =0;
    char yn = 'y';

    Eintrag telbuch[N];     //Eingabe eines Eintrags für das Telefonbuch

    while (yn == 'y')
    {
        cout << "Name, Vorname, Telefonnummer eingeben: n";
        cin >> telbuch[anzahl].familienname >> telbuch[anzahl].vorname >> telbuch[anzahl].telnummer;

        int fach=hashing(telbuch[anzahl].familienname);     //Anzeige, welcher Hashwert zugeordnet wurde
        cout<<fach<<endl;

        anzahl ++;
        if (anzahl<130)     //falls noch nicht die Maximalanzahl erreicht ist können weitere Einträge eingegeben werden
        {
            cout << "weitere Daten? (y/n) ";
            cin >> yn;
        }
        else
            yn='f';
    }

return 0;
}

[Jockelx]

Hallo,

ich werde aus deinem Code nicht schlau.
Wo ist denn bei dir eine Matrix?
Die genaue Aufgabenstellung wäre gut, aber ich denke das soll so ungefähr aussehen:

Matrix:
In einer Zeile landen Einträge mit dem selben Hash (daher ist Hash auch nicht eindeutig):
{Schmitt, Jens, 123}   | {Schneider, Ute, 4645654} | | |
{Meier, Petra, 645645} | {Meisner, Dirk, 1253} | | |
{Thiele, Olaf, 435345} | | | |

Hift das schon?

[Jacqueline]

Hallo Jockelx,

vielen Dank für deine schnelle Antwort.
Ich habe es mir schon gedacht, wahrscheinlich liege ich mit meinem Code total falsch, weil ich auch einfach nicht weiter komme und irgendwie total keinen Plan mehr habe.
Oh Hilfe ich hoffe es wird mit viel Übung irgendwann mal besser.
Ich zeige dir mal die genau Aufgabenstellung.

Eine Matrix soll ein Telefonbuch repräsentieren. Die Elemente der Matrix sind Datensätze bestehend aus dem Familiennamen, Vornamen und einer Telefonnummer. Jede Matrixzeile enthält 5 solcher Einträge.

Realisieren Sie menügesteuert folgende Funktionalitäten:

Einfügen eines neuen Telefonbucheintrages. Dabei sollen die benötigten Daten von der Tastatur aus eingelesen werden. Danach soll der eingegebene Nachname mit Hilfe einer C++-Funktion „hashing“, die die oben beschriebene Wirkungsweise realisiert, auf die Menge von 26 Zahlen (0...25) abgebildet werden. Die sich ergebende Zahl soll als Zeilenindex der „Telefonmatrix“ interpretiert werden. Wenn in der betreffenden Zeile noch mindestens ein Eintrag frei ist, so sind die eingegebenen Werte dorthin zu kopieren, anderenfalls geschieht nichts. Der Nutzer ist über den Erfolg des Eintragens zu informieren.
Suchen eines Telefonbucheintrages. Dabei soll ein Nachname von der Tastatur eingelesen werden. Auf diesen ist wiederum die C++-Funktion „hashing“ anzuwenden, im resultierenden Zeilenindex ist nach dem Namen zu suchen. Der Nutzer erhält als Antwort auf die Suchanfrage alle gespeicherten Werte bezüglich des eingegebenen Nachnamens oder aber die Nachricht, dass ein solcher Name nicht gespeichert ist.

Das Menü soll mindestens 10 mal aufgerufen werden.

Sorry sorry das ist jetzt etwas viel, eure verzweifelte Jacqueline

Ich hoffe ich bin später auch mal in der Lage hier jemandem zu helfen

[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

[Furble Wurble]

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