Binäre Suche in einem Telefonbuch [solved]

Hallo Community!

habe eine Aufgabe in der Uni, die ich nicht geknackt bekomme und hoffe
ihr könnt mir ein bisschen auf die Sprünge helfen.

Aufgabenstellung

"Gegeben sei die Klasse Eintrag:
public class Eintrag
{
string name;
string vorname;
string ort;
long telefonNummer;
}

Erstellen sie eine Klasse TelefonBuch. Jedes Telefonbuch hat eine Menge von
Einträgen und bietet Funktionen für die Suche nach Einträgen bei gegebener
Telefonnummer bzw. für die Suche nach Telefonnummern bei gegebenen
Werten für name, Vorname und Ort an. Setzen sie dazu (manuel!) binäre Suche ein."

Soweit ich verstanden habe, brauche ich also eine Klasse die Objekte der Klasse
Eintrag irgendwie speichert (array?) und zwei Suchfunktionen bietet: Einmal
Nummer, dafür gibts Name, Vorname und Ort und einmal genau umgekehrt.

Wie man generell eine binäre Suche in einem int[] durchführt ist mir klar,
darum gehts mir hier auch nicht wirklich. Was ich konkret nicht verstehe ist,
wie ich das ganze am besten aufbaue und wie man die binäre Suche auf diese
Einträge (Klassen) am besten anwendet.

Die Einträge in ein Array zu werfen war meine erster Versuch, aber ich kann
bei einer binären Suche ja nur Nummern und keine Strings vergleichen, zudem
besteht das array ja nicht aus einzelnen Werten sondern Objekten (damit komm
ich mal gar nicht klar). Dazu kommt, das je nach Kriterium das Ganze ja gar nicht
alphabetisch sortiert ist (also wenn ich nach der Nummer suche z.B.) muss ich
das dann vorher erstmal sortieren!?

Ich poste hier mal meinen Ansatz, auch wenn der sicherlich nicht so ganz richtig
ist.

Klasse Eintrag:

public class Eintrag
    {
        string name;
        string vorname;
        string ort;
        long telefonNummer;

       public Eintrag(string name, string vorname, string ort, long telefonNummer)
        {
            this.name = name;
            this.vorname = vorname;
            this.ort = ort;
            this.telefonNummer = telefonNummer;
        }
    }

