- ベストアンサー
bsearch関数の内容について
keibou21の回答
- keibou21
- ベストアンサー率31% (18/58)
#3です >すいません、全然分かりません。 私が提示したコードを実際に動作させてみましたか？ そしてそれぞれのアドレスがどうなっているかデバッガなりコンソール出力で確かめてみましたか？ また、「アドレスの演算を行ったことはありますか？」の回答がありませんが、どうなんでしょ？ とりあえず、C言語の解説本やWebを参考にして復習されることをお勧めします。
関連するQ&A
- アルゴリズム:2分探索の時間計算量
アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。 /* ２分探索 */ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を２分探索 ---*/ int bin_search(const int a[], int n, int key) { int pl = 0;/* 探索範囲先頭の添字【1】 */ int pr = n-1;/* 〃 末尾の添字 【2】*/ int pc; /* 〃 中央の添字 */ do { pc = (pl + pr) / 2;/*【3】*/ if (a[pc] == key) /* 探索成功【4】 */ return (pc);/*【5】*/ else if (a[pc] < key)/*【6】*/ pl = pc + 1;/*【7】*/ else /*【8】*/ pr = pc - 1;/*【9】*/ } while (pl <= pr);/*【10】*/ return (-1);/* 探索失敗【11】 */ } のプログラムがありますが、【1】から【11】までの 実行回数と計算量は次のようになるそうですが、 実行回数 計算量 【1】 1 O(1) 【2】 1 O(1) 【3】 logn O(logn) 【4】 logn O(logn) 【5】 1 O(1) 【6】 logn O(logn) 【7】 logn O(logn) 【8】 logn O(logn) 【9】 logn O(logn) 【10】 logn O(logn) 【11】 1 O(1) なぜ【3】や【4】がlognになるんでしょうか？ 詳しく教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- c言語関数の(1)～(5)までの部分が何をやっているのかよく分からない
c言語関数の(1)～(5)までの部分が何をやっているのかよく分からないので、どなたか解説をお願いします。 int memcmp(const void *s1, const void *s2, size_t n) { const unsigned char *p1 = (const unsigned char *)s1; const unsigned char *p2 = (const unsigned char *)s2; while (n-- > 0) { if (*p1 != *p2) return (*p1 - *p2); p1++; p2++; } return (0); } return (*p1 - *p2); > (1) ---------------------------------------------------------------------- char *strcat(char *s1, const char *s2) { char *p = s1; while (*s1) s1++; /* s1を末尾まで進める */ while (*s1++ = *s2++) ; /* '\0'が見つかるまでs2をコピー */ return (p); } while (*s1++ = *s2++) ; > (2) ---------------------------------------------------------------------- char *strstr(const char *s1, const char *s2) { const char *p1 = s1; const char *p2 = s2; while (*p1 && *p2) { if (*p1 == *p2) { p1++; p2++; } else { p1 -= p2 - s2 - 1; p2 = s2; } } return (*p2 ? NULL : (char *)(p1 - (p2 - s2))); } while (*p1 && *p2) > (3) p1 -= p2 - s2 - 1; > (4) ---------------------------------------------------------------------- char *strcpy(char *s1, const char *s2) { char *p = s1; while (*s1++ = *s2++) ; return (p); } while (*s1++ = *s2++) > (5) ; > (5) ----------------------------------------------------------------------
- ベストアンサー
- C・C++・C#
- c言語の問題です。ファイルからデータを読み込み連結リストに記憶しソートするプログラムです。お願いします
ソート部分がどうしてもできません。 またソートは以下のアルゴリズムで行うものです 与えられたリストをリストＡ、ソート済みのリストをリストＢとする。処理の開始段階では、リストＢは空である。 1.リストＡの要素の中で、最大値をもつ要素Ｃを探す。 2.要素ＣをリストＡから削除する。 3.要素ＣをリストＢの先頭に挿入する。 4.リストＡが空であれば終了。空でなければ 1. にもどる。 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct physical Physical; struct physical { char name[41]; int age; float height; float weight; Physical *next; }; void read_data(char *file,Physical *p,Physical *tail); int comp1(const Physical *, const Physical *); int comp2(const Physical *, const Physical *); int comp3(const Physical *, const Physical *); int comp4(const Physical *, const Physical *); void sort(char *arg,Physical *p,Physical *q); Physical *listsort(Physical *p, int (*compar)(const void *, const void *)); int main(void) { char s[20],t,u[20]; Physical *p,*tail,*q; p=malloc(sizeof(Physical)); q=malloc(sizeof(Physical)); tail=malloc(sizeof(Physical)); while(1) { printf("CMD>"); fflush(stdout); fgets(s,20,stdin); sscanf(s,"%c %s",&t,u); switch(t){ case 'q':exit(0); case 'r':read_data(u,p,tail); break; case 's':sort(u,p,q); break; case 'd': while(q!=NULL) { printf("%s %d %.1f %.1f ",q->name,q->age,q->height,q->weight ); q=q->next;} break; } } free(p); return 0; } void read_data(char *file,Physical *p,Physical *tail){ FILE *fp; char string[100]; Physical header; tail=&header; header.next = NULL; p->next = NULL; tail->next = p; tail = p; if ((fp = fopen(file, "r")) == NULL) { exit(1); } while(fgets(string,sizeof(string),fp)!= NULL) { sscanf(string,"%s %d %f %f",p->name,&p->age,&p->height,&p->weight); Physical *tail2; tail2=malloc(sizeof(Physical)); tail2->next=NULL; p->next=tail2; p=tail2; } fclose(fp); } void sort(char *arg,Physical *p,Physical *q){ if(strcmp(arg,"name") == 0) q=listsort(p,(int(*)(const void*, const void*))comp1); if(strcmp(arg,"age") == 0) q=listsort(p,(int(*)(const void*, const void*))comp2); if(strcmp(arg,"height") == 0) q=listsort(p,(int(*)(const void*, const void*))comp3); if(strcmp(arg,"weight") == 0) q=listsort(p,(int(*)(const void*, const void*))comp4); } Physical *listsort(Physical *p,int (*compar)(const void *, const void *)){ Physical *q, *max,*s,*head; s=malloc(sizeof(Physical)); head=malloc(sizeof(Physical)); head=NULL; while(p->next){max = p, q = p->next; while( q->next ) { if( compar(q->next,max->next) ) max = q; q = q->next;} s=max->next; max->next=max->next->next; if(head==NULL) {head=s;} s->next=s; } return head; } int comp1(const Physical *a, const Physical *b){ return (strncmp(a->name,b->name,sizeof(Physical))); } int comp2(const Physical *a, const Physical *b){ if(a->age > b->age) return 1; else return 0; } int comp3(const Physical *a, const Physical *b){ if(a->height > b->height) return 1; else return 0; } int comp4(const Physical *a, const Physical *b){ if(a->weight > b->weight) return 1; else return 0; }
- 締切済み
- C・C++・C#
- Cの関数定義で見慣れない記述がありました
libeventというソフトのソースに以下のような関数定義がありました。 この関数の定義部分が見慣れないものでした。 この関数は、size_tを戻り値としてもち、_event_strlcpyという名前で、 引数として、dst, src, sizの三つをもつというのはわかるのですが、 どうして_event_strlcpy(dst, src, siz)のように、 引数に型が宣言されていないのでしょうか？こういう書き方はアリなのですか？ 普通は、_event_strlcpy(char *dst, const char *src, size_t size) というように書くものではないでしょうか？ しかも、_event_strlcpy(dst, src, siz)の次の行からの、 char *dst;const char *src;size_t size;の三行は何なのでしょうか？ このような位置にこういった書き方をするのはアリなのですか？ size_t _event_strlcpy(dst, src, siz) char *dst; const char *src; size_t siz; { register char *d = dst; register const char *s = src; register size_t n = siz; /* Copy as many bytes as will fit */ if (n != 0 && --n != 0) { do { if ((*d++ = *s++) == 0) break; } while (--n != 0); } /* Not enough room in dst, add NUL and traverse rest of src */ if (n == 0) { if (siz != 0) *d = '\0'; /* NUL-terminate dst */ while (*s++) ; } return(s - src - 1); /* count does not include NUL */ }
- ベストアンサー
- C・C++・C#
- strtol関数をmalloc()関数を使用して次のソースプログラムを
strtol関数をmalloc()関数を使用して次のソースプログラムを修正しなさいを言われました。 どなたか詳しい方よろしくお願いします。 #include <limits.h> #include <ctype.h> #include <errno.h> #include <stdio.h> int _space_sign(const char *s, const char **endptr); int _space_sign(const char *s, const char **endptr) { int sign ; while (isspace((unsigned char)*s)) ++s; sign = 0; switch (*s) { case '-': sign = -1; // fall through case '+': ++s; break; } *endptr = s; return sign; } long int strtolong(const char * s, char ** endptr, int base) { int c; int sign = _space_sign(s, (const char**)&s); long result; if (s[0] == '0') { ++s; if ((s[1] | 0x20) == 'x') { if (base == 0 || base == 16) { ++s; base = 16; } } else if (base == 0) base = 8; } else if (base == 0) base = 10; result = 0; for (; c = tolower((unsigned char)*s), isdigit(c) || ('a' <= c && c <= 'v'); s++) { int d ; if( isdigit(c) ) d= c - '0' ; else d = c - 'a' + 10; if (d >= base) break; if (result > (LONG_MAX - d - sign) / base) { errno = ERANGE; result = sign ? LONG_MIN : LONG_MAX; } else { result = result * base + d; } } if (endptr != NULL) *endptr = (char*)s; if (sign != 0) result = -result; return result; } int main(void) { char s[128], *e; long n; int base; printf("何進数で変換しますか。"); scanf("%d", &base); printf("変換する数値を入力してください。"); scanf("%s", s); n = strtolong(s, &e, base); if (errno != ERANGE) { printf("変換数値＝%ld\n", n); if (*e != '\0') { printf("変換不可能部分＝%s\n", e); printf("%d文字目の\'%c\'が変換不可\n", e-s+1, *e); } } else if (n == LONG_MAX) printf("long値で表現できる値を上回りました。\n"); else if (n == LONG_MIN) printf("long値で表現できる値を下回りました。\n"); return 0; }
- ベストアンサー
- C・C++・C#
- 前回質問させて頂き、改善できるところはしました。
前回質問させて頂き、改善できるところはしました。 再度駄目な所をご指摘お願いします。 仕様は出来るだけ標準関数に近いものを自作したいと思っています。 //---------------------------- MyStrstr ----------------------------------// char *MyStrstr(const char *str1, const char *str2) { const char *p1 = str1; const char *p3 = str1; const char *p2 = str2; while(*p1 != *p2 && *p1 && *p2) { *p1++; *p3++; } while(*p1 == *p2){ *p1++; *p2++; } return (*p2 ? NULL : (char*)p3); } //------------------------------ 終了 ------------------------------------// //---------------------------- MyStrcat ----------------------------------// char *MyStrcat(char *str1, const char *str2) { char *p1 = str1; const char *p2 = str2; while(*p1 != NULL){ p1++; } if(*p2){ while(*p2 != NULL){ *p1 = *p2; p1++; p2++; } } if(*p2 == NULL){ *p1 = *p2; } return p1; } //------------------------------ 終了 ------------------------------------// //---------------------------- MyStrcmp ----------------------------------// int MyStrcmp(const char *str1, const char *str2) { const char *p1 = str1; const char *p2 = str2; while(*p1 != NULL || *p2 != NULL){ if(*p1 == *p2){ p1++; p2++; }else{ if(*p1 < *p2) return -1; if(*p1 > *p2) return 1; } } return 0; } //------------------------------ 終了 ------------------------------------// //----------------------------- MyMemcpy -----------------------------------// void *MyMemcpy(void *str1, void *str2, size_t n) { char *p1 = (char*)str1; char *p2 = (char*)str2; while(n--){ *p1 = *p2; p1++; p2++; } return str1; } //------------------------------ 終了 ------------------------------------// //---------------------------- MyStrcpy ----------------------------------// char *MyStrcpy(char *str1, const char *str2) { char *p1 = str1; const char *p2 = str2; while( *p2 != NULL){ *p1 = *p2; p1++; p2++; } if(*p2 == NULL){ *p1 = *p2; } return p1; } //------------------------------ 終了 ------------------------------------// //---------------------------- MyMe
- ベストアンサー
- C・C++・C#
- memcpy,memcmp,strcmp,strlen,strcat,
memcpy,memcmp,strcmp,strlen,strcat,strcpy,strstr,strchr 以上の関数を自作しました。 ひとつひとつを見たときに動作を確認したところうまく出来たのですが、この関数をプログラムに組み込んだところうまく動作しませんでした。 どこか間違っているところがあったら指摘して頂きたいと思います<m(__)m> ちなみに標準関数と全く同じものにしたいわけではなく、それを自分なりに考えて作りたいという趣旨ですので、ご理解ください。 char *MyMemcpy(char *str1, char *str2, size_t n) { char *p1 = str1; char *p2 = str2; while(n--){ *p1 = *p2; p1++; p2++; } return str1; } void *MyMemcmp(void *str1, void *str2) { char *p1 = (char*)str1; char *p2 = (char*)str2; int n = 0, k = 0; while( *p1 != '\0'){ *p1++; n++; } while( *p2 != '\0'){ *p2++; k++; } if(n > k){ return str1; }else if(n == k){ return 0; }else if(n < k){ return str2; } } char *MyStrcmp(char *str1, char *str2) { char *p1 = str1; char *p2 = str2; int n = 0, k = 0; while( *p1 != '\0'){ *p1++; n++; } while( *p2 != '\0'){ *p2++; k++; } if(n > k){ return str1; }else if(n == k){ return 0; }else if(n < k){ return str2; } } size_t MyStrlen(const char *str1) { char *p1 = (char*)str1; size_t len = 0; while(*p1 != NULL){ *p1++; len++; } return len; } char *MyStrcat(char *str1, const char *str2) { char *p1 = str1; char *p2 = (char*)str2; while(*p1 != NULL){ *p1++; } while(*p2 != NULL){ *p1 = *p2; *p1++; *p2++; } return str1; } char *MyStrcpy(char *str1, char *str2) { char *p1 = str1; char *p2 = str2; while( *p2 != NULL){ *p1 = *p2; *p1++; *p2++; } *p1 = '\0'; return str1; } char *MyStrstr(char *str1, char *str2) { char *p1 = str1; char *p2 = str2; while(*p1 != *p2) { if(*p1 == '\0'){ return 0; } *p1++; } return p1; } char *MyStrchr(const char *str1, char str2) { char *p1 = (char*)str1; while(*p1 != str2) { if(*p1 == '\0'){ return 0; } *p1++; } return p1; }
- ベストアンサー
- C・C++・C#
- Ｃ言語のクイックソートについて
下記のようなクイックソートのプログラムをコーディングしたのですが、比較回数・挿入回数・シフト回数をそれぞれ知りたいのですが、どこにそれぞれのカウンタを挿入すればよいでしょうか？ よろしくお願いします。 void quick(int a[],int left,int right) int i; int pl=left; int pr=right; int pivot; int tmp; pivot=a[(pl+pr)/2]; do{ while(a[pl]<pivot) { pl++; } while(a[pr]>pivot) { pr--; } if(pl<=pr) { swap(&a[pl],&a[pr]); pl++; pr--; } } while(pl<=pr); if(left<pr) { quick(a,left,pr); } if(pl<right) { quick(a,pl,right); } } void swap(int *x,int *y) { int temp; temp=*x; *x=*y; *y=temp; }
- 締切済み
- C・C++・C#
- c++のnew演算子をオーバーロードできるものの、
c++のnew演算子をオーバーロードできるものの、 delete演算子をオーバーロードできなくて悩んでいます。 コンパイルは通るのですが、ランタイム時に ペアとなるdeleteが呼ばれません。 inline void* operator new(size_t size, const char* filename , int line , const char* funcname ) { return my_local_malloc( size , filename , line , funcname ); } inline void operator delete(void* pMem, const char* filename , int line , const char* funcname ) { my_local_free( pMem , filename , line , funcname ); } deleteも確実にオーバーロードできる方法を ご存知のかた、お教え願います。
- 締切済み
- C・C++・C#
補足
アドレスの演算はしたことがありません。 #include <stdio.h> int main(void) { char work1[10]; char* a = work1; int work2[10]; int* b = work2; a = a + 1; b = b + 1; printf("a=%d", a); printf("b=%d", b); } を実行したところ、 a=-1073757615 b=-1073757676 となりました。たぶん目的とするプログラムになっていないような気がしますが。。