weixin_47375012
weixin_47375012
2021-03-29 16:45
采纳率: 57.1%
浏览 323

留学狗求大佬帮我看看这个C++哈希的问题怎么解答,需要在linux上跑

这是英文原文,链接: https://pan.baidu.com/s/1obkghFd_C59xibGdI_-Mlw 提取码: r75f 

以下是翻译版本问题要求:

描述(85分可交付成果/正确性/ 15分设计)

我们首先提供您对该问题将要做什么的摘要。可交付成果 文件的末尾将提供输出格式。您将测试每个哈希 具有以下内容的实现:

A)表中的元素总数(N),表的大小(T),负载系数 (Lambda = N / T),平均碰撞次数(M = C / N)和总碰撞次数 碰撞(C),

B)您将检查另一个给定文件query_words.txt中的每个单词是否在哈希中 表格,并根据是否找到该单词打印相应的输出 找到了,找到该单词需要进行多少次探查(如果存在)。虽然你是 随文件一起提供,我们将使用看不见的测试文件以及另一个文件名,该文件名可能会 包含words.txt中所有单词的子集。

为了实现上述目的,您将编写一个名为create_and_test_hash.cc的测试程序。 您的程序应像这样从终端运行(终端提示符为%):

% ./create_and_test_hash <words file name> <query words file name> <flag>

对于二次探测应为“二次”,对于线性探测应为“ linear”,而“ double”应为“ double” 用于双重哈希。

哈希和堆项目 例如,您可以在终端上写:

% ./create_and_test_hash words.txt query_words.txt quadratic

您可以使用提供的Makefile来编译和测试您的代码。

对于双哈希,格式将略有不同,即如下:

%./create_and_test_hash words.txt query_words.txt double R

或者,也可以使用:

%./create_and_test_hash words.txt query_words.txt double

这里R是在实现double时应该使用的可选R值 在课堂上讨论并在教科书中描述的哈希技术:hash2(x)= R –(x mod R)。如果用户没有输入一个默认的R值,则应在代码中指定一个默认值 命令行。

一,使用线性和二次探测进行散列(20分)

修改提供的代码,以进行二次和线性探测,并测试create_and_test_hash。

不要在其中的main()函数内编写任何功能 create_and_test_hash.cc。在testHashingWrapper()中编写所有功能 该文件中的功能。我们将使用我们自己的main函数,直接调用 testHashingWrapper()。此包装函数将传递所有命令行参数 就像通常在主要功能中一样。

您将打印上面提到的值,然后打印查询的单词,无论它们是 找到了,并确定了多少次探查。确切的交付物和输出格式 在文件末尾进行了描述。

二。双重哈希(25分)

编写代码以实现double_hashing.h,并使用create_and_test_hash进行测试。 这将是二次探测的变体。区别在于功能 FindPos(),现在必须使用其他策略来提供探测。作为第二个哈希 函数,请使用在课堂讲义中讨论并在教科书中找到的hash2(x)= R – (x mod R)。我们将使用我们自己的R值测试您的代码。此外,请指定哪个R README.HASH文件中用于测试程序的值。 切记不要在main()函数中包含任何功能 create_and_test_hash.cc。

您将打印当前的R值,上面A部分中提到的值,然后是 查询的单词,是否找到它们以及确定该单词需要进行多少次探查。精确的 文件的末尾描述了可交付成果和输出格式。

三,拼写检查(40分)

现在,您可以通过使用线性或二次或双精度来实现拼写检查器 哈希算法。给定一个文档,您的程序应正确输出所有 带有此类标签的拼写单词以及所有拼写错误的单词。对于每个拼写错误的单词 您应该提供字典中的候选更正列表,该列表可以由 将以下规则之一应用于拼写错误的单词:

a)在任何可能的位置添加一个字符

b)从单词中删除一个字符

c)交换单词中的相邻字符 您的程序应从命令行运行,如下所示:

% ./spell_check <document file> <dictionary file>

系统会为您提供一个名为document1_short.txt,document_1.txt的小文档, 还有一个字典文件,其中包含大约370k个单词,名为wordsEnglish.txt。 例如,您的拼写检查器应更正以下错误。

决定性->决定性(情况A) 决策->决策(案例B) 乡镇->国家(案例C)

纠正提供的词典文件中不存在的任何单词(即使它是正确的) 英文)。

一些提示:1.请注意,我们提供的词典是实际英语词典的子集, 只要您的拼写检查是合乎逻辑的,您就可以取得成绩。 例如, 字母“ i”不在词典中,更正可能是“中”,“如果”甚至是 “你好”。 这是可接受的输出。

2.另外,如果将“编辑者”更正为“编辑者”,则可以。 (案例B,删除 特点)

3.我们建议删除开头和结尾的所有标点符号,对于所有标点符号 单词会将字母转换为小写字母(例如,“ Hello!”被替换为“ hello”, 在拼写检查之前)。

不要在spell_check.cc的main()函数内编写任何功能。 写 该文件中的testSpellingWrapper()内部的所有功能。 我们将使用我们的 自己的主要功能,直接调用testSpellingWrapper()。 该包装函数是 传递了所有命令行参数,就像通常在main函数中一样。 您将打印该单词,无论它是否已经正确拼写(又名找到),以及所有 如果在词典中找不到该单词,则可能进行拼写更正。 提防 解析时在文档中使用标点符号和格式! 确切的可交付成果和输出格式如下所述。

(以下某部分是我要递交的文件,我省略翻译)

格式 对于线性和二次探测标志(第一部分),格式应如下:

number_of_elements: <int>
size_of_table: <int>
load_factor: <float>
average_collisions: <float>
total_collisions: <int>
<new line>
<word1> Found <probes1>
<word2> Not_Found <probes2>
<word3> Found <probes3>

请包括在表格属性部分和单词列表之间显示的单行(ASCII 10,列为“ <新行>”)。 请加下划线 在“没有”和“找到”之间。 这里显示的单词列表是一个示例,实际输出将取决于query_words.txt中的单词。average_collisions和total_collisions的值将根据所使用的计算机而有所不同。 切换机器或寻求帮助时请注意这一点。 您的提交将在同一台计算机上评分,因此,只要您的实现对其他所有内容都是正确的,这些值就将保持一致。 对于所有标记(线性,二次和双精度),都会发生这种情况。

正确输出的示例(数字不代表实际表):

number_of_elements: 670
size_of_table: 1560
load_factor: 0.429487
average_collisions: 0.005
total_collisions: 3
hill Found 1
skiny Not_Found 3
baked Found 1

 

对于双标记(第二部分),格式应如下:

r_value: <int>
<SAME FORMAT AS LINEAR / QUADRATIC>

双散列的输出之间唯一的区别是增加了一行 r_value:<int>。 紧接在该行下方的输出应与线性输出相同 和二次探查,如上所述。 请在“不”之间添加下划线 和“找到”。

正确输出的示例(数字不代表实际表):

number_of_elements: 200
size_of_table: 750
load_factor: 0.266666
average_collisions: 0.0135
total_collisions: 3
hill Found 1
skiny Not_Found 3
baked Found 1

对于拼写检查(第三部分),输出应如下所示。

<word1> is CORRECT
<word2> is CORRECT
<word3> is INCORRECT
*** <word3> -> <alternate word> *** case <TYPE: A, B or C>
*** <word3> -> <alternate word> *** case <TYPE: A, B or C>
<word4> is CORRECT

请确保您的空格,大写字母和换行符正确无误。 请在输出中包括***和->。 这里显示的单词列表是一个 例如,实际输出将取决于文档文件中的单词。 可能有 每个案例类型有一个以上的结果。

正确输出的示例:(显示的单词不代表实际值 输入)

country is CORRECT
likely is CORRECT
climbing is CORRECT
lwa is INCORRECT
*** lwa -> wa *** case B
*** lwa -> la *** case B
*** lwa -> law *** case C
cases is CORRECT

 

 

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • ProfSnail
    ProfSnail 2021-03-29 17:29
    已采纳

    谢邀,私信沟通一手。

    点赞 评论
  • weixin_47375012
    weixin_47375012 2021-03-29 18:12

    已经有人在帮我处理了,谢谢各位大佬

    点赞 评论

相关推荐