Wie nutze ich hier den Struct zur binären Suche?
Guten Tag,
ich versuche mir gerade selbst c beizubringen und bin nun bei den Thema Structs angekommen , dazu habe ich die folgende Aufgabe:
Hier mein trauriger Versuch:
Die binäre Suche sollte richtig sein, mir geht es darum den struct richtig zu nutzen, leider verstehe ich dies nach 100 YouTube Videos immer noch nicht:(
Dieses a[start].number habe ich auch nicht so richtig verstanden. Dies stand in einem Buch, warum dies funktioniert keine Ahnung
Hoffe ihr könnt mir hier helfen
5 Antworten
Die Struktur bestimmt doch nur, welche Daten in Deiner Liste sind. Jeder Eintrag hat eben einen bestimmten Aufbau, in Deinem Fall eine Nummer, einen Namen und einen Preis. Könnten auch andere Daten sein, beispielsweise Adressen oder sonstwas.
Was macht jetzt diese Suche? Sie sucht in einer Liste von nach Nummer sortierten Einträgen den Eintrag mit einer gegebenen Nummer und gibt die Daten aus.
Das hat nichts mit der "Nutzung der struct" zu tun. Dass hier eine struct verwendet wird, bedeutet nur, dass Elemente der Liste keine "einfachen Datentypen" wie int oder byte sind, sondern eben "komplexe Daten".
Naja, so falsch sieht's jetzt auf den ersten Blick nicht aus. Musst es halt mal testen und auch Randfälle betrachten wie: gesuchtes Element ist genau das erste oder genau in der Mitte oder genau das letzte oder gar nicht in der Liste.
Der Witz an der binären Suche ist ja, den Aufwand zu minimieren. Also was macht man? Man schaut sich die Mitte der Liste an und prüft, ob man sein Element gefunden hat. Wenn nicht, dann weiß man wegen der Sortierung genau, ob es links oder rechts weitergesucht werden muss. Dann nimmt man von dieser Hälfte eben wieder die Mitte - und immer so weiter.
Dann kommt irgendwann der Punkt, wo nur noch ein Element übrig ist - und entweder das ist es dann, oder man hat es nicht gefunden.
Deine Implementierung beispielsweise sucht immer weiter, auch wenn sie das Element schon gefunden hätte (siehe Zeile 60). Da könntest Du bereits abbrechen und die Ausgabe machen.
Falls es Dir um die Nutzung der Elemente der Liste geht, dann bedenke:
Auf ein Element eines Arrays a greifst Du zu über a[index]. Wenn das Element eines Arrays jetzt ein struct ist, dann hat das noch "Untervariablen", z.B. number.
Achso meinst du das:)
Also meine Frage bezieht sich hauptsächlich auf den struc und wie ich die Aufgaben erfülle. Das die binäre Suche noch verbesserungswürdig ist, war mir klar, habe gestern nur den pseudocode übersetzt und ein bissche umgespielt.
Da muss ich mich später noch einmal genauer mit beschäftigen.
Naja, welche Fragen hast Du denn konkret zum struct? Ein struct ist (wie der Name andeutet) ein strukturierter Datentyp. Variablen von diesem Typ haben immer denselben Aufbau, nämlich den, den Du in der Definition der struct vorgibst.
In Deinem Fall besteht ein "Element" vom Typ pk eben aus mehreren Elementen:
- number
- food
- price
Sprich, wenn Du eine Variable vom Typ pk hast, dann kannst Du auf diese 3 Werte für diese Variable zugreifen:
pk wurst;
pk brot;
wurst.number = 0815;
wurst.price = 1.99f;
brot.number = 4711;
brot.price = 2.49f;
Jetzt hast du eben nicht eine Variable von diesem Typ, sondern ein Array (eine Liste fester Länge) von lauter pks. Sprich, jedes Element ist ein pk.
Daher kannst Du sowas machen wie
a[i].price = 5.99f;
Das setzt für das i-te Element im Array den Preis auf 5,99.
Und das ist der ganze Sinn einer struct. Variablen zu machen, welche mehr als nur einen einzigen Wert, sondern einen ganzen "Datensatz", eine Datenstruktur, aufnehmen können.
Achso, also wenn ich nun den price in meiner Aufgabe ausgeben will, muss ich a[center].price schreiben? Da center der Index des arrays ist, wo number, food price jeweils zugehörig zueinander drinnen sind?
Hallo,
ich versuche gerade diesen Code einmal zu testen, nur wie bekommt man einen Array mit zahlen, wobei jede Zahl wiederum auf andere Elemente wie Preis etc verweist?
Ich verstehe die Frage nicht so richtig. Das ist doch bereits in Deinem Array a[] gegeben, denn jedes Element des Arrays ist doch von Deinem Typ pk, welcher diese Daten enthält.
Ein struct fasst in C mehrere Variablen zusammen. Der Aufbau ist wie folgt:
struct MyStruct {
int val1;
char *str;
float val2;
};
Dadurch wurde das ein struct deklariert, das den Namen MyStruct trägt.
Um ein struct zu initialisieren, gibt es mehrere Möglichkeiten:
struct MyStruct my_struct;
Alternativ wäre folgendes möglich:
struct MyStruct {
int val1;
char *str;
float val2;
} my_struct;
Man kann den Namen auch weglassen, also:
struct {
int val1;
char *str;
float val2;
} my_struct;
Über den Punkt weißt Du eine Variable einen Wert zu. Wenn es sich aber um einen Pointer handelt, dann musst Du diesen vorher dereferenzieren und dann den Wert zuweisen. Als Vereinfachung gibt es das ->
Dir ist klar, dass du evtl. auf Bereiche zugreifst, die außerhalb des Arrays liegen, da du die Gültigkeit der eingabeparameter nicht prüfst?
Außerdem würde ich den Fall a[center].number==number extra behandeln, da du sonst unnötig oft iterierst...
Hallo,
ja das könnte sein.
Da muss ich nochmal schauen wie man dies prüfen soll/kann.
Ich danke dir
Den Fall a[center].number==number habe ich auch nicht so richtig verstanden, dies kommt aus einem Buch.
Ich weiß nicht warum man auf dies hier tut a[center].number, ich hätte es ohne .number gemacht.
Das mit dem ".number" machst du deshalb, da im Array das Struct drinnen ist.
Mit ".number" greifst du dnan auf die "number"-variable aus dem Struct zu.
Hat es irgend einen tieferen Sinn, daß Du es rekursiv implementierst?
Der Prototyp der Funktion passt doch sonst soweit. Es ist prinzipiell egal, welchen Typs ein Array ist, die Benutzung bleibt doch im Prinzip gleich?
Der tiefere Sinn ist, dass die binäre Suche sich wunderbar kurz rekursiv implementieren lässt und quasi schon danach schreit, rekursiv implementiert zu werden, weil dasselbe auf derselben Struktur mit verminderter Komplexität geschieht.
Da ich allerdings keine getrennten Abstiegspfade habe, also keinen Stack wie bei einem Quicksort benötige, ist es unnötig.
Eine einfache iterative Implementierung ist daher tatsächlich genauso kurz und einfach. Speicherkomplekität liegt bei O(1), da ich nur die Zustandvariablen benötige, Laufzeitkomplexität ist O(log_2(n)) wie gehabt.
Die Binärsuche ist im Endeffekt eine Endrekursion, rekursiv Implementiert habe ich eine deutlich höhere Speicherkomplexität (O(log_2(n)).
Klar kann man das iterativ tun - vermutlich ist das aber zum einen eine Übung zur Rekursion, zum anderen finde ich persönlich es "verständlicher". Also ich hätte es auch rekursiv implementiert :-)
Gut, das wäre natürlich eien Option (Lernziel: Rekursion).
In Bibliotheken ist es iterativ implementiert, weil eben insgesamt günstiger, ich verweise einfach mal auf Bibliothekscode, dann muß ich nicht selbst eintippen, es ist etwas länger, weil es für beliebige Datentypen mit externer compare-Funktion geschrieben ist:
https://code.woboq.org/userspace/glibc/bits/stdlib-bsearch.h.html
Du mußt Dir also natürlich noch die Generik und die damit verbundene 'Pointermagie' wegedenken (Zeile 32 und 33). Ich denke, das ist kurz genug :-D.
Wie gesagt: Ich kann's schon ;-) Danke trotzdem für den Code.
Naja, faule Menschen würden einfach bsearch() aufrufen, aber ich glaube das ist dann wirklich nicht im Sinne der Aufgabenstellung *har har*.
if..if..else..else..if..else
Das ist der Stoff aus dem meine Alpträume gemacht sind.
Naja. Ich finde das übersichtlicher als irgendwelche "return"s einzubauen. Den Code hier kann man gerade noch überschauen. Sind nur zwei Ebenen.
Verschachtelt ist gut und richtig! Sonst führst du ja unnötig Code aus.
Da sind doch schon einige returns.
if .. if .. return .. else .. return .. else .. if .. return .. else .. return
Den Code hier kann man gerade noch überschauen
Das ist der Anspruch? Dass man den Code "gerade noch überschauen" kann?
Gruß
Nein. Der Anspruch ist, Code zu schreiben, den man verstehen kann. Und das ist hier der Fall. Hast Du schon mal "professionellen" Quellcode gesehen? Wenn das hier für Dich schon der Stoff für Albträume ist, dann möchte ich nicht wissen, wie's Dir dann gehen würde...
Außerdem war "gerade noch überschauen" eher spöttisch gemeint für: Wo ist denn Dein Problem?
Dann möchte ich Deinen Code lieber auch nicht sehen... Ist aber wohl philosophisch.
Kannst ja mal aufschreiben, wie Du es gemacht hättest. Einfach nur, weil ich neugierig bin und ja gerne dazulerne ;-)
Na, Du kennst doch sicher uncle Bob.
"Clean Code: A Handbook of Agile Software Craftsmanship" von Robert Martin
Falls nicht, viel Spaß beim Lesen.
Gruß
Nö, das Buch kenne ich nicht. Und ein schnelles Überfliegen zeigt mir, dass ich es auch nicht kennen brauche. Und wenn in diesem Buch steht, dass obiger Code ein Alptraum sei, dann ist das noch mehr Grund, mir das Geld zu sparen. Denn für diese 20 Zeilen rekursive Funktion lohnt der Aufwand nicht.
Nein, so hätte ich das auch nicht hingeschrieben (schon alleine, weil es zwei Stellen gibt, an der ein Fund erkannt werden kann), aber der Code ist jetzt auch nichts, wofür man sich in die Ecke stellen müsste.
Bin raus .....
Kannst Du ja ruhig sein. Ich finde einfach nur, man kann's a) auch übertreiben und b) mache ich 90% der Dinge ohnehin, auch ganz ohne Buch.
Hilft uns gar nicht , mach lieber mal eine Lösung und dann gucken wir uns an ob man das einfacher versteht . Und komm mir nicht mit diversen konstrukten , macht übrigens code auch nicht kleiner oder schneller . manchmal ist simple einfach besser . da bringt mir jetzt auch nix das irgendeiner meint nie IF zu schachteln , leiber dann 5 klassen ineinander schachteln und aufrufe etc auszulagern ? hallo , wenn ich 4+2=6 rechne brauch ich jetzt nicht die mathematisch korrekte beweisführung das es vielleicht a²+b²=c² ist und ich lieber mal eine funktion implementiere die das ausrechnet und als ergebnis im array zurück liefert. oder wie man sonst sagt, in OOP sollte es nur klassen geben und gar keine primitive datentypen . kann man denken führt aber zu nix produktiven , wie schon gesagt eher zu philosophischen aspekten .
Hallo, danke für deine Antwort.
Aso nehme ich an, dass meins erstmal falsch ist? Mist:)
Ach man ich habe sowas von keine Ahnung wie ich dies Aufgabe lösen soll, sitze schon rund 6 h.