C 標準関数逆引き辞典

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

#define STR_MAX  256  /* 文字列の最大長 */

/* 比較関数 */
int strcmp_asc(const void *, const void *);

int main(void)
{
  /* 検索するデータ */
  char systems[][STR_MAX] =
  {
      "Windows"
    , "ウィンドウズ"
    , "Linux"
    , "リナックス"
    , "Solaris"
    , "ソラリス"
  };

  int i;
  int length, index;
  char search[STR_MAX], *result;

  /* 要素数を求める */
  length = sizeof(systems) / STR_MAX;

  /* 昇順でソート */
  qsort(systems, length, STR_MAX, strcmp_asc);

  printf("▼ソートしたデータ\n");
  for (i = 0; i < length; i++)
  {
    printf("systems[%d]=%s\n", i, systems[i]);
  }

  /* 要素を検索 */
  strcpy(search, "ウィンドウズ");
  result = (char *)bsearch(search, systems, length, STR_MAX,
                           strcmp_asc);
  if (result == NULL)
  {
    printf("[%s] が見つかりませんでした。\n", search);
    return EXIT_FAILURE;
  }

  index = (result - systems[0]) / STR_MAX;
  printf("[%s] が見つかりました。\n", result);
  printf("[%s] のインデックスは %d です。\n", result, index);

  return EXIT_SUCCESS;
}

/**
 * 文字列を辞書式順序の昇順で比較します。
 * @param sa 比較する文字列
 * @param sb 比較する文字列
 * @return sa が sb と等しい場合は 0 、
 *         sa が sb より小さい場合は -1 以下、
 *         sa が sb より大きい場合は 1 以上
 */
int strcmp_asc(const void *sa, const void *sb)
{
  return strcmp((char *)sa, (char *)sb);
}

▼ソートしたデータ
systems[0]=Linux
systems[1]=Solaris
systems[2]=Windows
systems[3]=ウィンドウズ
systems[4]=ソラリス
systems[5]=リナックス
[ウィンドウズ] が見つかりました。
[ウィンドウズ] のインデックスは 3 です。

void *bsearch(const void *e, const void *a, size_t n, size_t sz,
              int (__cdecl *cf)(const void *ea, const void *eb))

要素 n 個をソートした配列 a から要素 e を検索します。
sz には、要素のサイズ（バイト数）を指定します。

要素 e が見つかった場合は、その要素へのポインタを返します。
要素 e が見つからなかった場合は、NULL を返します。

検索の際、比較関数 cf が呼び出されます。
cf には、独自に作成した比較関数を指定します。

比較関数は、２つの引数を取るように作成します。
引数の型は、void ポインタ（ const void * ）です。

ここでは説明のため、その引数を ea 、eb とします。 この ea と eb に比較する要素が渡されるので、それを比較した値を返すようにします。

昇順でソートした場合、返す値は次のようになります。

• ea が eb と等しい … 0
• ea が eb より小さい（ ea < eb ） … -1 以下（負）
• ea が eb より大きい（ ea > eb ） … 1 以上（正）

降順でソートした場合は、昇順の正と負を逆にします。

• ea が eb より小さい（ ea < eb ） … 1 以上（正）
• ea が eb より大きい（ ea > eb ） … -1 以下（負）

返す値は、qsort 関数と同じです。
通常は、qsort 関数に指定した比較関数を cf に指定します。

• ▽ qsort 関数はこちら
• 配列の要素をソートする

●引数

e … 検索する要素
a … ソートした配列
n … ソートした要素の個数
sz … 要素のサイズ（バイト数）
cf … 比較関数

●戻り値

・要素 e が見つかった … その要素へのポインタ
・要素 e が見つからなかった… NULL

●補足１

検索には、２分探索（バイナリサーチ）のアルゴリズムが適用されます。

●補足２

配列 a に要素 e が重複している場合は、そのうちの一つを返します。

この場合、どの要素のポインタになるかは予測できません。
要素の並びによって変わります。

●補足３

文字列の配列だけでなく、他の型の配列も検索できます。

次の３つの例を挙げておきます。

• ワイド文字列の配列を検索
• 整数の配列を検索
• 構造体の配列を検索

---

［例１］ ワイド文字列の配列を検索

≪宣言≫

#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

#define STR_MAX  256  /* 文字列の最大長 */

/* 比較関数 */
int wcscmp_asc(const void *, const void *);

int main(void)
{
  /* 検索するデータ */
  wchar_t systems[][STR_MAX] =
  {
      L"Windows"
    , L"ウィンドウズ"
    , L"Linux"
    , L"リナックス"
    , L"Solaris"
    , L"ソラリス"
  };

  int i;
  int length, index;
  int datasize = sizeof(wchar_t) * STR_MAX;
  wchar_t search[STR_MAX], *result;

  setlocale(LC_ALL, "ja");  /* ロケールを日本語に設定 */

  /* 要素数を求める */
  length = sizeof(systems) / datasize;

  /* 昇順でソート */
  qsort(systems, length, datasize, wcscmp_asc);

  wprintf(L"▼ソートしたデータ\n");
  for (i = 0; i < length; i++)
  {
    wprintf(L"systems[%d]=%s\n", i, systems[i]);
  }

  /* 要素を検索 */
  wcscpy(search, L"ソラリス");
  result = (wchar_t *)bsearch(search, systems, length, datasize,
                              wcscmp_asc);
  if (result == NULL)
  {
    printf("[%s] が見つかりませんでした。\n", search);
    return EXIT_FAILURE;
  }

  index = (result - systems[0]) / STR_MAX;
  wprintf(L"[%s] が見つかりました。\n", result);
  wprintf(L"[%s] のインデックスは %d です。\n", result, index);

  return EXIT_SUCCESS;
}

