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.             ++hash->data_n;
  144.             len = pos_now - pos_prev;
  145.             if (hash->len_max < len) {
  146.                 hash->len_max = len;
  147.             }
  148.             pos_prev = pos_now + 1;
  149.             if (c == EOF) {
  150.                 break;
  151.             }
  152.         }
  153.         pos_now++;
  154.     }
  155.     fclose(fp);
  156.     // HashTableサイズ決め (単語数の2倍以上 かつ 素数)
  157.     int n;
  158.     hash->tbl_size = hash->data_n * 2;
  159.     while (1) {
  160.         for (n = 2; (n * n < hash->tbl_size) && (hash->tbl_size % n); ++n);
  161.         if (hash->tbl_size % n) {   /* 素数 */
  162.             break;
  163.         }
  164.         ++hash->tbl_size;
  165.     }
  166.     // 確保
  167.     if (NULL == (hash->table = (char **) malloc(sizeof(char *) * hash->tbl_size))) {
  168.         return EC_MemAlloc;
  169.     }
  170.     memset(hash->table, 0x00, sizeof(char *) * hash->tbl_size);
  171.     if (NULL == (hash->ref_search_count = (int *) malloc(sizeof(int) * hash->tbl_size))) {
  172.         return EC_MemAlloc;
  173.     }
  174.     memset(hash->ref_search_count, 0x00, sizeof(int) * hash->tbl_size);
  175.  
  176.     return EC_Normal;
  177. }
  178.  
  179. void hash_delete(HASH_DATA * hash)
  180. {
  181.     int i;
  182.     if (hash) {
  183.         if (hash->table) {
  184.             for (i = 0; i < hash->tbl_size; i++) {
  185.                 if (hash->table[i]) {
  186.                     free(hash->table[i]);
  187.                     hash->table[i] = NULL;
  188.                 }
  189.             }
  190.             free(hash->table);
  191.             hash->table = NULL;
  192.         }
  193.         if (hash->ref_search_count) {
  194.             free(hash->ref_search_count);
  195.             hash->ref_search_count = NULL;
  196.         }
  197.         memset(hash, 0x00, sizeof(HASH_DATA));
  198.     }
  199. }
  200.  
  201. ERR_CODE hash_make(HASH_DATA * hash, char *filename)
  202. {
  203.     FILE *fp = NULL;
  204.     char *buf = NULL, *p;
  205.     int c;
  206.     ERR_CODE res = EC_Normal;
  207.  
  208.     // バッファ確保
  209.     if (NULL == (buf = (char *) malloc(sizeof(char) * (hash->len_max + 2)))) {
  210.         res = EC_MemAlloc;
  211.         goto END_hash_make;
  212.     }
  213.     // 読み込み ＆ ハッシュに追加
  214.     fp = fopen(filename, "r");
  215.     p = &buf[0];
  216.     while (c = fgetc(fp)) {
  217.         if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == EOF) {
  218.             *p = '\0';
  219.             p = &buf[0];
  220.             if (strlen(buf)) {
  221.                 if (EC_Normal != (res = hash_add(hash, &buf[0]))) {
  222.                     goto END_hash_make;
  223.                 }
  224.             }
  225.             if (c == EOF) {
  226.                 break;
  227.             }
  228.         } else {
  229.             *p++ = (char) c;
  230.         }
  231.     }
  232.     // 終了
  233.     res = EC_Normal;
  234.   END_hash_make:
  235.     if (buf) {
  236.         free(buf);
  237.         buf = NULL;
  238.     }
  239.     if (fp) {
  240.         fclose(fp);
  241.         fp = NULL;
  242.     }
  243.  
  244.     return res;
  245. }
  246.  
  247. ERR_CODE hash_add(HASH_DATA * hash, char *str)
  248. {
  249.     int index;                  // 追加先
  250.     int next_step;              // 衝突時追加先探索ステップ
  251.     int limit;                  // 追加先が見つからない場合への備え
  252.  
  253.     // hash値取得
  254.     index = hashfunc_h(str, hash);
  255.     hash->ref_search_count[index]++;    // 探索参照カウンタ
  256.     // 衝突
  257.     if (hash->table[index]) {
  258.         // 同一文字列
  259.         if (0 == strcmp_ignore(hash->table[index], str)) {
  260.             if (hash->mode == AMD_MUSI) {
  261.                 return EC_Normal;   // 追加しない
  262.             }
  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.             }
  272.         }
  273.         // 追加先をみつけられなかったら、エラー
  274.         if (limit >= hash->tbl_size) {
  275.             return EC_CantAddHash;
  276.         }
  277.     }
  278.     // 追加
  279.     if (NULL == (hash->table[index] = (char *) malloc(sizeof(char) * strlen(str) + 1))) {
  280.         return EC_MemAlloc;
  281.     }
  282.     strcpy(hash->table[index], str);
  283.  
  284.     // end
  285.     return EC_Normal;
  286. }
  287.  
  288. void hash_show(HASH_DATA * hash, char *src_filename)
  289. {
  290.     int i;
  291.     char b[256];
  292.     int keta_cell;              // セル番号桁数
  293.     int keta_ref;               // 参照回数桁数
  294.     int m;
  295.  
  296.     // 桁数計算
  297.     keta_cell = sprintf(b, "%d", hash->tbl_size);
  298.     for (i = m = 0; i < hash->tbl_size; i++) {
  299.         if (m > hash->ref_search_count[i]) {
  300.             m = hash->ref_search_count[i];
  301.         }
  302.     }
  303.     keta_ref = sprintf(b, "%d", m);
  304.  
  305.     // 出力
  306.     fprintf(stdout, "・入力ファイル     : %s\n", src_filename);
  307.     fprintf(stdout, "・最大文字長       : %d\n", hash->len_max);
  308.     fprintf(stdout, "・文字列数         : %d個\n", hash->data_n);
  309.     fprintf(stdout, "・Hashテーブル数   : %d個\n", hash->tbl_size);
  310.     fprintf(stdout, "・Hash追加モード   : 同一文字列を、%s\n", getStr_ADD_MODE(hash->mode));
  311.     fprintf(stdout, "・当結果出力モード : 空のテーブル要素を出力%s\n", hash->flag_res_out ? "する" : "しない");
  312.     for (i = 0; i < hash->tbl_size; i++) {
  313.         if (hash->flag_res_out || hash->table[i]) {
  314.             fprintf(stdout, "[%0*d] 参照回数 = %0*d, 格納文字 = [%s]\n", keta_cell, i, keta_ref, hash->ref_search_count[i]
  315.                     , hash->table[i] ? hash->table[i] : "");
  316.         }
  317.     }
  318. }
  319.  
  320. /*
  321.  *      hash functions
  322.  */
  323.  
  324. int hashfunc_h(char *s, HASH_DATA * hash)
  325. {
  326.     int r = 0;
  327.     while (*s) {
  328.         *s = tolower(*s);
  329.         if ('a' <= *s && *s <= 'z') {
  330.             r = r * 26 + (*s - 'a');
  331.             r %= hash->tbl_size;
  332.         }
  333.         ++s;
  334.     }
  335.     return r;
  336. }
  337.  
  338. int hashfunc_p(char *s, HASH_DATA * hash)
  339. {
  340.     int r = 0;
  341.     int m = 0;
  342.  
  343.     while (*s) {
  344.         *s = tolower(*s);
  345.         if ('a' <= *s && *s <= 'z') {
  346.             r *= 26;
  347.             m = m * 26 + (*s - 'a');
  348.             r += m / hash->tbl_size;
  349.             m %= hash->tbl_size;
  350.             r %= hash->tbl_size;
  351.         }
  352.         ++s;
  353.     }
  354.     return r;
  355. }
  356.  
  357. // End of cs_161_165.c
Runtime error #stdin #stdout 0.01s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/q13mMZ
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!