qsortとbsearch

7772 ワード

c struct null System 言語

C言語ではbsearch()で二分検索が可能である.qsort()と同様にbsearch()もライブラリで、比較サブ関数もカスタマイズします.プロトタイプは次のとおりです.

void * bsearch ( const void * key,  const void * base, size_t nmem,  size_t size, int ( * comp) ( const  void * , const void * ) ) ;

keyは検索する要素を指し、baseは検索する配列を指し、nmemは検索長、一般に配列長、sizeは各要素が占めるバイト数であり、一般的にsizeof(...)を用いる.compは比較サブ関数を指し、比較のルールを定義します.データは予めソートされ、ソートされたルールはcompが比較サブ関数を指すルールと同じでなければならないことに注意してください.検索に成功すると、配列内の一致する要素のアドレスが返され、逆に空が返されます.複数の要素が一致した場合、bsearch()はどちらを返すか定義していません.
例:

# include < stdio. h> 
 # include < stdlib. h> 
 
 # define NUM 8
 
 int compare( const void * p, const void * q) 
 { 
     return ( * ( int * ) p - * ( int * ) q) ; 
 } 
 
 int main( int argc, char * argv[ ] ) 
 { 
     int array[ NUM] = { 9, 2, 7, 11, 3, 87, 34, 6} ; 
     int key = 3; 
     int * p; 
 
     
     qsort ( array, NUM, sizeof ( int ) , compare) ; 
     p = ( int * ) bsearch ( & key, array, NUM, sizeof ( int ) , compare) ; 
 
     ( p = = NULL ) ? puts ( "not found" ) : puts ( "found" ) ; 
 
     return 0; 
 }

結果は次のとおりです.
found

例openJugde 2804:
#include #include #include #include struct DIC { char str[11]; char ptr[11]; }; struct DIC dic[100005];//qsort比較関数int compare(const void*a,const void*b){//puts((*(struct DIC*)a).ptr);return strcmp((*(struct DIC*)a).ptr,(*(struct DIC*)b).ptr);}//bsearch比較関数int scompare(const void*a,const void*b){return(strcmp((char*)a,(*(struct DIC*)b).ptr);}int main(){ char s[30]; int n=0,i,j,k,temp; while(1){ gets(s); if(s[0]=='/0') break; for(i=0;s[i]!=' ';i++) dic[n].str[i]=s[i]; dic[n].str[i]='/0'; for(i=i+1,j=0;s[i]!='/0';i++){ dic[n].ptr[j++]=s[i]; } dic[n].ptr[j]='/0'; n++; } qsort(dic,n,sizeof(dic[0]),compare); while(scanf("%s",s)!=EOF){ DIC *p; p=(DIC*)bsearch(s,dic,n,sizeof(DIC),scompare); if(p==NULL){ printf("eh/n"); }else{ printf("%s/n",p->str); } } system("pause"); return 0; }

HTML 5+AJAXオリジナルブロックアップロードファイルのキーパラメータ設定

『HTML 5モバイル開発ガイド』——ノート6(CSS 3新特性)