Klasse Telefonbuch:

   class Telefonbuch
    {
       // static test with 5 Entries only
        Eintrag[] entries = new Eintrag[4];

        public Telefonbuch(Eintrag e1, Eintrag e2, Eintrag e3, Eintrag e4, Eintrag e5)
        {
            entries[0] = e1;
            entries[1] = e2;
            entries[2] = e3;
            entries[3] = e4;
            entries[4] = e5;
        }

        public long searchEntry(long number)
        {
            //do something to return correct name, surname and place
        }
        public long searchNumber(string name, string vorname, string ort)
        {
            //do something to return correct number
        }

Meine Versuche, das Array mit den Objekten in ein int[] zu verwandeln zeig ich
mal aus peinlichkeitsgründen lieber nicht, das geht sicherlich eh nicht wirklich so...

Vielen Dank für eure Zeit.

kind regards,
Ingram

Hallo ingram333,

ein Eintrag-Array zu verwenden, ist schon ok. Das Array musst du natürlich sortieren, damit du binäre Suche verwenden kannst. Zum Sortieren schreibst du dir eine IComparer<Eintrag> oder implementierst für Eintrag IComparable<Eintrag>. Wenn du das hast, sollten sich auch die anderen Probleme in Luft auflösen.

herbivore

Hi ingram333,

also 1. siehst du es richtig, dass die Werte innerhalb deiner liste vorher sortiert sein müssen, sonst funktioniert die binäre Suche natürlich nicht.

Ich würde ein Dictionary verwenden mit der Telefonnummer als Key und deinen Eintragsobjekten als Value. So kannst du später schonmal elegant nach den passenden Einträgen passend zu einer Telefonnummer suchen.

Für den anderen Fall, das nach einem Namen gesucht werden soll, schau dir mal die Methode String.Compare() an. Das sollte eigentlich helfen, da diese dir zeigt ob ein String größer, kleiner oder gleich einem anderen String ist. Ich finde das unterstützt perfekt das Prinzip der binären Suche.

MfG
wax

ich finde den datentyp long für eine telefonnummer nicht geeignet. beispiel: 0049123456. Es werden die ersten zwei ziffern abgeschnitten. Dann funktioniert die nummer nicht mehr.

Gruß pdelvo

Vielen Dank erstmal für eure hilfreichen Antworten.

Ich hab den ersten Tip (nachdem ich mich erstmal einlesen musste)
mal versuchsweise umgesetzt.

public class Eintrag : IComparable
    {
        string name;
        string vorname;
        string ort;
        long telefonNummer;

       public Eintrag(string name, string vorname, string ort, long telefonNummer)
        {
            this.name = name;
            this.vorname = vorname;
            this.ort = ort;
            this.telefonNummer = telefonNummer;
        }

       // we need to overwrite ToString() to use our own structure
       // and handling the long value
       public override string ToString()
       {
           return String.Format("{0} {1} {2} {3}", this.name,
                this.vorname, this.ort, this.telefonNummer.ToString());
       }
       
      //implementing ICompare for telefon numbers, so they are our new index
      public int CompareTo(object obj)
       {
           if (obj is Eintrag)
           {
               Eintrag a1 = (Eintrag)obj;
               return this.telefonNummer.CompareTo(a1.telefonNummer);
           }
           else
               throw new ArgumentException("Wrong Object Type!");
       }
    }

    
    class Telefonbuch
    {
        static void Main(string[] args)
        {
            
            // first option, sort the array by number
            ArrayList entriesBynumber = new ArrayList();
            entriesBynumber.Add(new Eintrag("Aname", "Anton", "Frankfurt", 03912345678));
            entriesBynumber.Add(new Eintrag("Bname", "Peter", "Aachen", 04912345678));
            entriesBynumber.Add(new Eintrag("Cname", "Franz", "Ulm", 05912345678));
            entriesBynumber.Add(new Eintrag("Dname", "Franz", "Ulm", 01912345678));

            // Sort() now uses the telefon numbers as index thanks to ICompare
            entriesBynumber.Sort();

            foreach (Eintrag e in entriesBynumber)
            {
                Console.WriteLine(e);
            }

            Console.ReadLine();

            
        }
    }

Funktioniert soweit prima, aber wie kann ich das nun in der Eintrag
Klasse für die anderen Suchkriterien auch verfügbar machen? Ich bin
ja nicht so der erfahrene Programmierer, aber rein von der logik kann
ich das doch so nur einmal pro Klasse machen, oder? Also müsste ich
nun verschiedene Eintrag Klassen erstellen und jeweils ein anderes
Kriterium bei ICompare angeben? Geht das ggf. eleganter?

Zur Suche werde ich dann mal String.Compare genauer anschauen, sieht
genau nachdem aus das ich gesucht habe, danke.

Das "long" war in der Aufgabenstellugn vorgegeben... hmm... ich lass
das erstmal so, aber danke für den Hinweis.

Hallo ingram333,

wenn du .NET 2.0 oder höher benutzt, solltest du die generische Variante von IComparable, also IComparable<Eintrag> verwenden.

aber rein von der logik kann ich das doch so nur einmal pro Klasse machen, oder? Also müsste ich nun verschiedene Eintrag Klassen erstellen und jeweils ein anderes Kriterium bei ICompare angeben? Geht das ggf. eleganter?

Mehrere Eintrag-Klassen solltest du auf keinen Fall erstellen. Es sollte zwar nur eine Implementierung von IComparable<Eintrag> geben, aber du kannst mehrere Implementierungen von IComparer<Eintrag> zur Verfügung stellen.

herbivore

aha, so geht das also. Danke hat wunderbar geklappt!

Ist zwar sicher nicht die beste Telefonbuch Suche die jeh geschrieben wurde,
aber sollte reichen zum bestehen.

Danke noch mal für eure Zeit.