題目5: ハッシュ法

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

/* 文字列の最大長をあらかじめ決めておく */
#define M 32

/* 実験 1 で作成 */
int linear_search( char* data[], int n, char str[] ){
  /* 内容は省略 (実験のテキストを参照) */
}


/* データの入力と配列 data, 変数 n のセットアップ */
/* この関数の内容は少し難しいかもしれないため，
   ひとまずコピーして使うだけでよい           */
void setup( char* file_name, char*** data_p, int* n_p ){  
  FILE* fp;
  char** data;
  char line[M];
  int i, j, n;

  printf("データの読み込み開始 ...\n");

  /* データファイルをオープンし，その 1 行目からデータ数を読み取る．
     読み込んだ時点ではデータ数は文字列であるため，それを atoi 関数を
     使って int 型へ変換し，n へ代入する */
  fp = fopen(file_name, "r");
  if ( NULL == fp ){
    printf("データファイルをオープンできません\n");
    exit(1);
  }
  fgets(line, sizeof(line), fp);
  n = atoi(line);
  printf("データ数 = %d\n", n);

  /* データ数 n が確定したら，その長さのポインタ配列を確保する */
  data = (char**) calloc( n, sizeof(char*) );
  if ( NULL == data ){
    printf("メモリ確保に失敗しました\n");
    exit(1);
  }

  /* データファイルから 1 行ずつ（全部で n 行）読み込み，
     ポインタ配列の各要素にその分のメモリを確保しながら
     代入していく */
  for ( i = 0; i < n; i++ ){
    data[i] = (char*) calloc( M, sizeof(char) );
    if ( NULL == data[i] ){
      printf("メモリ確保に失敗しました\n");
      exit(1);
    }
    fgets( data[i], M, fp ); /* sizeof(data[i]) とはできない */
    j = strlen(data[i]) - 1;
    data[i][j] = '\0';       /* 末尾の改行文字を '\0' で上書き */
  }

  fclose(fp);
  printf(" ... データの読み込み完了\n\n");

  /* 上記の変数 data, n はそれぞれこの関数内だけで有効な変数であり，
     main 関数内での data, n とは別物である．
     その代わり，main 関数内での data と n の番地が引数 data_p, n_p 
     で与えられているので，最後に (この関数内での) data と n の内容を
     ポインタを使って反映させる */
  (*data_p) = data;
  (*n_p) = n;
}


int main(int argc, char* argv[]){

  char** data;
  int i, n, pos;  
  clock_t start, end;
  float time;

  if ( argc < 3 ){
    printf("コマンドライン引数にデータファイル名と探索対象文字列を指定して下さい\n");
    return 1;
  }
  printf("データファイル = %s\n", argv[1]);
  printf("探索する文字列 = \"%s\"\n", argv[2]);

  /* データのセットアップ：上の関数を次のように使って下さい */
  setup( argv[1], &data, &n );

  /* 時間測定の開始 */
  start = clock();
  /* 以下を少し書き換えて，同じ探索を (例えば) 1000 回繰り返すようにしなさい */
  /* ただし，見つかった・見つからなかったのメッセージは 1 回のみとする */
  pos = linear_search( data, n, argv[2] );
  if ( -1 == pos ){
     printf("\"%s\" は見つかりませんでした\n", argv[2]);
  }
  else{
     printf("\"%s\" は %d 番目に見つかりました\n", argv[2], pos+1 );
  }
  end = clock();

  time = (float)(end - start)/CLOCKS_PER_SEC;
  printf("探索 (1000回) にかかった時間 = %7.3f 秒\n", time);

  for ( i = 0; i < n; i++ ){
    free(data[i]);
  }
  free(data);

  return 0;
}

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

/* 文字列の最大長をあらかじめ決めておく */
#define M 32

struct hash_node {
  char string[M];
  struct hash_node* next;
};

/* ハッシュ関数：実験テキストを参照 */
int h ( char str[], int n ){
  /* 内容は省略 (実験のテキストを参照) */
}

/* ハッシュ探索：実験テキストを参照 */
int hash_search( struct hash_node* data[], int n, char str[] ){
  /* 内容は省略 (実験のテキストを参照) */
}

/* データの入力と配列 data のセットアップ */
/* この関数の内容は少し難しいかもしれないため，
   ひとまずコピーして使うだけでよい           */
void setup( char* file_name, struct hash_node** data, int n ){
  FILE* fp;
  char s[M];
  int i, j, num, index;
  struct hash_node* p;

  printf("データの読み込み開始 ...\n");

  fp = fopen(file_name, "r");
  if ( NULL == fp ){
    printf("データファイルをオープンできません\n");
    exit(1);
  }
  fgets(s, sizeof(s), fp);
  num = atoi(s);
  printf("データ数 = %d\n", num);
  
  for ( i = 0; i < num; i++ ){
    fgets( s, sizeof(s), fp );
    j = strlen(s) - 1;
    s[j] = '\0';
    
    /* 以下は実験テキストの内容の実装 */
    index = h( s, n );
    if ( NULL == data[index] ){
      data[index] = (struct hash_node*) malloc( sizeof(struct hash_node) );
      strcpy( data[index]->string, s );
      data[index]->next = NULL;
    }
    else{
      p = (struct hash_node*) malloc( sizeof(struct hash_node) );
      strcpy( p->string, s );
      p->next = data[index];
      data[index] = p;
    }
  }

  fclose(fp);
  printf(" ... データの読み込み完了\n\n");
}


int main(int argc, char* argv[]){
  struct hash_node** data;
  struct hash_node* p;
  int i, n, ans;
  clock_t start, end;
  float time;

  if ( argc < 4 ){
    printf("コマンドライン引数にデータファイル名と（ハッシュ用）ポインタ配列の長さ，探索対象文字列を指定して下さい\n");
    return 1;
  }
  n = atoi(argv[2]);

  printf("データファイル = %s\n", argv[1]);
  printf("ポインタ配列の長さ = %d\n", n);
  printf("探索する文字列 = \"%s\"\n", argv[3]);

  data = (struct hash_node**) calloc( n, sizeof(struct hash_node*) );
  if ( NULL == data ){
    printf("メモリ確保に失敗しました\n");
    return 1;
  }
  for ( i = 0; i < n; i++ ){
    data[i] = NULL;
  }

  setup( argv[1], data, n );

  /* 時間測定の開始 */
  start = clock();
  /* 以下を少し書き換えて，同じ探索を (例えば) 1000 回繰り返すようにしなさい */
  /* ただし，見つかった・見つからなかったのメッセージは 1 回のみとする */
  ans = hash_search( data, n, argv[3] );

  if ( -1 == ans ){
      printf("\"%s\" は見つかりませんでした\n", argv[3]);
  }
  else{
      printf("\"%s\" は見つかりました\n", argv[3]);
  }
  end = clock();

  time = (float)(end - start)/CLOCKS_PER_SEC;

  printf("探索 (1000回) にかかった時間 = %7.3f 秒\n", time);

  /* メモリの解放 */
  for ( i = 0; i < n; i++ ){
    while ( NULL != data[i] ){
      p = data[i];
      data[i] = data[i]->next;
      free(p);
    }
  }
  free(data);

  return 0;
}