0

配列に対してバイナリ検索を実行しようとしていますが、文字列のすべての出現箇所を見つける必要があります。試してみましたがbsearch、どうすればいいのかわかりません。

/* data structures */

typedef struct {
    char *name;
    char *value;
} acronym;

struct {
    acronym *tab;
    size_t size;
} acronymArray;

/* code */

char buf[256];
fgets(buf, sizeof buf, stdin);
for (size_t i = 0; i < acronymArray.size; ++i) 
       if (!strcmp(buf, acronymArray.tab[i].name)) 
           printf("Found: %s\n", acronymArray.tab[i].value);

 /* How to translate it with a binary search ?
    Of course my array was sorted with qsort previously */

私はそれを試しましたが、それは1回だけ機能します:

if ((k = bsearch(k, acronymArray.tab, acronymArray.size, sizeof *acronymArray.tab, compare)))
    printf("found : %s\n", k->value);

ブール変数を構造«頭字語»に入れることを考えましたが、よくわかりません...これは宿題ではありません。

どうもありがとう !

4

2 に答える 2

5

それは非常に単純なはずです。二分探索でオカレンスを見つけ、見つかったアイテムと等しくないものが見つかるまで(またはシーケンスの終わりが見つかるまで)見つかったオカレンスから前方/後方を探します。すべてのオカレンスは、ソートされたリストで連続している必要があります。

于 2012-05-04T13:04:23.183 に答える
0

すべてのコードを投稿する必要があると思います。文字列が格納される通常の方法は、ハッシュテーブルまたはバイナリツリーを使用することです。

于 2012-05-04T13:20:03.417 に答える