mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Binäre suche eines strings in einer tabelle


Autor: sam (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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/...

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!

Autor: Christian Schifferle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-(

Autor: sam (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich hab aber weit über 50 einträge...dass nur 3 Parameter in der List
sind, ist nur ein Beispiel....

Autor: Christian Schifferle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: sam (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
danke...
und was passiert, wenn die strings unterschiedliche Länge habe?....zum
vergleich verwende ich die fertige funktion "strcmp" von c

Autor: Marcus M. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter Mahler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.