fork download
copy 
  1. // cs_161_165.c
  2. /*
  3.     C/C++の宿題片付けます 161代目
  4.     http://t...content-available-to-author-only...h.net/test/read.cgi/tech/1354070278/165
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include <ctype.h>
  11.  
  12. /* 共通エラーコード */
  13. typedef enum {
  14.     EC_Normal,                  // 正常終了
  15.     EC_FileOpen,                // ファイルオープン失敗
  16.     EC_MemAlloc,                // メモリ確保失敗
  17.     EC_CantAddHash,             // Hashテーブル記録先が見つけられなかった(衝突時のハッシュ関数が甘い)
  18. } ERR_CODE;
  19. char *getStr_ERR_CODE(ERR_CODE ec)
  20. {
  21.     switch (ec) {
  22.     case EC_Normal      :return "正常終了";
  23.     case EC_FileOpen    :return "ファイルオープン失敗";
  24.     case EC_MemAlloc    :return "メモリ確保失敗";
  25.     case EC_CantAddHash :return "Hashテーブル記録先が見つけられなかった(衝突時のハッシュ関数が甘い)";
  26.     }
  27.     return "";
  28. }
  29.  
  30. /* 重複文字列があったときに、追加するか無視するか */
  31. typedef enum {
  32.     AMD_ADD,                    // 追加する
  33.     AMD_MUSI,                   // 追加しない
  34. } ADD_MODE;
  35. char *getStr_ADD_MODE(ADD_MODE code)
  36. {
  37.     switch (code) {
  38.     case AMD_ADD    :return "追加する";
  39.     case AMD_MUSI   :return "追加しない";
  40.     }
  41.     return "";
  42. }
  43.  
  44. /* data */
  45. typedef struct {
  46.     ADD_MODE mode;              // (手動設定)重複時の動作
  47.     int flag_res_out;           // (手動設定)結果出力時、空のテーブル要素を出力するかどうなのか(1 or 0)
  48.     int data_n;                 // 文字列数
  49.     int len_max;                // 文字列最大長
  50.     int tbl_size;               // ハッシュテーブルサイズ
  51.     char **table;               // ハッシュテーブル
  52.     int *ref_search_count;      // table[] 探索参照カウンタ
  53. } HASH_DATA;
  54.  
  55. /* prototype */
  56. extern int hashfunc_h(char *s, HASH_DATA * hash);
  57. extern int hashfunc_p(char *s, HASH_DATA * hash);
  58. extern ERR_CODE hash_creat(HASH_DATA * hash, char *filename);
  59. extern ERR_CODE hash_make(HASH_DATA * hash, char *filename);
  60. extern ERR_CODE hash_add(HASH_DATA * hash, char *str);
  61. extern void hash_show(HASH_DATA * hash, char *src_filename);
  62. extern void hash_delete(HASH_DATA * hash);
  63. extern int strcmp_ignore(char *s1, char *s2);
  64.  
  65. /*
  66.  *      main
  67.  */
  68. int main(int argc, char *argv[])
  69. {
  70.     int res = (int) EC_Normal;
  71.     HASH_DATA hd;
  72.  
  73.     // 初期化
  74.     memset(&hd, 0x00, sizeof(HASH_DATA));
  75.     hd.mode = AMD_MUSI;         // (手動設定)重複時の動作
  76.     hd.flag_res_out = 1;        // (手動設定)結果出力時、空のテーブル要素を出力するかどうなのか(1 or 0)
  77.     if (EC_Normal != (res = hash_creat(&hd, argv[1]))) {
  78.         goto END_main;
  79.     }
  80.     // ハッシュ作成
  81.     if (EC_Normal != (res = hash_make(&hd, argv[1]))) {
  82.         goto END_main;
  83.     }
  84.     // 結果表示
  85.     hash_show(&hd, argv[1]);
  86.     // 終了
  87.     res = (int) EC_Normal;
  88.   END_main:
  89.     hash_delete(&hd);
  90.     if (res != EC_Normal) {
  91.         fprintf(stderr, "Err :%s\n", getStr_ERR_CODE(res));
  92.     }
  93.     return res;
  94. }
  95.  
  96. /* 大小文字区別なし文字列比較 (負:s1<s2, 正:s1>s2, 0:s1==s2)
  97.  *  ※ s1="321", s2="321000"のときは、s1 < s2
  98.  */
  99. int strcmp_ignore(char *s1, char *s2)
  100. {
  101.     int cmp;
  102.     while (1) {
  103.         cmp = tolower((int) *s1) - tolower((int) *s2);
  104.         if (cmp) {
  105.             break;
  106.         }
  107.         if (*s1 == '\0' && *s2 == '\0') {
  108.             break;
  109.         }
  110.         s1++;
  111.         s2++;
  112.     }
  113.  
  114.     return cmp;
  115. }
  116.  
  117. /*
  118.  *      HASH_DATA operation
  119.  */
  120. // ファイル filename を解析して、HASH_DATAを初期化
  121.  
  122. ERR_CODE hash_creat(HASH_DATA * hash, char *filename)
  123. {
  124.     FILE *fp;
  125.     int len, pos_now, pos_prev;
  126.     int c;
  127.  
  128.     // 単語数カウント
  129.     if (NULL == (fp = fopen(filename, "r"))) {
  130.         return EC_FileOpen;
  131.     }
  132.     pos_now = pos_prev = 0;
  133.     while (c = fgetc(fp)) {
  134.         if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == EOF) {
  135.             ++hash->data_n;
  136.             len = pos_now - pos_prev;
  137.             if (hash->len_max < len) {
  138.                 hash->len_max = len;
  139.             }
  140.             pos_prev = pos_now + 1;
  141.             if (c == EOF) {
  142.                 break;
  143.             }
  144.         }
  145.         pos_now++;
  146.     }
  147.     fclose(fp);
  148.     // HashTableサイズ決め (単語数の2倍以上 かつ 素数)
  149.     int n;
  150.     hash->tbl_size = hash->data_n * 2;
  151.     while (1) {
  152.         for (n = 2; (n * n < hash->tbl_size) && (hash->tbl_size % n); ++n);
  153.         if (hash->tbl_size % n) {   /* 素数 */
  154.             break;
  155.         }
  156.         ++hash->tbl_size;
  157.     }
  158.     // 確保
  159.     if (NULL == (hash->table = (char **) malloc(sizeof(char *) * hash->tbl_size))) {
  160.         return EC_MemAlloc;
  161.     }
  162.     memset(hash->table, 0x00, sizeof(char *) * hash->tbl_size);
  163.     if (NULL == (hash->ref_search_count = (int *) malloc(sizeof(int) * hash->tbl_size))) {
  164.         return EC_MemAlloc;
  165.     }
  166.     memset(hash->ref_search_count, 0x00, sizeof(int) * hash->tbl_size);
  167.  
  168.     return EC_Normal;
  169. }
  170.  
  171. void hash_delete(HASH_DATA * hash)
  172. {
  173.     int i;
  174.     if (hash) {
  175.         if (hash->table) {
  176.             for (i = 0; i < hash->tbl_size; i++) {
  177.                 if (hash->table[i]) {
  178.                     free(hash->table[i]);
  179.                     hash->table[i] = NULL;
  180.                 }
  181.             }
  182.             free(hash->table);
  183.             hash->table = NULL;
  184.         }
  185.         if (hash->ref_search_count) {
  186.             free(hash->ref_search_count);
  187.             hash->ref_search_count = NULL;
  188.         }
  189.         memset(hash, 0x00, sizeof(HASH_DATA));
  190.     }
  191. }
  192.  
  193. ERR_CODE hash_make(HASH_DATA * hash, char *filename)
  194. {
  195.     FILE *fp = NULL;
  196.     char *buf = NULL, *p;
  197.     int c;
  198.     ERR_CODE res = EC_Normal;
  199.  
  200.     // バッファ確保
  201.     if (NULL == (buf = (char *) malloc(sizeof(char) * (hash->len_max + 2)))) {
  202.         res = EC_MemAlloc;
  203.         goto END_hash_make;
  204.     }
  205.     // 読み込み ＆ ハッシュに追加
  206.     fp = fopen(filename, "r");
  207.     p = &buf[0];
  208.     while (c = fgetc(fp)) {
  209.         if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == EOF) {
  210.             *p = '\0';
  211.             p = &buf[0];
  212.             if (strlen(buf)) {
  213.                 if (EC_Normal != (res = hash_add(hash, &buf[0]))) {
  214.                     goto END_hash_make;
  215.                 }
  216.             }
  217.             if (c == EOF) {
  218.                 break;
  219.             }
  220.         } else {
  221.             *p++ = (char) c;
  222.         }
  223.     }
  224.     // 終了
  225.     res = EC_Normal;
  226.   END_hash_make:
  227.     if (buf) {
  228.         free(buf);
  229.         buf = NULL;
  230.     }
  231.     if (fp) {
  232.         fclose(fp);
  233.         fp = NULL;
  234.     }
  235.  
  236.     return res;
  237. }
  238.  
  239. ERR_CODE hash_add(HASH_DATA * hash, char *str)
  240. {
  241.     int index;                  // 記録先
  242.     int next_step;              // 衝突時書き込み先探索ステップ
  243.     int limit;                  // 記録先が見つからない場合への備え
  244.  
  245.     // hash値取得
  246.     index = hashfunc_h(str, hash);
  247.     hash->ref_search_count[index]++;    // 探索参照カウンタ
  248.     // 衝突
  249.     if (hash->table[index]) {
  250.         // 同一文字列
  251.         if (0 == strcmp_ignore(hash->table[index], str)) {
  252.             if (hash->mode == AMD_MUSI) {
  253.                 return EC_Normal;
  254.             }
  255.         }
  256.         // 衝突後 入れ先探索
  257.         next_step = hashfunc_p(str, hash);
  258.         for (limit = 0; limit < hash->tbl_size; limit++) {
  259.             index = (index + next_step) % hash->tbl_size;
  260.             hash->ref_search_count[index]++;    // 探索参照カウンタ
  261.             if (NULL == hash->table[index]) {
  262.                 break;
  263.             }
  264.         }
  265.         if (limit >= hash->tbl_size) {
  266.             return EC_CantAddHash;
  267.         }
  268.     }
  269.     // 追加
  270.     if (NULL == (hash->table[index] = (char *) malloc(sizeof(char) * strlen(str) + 1))) {
  271.         return EC_MemAlloc;
  272.     }
  273.     strcpy(hash->table[index], str);
  274.  
  275.     // end
  276.     return EC_Normal;
  277. }
  278.  
  279. void hash_show(HASH_DATA * hash, char *src_filename)
  280. {
  281.     int i;
  282.     char b[256];
  283.     int keta_cell;              // セル番号桁数
  284.     int keta_ref;               // 参照回数桁数
  285.     int m;
  286.  
  287.     // 桁数計算
  288.     keta_cell = sprintf(b, "%d", hash->tbl_size);
  289.     for (i = m = 0; i < hash->tbl_size; i++) {
  290.         if (m > hash->ref_search_count[i]) {
  291.             m = hash->ref_search_count[i];
  292.         }
  293.     }
  294.     keta_ref = sprintf(b, "%d", m);
  295.  
  296.     // 出力
  297.     fprintf(stdout, "・入力ファイル     : %s\n", src_filename);
  298.     fprintf(stdout, "・最大文字列長     : %d\n", hash->len_max);
  299.     fprintf(stdout, "・文字列数         : %d個\n", hash->data_n);
  300.     fprintf(stdout, "・Hashテーブル数   : %d個\n", hash->tbl_size);
  301.     fprintf(stdout, "・Hash追加モード   : 同一文字列を、%s\n", getStr_ADD_MODE(hash->mode));
  302.     fprintf(stdout, "・当結果出力モード : 空のテーブル要素を出力%s\n", hash->flag_res_out ? "する" : "しない");
  303.     for (i = 0; i < hash->tbl_size; i++) {
  304.         if (hash->flag_res_out || hash->table[i]) {
  305.             fprintf(stdout, "[%0*d] 参照回数 = %0*d, 格納文字 = [%s]\n", keta_cell, i, keta_ref, hash->ref_search_count[i]
  306.                     , hash->table[i] ? hash->table[i] : "");
  307.         }
  308.     }
  309. }
  310.  
  311. /*
  312.  *      hash functions
  313.  */
  314.  
  315. int hashfunc_h(char *s, HASH_DATA * hash)
  316. {
  317.     int r = 0;
  318.     while (*s) {
  319.         *s = tolower(*s);
  320.         if ('a' <= *s && *s <= 'z') {
  321.             r = r * 26 + (*s - 'a');
  322.             r %= hash->tbl_size;
  323.         }
  324.         ++s;
  325.     }
  326.     return r;
  327. }
  328.  
  329. int hashfunc_p(char *s, HASH_DATA * hash)
  330. {
  331.     return 1;
  332. }
  333.  
  334. // End of cs_161_165.c
  335.  
Runtime error #stdin #stdout 0.01s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/W7QL8f
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!