0

我刚开始使用哈希表和链表，我被分配了涉及它们的任务。

我将使用文本文件“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”中每个字符串的哈希值，如果哈希值相同，增加一个计数器来计算冲突次数？不太确定我将如何去做。

我不知道如何计算“执行的操作数”。对此有什么想法吗？

再次注意：“操作数”是指每个单词在链表中访问的节点数。

非常感谢任何关于我应该如何解决这些问题的提示/帮助。

4

0 回答 0