Linux講座にようこそ。このページは「Ｃ言語プログラミング入門 - 第14章．ライブラリ関数 - 一般ユーティリティライブラリ」です。

Ｃ言語プログラミング入門

14. ライブラリ関数（31/36） - ユーティリティライブラリ（4/5）

14.43 検索と整列の関数

14.43.1 bsearch関数

bsearch（binary search）関数は配列中から該当する要素を検索（サーチ）します。前提条件として、配列の内容は昇順に整列（ソート）されていなければなりません。

【表14-7-8】 bsearch関数
形式#include <stdlib.h>
void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
          int (*compar)(const void *, const void *));
返り値検索出来た場合は該当する要素のポインタを返し、検索出来なかった場合はNULLを返します。該当する要素が複数あった場合はどの要素のポインタが返るかは不定です。
引数
const void *key
検索キーを指定します。
const void *base
検索する配列を指定します。
size_t nmemb
検索する配列の要素数を指定します。
size_t size
検索する配列の要素の大きさをバイト単位で指定します。
int (*compar)(const void *, const void *)
検索キー（第１引数）と検索する配列の要素（第２引数）の値を比較する関数を指定します。

第５引数に指定したは関数はbsearch関数から呼び出されます。その時、第１引数は検索キーで、第２引数は検索キーと比較する配列要素が渡ってきますので、それを比較して次のような値を返すようにします。

  • 検索キーが検索する配列の要素の値より小さい場合は負の整数を返します。
  • 検索キーと検索する配列の要素の値が等しい場合は０を返します。
  • 検索キーが検索する配列の要素の値より大きい場合は正の整数を返します。

14.43.2 qsort関数

qsort関数は配列要素を昇順（小から大）または、降順（大から小）に整列（ソート）します。

【表14-7-9】 qsort関数
形式#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
          int(*compar)(const void *, const void *));
返り値ありません。
引数
void *base
整列する配列を指定します。
size_t nmemb
整列する配列の要素数を指定します。
size_t size
整列する配列の要素の大きさをバイト単位で指定します。
int(*compar)(const void *, const void *)
整列する配列の要素の値を比較する関数を指定します。

第４引数に指定したは関数はqsort関数から呼び出されます。その時、引数には比較する配列要素が渡ってきますので、それを比較して次のような値を返すようにします。（降順の場合は小さい場合と大きい場合を逆にします）

  • 第１引数が第２引数の値より小さい場合は負の整数を返します。
  • 第１引数と第２引数の値が等しい場合は０を返します。
  • 第１引数が第２引数の値より大きい場合は正の整数を返します。

14.43.3 例題

郵便番号と住所を記入したファイルを入力して、指定された郵便番号に対する住所を表示します。郵便番号として「end」を入力したら終了します。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <errno.h>
  5. #define DATAMAX    20
  6.  
  7. /* 住所データ構造体 */
  8. typedef struct
  9. {
  10.     char    ad_jip_code[8];            /* 郵便番号 */
  11.     char    ad_address[80];            /* 住所 */
  12. } type_address;
  13.  
  14. /* 関数プロトタイプ宣言 */
  15. int sort_comp(const void *AdressRec1, const void *AdressRec2);    /* ソート用比較関数 */
  16. int search_comp(const void *JipCode, const void *AdressRec);      /* 検索用比較関数 */
  17.  
  18. int main(void)
  19. {
  20.     FILE            *fp;
  21.     char            *address_path = "./DATA/ex14_7_3_jip.dat";
  22.     type_address    address_data[DATAMAX];    /* 住所データ */
  23.     type_address    *p_address;
  24.     int             idx_cnt;
  25.     char            jip_code[20];
  26.  
  27.     /* 住所データを入力 */
  28.     if((fp = fopen(address_path, "r")) != NULL)
  29.     {
  30.         idx_cnt = 0;
  31.         while(fscanf(fp, "%7s,%s",
  32.             address_data[idx_cnt].ad_jip_code,
  33.             address_data[idx_cnt].ad_address) != EOF)
  34.         {
  35.             ++idx_cnt;
  36.         }
  37.         fclose(fp);
  38.     }
  39.     else
  40.     {
  41.         fprintf(stderr, "%s\n", strerror(errno));
  42.         exit(EXIT_FAILURE);
  43.     }
  44.  
  45.     /* 入力した住所データをソート */
  46.     qsort(address_data, idx_cnt, sizeof(type_address), sort_comp);
  47.  
  48.     /* 検索 */
  49.     while(1)
  50.     {
  51.         printf("郵便番号を入力してください ==> ");
  52.         scanf("%s", jip_code);
  53.  
  54.         if (strncmp(jip_code, "end", 3) != 0)
  55.         {
  56.             /* 入力した郵便番号をキーとして、住所データを検索 */
  57.             if ((p_address =
  58.                 bsearch(jip_code, address_data, idx_cnt,
  59.                         sizeof(type_address), search_comp)) != NULL)
  60.             {
  61.                 printf("%s\n", p_address->ad_address);
  62.             }
  63.             else
  64.             {
  65.                 printf("検索できませんでした。\n");
  66.             }
  67.         }
  68.         else
  69.         {
  70.             break;
  71.         }
  72.     }
  73.  
  74.     return EXIT_SUCCESS;
  75. }
  76.  
  77. /* ソート用比較関数 */
  78. int sort_comp(const void *pRec1, const void *pRec2)
  79. {
  80.     return strcmp(((type_address *)pRec1)->ad_jip_code,
  81.                   ((type_address *)pRec2)->ad_jip_code);
  82. }
  83.  
  84. /* 検索用比較関数 */
  85. int search_comp(const void *pJipCode, const void *pRec)
  86. {
  87.     return strcmp((char *)pJipCode,
  88.                   ((type_address *)pRec)->ad_jip_code);
  89. }
$ cat ./DATA/ex14_7_3_jip.dat
2430035,神奈川県厚木市愛甲
2430038,神奈川県厚木市愛名
2430126,神奈川県厚木市岡津古久
2430125,神奈川県厚木市小野
2430032,神奈川県厚木市恩名
2430031,神奈川県厚木市戸室
2430121,神奈川県厚木市七沢
2430033,神奈川県厚木市温水
2430039,神奈川県厚木市温水西
2430036,神奈川県厚木市長谷
2430034,神奈川県厚木市船子
2430037,神奈川県厚木市毛利台
2430122,神奈川県厚木市森の里
2430123,神奈川県厚木市森の里青山
2430124,神奈川県厚木市森の里若宮
$
$ ./ex14_7_3.prg
郵便番号を入力してください ==> 2430124
神奈川県厚木市森の里若宮
郵便番号を入力してください ==> 2430031
神奈川県厚木市戸室
郵便番号を入力してください ==> 2430126
神奈川県厚木市岡津古久
郵便番号を入力してください ==> 2430000
検索できませんでした。
郵便番号を入力してください ==> end
$
31行目
住所ファイル（ex14_7_3_jip.dat）を住所データ配列（address_data）に入力します。
46行目
住所データ配列を郵便番号をキーとしてqsort関数でソートします。
57行目
住所データ配列から入力した郵便番号をbsearch関数で検索します。
80行目
仮引数として渡された住所データの２つの要素の郵便番号をstrcmp関数で比較して、結果を返り値として返します。
87行目
仮引数として渡された郵便番号と住所データの郵便番号をstrcmp関数で比較して、結果を返り値として返します。