落書きノート

ふと自分が気になった事を書いてます

C言語でアルゴリズムとデータ構造

今日はプログラミングが捗りました。Go言語とCrystal言語。ところで今日の最後にこの本の問題を解いてます。久しぶりにやりました。二分探索法と線形探索法を使った問題です。世界で闘うプログラミング力を鍛える本、いつやるんでしょうかね。自分でも思います。

新・明解C言語によるアルゴリズムとデータ構造

新・明解C言語によるアルゴリズムとデータ構造

// q3_8

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

int int_cmpr(const int *a, const int *b) {
  if(*a < *b)
    return -1;
  else if(*a > *b)
    return 1;
  else
    return 0;
}

void *binsearch(const void *key, const void *base, size_t nmemb,
                size_t size, int (*compar)(const void *, const void *)) {
  int pl = 0;
  int pr = nmemb - 1;
  int pc;

  do {
    pc = (pl + pr) / 2;
    if(compar(base + pc * size, key) == 0)
      return (void *)base + pc * size;
    else if(compar(base + pc * size, key) == 1)
      pl = pc + 1;
    else
      pr = pc - 1;
  } while (pl <= pr);

  return NULL;
}

int main(void) {
  int i, nx, ky;
  int *x, *p;

  puts("bsearch関数による探索");
  printf("要素数 : ");
  scanf("%d", &nx);
  x = calloc(nx, sizeof(int));
  printf("降順に入力してください。\n");
  printf("x[0] : ");
  scanf("%d", &x[0]);
  
  for(i = 1; i < nx; i++) {
    do {
      printf("x[%d] : ", i);
      scanf("%d", &x[i]);
    } while (x[i] > x[i - 1]);
  }
  
  printf("探す値 : ");
  scanf("%d", &ky);
  
  p = binsearch(&ky,
                x,
                nx,
                sizeof(int),
                (int (*)(const void *, const void *))int_cmpr
                );
  
  if(p == NULL)
    puts("探索に失敗しました。");
  else
    printf("%dはx[%d]にあります。\n", ky, (int)(p - x));
  free(x);
  
  return 0;
}

// q3_9

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

int int_cmpr(const int *a, const int *b) {
  if(*a < *b)
    return -1;
  else if(*a > *b)
    return 1;
  else
    return 0;
}

int *search(int *x, int *p, int n) {
  int i = n - 1;
  int key = x[n];
  while(1) {
    if(i == -1)
      return p;
    if(x[i] == key)
      return x + i;
    i--;
  }
}

void *bsearchx(const void *key, const void *base, size_t nmemb,
                size_t size, int (*compar)(const void *, const void *)) {
  int pl = 0;
  int pr = nmemb - 1;
  int pc;
  
  do {
    pc = (pl + pr) / 2;
    if(compar(base + pc * size, key) == 0)
      return (void *)base + pc * size;
    else if(compar(base + pc * size, key) == 1)
      pl = pc + 1;
    else
      pr = pc - 1;
  } while (pl <= pr);
  
  return NULL;
}

int main(void) {
  int i, nx, ky;
  int *x, *p;

  puts("bsearch関数による探索");
  printf("要素数 : ");
  scanf("%d", &nx);
  x = calloc(nx, sizeof(int));
  printf("降順に入力してください。\n");
  printf("x[0] : ");
  scanf("%d", &x[0]);
  
  for(i = 1; i < nx; i++) {
    do {
      printf("x[%d] : ", i);
      scanf("%d", &x[i]);
    } while (x[i] > x[i - 1]);
  }
  
  printf("探す値 : ");
  scanf("%d", &ky);
  
  p = bsearchx(&ky,
                x,
                nx,
                sizeof(int),
                (int (*)(const void *, const void *))int_cmpr
                );
  
  if(p == NULL)
    puts("探索に失敗しました。");
  else {
    p = search(x, p, (int)(p - x));
    printf("%dはx[%d]にあります。\n", ky, (int)(p - x));
  }
  free(x);
  
  return 0;
}