我刚开始使用哈希表和链表,我被分配了涉及它们的任务。
我将使用文本文件“words.txt”作为带有链接列表的哈希表来创建字典,以对名为“gettysburg_address.txt”的文本文件进行拼写检查。
我得到了“带链表的 HashTable 类”的源代码,如下所示:
哈希表.cpp
#include <string>
#include "listtools.h"
#include "listtools.cpp"
#include "hashtable.h"
using LinkedListSavitch::Node;
using LinkedListSavitch::search;
using LinkedListSavitch::headInsert;
using namespace std;
#define HASH_WEIGHT 31
namespace HashTableSavitch
{
HashTable::HashTable()
{
for (int i = 0; i < SIZE; i++)
{
hashArray[i] = NULL;
}
}
HashTable::~HashTable()
{
for (int i=0; i<SIZE; i++)
{
Node<string> *next = hashArray[i];
while (next != NULL)
{
Node<string> *discard = next;
next = next->getLink( );
delete discard;
}
}
}
unsigned int HashTable::computeHash(string s) const
{
unsigned int hash = 0;
for (unsigned int i = 0; i < s.length( ); i++)
{
hash = HASH_WEIGHT * hash + s[i];
}
return hash % SIZE;
}
bool HashTable::containsString(string target) const
{
int hash = this->computeHash(target);
Node<string>* result = search(hashArray[hash], target);
if (result == NULL)
return false;
else
return true;
}
void HashTable::put(string s)
{
int hash = computeHash(s);
if (search(hashArray[hash], s) == NULL)
{
// Only add the target if it's not in the list
headInsert(hashArray[hash], s);
}
}
} // HashTableSavitch
我想执行以下操作:
1.显示任何拼写错误的单词(如果单词不在字典中,则认为拼写错误)
2.加载字典“words.txt”时统计Hash Table每个单元格的碰撞次数,每行存储/显示数据20个
3.计算拼写错误和正确的单词数 - 在每种情况下,计算执行的操作数并存储/显示这些数字 - 此外,存储/显示拼写错误和正确单词的平均操作数 - 注意: “操作数”是指每个单词在链表中访问的节点数
这是我到目前为止所拥有的:
主文件
#include <iostream>
#include <fstream>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <string>
#include "hashtable.h"
using namespace std;
using HashTableSavitch::HashTable;
void upToLow(string & str);
void removePunct(string & str);
int main()
{
HashTable h;
string currWord;
string word;
int countMisspelled = 0;
int countCorrect = 0;
//Get input from words.rtf
ifstream dictionary("words.txt");
//File checking
if (dictionary.fail())
{
cout << "File does not exist" << endl;
cout << "Exit program" << endl;
}
//Create the dictionary as a hash table
while(dictionary >> currWord)
{
h.put(currWord);
}
dictionary.close();
//Get input from gettysburg_address.txt
ifstream input("gettysburg_address.txt");
//File checking
if (input.fail())
{
cout << "File does not exist" << endl;
cout << "Exit program" << endl;
}
//Spell check gettysburg_address.txt
cout << "Misspelled words : " << endl;
cout << endl;
//If a word is not in the dictionary assume misspelled
while(input >> word)
{
removePunct(word);
upToLow(word);
if(h.containsString(word) == false)
{
countMisspelled++; // Increment misspelled words count
cout << word << " ";
if(countMisspelled % 20 == 0) // Display misspelled words 20 per line
{
cout << endl;
}
}
else
{
countCorrect++; // Increment correct words count
}
}
input.close();
cout << endl;
cout << endl;
cout << "Number of misspelled words : " << countMisspelled << endl;
cout << "Number of correct words : " << countCorrect << endl;
return 0;
}
/*Function to convert uppercase letters to lowercase*/
void upToLow(string & str)
{
for (unsigned int i = 0; i < strlen(str.c_str()); i++)
if (str[i] >= 0x41 && str[i] <= 0x5A)
str[i] = str[i] + 0x20;
}
/*Function to remove punctuation from string*/
void removePunct(string & str)
{
str.erase(remove_if(str.begin(), str.end(), static_cast<int(*)(int)>(&ispunct)),str.end());
}
到目前为止,我已经设法对给定的文本文件进行拼写检查,并显示拼写错误的单词以及“正确”和“拼写错误”的计数。但我真的不知道我应该怎么做来计算碰撞和操作。我的导师非常简要地介绍了哈希表和链表,所以我对此很陌生。
为了计算冲突次数,我是否会比较“words.txt”中每个字符串的哈希值,如果哈希值相同,增加一个计数器来计算冲突次数?不太确定我将如何去做。
我不知道如何计算“执行的操作数”。对此有什么想法吗?
再次注意:“操作数”是指每个单词在链表中访问的节点数。
非常感谢任何关于我应该如何解决这些问题的提示/帮助。