プログラマ専用SNS ミクプラ

コード:

/*hash_open.h*/

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

typedef struct cell{     //バケットの構造体
  int key;               //キー（整数値）
}CELL;
CELL*Htable;             //ハッシュ表（開放番地法、連鎖法）

#define INTV -1          //初期化定数
#define FLS  -1          //関数戻り値（エラー値）

#include"Hash_funcs.c"      //ハッシュ関数
#include"Hash.c"            //ハッシュ表関連の関数
#include"Hash_open.c"          //開放番地法操作関数

#define STORE rc = store(Htable, HSIZE, DVS, inv)     //キーの格納
#define CHECK  rc = check_Htable(Htable, HSIZE)        //ハッシュ表が初期化されているか
#define DELHASH deallocate_Htable(Htable)              //ハッシュ表の削除

コード:

/* Hash.c */

//入力値：hsize    ハッシュ表の大きさ（番地空間）
//戻り値：Htable   ハッシュ表の先頭番地

CELL *allocate_Htable(int hsize){
  CELL *Htable;
  Htable = (CELL*)malloc(sizeof(CELL)*hsize);   //ハッシュ表を割り付け
  if(Htable == NULL){
    printf("空き記憶域がありません。\n");
    exit(1);
  }
  return Htable;
}


//入力値： hsize    ハッシュ表の大きさ（番地空間）
//　　　　 **Htable ハッシュ表の先頭番地
//戻り値：　　　　　　無し
void deallocate_Htable(CELL *Htable){
  free(Htable);
  return;
}

コード:

/*Hash_funcs.c */

// 入力引数             key :  キー
//                  m od :  除数
// 戻り値              hv :   ハッシュ値
int hash(int key, int mod){   // 剰余法
  int hv;                   // 剰余
  hv = key % mod;               // 剰余をhash値とする
  return hv;
}



//  入力値 :       adrs     (当該)バケット番号
//               size    hash表の大きさ
//               cons     定数(増分)
//  戻り値 :       adrs     バケット番号
int prob_lin(int size, int cons, int adrs){ // 線形探査関数
  cons = 2999;
  adrs += cons;
  if (size <= adrs)               // アドレスが番地空間を越えた
    adrs -= size;
  return adrs;
};

コード:

/* Hash_main.c */

#define HSIZE 1000000 // ハッシュ表の大きさ(100万)
#define DVS 999983 // 除数(HSIZEを超えない最大の素数)
#define CONSL 19 // 線形探査法の定数

#define CONSR1 99989 // HSIZE / 2 < 二重分散法1の定数
#define CONSR2 199999 // 二重分散法2の定数 < 2 * HSIZE

#include "hash_open.h" // 開放番地法

#include "utilities.c" // ユーティリティ関数
#include "Hash_message.c" // メッセージ出力関数
#define NARG 2 // コマンドライン引数
#define FMTF "%d\n" // ファイル入力
#define NFL3

int COUNT;

int main(void) {
  FILE *fin ;
  int cmdnum , // コマンド番号
      rc , // 関数の戻り値
      i = 0 ,
      inv , // 入力値(集合の要素)
      oun = HSIZE / 10 ; // 処理レコード数出力単位
      double microsec;
      clock_t start, end;
      float o = 0.0;

  fin =open_file("integer1MR.dat", "r" ) ; // 入力ファイル(整数の集合)

  Htable = allocate_Htable(HSIZE) ; // ハッシュ表の動的割付け
  init_tbl(Htable, HSIZE) ; // ハッシュ表初期化


    printf("要素数　  占有率　   総探査回数　　格納時間（秒）\n");
    while (fscanf(fin, FMTF, &inv) != EOF) { // キーの読込み
    start = clock();
    STORE ; // キーの格納
    end = clock();
    microsec = (double)(end - start) / CLOCKS_PER_SEC;
    if (rc == FLS) printf( "%d は格納できません\n" , inv);
    if (++i % oun == 0) {   
    o = i / 1000000;
       printf(" %d   %f      %d         %f      \n", i, o, COUNT, microsec);
     }
  }


  return 0;
}

コード:

/*Hash_open.c*/

extern int COUNT;

//   *table : hash表
//    size :  hash表の大きさ
void init_tbl(CELL *Htable, int hsize){  //ハッシュ表を初期化
  int i;
  for(i = 0; i < hsize; i++) {
    Htable[i].key = INTV ;
  }
  return ;
}

コード:

//   入力値 :        *table      hash表
//                  size      hash表の大きさ
//                  cons       除数
//                  inv        入 力値
//   戻り値 :                    バケット番号、-1(無い場合)
int store(CELL *table, int size, int cons, int inv) {
  int adr ,                               // hash表の番地
    i=1;                               // 探査回数
  COUNT++;                               // 総探査回数
  adr = hash(inv, cons) ;                  // hash値を計算
  while(i <= size){
    if (table[adr].key == INTV){          // adrsi番地は空いている
      COUNT++;
      table[adr].key = inv;        // adrs番地に格納
      return adr;
    }
    else if (table[adr].key != INTV){// adrs番地は空いていない
      COUNT++;
      if (table[adr].key == inv)        // 入力値は既格納
	return FLS;
      adr = prob_lin(size, CONSL, adr);      // 線形探査法による次の番地
      ++i;
    }
  }
  return FLS;
}

コード:

/*utilities.c*/

 // 入力引数 fname : ファイル名
// mode : ファイルモード
FILE *open_file(char *fname, char *mode) {
FILE *fp ;
if ((fp = fopen(fname, mode)) == 0) { //ファイルのオープン
printf("%s がオープンできません\n", fname) ;
exit(0) ;
}
return fp ;
}