这是为什么呢传递if语句？ [英] Why is this passing the if statement?
问题描述
您好有人可以帮助我找到什么原因造成的问题？出于某种原因，find_hash功能是给我的问题。应该失败的如果（表 - ＆GT; buckets_array [I]！= NULL）{和如果（表 - ＆GT; buckets_array [I] ！='\\ 0'）{，但它是不是和它去查了下，给了我一个分段错误。有什么可以引起第一2，如果声明传递，因为我最初将其设置为表 - > buckets_array [我] = NULL
编辑：谢谢 wildplasser 我想出了我的find_hash功能的更好的解决方案。
如果（表 - ＆GT; buckets_array [表 - ＆GT; hash_func（密钥）] == NULL）{
返回NULL;
}其他{
返回表 - ＆GT; buckets_array [表 - ＆GT; hash_func（键）] - GT;数据;
}
感谢你们每一个人的帮助。
/ * * hash.h /
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;typedef结构data_中的数据{
字符*键;
void *的数据;
结构data_中的数据*接下来的;
} data_el;typedef结构hash_table_ {
无效**秩序;
INT * number_next_calls;
INT * number_buckets;
INT * buckets_size;
INT *最糟糕的;
INT *总;
浮*平均水平;
INT（* hash_func）（字符*）;
INT（* comp_func）（void *的，无效*）;
data_el ** buckets_array;
} hash_table，* Phash_table;Phash_table new_hash（INT大小，INT（* hash_func）（字符*），INT（* cmp_func）（void *的，无效*））;
无效free_hash（Phash_table表）;
无效insert_hash（Phash_table表，字符*键，无效*数据）;
无效* find_hash（Phash_table表，字符*键）;
无效stat_hash（Phash_table表，为int *总，为int *最大，浮*平均值）;
无效* start_hash_walk（Phash_table表）;
无效* next_hash_walk（Phash_table表）;静态无效lower_case_word（字符* W）;/*hash.c*/
＃包括hash.hPhash_table new_hash（INT大小，INT（* hash_func）（字符*），INT（* cmp_func）（void *的，无效*））{
INT I; Phash_table table_p;
hash_table hash_table; table_p =（Phash_table）的malloc（sizeof的（hash_table））; / *设置函数指针* /
table_p-＆GT; hash_func = hash_func;
table_p-＆GT; comp_func = cmp_func; / *创建桶数组* /
table_p-＆GT; buckets_array =（data_el **）的malloc（sizeof的（data_el *）*（大小+ 1））;
table_p-＆GT; buckets_size =为（int *）malloc的（的sizeof（int）的*（大小+ 1））; / *设置顺序排列* /
table_p-＆GT;为了= NULL; / *设置inital性条件* /
table_p-＆GT;最差的=（INT *）malloc的（的sizeof（INT））;
table_p-个总=（INT *）malloc的（的sizeof（INT））;
table_p-＆GT;平均=（浮点*）malloc的（的sizeof（浮动））;
table_p-＆GT; number_buckets =（INT *）malloc的（的sizeof（INT））; *（table_p-＆GT; number_buckets）=大小; 对于（i = 0; I＆LT;大小;我++）{
table_p-＆GT; buckets_array [我] = NULL;
}
返回table_p;
}无效free_hash（Phash_table表）{ INT I;
I = 0;
data_el * CUR;
data_el * preV; / *自由秩序数组* /
如果（表 - ＆GT;！为了= NULL）{
免费（表 - ＆GT;的顺序）;
} / *免费桶阵列和阵列buckets_size * /
如果（表 - ＆GT; buckets_array！= NULL）{
对于（i = 0; I＆LT; *（表 - ＆GT; number_buckets）;我++）{
如果（表 - ＆GT; buckets_array [I]！= NULL）{ / * Travers的链表，并释放它* /
CUR =表 - ＆GT; buckets_array [I]
preV = CUR; 而（（CUR =当前＆GT;！下一个）= NULL）{
免费（preV）;
preV = CUR;
}
/ *免费的最后一个节点* /
免费（现）;
}
}
}
自由（表）;
}无效insert_hash（Phash_table表，字符*键，无效*数据）{
INT指数;
data_el * P * CUR; 指数=表 - ＆GT; hash_func（密钥）; / *头*插入/
如果（表 - ＆GT; buckets_array [指数] == NULL）{
表 - ＆GT; buckets_array [指数] =（data_el *）malloc的（的sizeof（data_el））;
表 - ＆GT; buckets_array [指数] - ＆GT;数据=数据;
表 - ＆GT; buckets_array [指数] - ＆gt;接下来= NULL;
表 - ＆GT; buckets_array [指数] - ＆GT;关键=键;
}其他{
CUR =表 - ＆GT; buckets_array [指数]
P =（data_el *）malloc的（的sizeof（data_el））;
P-＆GT;关键=键;
P-＆GT;数据=数据;
P-＆gt;接下来= CUR;
CUR = P;
表 - ＆GT; buckets_array [指数] = CUR;
} / *更新合计* /
*表 - 个总+ = 1; / *更新桶大小* /
（表 - ＆GT; buckets_size [指数]）+ = 1; / *更新最坏情况* /
如果（（表 - ＆GT; buckets_size [指数]）GT; *（表 - ＆GT;最差））{
*（表 - ＆GT;最差）=（表 - ＆GT; buckets_size [指数]）;
}其他{
*（表 - ＆GT;最差）+ = 1;
} / *更新平均* /
INT temp_total，temp_buckets; temp_total = *（表 - 个总）;
temp_buckets = *（＆表 - GT; number_buckets）;
*（表 - ＆GT;平均）=（浮点）temp_total /（浮点）temp_buckets;
}无效* find_hash（Phash_table表，字符*键）{
INT I;
I = 0; 而（1）{
如果（表 - ＆GT; buckets_array [I] =='\\ 0'）{
的printf（阵列结束）;
打破;
}
如果（表 - ＆GT; buckets_array [I]！= NULL）{
的printf（％检查）;
如果（表 - ＆GT;！buckets_array [I] ='\\ 0'）{
如果（表 - ＆GT; buckets_array [I] - ＆GT;！键= NULL）{
如果（的strcmp（表 - ＆GT; buckets_array [Ⅰ] - GT;键，键）== 0）{
的printf（找到它\\ n）;
打破;
}
}
}
}
我++;
} 如果（表 - ＆GT; buckets_array [I]！= NULL）{
输出（新asdasd％d个，*（为（int *）表 - ＆GT; buckets_array [Ⅰ] - GT;数据））;
返回表 - ＆GT; buckets_array [Ⅰ] - GT;数据;
}其他{
返回NULL;
}
}无效stat_hash（Phash_table表，为int *总，为int *最大，浮*平均）{
总=（表 - 个总）;
最大=（表 - ＆GT;最差）;
平均=（表 - ＆GT;平均）;
}无效* start_hash_walk（Phash_table表）{
INT I，max_buckets，一步，next_calls;
步骤= 0;
data_el * CUR;
next_calls = 0; max_buckets = *（表 - ＆GT; number_buckets）;
表 - ＆GT;为了=（无效**）的malloc（sizeof的（无效*）*（*（表 - 个总）））; / *设置number_next_calls为0 * /
表 - ＆GT; number_next_calls =安培; next_calls;
*（表 - ＆GT; number_next_calls）= 0; / *遍历ADT，并把所有数据放入指令序列* /
对于（i = 0; I＆LT; max_buckets;我++）{
如果（表 - ＆GT; buckets_array [I]！= NULL）{
CUR =表 - ＆GT; buckets_array [I]
而（现）{
表 - ＆GT;为了[步骤] =电流＆GT;数据;
步++;
CUR =当前＆gt;接下来，
}
}
} / *泡泡短* /
INT J，K; 为（J = 0; J＆≤（步骤 - 1）; J ++）{
为（K = 0; K＆≤（步骤 - 第（j + 1））; K ++）{
如果（（表 - ＆GT; comp_func）（表 - ＆GT;为了[J]，表 - ＆GT;为了[J + 1]）小于5）{
void *的温度; TEMP =表 - ＆GT;为了[J]。
表 - ＆GT;为了[J] =表 - ＆GT;为了[J + 1];
表 - ＆GT;为了[J + 1] =温度;
的printf（Swaping％S与％s \\ n，表 - ＆GT;为了[J]，表 - ＆GT;为了[J + 1]）;
}
}
}
返回表 - ＆GT;秩序;
}无效* next_hash_walk（Phash_table表）{ / *
检查next_has_walk已经次数量
如果大于总高，它会返回null
* / 如果（*（＆表 - GT; number_next_calls）＆GT; = *（表 - 个总））{
返回NULL;
}其他{
*（表 - ＆GT; number_next_calls）= *（表 - ＆GT; number_next_calls）+ 1;
返回表 - ＆GT;为了[*（表 - ＆GT; number_next_calls）];
}
}/*project4.c*/＃包括hash.h＃定义WORD_SIZE 40
＃定义DICTIONARY_SIZE 1000
的#define TRUE 1
＃定义FALSE 0INT hash_function（字符*字）{ INT总之，我;
I = 0;
总和= 0;
而（字[I]！='\\ 0'）{
总和=总和+字[I];
我++;
}
返回总和％1000;
}诠释主要（无效）{ / *创建桶数组* /
Phash_table字典;
void *的测试; 字典= new_hash（DICTIONARY_SIZE，hash_function，COMP）; INT I;
I = 0;
void *的频率[DICTIONARY_SIZE]
INT char_index = 0，dictionary_size = 0，NUM_WORDS = 0;
焦C，字[WORD_SIZE] 的printf（解析输入... \\ n）; 而（（C =的getchar（））！= EOF）{
如果（（C ==''）||（C =='，'）||（三==''）||（三==''）||（三==''）！| |
（三=='：'）|| （C =='\\ n'））{ / *一句话结束* /
如果（char_index）{
/ *字不是空的* /
字[char_index] ='\\ 0';
lower_case_word（字）;
如果（！find_hash（词典，单词））{
insert_hash（词典，单词频率[hash_function（字）]）;
}
频率[hash_function（字）] ++;
char_index = 0;
NUM_WORDS ++;
}
}其他{
字[char_index ++] = C;
}
} 的printf（有％d个字;％d个独特的词\\ n，NUM_WORDS，dictionary_size）;
}无效lower_case_word（字符* W）{
INT I = 0; 而（W [I]！='\\ 0'）{
W [i] = tolower的（W [I]）;
我++;
}
}
您 find_hash（）函数没有返回值。
您省略了一些功能：
Phash_table new_hash（INT大小，INT（*哈希）（字符*），INT（* COMP）（void *的，无效*））;
无效lower_case_word（字符*字）;
INT hash_function（字符*）;
INT comp_function（void *的，无效*）;
您还没有指定DICTIONARY_SIZE或WORD_SIZE。
您还没有宣布 C 在的main（）。
您还没有定义的 INT主要（无效）（或 INT主（INT ARGC，字符** argv的））。返回类型是 INT ，它以0或2个参数。
您已经定义都不初始化也不 char_index 。你没有定义字。你没有定义或初始化 NUM_WORDS 。
通常情况下，你应该提交编译code到SO。缺少的功能和标准的头是一回事;它是合法的（但温和的滋扰），如果你省略它们的定义。
您可能要考虑的比较功能是否应该采取无效常量* （或常量无效* ）参数，而不是仅仅无效* ;这将使它更普遍使用，例如用的qsort（）或 bsearch（）。
我不清楚哈希函数是否会采取获益无效* ，而不是的char * ;它可能应该是字符常量* 或无效常量* ，而不是一个不合格的指针。
在文体上，不要把周围任何空间 - ＆GT; 或 运营商。他们结合比什么都更紧密。一般情况下，把空间围绕二元运算符，如 / 。一般情况下，把空格逗号之后（但要保持一致甚至更多）。
hash.h
不要（通常＆MDASH;这是一个通常情况下）在头文件中声明静态函数。只需要在一个文件中的静态函数;还有的把它的头是没有意义的。一个头是源文件之间共享信息。如果事情是不会被其他文件中使用，有没有点宣布它。
确实保护头部，从重新加入：
的#ifndef HASH_H_INCLUDED
＃定义HASH_H_INCLUDED...头的其余部分在这里...#ENDIF / * * HASH_H_INCLUDED /
不要在标题任何使用头不需要不包括。在hash.h的材料都不需要任何＆LT;文件stdlib.h＆GT; 或＆LT; stdio.h中＆GT; 所以它可能不应该存在。
C标准使用的#include 之间和头名的空间;什么是不够好，他们应该是配不上你。
project4.c
您没有给予足够的重视编译器警告，或没有足够的编译器警告设置。如果你使用GCC，至少编译 -Wall 。当我测试的编译，我用的，例如：
GCC -O3 -g -std = C99 -Wall -Wextra -Wmissing的原型-Wstrict的原型-c project4.c
我希望我的code到组选项下顺利地编译。
您需要的#include＆LT;文件ctype.h方式＆gt; 声明 tolower的（）
功能补偿（）没有任何地方定义。我说：
静态INT补偿（void *的V1，无效* V2）
{
字符常量* S1 = V1;
字符常量* S2 = V2;
返回的strcmp（S1，S2）;
}
我也把静态在前hash_function（）来避免需要外部定义。
当我编译有一次，我得到了警告：
project4.c：51：警告：比较始终是假的，由于数据类型范围限制
这说明了一个问题。您声明 C 为字符，但后来写道：
，而（（C =的getchar（））！= EOF）
这是一个禁忌。功能的getchar（）返回 INT （是的，这个名字不好）。设定值可以返回包含每个字符的以及的独特价值EOF。您必须使用 INT 来得到可靠的行为。发生一的两个问题。要么你永远不会得到EOF因为赋值是一个（隐含的）无符号的类型，-1被映射到0xFF，而当将0xFF提升到 INT ，这是积极的因此不等于-1;或者你misinter preT有效字符（通常U + 00FF，Y，带分音符的小拉丁字母Y，通俗的y变音）作为EOF。
您应该考虑使用像字符isalnum（）而不是条件：
如果（（三==''）||（C ==''）||（C ==''）||（C =='！ ）||（C ==''）||
（三=='：'）|| （C =='\\ n'））
hash.c
在code省略的#include＆LT;文件string.h方式＆gt;
编译器说：
hash.c：在函数'find_hash：
hash.c：142：警告：格式参数太少
hash.c：在函数'start_hash_walk：
hash.c：219：警告：格式'％s'的预期中键入'字符*'，但参数2的类型'无效*'
hash.c：219：警告：格式'％s'的预期中键入'字符*'，但3个参数的类型'无效*'
行号应与少许盐进行治疗;我用奥尔曼式的布局，因此增加了一些行到code当我格式化了。但是，如果你的编译器不给你这种建议，你应该寻找一个编译器一样。
142线包括：
的printf（％检查）;
的％是不必要的。但是，你可能永远也看不到输出，直到打印的东西换行，或者你使用 fflush（标准输出）; 来强制数据输出
的printf（检查\\ n）;
作为一般规则，尤其是在调试过程中，最终打印的消息以换行符。
219行是：
的printf（Swaping％S与％s \\ n，表 - ＆GT;为了[J]，表 - ＆GT;为了[J + 1]）;
这也许应该阅读：
的printf（交换％S与％s \\ n，（字符*）表 - ＆GT;为了[J]，（字符*）表 - ＆GT;为了[J + 1]）;
由于订单是无效** 。你可能会用它作为一个的char ** ，当然更好。
操作
使用这些（未成年人）已修复的问题时，code编译和链接。当一些文字上运行，输出如下：
解析输入...
阵列ArrayEnd的ArrayEnd的ArrayEnd的ArrayEnd的ArrayEnd结束
输出换行！这大概也是值得打印出它是什么字符串，你刚刚处理，以及是否添加，或在数据中发现它已经。
在的一个问题的main（）：您使用它之前，你不intialize的频率阵列。此外，目前尚不完全清楚，为什么数组存在;为什么没有在频率信息被保持在哈希表正确？而为什么是频率信息的数组无效* 而不是说， INT ？
在一个批次的样本数据，程序概括输入为：
有68字; 0字独特。
独特的单词数量最初是令人担忧，但事实证明，你初始化 dictionary_size 0，并且永远不会改变它，然后打印出来，这样多输出是正确的。
我认为你需要自己编写的结构自卸车。这是一个函数，它给予（指针）结构时，输出有关该结构中的数据显诊断信息。我用的是一般形式：
无效dump_xyzstructure（FILE * FP，字符常量*标记，xyzstructure常量*数据）;
然后我可以这样写：
dump_xyzstructure（标准输出，初始化之后，＆安培; XYZ）;dump_xyzstructure（logfp，此时，＆安培; XYZ）;
等
您哈希表是pretty复杂。但是，你有哈希表调用哈希函数之外code，我不知道这是一个好主意。最主要的是，它不应该需要。由于需要您的哈希表，支持频率计数，哈希表应当记录你的频率;你不应该做，在若干辅助code主程序。
您可以通过精简结构简化生活。你没有动态分配在结构的一切。对特定的一个64位的机器，这是一个巨大的浪费空间。 （OK：它是空间浪费琐碎，但它费工夫太）
/ *设置inital性条件* /
table_p-＆GT;最差的=（INT *）malloc的（的sizeof（INT））;
table_p-个总=（INT *）malloc的（的sizeof（INT））;
table_p-＆GT;平均=（浮点*）malloc的（的sizeof（浮动））;
table_p-＆GT; number_buckets =（INT *）malloc的（的sizeof（INT））;
这将是更紧凑，有一个数据结构而不这些指针，在结构中仅使用一个元件。这将简化释放code，太（它简化了打印code，因为它不必担心指针是否已经分配与否）：
typedef结构hash_table
{
无效**秩序;
INT number_next_calls;
INT number_buckets;
INT * buckets_size; //在每个桶的条目数量
诠释最糟糕的;
INT总;
浮动平均水平;
INT（* hash_func）（字符*）;
INT（* comp_func）（void *的，无效*）;
data_el ** buckets_array;
} hash_table，* Phash_table;
平均可按需计算;它不保证在结构的地方，真的。失去所有这些指针，简化了code增色不少。
例如，这个片断：
如果（*（＆表 - GT; number_next_calls）＆GT; = *（表 - 个总））
{
返回NULL;
}
其他
{
*（表 - ＆GT; number_next_calls）= *（表 - ＆GT; number_next_calls）+ 1;
返回表 - ＆GT;为了[*（表 - ＆GT; number_next_calls）];
}
变成了：
如果（表 - ＆GT; number_next_calls＆GT; =表 - 个总）
{
返回NULL;
}
其他
{
表 - ＆GT; number_next_calls =表 - ＆GT; number_next_calls + 1;
返回表 - ＆GT;为了[表 - ＆GT; number_next_calls]。
}
甚至是：
如果（表 - ＆GT; number_next_calls＆GT; =表 - 个总）
返回NULL;
其他
返回表 - ＆GT;为了[++表 - ＆GT; number_next_calls]。
示例文本
这是我在SO注释中使用了不少：
欢迎到计算器。请注意，说'谢谢'在这里的preferred方式是通过了投票权好的问题和有用的答案（一旦你有足够的声誉这样做），并通过接受最有用的答案你问任何问题（这也给你一个小的推动你的名声）。请参阅
[常见问题]（http://stackoverflow.com/faq）尤其[我怎么在这里提问？]（HTTP： //stackoverflow.com/faq#howtoask）示例输出
大多数显示的数据都来自于
dump_hash_table（）功能;我需要看到什么是工作，什么不是。它的大部分实际上是工作＆MDASH;我没有修复了大部分的算法（最坏情况下的计算是错误的而且是固定）的。我已经离开了痕迹code，而输入正在解析。哈希表：0x10E700900在输入端
为了= 00000000
桶= 0x7FD9A3800000
哈希= 0x10E607A40
比较= 0x10E607AA0
下一页电话：0
铲斗：1000
最差：4
总计：74
平均：0.074000
铲斗3：2
斗67：1
斗97：1
桶99：2
铲斗105：1
斗211：2
斗213：1
斗219：2
斗220：1
斗226：1
斗227：4
斗229：1
斗307：3
斗312：3
斗317：1
斗319：4
斗321：3
斗328：1
斗334：1
斗337：1
斗349：3
斗418：3
斗420：3
斗421：1
斗425：1
斗431：1
斗433：1
斗438：1
斗448：2
斗451：1
斗463：1
斗531：1
斗537：1
斗542：1
斗551：1
斗634：2
斗646：1
斗649：2
斗651：1
斗656：1
斗663：1
斗748：1
斗752：2
斗771：1
斗880：1
斗888：1
斗942：1
斗959：1
独特的话：74
铲斗：48
有74字; 0字独特。hash.h
注意
hash.h现在必须包括＆LT;＆stdio.h中GT;才能够申报dump_hash_table（）。包括＆LT;文件stdlib.h方式＆gt;是没有必要的。/ * * hash.h /的#ifndef HASH_H_INCLUDED
＃定义HASH_H_INCLUDED＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;typedef结构数据
{
字符*键;
void *的数据;
结构数据*接下来的;
} data_el;typedef结构hash_table
{
无效**秩序;
INT number_next_calls;
INT number_buckets;
INT * buckets_size; //每个桶的大小的数组
诠释最糟糕的;
INT总;
浮动平均水平;
INT（* hash_func）（字符*）;
INT（* comp_func）（void *的，无效*）;
data_el ** buckets_array;
} hash_table，* Phash_table;Phash_table new_hash（INT大小，INT（* hash_func）（字符*），INT（* cmp_func）（void *的，无效*））;
无效free_hash（Phash_table表）;
无效insert_hash（Phash_table表，字符*键，无效*数据）;
无效* find_hash（Phash_table表，字符*键）;
无效stat_hash（Phash_table表，为int *总，为int *最大，浮*平均值）;
无效* start_hash_walk（Phash_table表）;
无效* next_hash_walk（Phash_table表）;无效dump_hash_table（FILE * FP，字符常量*标记，hash_table常量*表）;#ENDIF / * * HASH_H_INCLUDED /hash.c
/ * * hash.c /
＃包括hash.h
＃包括LT＆;＆string.h中GT;
＃包括LT＆;＆inttypes.h GT;Phash_table new_hash（INT大小，INT（* hash_func）（字符*），INT（* cmp_func）（void *的，无效*））
{
INT I; Phash_table table_p;
hash_table hash_table; table_p =（Phash_table）的malloc（sizeof的（hash_table））; / *设置函数指针* /
table_p-＆GT; hash_func = hash_func;
table_p-＆GT; comp_func = cmp_func; / *创建桶数组* /
table_p-＆GT; buckets_array =（data_el **）的malloc（sizeof的（data_el *）*（大小+ 1））;
table_p-＆GT; buckets_size =为（int *）malloc的（的sizeof（int）的*（大小+ 1））; / *设置顺序排列* /
table_p-＆GT;为了= NULL; / *设置inital条件* /
table_p-＆GT最坏= 0;
table_p-个总= 0;
table_p-＆GT;平均= 0.0;
table_p-＆GT; number_buckets =大小; 对于（i = 0; I＆LT;大小;我++）
{
table_p-＆GT; buckets_array [我] = NULL;
}
返回table_p;
}无效free_hash（Phash_table表）
{
INT I;
I = 0;
data_el * CUR;
data_el * preV; / *自由秩序数组* /
如果（表 - ＆GT;！为了= NULL）
{
免费（表 - ＆GT;的顺序）;
} / *免费桶阵列和阵列buckets_size * /
如果（表 - ＆GT;！buckets_array = NULL）
{
对于（i = 0; I＆LT;表 - ＆GT; number_buckets;我++）
{
如果（表 - ＆GT;！buckets_array [我] = NULL）
{ / * Travers的链表，并释放它* /
CUR =表 - ＆GT; buckets_array [I]
preV = CUR; 而（（CUR =当前＆GT;！下一个）= NULL）
{
免费（preV）;
preV = CUR;
}
/ *免费的最后一个节点* /
免费（现）;
}
}
}
自由（表）;
}无效insert_hash（Phash_table表，字符*键，无效*数据）
{
INT指数;
data_el * P * CUR; 的printf（插入：＆LT;＆LT;％S＆GT;＆GT;（数据数：％d）\\ n键，*（INT *）的数据）; 指数=表 - ＆GT; hash_func（密钥）; / *头*插入/
如果（表 - ＆GT; buckets_array [指数] == NULL）
{
表 - ＆GT; buckets_array [指数] =（data_el *）malloc的（的sizeof（data_el））;
表 - ＆GT; buckets_array [指数] - ＆GT;数据=数据;
表 - ＆GT; buckets_array [指数] - ＆gt;接下来= NULL;
表 - ＆GT; buckets_array [指数] - ＆GT;关键=键;
}
其他
{
CUR =表 - ＆GT; buckets_array [指数]
P =（data_el *）malloc的（的sizeof（data_el））;
P-＆GT;关键=键;
P-＆GT;数据=数据;
P-＆gt;接下来= CUR;
CUR = P;
表 - ＆GT; buckets_array [指数] = CUR;
} / *更新合计* /
表 - 个总+ = 1; / *更新桶大小* /
表 - ＆GT; buckets_size [指数] + = 1; / *更新最坏情况* /
如果（表 - ＆GT; buckets_size [指数]＆GT;＆表 - GT;最差）
{
表 - ＆GT;最差的=表 - ＆GT; buckets_size [指数]
} / *更新平均* /
表 - ＆GT;平均=（浮点）表 - 个总/（浮点）表 - ＆GT; number_buckets;
}无效* find_hash（Phash_table表，字符*键）
{
INT I = 0; 而（1）
{
如果（表 - ＆GT; buckets_array [I] =='\\ 0'）
{
的printf（阵列\\ n结束）;
打破;
}
如果（表 - ＆GT;！buckets_array [我] = NULL）
{
的printf（检查：\\ n）;
如果（表 - ＆GT;！buckets_array [I] ='\\ 0'）
{
如果（表 - ＆GT; buckets_array [I] - ＆GT;！关键= NULL）
{
如果（的strcmp（表 - ＆GT; buckets_array [Ⅰ] - GT;键，键）== 0）
{
的printf（找到它\\ n）;
打破;
}
}
}
}
我++;
} 如果（表 - ＆GT;！buckets_array [我] = NULL）
{
的printf（新条目％d个\\ N，*（（INT *）表 - ＆GT; buckets_array [I] - ＆GT;数据））;
返回表 - ＆GT; buckets_array [Ⅰ] - GT;数据;
}
其他
{
返回NULL;
}
}无效stat_hash（Phash_table表，为int *总，为int *最大，浮*平均值）
{
*总=表 - 个总;
*最大=表 - ＆GT;最差的;
*平均=表 - ＆GT;平均值;
}无效* start_hash_walk（Phash_table表）
{
INT I，max_buckets，一步，next_calls;
步骤= 0;
data_el * CUR;
next_calls = 0; max_buckets =表 - ＆GT; number_buckets;
表 - ＆GT;为了=（无效**）的malloc（sizeof的（无效*）*表 - 个总）;
表 - ＆GT; number_next_calls = 0; / *遍历ADT，并把所有数据放入指令序列* /
对于（i = 0; I＆LT; max_buckets;我++）
{
如果（表 - ＆GT;！buckets_array [我] = NULL）
{
CUR =表 - ＆GT; buckets_array [I]
而（现）
{
表 - ＆GT;为了[步骤] =电流＆GT;数据;
步++;
CUR =当前＆gt;接下来，
}
}
} / *泡泡短* /
INT J，K; 为（J = 0; J＆≤（步骤 - 1）; J ++）
{
为（K = 0; K＆≤（步骤 - 第（j + 1））; K +）
{
如果（（表 - ＆GT; comp_func）（表 - ＆GT;为了[J]，表 - ＆GT;为了[J + 1]）小于5）
{
void *的温度; TEMP =表 - ＆GT;为了[J]。
表 - ＆GT;为了[J] =表 - ＆GT;为了[J + 1];
表 - ＆GT;为了[J + 1] =温度;
的printf（交换％S与％s \\ n，（字符*）表 - ＆GT;为了[J]，（字符*）表 - ＆GT;为了[J + 1]）;
}
}
}
返回表 - ＆GT;秩序;
}无效* next_hash_walk（Phash_table表）
{
/ *
检查next_has_walk已经次数量
如果大于总高，它会返回null
* / 如果（表 - ＆GT; number_next_calls＆GT; =表 - 个总）
返回NULL;
其他
返回表 - ＆GT;为了[++表 - ＆GT; number_next_calls]。
}无效dump_hash_table（FILE * FP，字符常量*标记，hash_table常量*表）
{
fprintf中（FP，哈希表：为0x％0.8PRIXPTR％S \\ n，（uintptr_t形式）表，标签）;
如果（表== 0）
返回;
fprintf中（FP，订单=为0x％0.8PRIXPTR\\ n，（uintptr_t形式）表 - ＆GT;的顺序）;
fprintf中（FP，桶=为0x％0.8PRIXPTR\\ n，（uintptr_t形式）表 - ＆GT; buckets_array）;
fprintf中（FP，散列=为0x％0.8PRIXPTR\\ n，（uintptr_t形式）表 - ＆GT; hash_func）;
fprintf中（FP，比较=为0x％0.8PRIXPTR\\ n，（uintptr_t形式）表 - ＆GT; comp_func）;
fprintf中（FP，下一步的呼叫数：％d \\ n，表 - ＆GT; number_next_calls）;
fprintf中（FP，桶数：％d \\ n，表 - ＆GT; number_buckets）;
fprintf中（FP，最坏数：％d \\ n，表 - ＆GT;最差）;
fprintf中（FP，总数：％d \\ n，表 - 个总）;
fprintf中（FP，平均：％F \\ N，表 - ＆GT;平均）;
如果（表 - ＆GT;！buckets_size = 0）
{
INT unique_words = 0;
INT used_buckets = 0;
的for（int i = 0; I＆LT;表 - ＆GT; number_buckets;我++）
{
unique_words + =表 - ＆GT; buckets_size [I]
如果（表 - ＆GT;！buckets_size [I] = 0）
{
used_buckets ++;
fprintf中（FP木桶％3D数：％d \\ n，我，表 - ＆GT; buckets_size [I]）;
}
}
fprintf中（FP，唯一词数：％d \\ n，unique_words）;
fprintf中（FP，铲斗数：％d \\ n，used_buckets）;
}
}project4.c
/ * * project4.c /＃包括hash.h
＃包括LT＆;＆string.h中GT;
＃包括LT＆;＆文件ctype.h GT;＃定义WORD_SIZE 40
＃定义DICTIONARY_SIZE 1000
的#define TRUE 1
＃定义FALSE 0静态无效lower_case_word（字符* W）;静态INT hash_function（字符*字）
{
INT总之，我;
I = 0;
总和= 0;
而（字[I]！='\\ 0'）
{
总和=总和+字[I];
我++;
}
返回总和％1000;
}静态INT补偿（void *的V1，无效* V2）
{
字符常量* S1 = V1;
字符常量* S2 = V2;
返回的strcmp（S1，S2）;
}INT主要（无效）
{
/ *创建桶数组* /
Phash_table词典= new_hash（DICTIONARY_SIZE，hash_function，COMP）;
INT频率[DICTIONARY_SIZE] = {0};
INT char_index = 0，dictionary_size = 0，NUM_WORDS = 0;
字符字[WORD_SIZE]
INT℃; 的printf（解析输入... \\ n）; 而（（C =的getchar（））！= EOF）
{
如果（字符isalnum（c））的
字[char_index ++] = C;
其他
{
/ *一句话结束* /
如果（char_index）
{
/ *字不是空的* /
字[char_index] ='\\ 0';
lower_case_word（字）;
的printf（得到：％S \\ N字）;
如果（！find_hash（字典，字））
{
insert_hash（字典，字，和放大器;频率[hash_function（字）]）;
}
频率[hash_function（字）] ++;
char_index = 0;
NUM_WORDS ++;
}
}
} dump_hash_table（标准输出，在输入结束，字典）; 的printf（有％d个字;％d个独特的词\\ n，NUM_WORDS，dictionary_size）;
}静态无效lower_case_word（字符* W）
{
INT I = 0; 而（W [I]！='\\ 0'）
{
W [i] = tolower的（W [I]）;
我++;
}
}Hello can someone help me find what is causing the problem? For some reason the find_hash function is giving me problems. It should be failing the
if(table -> buckets_array[i] != NULL){andif(table -> buckets_array[i] != '\0'){but it is not and it going to the next check which gives me a segmentation fault. What can be causing the first 2 if's statement to pass since I initially set it to table -> buckets_array[i] = NULL?Edit: Thanks for
wildplasserI came up with a much better solution for my find_hash function.if(table->buckets_array[table->hash_func(key)] == NULL){ return NULL; }else{ return table -> buckets_array[table->hash_func(key)] -> data; }Thanks you everyone for the help.
/*hash.h*/ #include<stdio.h> #include<stdlib.h> typedef struct data_{ char *key; void *data; struct data_ *next; }data_el; typedef struct hash_table_ { void **order; int *number_next_calls; int *number_buckets; int *buckets_size; int *worst; int *total; float *average; int (*hash_func)(char *); int (*comp_func)(void*, void*); data_el **buckets_array; } hash_table, *Phash_table; Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *)); void free_hash(Phash_table table); void insert_hash(Phash_table table, char *key, void *data); void *find_hash(Phash_table table, char *key); void stat_hash(Phash_table table, int *total, int *largest, float *average); void *start_hash_walk(Phash_table table); void *next_hash_walk(Phash_table table); static void lower_case_word(char *w); /*hash.c*/ #include"hash.h" Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *)){ int i; Phash_table table_p; hash_table hash_table; table_p = (Phash_table)malloc(sizeof(hash_table)); /*Setting function pointers*/ table_p->hash_func = hash_func; table_p->comp_func = cmp_func; /*Create buckets array*/ table_p->buckets_array = (data_el **)malloc(sizeof(data_el *)*(size+1)); table_p->buckets_size = (int *)malloc(sizeof(int)*(size+1)); /*Setting order array*/ table_p->order = NULL; /*Setting inital condictions*/ table_p->worst = (int *)malloc(sizeof(int)); table_p->total = (int *)malloc(sizeof(int)); table_p->average = (float *)malloc(sizeof(float)); table_p->number_buckets = (int *)malloc(sizeof(int)); *(table_p->number_buckets) = size; for(i = 0; i < size; i++){ table_p->buckets_array[i] = NULL; } return table_p; } void free_hash(Phash_table table){ int i; i = 0; data_el *cur; data_el *prev; /*Free order array*/ if(table->order != NULL){ free(table->order); } /*Free Buckets array and buckets_size array*/ if(table ->buckets_array != NULL){ for(i=0; i < *(table->number_buckets); i++){ if(table->buckets_array[i] != NULL){ /*Travers the linked list and free it*/ cur = table->buckets_array[i]; prev = cur; while((cur = cur->next) != NULL){ free(prev); prev = cur; } /*Free the last node*/ free(cur); } } } free(table); } void insert_hash(Phash_table table, char *key, void *data){ int index; data_el *p, *cur; index = table->hash_func(key); /*Head insertion*/ if(table->buckets_array[index] == NULL){ table->buckets_array[index] = (data_el *)malloc(sizeof(data_el)); table->buckets_array[index]->data = data; table->buckets_array[index]->next = NULL; table->buckets_array[index]->key = key; }else{ cur = table->buckets_array[index]; p = (data_el *)malloc(sizeof(data_el)); p->key = key; p->data = data; p->next = cur; cur = p; table->buckets_array[index] = cur; } /*Update Total*/ *table->total += 1; /*Update Bucket Size*/ (table->buckets_size[index]) +=1; /*Updates Worst Case*/ if((table->buckets_size[index]) > *(table->worst)){ *(table->worst) = (table->buckets_size[index]); }else{ *(table->worst) +=1; } /*Update Average*/ int temp_total,temp_buckets; temp_total = *(table->total); temp_buckets = *(table->number_buckets); *(table->average)= (float)temp_total/(float)temp_buckets; } void *find_hash(Phash_table table, char *key){ int i; i = 0; while(1){ if(table->buckets_array[i] == '\0'){ printf("End of Array"); break; } if(table->buckets_array[i] != NULL){ printf("%Checking"); if(table->buckets_array[i] != '\0'){ if(table->buckets_array[i]->key != NULL){ if( strcmp(table->buckets_array[i]->key,key) == 0 ){ printf("Found it\n"); break; } } } } i++; } if(table->buckets_array[i] != NULL){ printf("new asdasd %d", *((int *)table->buckets_array[i]->data)); return table->buckets_array[i]->data; }else{ return NULL; } } void stat_hash(Phash_table table, int *total, int *largest, float *average){ total = (table->total); largest = (table->worst); average = (table->average); } void *start_hash_walk(Phash_table table){ int i, max_buckets,step,next_calls; step = 0; data_el *cur; next_calls = 0; max_buckets = *(table ->number_buckets); table->order = (void**)malloc(sizeof(void *)*(*(table->total))); /*Set number_next_calls to 0*/ table->number_next_calls = &next_calls; *(table->number_next_calls) = 0; /*Traverse the ADT and put all data into order array*/ for(i = 0; i < max_buckets; i++){ if(table->buckets_array[i] != NULL){ cur = table->buckets_array[i]; while(cur){ table->order[step] = cur->data; step ++; cur = cur->next; } } } /*Bubble Short*/ int j,k; for(j = 0; j < (step - 1);j++){ for(k = 0;k < (step -(j+1));k ++){ if((table->comp_func)(table->order[j],table->order[j+1]) < 5){ void *temp; temp = table->order[j]; table->order[j] = table->order[j+1]; table->order[j+1] = temp; printf("Swaping %s with %s\n",table->order[j],table->order[j+1]); } } } return table->order; } void *next_hash_walk(Phash_table table){ /* Check the amount of times next_has_walk has been if higher than total, it will return null */ if(*(table->number_next_calls) >= *(table->total)){ return NULL; }else{ *(table->number_next_calls) = *(table->number_next_calls) + 1; return table->order[*(table->number_next_calls)]; } } /*project4.c*/ #include"hash.h" #define WORD_SIZE 40 #define DICTIONARY_SIZE 1000 #define TRUE 1 #define FALSE 0 int hash_function(char *word){ int sum,i; i = 0; sum = 0; while(word[i] != '\0'){ sum = sum + word[i]; i++; } return sum%1000; } int main(void){ /*Creating buckets array*/ Phash_table dictionary; void *test; dictionary = new_hash(DICTIONARY_SIZE,hash_function,comp); int i; i = 0; void *frequency[DICTIONARY_SIZE]; int char_index = 0, dictionary_size = 0, num_words = 0; char c, word[WORD_SIZE]; printf("Parsing input ...\n"); while ((c = getchar()) != EOF) { if ((c == ' ') || (c == ',') || (c == '.') || (c == '!') || (c == '"') || (c == ':') || (c == '\n')) { /* End of a word */ if (char_index) { /* Word is not empty */ word[char_index] = '\0'; lower_case_word(word); if(!find_hash(dictionary,word) ){ insert_hash(dictionary,word,frequency[hash_function(word)]); } frequency[hash_function(word)]++; char_index = 0; num_words++; } }else{ word[char_index++] = c; } } printf("There were %d words; %d unique words.\n", num_words,dictionary_size); } void lower_case_word(char *w){ int i = 0; while (w[i] != '\0') { w[i] = tolower(w[i]); i++; } }
解决方案Your
find_hash()function does not return a value.You omitted some functions:
Phash_table new_hash(int size, int (*hash)(char *), int (*comp)(void *, void *)); void lower_case_word(char *word); int hash_function(char *); int comp_function(void *, void *);You've not specified DICTIONARY_SIZE or WORD_SIZE.
You've not declared
cinmain().You've not defined
int main(void)(orint main(int argc, char **argv)). The return type isint, and it takes 0 or 2 arguments.You've neither defined nor initialized
char_index. You didn't defineword. You didn't define or initializenum_words.Generally, you should submit compilable code to SO. The missing functions and standard headers are one thing; it is legitimate (but a mild nuisance) if you omit their definitions.
You might want to consider whether the comparison function should be taking
void const *(orconst void *) arguments instead of justvoid *; it will make it more generally usable, for example withqsort()orbsearch().I'm not clear whether the hash function would benefit from taking a
void *instead of achar *; it should probably be achar const *orvoid const *rather than an unqualified pointer.Stylistically, do not put spaces around either
->or.operators. They bind tighter than anything else. Generally, put spaces around binary operators such as/. Generally, put spaces after commas (but be consistent even more).
hash.h
Do not (usually — this is a usual case) declare static functions in headers. A static function is only needed in one file; there is no point in putting it in the header. A header is for sharing information between source files. If something isn't going to be used by other files, there's no point in declaring it.
Do protect headers from reinclusion:
#ifndef HASH_H_INCLUDED #define HASH_H_INCLUDED ...rest of header here... #endif /* HASH_H_INCLUDED */Do not include in the header anything that is not needed to use the header. None of the material in "hash.h" requires either
<stdlib.h>or<stdio.h>so it probably shouldn't be there.The C standard uses a space between
#includeand the header name; what's good enough for them should be good enough for you.project4.c
You aren't paying enough attention to compiler warnings, or don't have enough compiler warnings set. If you're using GCC, compile with
-Wallat least. When I was test compiling, I used, for example:gcc -O3 -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -c project4.cI expect my code to compile cleanly under that set of options.
You need
#include <ctype.h>to declaretolower().Function
comp()is not defined anywhere. I added:static int comp(void *v1, void *v2) { char const *s1 = v1; char const *s2 = v2; return strcmp(s1, s2); }I also put
staticin front ofhash_function()to avoid needing an external definition.One time when I compiled, I got the warning:
project4.c:51: warning: comparison is always false due to limited range of data typeThat shows a problem. You declared
caschar, but then wrote:while ((c = getchar()) != EOF)This is a no-no. The function
getchar()returns anint(yes, the name is not good). The set of values it can return includes every character plus a distinct value EOF. You must use anintto get reliable behaviour. One of two problems occurs. Either you never get EOF because the assignment is to an (implicitly) unsigned type, and -1 gets mapped to 0xFF, and when 0xFF is promoted to anint, it is positive and therefore not equal to -1; or you misinterpret a valid character (often U+00FF, ÿ, SMALL LATIN LETTER Y WITH DIAERESIS, colloquially y-umlaut) as EOF.You should consider using something like
!isalnum()instead of the condition:if ((c == ' ') || (c == ',') || (c == '.') || (c == '!') || (c == '"') || (c == ':') || (c == '\n'))
hash.c
The code omitted
#include <string.h>.The compiler says:
hash.c: In function ‘find_hash’: hash.c:142: warning: too few arguments for format hash.c: In function ‘start_hash_walk’: hash.c:219: warning: format ‘%s’ expects type ‘char *’, but argument 2 has type ‘void *’ hash.c:219: warning: format ‘%s’ expects type ‘char *’, but argument 3 has type ‘void *’The line numbers should be treated with a pinch of salt; I use Allman style layout and therefore added a number of lines to your code when I formatted it. But if your compiler isn't giving you this sort of advice, you should be looking for a compiler that does.
Line 142 contains:
printf("%Checking");The
%is unneeded. However, you may never see the output until something prints a newline, or you usefflush(stdout);to force the data out.printf("Checking\n");As a general rule, especially during debugging, end printed messages with a newline.
Line 219 is:
printf("Swaping %s with %s\n",table->order[j],table->order[j+1]);It should probably read:
printf("Swapping %s with %s\n", (char *)table->order[j], (char *)table->order[j+1]);because
orderis avoid **. You might be better off with it being achar **, of course.
Operations
With those (minor) issues fixed, the code compiles and links. When run on some text, the output looks like:
Parsing input ... End of ArrayEnd of ArrayEnd of ArrayEnd of ArrayEnd of ArrayEnd of ArrayOutput newlines! It is probably also worth printing out what string it is you've just processed, and whether you added it or found it already in the data.
One problem in
main(): you do not intialize thefrequencyarray before you use it. Further, it isn't entirely clear why the array exists; why isn't the frequency information being kept in the hash table proper? And why is the frequency information an array ofvoid *rather than, say,int?On one lot of sample data, the program summarized the input as:
There were 68 words; 0 unique words.The number of unique words is initially worrisome, but it turns out that you initialize
dictionary_sizeto 0 and never change it and then print it, so that much of the output is correct.
I think you need to write yourself a structure dumper. That's a function that when given a (pointer to the) structure, prints sensible diagnostic information about the data in the structure. I use the general form:
void dump_xyzstructure(FILE *fp, char const *tag, xyzstructure const *data);Then I can write:
dump_xyzstructure(stdout, "After initialization", &xyz); dump_xyzstructure(logfp, "At this point", &xyz);Etc.
Your hash table is pretty complex. However, you have code outside the hash table calling the hash function, and I'm not sure that's a good idea. Mostly, it shouldn't need to. Since your hash table is needed to support frequency counting, the hash table should be recording the frequencies for you; you should not be doing that in the auxilliary code in the main program.
You can simplify life by streamlining the structure. You don't have to dynamically allocate everything in the structure. On a 64-bit machine in particular, that is a huge waste of space. (OK: it is a trivial waste of space, but it a waste of effort too.)
/*Setting inital condictions*/ table_p->worst = (int *)malloc(sizeof(int)); table_p->total = (int *)malloc(sizeof(int)); table_p->average = (float *)malloc(sizeof(float)); table_p->number_buckets = (int *)malloc(sizeof(int));It would be more compact to have a data structure without those pointers, using just an element in the structure. It will simplify the deallocation code, too (and it simplifies the printing code because it doesn't have to worry about whether the pointers have been allocated or not):
typedef struct hash_table { void **order; int number_next_calls; int number_buckets; int *buckets_size; // Number of entries in each bucket int worst; int total; float average; int (*hash_func)(char *); int (*comp_func)(void*, void*); data_el **buckets_array; } hash_table, *Phash_table;The average can be computed on demand; it doesn't warrant a place in the structure, really. Losing all those pointers simplifies the code considerably.
For example, this fragment:
if (*(table->number_next_calls) >= *(table->total)) { return NULL; } else { *(table->number_next_calls) = *(table->number_next_calls) + 1; return table->order[*(table->number_next_calls)]; }becomes:
if (table->number_next_calls >= table->total) { return NULL; } else { table->number_next_calls = table->number_next_calls + 1; return table->order[table->number_next_calls]; }or even:
if (table->number_next_calls >= table->total) return NULL; else return table->order[++table->number_next_calls];
Sample text
This is something I use quite a lot in SO comments:
Welcome to StackOverflow. Please note that the preferred way of saying 'thanks' around here is by up-voting good questions and helpful answers (once you have enough reputation to do so), and by accepting the most helpful answer to any question you ask (which also gives you a small boost to your reputation). Please see the
[FAQ](http://stackoverflow.com/faq)and especially[How do I ask questions here?](http://stackoverflow.com/faq#howtoask)
Sample Output
Most of the data shown comes from the
dump_hash_table()function; I needed to see what was working and what was not. Most of it was actually working — I didn't have to fix up much of the algorithm (the worst case calculation was faulty and is fixed). I've left out the trace code while the input was being parsed.Hash Table: 0x10E700900 At end of input Order = 0x00000000 Buckets = 0x7FD9A3800000 Hash = 0x10E607A40 Comp = 0x10E607AA0 Next calls: 0 Buckets: 1000 Worst: 4 Total: 74 Average: 0.074000 Bucket 3: 2 Bucket 67: 1 Bucket 97: 1 Bucket 99: 2 Bucket 105: 1 Bucket 211: 2 Bucket 213: 1 Bucket 219: 2 Bucket 220: 1 Bucket 226: 1 Bucket 227: 4 Bucket 229: 1 Bucket 307: 3 Bucket 312: 3 Bucket 317: 1 Bucket 319: 4 Bucket 321: 3 Bucket 328: 1 Bucket 334: 1 Bucket 337: 1 Bucket 349: 3 Bucket 418: 3 Bucket 420: 3 Bucket 421: 1 Bucket 425: 1 Bucket 431: 1 Bucket 433: 1 Bucket 438: 1 Bucket 448: 2 Bucket 451: 1 Bucket 463: 1 Bucket 531: 1 Bucket 537: 1 Bucket 542: 1 Bucket 551: 1 Bucket 634: 2 Bucket 646: 1 Bucket 649: 2 Bucket 651: 1 Bucket 656: 1 Bucket 663: 1 Bucket 748: 1 Bucket 752: 2 Bucket 771: 1 Bucket 880: 1 Bucket 888: 1 Bucket 942: 1 Bucket 959: 1 Unique words: 74 Used Buckets: 48 There were 74 words; 0 unique words.
hash.h
Note that
hash.hmust now include<stdio.h>to be able to declaredump_hash_table(). Including<stdlib.h>is not necessary./*hash.h*/ #ifndef HASH_H_INCLUDED #define HASH_H_INCLUDED #include <stdio.h> #include <stdlib.h> typedef struct data { char *key; void *data; struct data *next; } data_el; typedef struct hash_table { void **order; int number_next_calls; int number_buckets; int *buckets_size; // Array of sizes of each bucket int worst; int total; float average; int (*hash_func)(char *); int (*comp_func)(void*, void*); data_el **buckets_array; } hash_table, *Phash_table; Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *)); void free_hash(Phash_table table); void insert_hash(Phash_table table, char *key, void *data); void *find_hash(Phash_table table, char *key); void stat_hash(Phash_table table, int *total, int *largest, float *average); void *start_hash_walk(Phash_table table); void *next_hash_walk(Phash_table table); void dump_hash_table(FILE *fp, char const *tag, hash_table const *table); #endif /* HASH_H_INCLUDED */
hash.c
/*hash.c*/ #include "hash.h" #include <string.h> #include <inttypes.h> Phash_table new_hash(int size, int (*hash_func)(char *), int (*cmp_func)(void *, void *)) { int i; Phash_table table_p; hash_table hash_table; table_p = (Phash_table)malloc(sizeof(hash_table)); /*Setting function pointers*/ table_p->hash_func = hash_func; table_p->comp_func = cmp_func; /*Create buckets array*/ table_p->buckets_array = (data_el **)malloc(sizeof(data_el *)*(size+1)); table_p->buckets_size = (int *)malloc(sizeof(int)*(size+1)); /*Setting order array*/ table_p->order = NULL; /*Setting inital conditions*/ table_p->worst = 0; table_p->total = 0; table_p->average = 0.0; table_p->number_buckets = size; for (i = 0; i < size; i++) { table_p->buckets_array[i] = NULL; } return table_p; } void free_hash(Phash_table table) { int i; i = 0; data_el *cur; data_el *prev; /*Free order array*/ if (table->order != NULL) { free(table->order); } /*Free Buckets array and buckets_size array*/ if (table->buckets_array != NULL) { for (i = 0; i < table->number_buckets; i++) { if (table->buckets_array[i] != NULL) { /*Travers the linked list and free it*/ cur = table->buckets_array[i]; prev = cur; while ((cur = cur->next) != NULL) { free(prev); prev = cur; } /*Free the last node*/ free(cur); } } } free(table); } void insert_hash(Phash_table table, char *key, void *data) { int index; data_el *p, *cur; printf("Inserting: <<%s>> (data: %d)\n", key, *(int *)data); index = table->hash_func(key); /*Head insertion*/ if (table->buckets_array[index] == NULL) { table->buckets_array[index] = (data_el *)malloc(sizeof(data_el)); table->buckets_array[index]->data = data; table->buckets_array[index]->next = NULL; table->buckets_array[index]->key = key; } else { cur = table->buckets_array[index]; p = (data_el *)malloc(sizeof(data_el)); p->key = key; p->data = data; p->next = cur; cur = p; table->buckets_array[index] = cur; } /*Update Total*/ table->total += 1; /*Update Bucket Size*/ table->buckets_size[index] +=1; /*Updates Worst Case*/ if (table->buckets_size[index] > table->worst) { table->worst = table->buckets_size[index]; } /*Update Average*/ table->average = (float)table->total / (float)table->number_buckets; } void *find_hash(Phash_table table, char *key) { int i = 0; while (1) { if (table->buckets_array[i] == '\0') { printf("End of Array\n"); break; } if (table->buckets_array[i] != NULL) { printf("Checking:\n"); if (table->buckets_array[i] != '\0') { if (table->buckets_array[i]->key != NULL) { if (strcmp(table->buckets_array[i]->key, key) == 0 ) { printf("Found it\n"); break; } } } } i++; } if (table->buckets_array[i] != NULL) { printf("New entry %d\n", *((int *)table->buckets_array[i]->data)); return table->buckets_array[i]->data; } else { return NULL; } } void stat_hash(Phash_table table, int *total, int *largest, float *average) { *total = table->total; *largest = table->worst; *average = table->average; } void *start_hash_walk(Phash_table table) { int i, max_buckets, step, next_calls; step = 0; data_el *cur; next_calls = 0; max_buckets = table ->number_buckets; table->order = (void**)malloc(sizeof(void *) * table->total); table->number_next_calls = 0; /*Traverse the ADT and put all data into order array*/ for (i = 0; i < max_buckets; i++) { if (table->buckets_array[i] != NULL) { cur = table->buckets_array[i]; while (cur) { table->order[step] = cur->data; step ++; cur = cur->next; } } } /*Bubble Short*/ int j, k; for (j = 0; j < (step - 1);j++) { for (k = 0;k < (step -(j+1));k ++) { if ((table->comp_func)(table->order[j], table->order[j+1]) < 5) { void *temp; temp = table->order[j]; table->order[j] = table->order[j+1]; table->order[j+1] = temp; printf("Swapping %s with %s\n", (char *)table->order[j], (char *)table->order[j+1]); } } } return table->order; } void *next_hash_walk(Phash_table table) { /* Check the amount of times next_has_walk has been if higher than total, it will return null */ if (table->number_next_calls >= table->total) return NULL; else return table->order[++table->number_next_calls]; } void dump_hash_table(FILE *fp, char const *tag, hash_table const *table) { fprintf(fp, "Hash Table: 0x%.8" PRIXPTR " %s\n", (uintptr_t)table, tag); if (table == 0) return; fprintf(fp, " Order = 0x%.8" PRIXPTR "\n", (uintptr_t)table->order); fprintf(fp, " Buckets = 0x%.8" PRIXPTR "\n", (uintptr_t)table->buckets_array); fprintf(fp, " Hash = 0x%.8" PRIXPTR "\n", (uintptr_t)table->hash_func); fprintf(fp, " Comp = 0x%.8" PRIXPTR "\n", (uintptr_t)table->comp_func); fprintf(fp, " Next calls: %d\n", table->number_next_calls); fprintf(fp, " Buckets: %d\n", table->number_buckets); fprintf(fp, " Worst: %d\n", table->worst); fprintf(fp, " Total: %d\n", table->total); fprintf(fp, " Average: %f\n", table->average); if (table->buckets_size != 0) { int unique_words = 0; int used_buckets = 0; for (int i = 0; i < table->number_buckets; i++) { unique_words += table->buckets_size[i]; if (table->buckets_size[i] != 0) { used_buckets++; fprintf(fp, " Bucket %3d: %d\n", i, table->buckets_size[i]); } } fprintf(fp, " Unique words: %d\n", unique_words); fprintf(fp, " Used Buckets: %d\n", used_buckets); } }
project4.c
/*project4.c*/ #include "hash.h" #include <string.h> #include <ctype.h> #define WORD_SIZE 40 #define DICTIONARY_SIZE 1000 #define TRUE 1 #define FALSE 0 static void lower_case_word(char *w); static int hash_function(char *word) { int sum, i; i = 0; sum = 0; while (word[i] != '\0') { sum = sum + word[i]; i++; } return sum%1000; } static int comp(void *v1, void *v2) { char const *s1 = v1; char const *s2 = v2; return strcmp(s1, s2); } int main(void) { /*Creating buckets array*/ Phash_table dictionary = new_hash(DICTIONARY_SIZE, hash_function, comp); int frequency[DICTIONARY_SIZE] = { 0 }; int char_index = 0, dictionary_size = 0, num_words = 0; char word[WORD_SIZE]; int c; printf("Parsing input ...\n"); while ((c = getchar()) != EOF) { if (isalnum(c)) word[char_index++] = c; else { /* End of a word */ if (char_index) { /* Word is not empty */ word[char_index] = '\0'; lower_case_word(word); printf("Got: %s\n", word); if (!find_hash(dictionary, word)) { insert_hash(dictionary, word, &frequency[hash_function(word)]); } frequency[hash_function(word)]++; char_index = 0; num_words++; } } } dump_hash_table(stdout, "At end of input", dictionary); printf("There were %d words; %d unique words.\n", num_words, dictionary_size); } static void lower_case_word(char *w) { int i = 0; while (w[i] != '\0') { w[i] = tolower(w[i]); i++; } }
这篇关于这是为什么呢传递if语句？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
