| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 8083 人关注过本帖
标题:Hash应用 - 哈希(散列)表
只看楼主 加入收藏
dicklin
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2004-11-1
收藏
 问题点数:0 回复次数:50 
Hash应用 - 哈希(散列)表
写一个用Hash表存储一定数量string的程序。
Hash表的长度为350。给你一个435行的数据文件。这个文件以一行以'-'开头的数据结束。
下面是Hash函数要求:
H=int(k) mod 350
int(k)=P*k+c  //这后面没有读懂(c可能是统计string出现的次数吧)
其中
k=0为起始值
P是你自己选择的一个合适的素数
用动态链表处理碰撞问题。
你的程序须制定表中链表(应该是处理碰撞用的动态链表)长度来分析Hash表的效率。
你必须统计长度为0,1,2等等的链表的个数,并在程序中以简要的形式把它显示出来,
你在这个结果的基础上,可以了解到Hash表中是否出现过多的碰撞,从而改进的程序(应该是通过修改你给定的P值)
这个网站将给你一个有4小段检索字的数据文件http://www.staff.ncl.ac.uk/albert.koelmans/data.txt
你可以在你Hash表中检索这些单词,并了解这些检索字是否在你的Hash表中出现过

[此贴子已经被风中涟漪于2004-11-07 01:56:33编辑过]


搜索更多相关主题的帖子: 哈希 Hash 应用 
2004-11-01 22:23
dicklin
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2004-11-1
收藏
得分:0 
原来积分可以送那么多的!!请那位好人帮我答阿~我保证以后的积分都给他了!谢谢大家!
2004-11-01 22:32
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 
hash表why not自己写。
2004-11-01 23:03
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

这个文件以一行以'-'开头的数据结束

这句看不懂!

2004-11-01 23:15
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

我散列学得不好,既然出了国,叫D鬼佬帮手吧,呵呵,帮不了就fu%k...

2004-11-01 23:23
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

给个我都不太看懂的例子你吧!用char*的,其实就是string旧方式。

int Hash(char* K, int m) //其实char*相当于string,只是用法不同 { int len = strlen(K); //如果用string,可以用Length函数直接得出长度 unsigned int h = 0; //h为累加变量 for(int i=0;i<len;i++) { //计算K对应的整数 h<<=3; //h的值左移3位(我这里没懂,移位学得不好) h+=K[i]; //把K[i]字符的整数值累加到h上 } return h%m; //返回这个整数整除以m的余数 }

用ASCII码累加到无符号整型变量h上,并在每次累加之前把h的值左移3个二进制位,即扩大8倍。

声明一下,我不会帮你做作业的,自己的作业自己做,要一起讨论还是没问题的。

[此贴子已经被作者于2004-11-01 23:40:23编辑过]

2004-11-01 23:38
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

你题目给出的要求我暂时一头雾水……

碰撞问题 大概是我书上写的 冲突问题吧,我书上有链表写的示例……

2004-11-01 23:46
dicklin
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2004-11-1
收藏
得分:0 

老大你的书那里有的买阿???这里的老外都很自私的。。这里中国人又少!!哎!可怜啊!!可能是我翻译得不太好,我现在把原文放上来。你帮我研究一下啊!不过怎么也好,先谢谢你的回复,等我多点介绍朋友来灌水!哈哈!

Write a program that uses hashing to store a series of strings. The hash table should have a length of 350. You are given a data file which contains 425 lines. The file is herehttp://www.staff.ncl.ac.uk/albert.koelmans/data.txt) The file is terminated by a single line containing a '-' in the first position. The following hashing function is suggested: H = int(k) mod 350, where int(k) = P*k+c summed for all ASCII codes c in the string, where k = 0 is the start value. P is a suitably chosen prime number (choose it yourself). The method of dealing with collisions should be the dynamic linked list version. Your program must analyze the efficiency of your hashing scheme by determining how long the linked lists in the table are, i.e. you must count how many linked lists of length 0, 1, 2 and so on, there are. These results should be presented by your program in easily digestable form. After seeing the results, you might want to try to improve upon your hashing scheme if the number of collisions is excessive. Finally, the data file contains a small fourth section with search words. You should search for each word in your final hash table, and report whether each word is present or not.

2004-11-02 01:00
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

我睡了,把文章复制了,我下去查查字典先,我的书在国内买的,你那里可能没有。

老外是经济头脑,技术不跟外人分,就是自己族人也一样,不用看不惯。

其实我也半桶水,不敢逞强帮你做。睡了,good night!

2004-11-02 01:11
dicklin
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2004-11-1
收藏
得分:0 
真的谢谢你!!原来还有那么贴心的版主!!!!我晕拉!!!支持支持~~~
2004-11-02 01:34
快速回复:Hash应用 - 哈希(散列)表
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020165 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved