Telefonbuch

[Moeki]

  Zitat

Beobachten Sie sich, wenn Sie in einer geordneten Folge, z.B. in einem Telefonbuch, nach einem Eintrag suchen. Formalisieren Sie Ihre Vorgehensweise und schreiben Sie einen Algorithmus. Analysieren Sie den Algorithmus hinsichtlich seiner Laufzeit.

type telefonbuch = record

                          ort = array [1..maxint] of char;

                          vorwahl = array [1..maxint] of byte;

                          name = array (1..maxint) of char;

                          vorname = array (1..maxint) of char;

                          straße = array (1..maxint) of char;

                          telefonnummer = array (1..maxint) of int;

                          end.

Ich würde jetzt mit 4 ineinander verketteten while schleifen, jeweils den nächsten ort (dann namen, dann vornamen, dann straße) wählen, solange der gegebene ort kleiner als der gesucht ort ist. denn char ist ein skalarer datentyp. das setzt voraus, dass man immer am anfang anfängt und nicht zwischendurch. dieses problem kann man ja mit 4 ineinander verketteten while schleifen lösen, die dann rückwärts laufen. jedenfalls hat man ja dann irgendwann den gesuchten eintrag mit der jeweiligen vorwahlnummer und telefonnummer. oder?

hinsichtlich der laufzeit ist mein algorithmus linear, denke ich.

[U-- °LoneWolf°]

Ups Sorry hatte die obenstehende Aufgabenstellung überlesen.

Aber wiso benötigst du 4 schleifen?

Denn wenn du den Ort hats bekommst du automatisch die Vorwahl.

Wenn du den Vor- und Nachnamen in Kombination mit der Straße und hausnummer hast bekommst du die Telefonnummer.

[Moeki]

das ist richtig.

ich brauche aber eine schleife für den ort, eine für den namen, einen vor den vornamen und eine für die straße. = 4. bei der straße bin ich mir nicht so ganz sicher aber es kann ja sein, dass es zwei hugo müller in unterschiedlichen straßen gibt.

[Muadibb]

Ist die Frage, wie genau Du das machen sollst:

Wenn Du auch Dein Vorgehen beim alphabetischen Suchen beschreiben sollst, dann wird etwas komplexer, da Du ja (zumindest mache ich das so ) eine Art Teilung machst. Der Ort München ist gesucht und Du schlägst das Telefonbuch bei "I" auf. Also gehst Du weiter nach hinten, usw.

Das selbe Schema verfolge ich bei dem Namen und den anderen Attributen.

Klingt für mich ein wenig nach binärer Suche .

Seit Ihr anderer Meinung?

[Moeki]

binäre suche hört sich gut an, aber dann jeweils für den ort, name, vorname und straße, denke ich. oder kann man das ineinander schachteln?

das ist aber wieer abhängig davon, was für ein "telefonbuch-sucher" man ist. ich schlage das buch zB nicht immer in der mitte auf *gg*

die laufzeit wäre dann O(log n).

[Muadibb]

Ja, schachteln musst Du wohl, Da Du erst nach dem Namen suchen kannst, wenn Du den Ort kennst. Du kannst auch erst nach der Strasse suchen, wenn Du den Namen kennst.

Naja, wenn Du nicht direkt die Mitte nimmst, kann es ja Vorteile aber auch Nachteile haben, je nachdem, ob Du näher am Ziel bist oder nicht

[U-- °LoneWolf°]

Em du brauchst doch die While schleife nur damit bei gefundenem Datensatz sofort abgebrochen wird oder? Dann kannst du es Theoretisch sogar mit einer Schleife lösen. Das zauberwort heist IF abfrage