Hallo, ich will mit einer binären Suche eine Tabelle nach einem string durchsuchen. dazu habe ich folgende Funktion im Netz gefunden: http://www.codeguru.com/Cpp/Cpp/algorithms/search/article.php/c5095/ meine Tabelle und mein struct sihet im mom folgendermassen aus: const comm_struct comm_tab[] = { // command table {"igain"/*, igain}, // remote commands {"period", &period}, {"pgain", &pgain}, // {"", NULL} // end of table }; typedef struct{ char *parameter; char *PtrList; }comm_struct; wie muss ich mein struct anpassen und meine tabelle anpassen, damit sie mit der Funktion funktioniert?...danke!
Wenn du nicht mindestens 50 Einträge in deiner Liste hast dann vergiss das mit der binären Suche ganz schnell. Der Codieraufwand ist viel zu gross. Durchlauf einfach deine Liste bis du den richtigen Eintrag gefunden hast. Wenn du darauf achtest dass die Strings sortiert in der Liste abgelegt sind kannst du die Suche abbrechen wenn der String in der Liste alphabetisch grösser ist als der gesuchte Stringwert. P.S Die von dir dargestellte Struktur wird wohl kein Compiler so übersetzen können :-(
ich hab aber weit über 50 einträge...dass nur 3 Parameter in der List sind, ist nur ein Beispiel....
Dann überleg mal die Logik der binären Suche, dann kannst du dir deine Suchfunktion ganz einfach selber schreiben. Angenommen du hast 80 Einträge in der List, welche sortiert(!) vorliegt. Jetzt vergleichst du den mittleren (40sten) Eintrag der Liste mit dem zu suchenden Schlüsselwort. Ist der Eintrag in der Liste kleiner als das gesuchte Wort dann suchst du in der unteren Hälfte der Liste weiter. Ist der Eintrag in der Liste grösser als das gesuchte Wort dann suchst du in der oberen Hälfte weiter. Dazu verwendest du am besten 2 Schleppvariablen (z.B. nLow, nHigh) welche du zu Beginn der Suche mit dem minimalen (0) und maximalen (in unserem Beispiel 79) Arrayindex initialisierst. Wenn bei der Suche nHigh plötzlich kleiner als nLow wird dann konnte der Eintrag nicht gefunden werden.
danke... und was passiert, wenn die strings unterschiedliche Länge habe?....zum vergleich verwende ich die fertige funktion "strcmp" von c
Hallo sam, IMHO würde ich nicht mit strcmp vergleichen, sondern immer nur das nächste Zeichen, das noch nicht passte. Bsp: Eingabe = Hallo ; Liste = {Alpha, Hallo, Lima, Tango, Yankee} Nun legst Du los mit: unsigned char macht_position(void) { nhigh = 4, nlow = 0; npos = (nhigh - nlow) / 2 matchpos = 0; matchmax = 3; if (Liste [npos][matchpos] > Eingabe[matchpos) nhigh = npos; if (Liste [npos][matchpos] < Eingabe[matchpos) nhigh = npos; if (Liste [npos][matchpos] == Eingabe[matchpos) { if (matchpos < matchmax) matchpos ++; else if (strcmp (Liste[npos], Eingabe, strlen(Eingabe)) ) return TRUE; else return FALSE; } } Was passiert ist folgendes: Ist Eingabe an der ersten Stelle kleiner als die erste Stelle der Eingabe, dann wird im oberen Teil der Liste weiter nachgeschaut. Man halbiert also immer die betrachtete Menge. Weiterhin weiß ich, bis zu welcher Steelle maximal Unterschiede auftauchen können - matchmax. Nun benutze ich den oberen Algorithmus so lange, bis dies ich diese Tiefe erreichen und weiß, das mein betrachteter String bis dort übereinstimmt. Schlußendlich schaue ich noch mit strcmp nach obs wirklich so ist und geb dann den entsprechenden Wert zurück. Dies ist wesendlich schneller, als die strcmp Funktion, die jedesmal den gesamten STring vergleicht. Gruß Marcus
Hallo, das Zauberwort lautet bsearch und qsort! bsearch tut genau das, was Christian erläutert. Ist dein Array von Strings noch nicht sortiert, verwendest du dazu die Funktion qsort. Sowohl bei bsearch als auch bei qsort gibst du eine Vergleichsfunktion, die du nach belieben ausprogrammieren kannst. Beide Funktionen sollten auch auf uC problemlos funktionieren. 'qsort' kannst du natürlich nicht auf Strings im Flash anwenden, die müssen vorher schon sortiert sein. Gruss, Peter
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.