Anwendung der Suchalgorithmen
Zielsetzung
Bei der Entwicklung von Suchalgorithmen haben wir bisher Zahlen als einfachste sortierbare Daten betrachtet. Bei realen Anwendungen hat man es meist mit komplexeren Datensätzen zu tun, die aus verschiedensten Daten bestehen. So könnte eine Datei mit Adressdaten wie den folgenden gegeben sein, die nach einem bestimmten Kriterium (z.B. dem Nachnamen) sortiert werden soll.
Krause,Stefanie,Brandenburgische Str. 20,74343,Sachsenheim Brandt,Mandy,Scharnweberstrasse 84,68199,Mannheim Almenhof Möller,Jens,Schoenebergerstrasse 47,08313,Bernsbach Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz Koertig,Christine,Hardenbergstraße 82,66887,Niederalben Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen Schreiber,Barbara,Stresemannstr. 56,66592,St Wendel ...
Download: Datenbestand unsortiert: adressdaten.csv
Download: Datenbestand nach Name sortiert: adressdaten.csv
Ziel ist es, ein gegebenes Suchprogramm so anzupassen, dass man beim vorliegenden Datenbestand benutzen kann.
Ein gegebenes Suchprogramm
Wir gehen von einem getesteten Programm zum Suchen in einer Liste mit Zahlen aus. Im vorliegenden Fall handelt es sich um eine Implementierung der binären Suche
# binäre Suche
def suchen(name, liste):
indexErgebnis = -1
gefunden = False
links = 0
rechts = len(liste)-1
while not gefunden and links <= rechts:
mitte = (links + rechts) // 2
if name == liste[mitte][0]:
gefunden = True
indexErgebnis = mitte
elif name < liste[mitte][0]:
rechts = mitte-1
else:
links = mitte+1
return indexErgebnis
Aufgabe 1
Teste das gegebene Suchprogramm mit geeigneten Testdaten.
Anpassung des Suchprogramms
Wir gehen nach wie vor davon aus, dass die Daten in der oben gezeigten Weise in einer Datei vorliegen.
Bevor der gegebene Suchalgorithmus auf diesen Daten operieren kann, müssen die Daten zunächst in eine Listenform überführt werden.
[
('Krause','Stefanie','Brandenburgische Str. 20','74343,Sachsenheim'),
('Brandt','Mandy','Scharnweberstrasse 84','68199','Mannheim Almenhof'),
('Möller','Jens','Schoenebergerstrasse 47','08313,Bernsbach'),
...
]
Diese Datentransformationen können mit Funktionen des Python-Programms listenoperationen_zum_laden_und_speichern.py durchgeführt werden:
Wenn man jetzt das oben gezeigte Suchprogramm anwenden möchte, muss man auf die vorgegebenen Funktionen zur Datentransformation zurückgreifen und den Vergleich der Datenobjekte anpassen. Der folgende Quelltext zeigt, wie das geht.
from listenoperationen_zum_laden_und_speichern import *
# binäre Suche
def suchen(name, liste):
indexErgebnis = -1
gefunden = False
links = 0
rechts = len(liste)-1
while not gefunden and links <= rechts:
mitte = (links + rechts) // 2
if name == liste[mitte][0]:
gefunden = True
indexErgebnis = mitte
elif name < liste[mitte][0]:
rechts = mitte-1
else:
links = mitte+1
return indexErgebnis
# Test
text = textAusDatei('adressdaten_sortiert_name.csv')
listeDaten = tupelListeAusText(text)
index = suchen('Schmitt', listeDaten)
print(index)
Aufgabe 2
Teste das angepasste Suchprogramm. Beachte, dass die Dateien
listenoperationen_zum_laden_und_speichern.py
und
adressdaten_sortiert_name.csv
im selben Verzeichnis wie das Programm vorliegen müssen.
Aufgabe 3
Passe analog ein Programm zur linearen Suche in einer Zahlenliste an die vorliegende Situation mit komplexen Datensätzen an. Teste mit derselben Datenbasis wie bei der binären Suche. Eventuell muss du etwas Geduld bei der Ausführung des angepassten Programms haben. Erkläre, woran das liegt. (Hinweis: Zum Vorabtesten kann man kleinere Datenbestände benutzen.)