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