/**
 * ワイド文字列を辞書式順序の昇順で比較します。
 * @param sa 比較するワイド文字列
 * @param sb 比較するワイド文字列
 * @return sa が sb と等しい場合は 0 、
 *         sa が sb より小さい場合は -1 以下、
 *         sa が sb より大きい場合は 1 以上
 */
int wcscmp_asc(const void *sa, const void *sb)
{
  return wcscmp((wchar_t *)sa, (wchar_t *)sb);
}

ソースファイル

次のような出力になります。

▼ソートしたデータ
systems[0]=Linux
systems[1]=Solaris
systems[2]=Windows
systems[3]=ウィンドウズ
systems[4]=ソラリス
systems[5]=リナックス
[ソラリス] が見つかりました。
[ソラリス] のインデックスは 4 です。

---

［例２］ 整数の配列を検索

≪宣言≫

#include <stdio.h>
#include <stdlib.h>
#include <search.h>

/* 比較関数 */
int numcmp_asc(const void *, const void *);

int main(void)
{
  /* 検索するデータ */
  int nums[] = {100, 2, 200, 1, 20, 10};

  int i;
  int length, index;
  int intsize = sizeof(int);
  int search, *result;

  /* 要素数を求める */
  length = sizeof(nums) / intsize;

  /* 昇順でソート */
  qsort(nums, length, intsize, numcmp_asc);

  printf("▼ソートしたデータ\n");
  for (i = 0; i < length; i++)
  {
    printf("nums[%d]=%d\n", i, nums[i]);
  }

  /* 要素を検索 */
  search = 100;
  result = (int *)bsearch(&search, nums, length, intsize,
                          numcmp_asc);
  if (result == NULL)
  {
    printf("[%d] が見つかりませんでした。\n", search);
    return EXIT_FAILURE;
  }

  index = result - nums;
  printf("[%d] が見つかりました。\n", *result);
  printf("[%d] のインデックスは %d です。\n", *result, index);

  return EXIT_SUCCESS;
}

/**
 * 数値を昇順で比較します。
 * @param na 比較する数値
 * @param nb 比較する数値
 * @return na が nb と等しい場合は 0 、
 *         na が nb より小さい場合は -1 以下、
 *         na が nb より大きい場合は 1 以上
 */
int numcmp_asc(const void *na, const void *nb)
{
  return *(int *)na - *(int *)nb;
}

ソースファイル

次のような出力になります。

▼ソートしたデータ
nums[0]=1
nums[1]=2
nums[2]=10
nums[3]=20
nums[4]=100
nums[5]=200
[100] が見つかりました。
[100] のインデックスは 4 です。

---

［例３］ 構造体の配列を検索

≪宣言≫

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

#define STR_MAX  256  /* 文字列の最大長 */

/* 比較関数 */
int idcmp_asc(const void *, const void *);

/* ユーザの情報 */
typedef struct user
{
  char id[STR_MAX];    /* ID */
  char name[STR_MAX];  /* 名前 */
} User;

int main(void)
{
  /* 検索するデータ */
  User users[] = {
          {"43987", "田中"}
        , {"97032", "山田"}
        , {"17416", "佐藤"}
        , {"77095", "鈴木"}
  };

  int i;
  int length, index;
  int datasize = sizeof(User);
  User search, *result;

  /* 要素数を求める */
  length = sizeof(users) / datasize;

  /* ID の昇順でソート */
  qsort(users, length, datasize, idcmp_asc);

  printf("▼ソートしたデータ\n");
  printf("   [ID]   [名前]\n");
  for (i = 0; i < length; i++)
  {
    printf("%d  %s  %s\n", i, users[i].id, users[i].name);
  }

  /* 要素を検索 */
  strcpy(search.id, "77095");
  result = (User *)bsearch(&search, users, length, datasize,
                           idcmp_asc);
  if (result == NULL)
  {
    printf("[%s] が見つかりませんでした。\n", search.id);
    return EXIT_FAILURE;
  }

  index = result - users;
  printf("[%s] が見つかりました。\n", result->id);
  printf("[%s] のインデックスは %d です。\n", result->id, index);

  return EXIT_SUCCESS;
}

/**
 * ID を昇順で比較します。
 * @param ua 比較するユーザ
 * @param ub 比較するユーザ
 * @return ua の ID が ub の ID と等しい場合は 0 、
 *         ua の ID が ub の ID より小さい場合は -1 以下、
 *         ua の ID が ub の ID より大きい場合は 1 以上
 */
int idcmp_asc(const void *ua, const void *ub)
{
  return strcmp(((User *)ua)->id, ((User *)ub)->id);
}

ソースファイル

次のような出力になります。

▼ソートしたデータ
   [ID]   [名前]
0  17416  佐藤
1  43987  田中
2  77095  鈴木
3  97032  山田
[77095] が見つかりました。
[77095] のインデックスは 2 です。