c++ - 实现散列 ADT 时发生读取访问冲突
问题描述
我正在开发一个哈希程序，它根据日期、邮政编码、性别等读取名人的文件。我已经在程序中取得了相当大的进步，但我一直被一个错误难住了好几个小时，这并没有让我编译我的程序。任何帮助或指导至少让我的程序运行的正确方向将不胜感激。将发布使用以下程序所需的文件以及我收到的错误消息。
在 Dictionary.exe 中的 0x006BEE72 处引发异常：0xC0000005：访问冲突读取位置 0xCDCDCE7D。抛出未处理的异常：读取访问冲突。 endEntry为 0xCDCDCDCD。
HashedEntry.h 的第 41 行出现错误，如下所示：
while (endEntry->nextPtr != nullptr) // <---- error gets triggered here
{
endEntry = endEntry->nextPtr;
}
客户端.cpp：
#include <iostream>
#include <fstream>
#include <cassert>
#include "HashedDictionary.h"
using namespace std;
struct FamousPerson {
string id;
char taxStatus;
string lastname;
string firstname;
int age;
string street;
string zip;
};
void readOnePerson(istream& infile, FamousPerson& readMe);
// the insertion operator overload is just here so that the HashedDictionary
// display function can use it to print FamousPerson objects.
ostream& operator<<(ostream& out, const FamousPerson& printMe);
int main() {
HashedDictionary<string, FamousPerson> h;
FamousPerson tempPerson;
ifstream infile("famous.txt");
assert(infile);
readOnePerson(infile, tempPerson);
while (infile) {
h.add(tempPerson.lastname, tempPerson);
cout << tempPerson << endl;
readOnePerson(infile, tempPerson);
}
h.display();
}
ostream& operator<<(ostream& out, const FamousPerson& printMe) {
out << printMe.id << " ";
out << printMe.taxStatus << " ";
out << printMe.lastname << " ";
out << printMe.firstname << " ";
out << printMe.age << " ";
out << printMe.street << " ";
out << printMe.zip;
return out;
}
void readOnePerson(istream& infile, FamousPerson& readMe) {
infile >> readMe.id;
infile >> readMe.taxStatus;
infile >> readMe.lastname;
infile >> readMe.firstname;
infile >> readMe.age;
infile >> readMe.street;
infile >> readMe.zip;
}
HashedEntry.h：
/** A class of entry objects for a hashing implementation of the
ADT dictionary.
@file HashedEntry.h */
#ifndef _HASHED_ENTRY
#define _HASHED_ENTRY
#include "Entry.h"
template<class KeyType, class ItemType>
class HashedEntry : public Entry<KeyType, ItemType>
{
private:
HashedEntry<KeyType, ItemType>* nextPtr;
public:
HashedEntry()
{
nextPtr = nullptr;
}
HashedEntry(ItemType newEntry, KeyType itemKey):Entry<KeyType,ItemType>(newEntry, itemKey)
{
nextPtr = nullptr;
}
HashedEntry(ItemType newEntry, KeyType itemKey, HashedEntry<KeyType, ItemType>* nextEntryPtr) :Entry<KeyType, ItemType>(newEntry, itemKey)
{
nextPtr->setItem(newEntry);
nextPtr->setKey(itemKey);
nextPtr = nextEntryPtr;
}
void setNext(HashedEntry<KeyType, ItemType>* nextEntryPtr)
{
HashedEntry<KeyType, ItemType>* newEntry = nextPtr;
HashedEntry<KeyType, ItemType>* endEntry = nextEntryPtr;
while (endEntry->nextPtr != nullptr)
{
endEntry = endEntry->nextPtr;
}
endEntry->nextPtr = nextEntryPtr;
endEntry = nullptr;
nextPtr = nextEntryPtr;
}
HashedEntry<KeyType, ItemType>* getNext() const
{
return nextPtr;
}
}; // end HashedEntry
//#include "HashedEntry.cpp"
#endif
哈希字典.h：
#include <string>
#include <cstdlib>
#include<iostream>
#include "DictionaryInterface.h"
#include "HashedEntry.h"
#ifndef _HASHED_DICTIONARY
#define _HASHED_DICTIONARY
using namespace std;
template< class KeyType, class ItemType>
class HashedDictionary : public DictionaryInterface<KeyType, ItemType>
{
private:
HashedEntry<KeyType, ItemType>** hashTable;
int itemCount; // Count of dictionary entries
int hashTableSize; // Table size must be prime
static const int DEFAULT_SIZE = 101;
public:
int hFunction(const KeyType& x) const
{
int num = Hrule(x) % hashTableSize;
return num;
}
int Hrule(const KeyType& ph) const
{
int numForm = 0;
for (int i = 0; i < ph.length(); i++)
{
numForm = numForm * 128 + ph[i];
}
return numForm;
}
HashedDictionary()
{
itemCount = 0;
hashTableSize = DEFAULT_SIZE;
hashTable = new HashedEntry<KeyType, ItemType> * [DEFAULT_SIZE];
}
HashedDictionary(int newHTableSize)
{
hashTableSize = newHTableSize;
itemCount = 0;
hashTable = new HashedEntry<KeyType, ItemType> * [newHTableSize];
}
bool isEmpty() const
{
return itemCount == 0;
}
int getNumberOfItems() const
{
return itemCount;
}
bool add(const KeyType& searchKey, const ItemType& newItem)
{
// Create entry to add to dictionary
HashedEntry<KeyType, ItemType>* entryToAddPtr =
new HashedEntry<KeyType, ItemType>(newItem, searchKey);
// Compute the hashed index into the array
int itemHashIndex = getHashIndex(searchKey);
// Add the entry to the chain at itemHashIndex
if (hashTable[itemHashIndex] == nullptr)
{
hashTable[itemHashIndex] = entryToAddPtr;
}
else
{
entryToAddPtr->setNext(hashTable[itemHashIndex]);
hashTable[itemHashIndex] = entryToAddPtr;
}
return true;
}
bool remove(const KeyType& searchKey)
{
bool itemFound = false;
// Compute the hashed index into the array
int itemHashIndex = getHashIndex(searchKey);
if (hashTable[itemHashIndex] != nullptr)
{
// Special case - first node has target
if (searchKey == hashTable[itemHashIndex]->getKey())
{
HashedEntry<KeyType, ItemType>* entryToRemovePtr =
hashTable[itemHashIndex];
hashTable[itemHashIndex] = hashTable[itemHashIndex]->getNext();
delete entryToRemovePtr;
entryToRemovePtr = nullptr; // For safety
itemFound = true;
}
else // Search the rest of the chain
{
HashedEntry<KeyType, ItemType>* prevPtr = hashTable[itemHashIndex];
HashedEntry<KeyType, ItemType>* curPtr = prevPtr->getNext();
while ((curPtr != nullptr) && !itemFound)
{
// Found item in chain so remove that node
if (searchKey == curPtr->getKey())
{
prevPtr->setNext(curPtr->getNext());
delete curPtr;
curPtr = nullptr; // For safety
itemFound = true;
}
else // Look at next entry in chain
{
prevPtr = curPtr;
curPtr = curPtr->getNext();
}
}
}
}
return itemFound;
}
void clear()
{
for (int i = 0; i < hashTableSize; i++)
{
while (hashTable[i] != nullptr)
{
HashedEntry<KeyType,ItemType>* delPtr = hashTable[i];
hashTable[i] = hashTable[i]->getNext();
delete delPtr;
delPtr= nullptr;
}
}
itemCount = 0;
}
ItemType getItem(const KeyType& itemKey) const
{
assert(contains(itemKey));
int itemHashIndex = getHashIndex(itemKey);
HashedEntry<KeyType,ItemType>* chainPtr = hashTable[itemHashIndex];
while((chainPtr != nullptr) && itemKey != chainPtr->getKey())
{
chainPtr = chainPtr->getNext();
}
if (chainPtr == nullptr)
{
return chainPtr->getItem();
}
}
bool contains(const KeyType& searchKey) const
{
int ItemHashIndex = getHashIndex(searchKey);
HashedEntry<KeyType, ItemType>* chainPtr = hashTable[ItemHashIndex];
while ((chainPtr != nullptr) && (searchKey != chainPtr->getKey()))
{
chainPtr = chainPtr->getNext();
}
return (chainPtr != nullptr);
}
//Working on getHashIndex and display
int getHashIndex(const KeyType& itemKey) const
{
return hFunction(itemKey);
/*
int i = 0;
int key = itemKey[i] * 32;
i++;
while (isalpha(itemKey[i]))
{
key = (key + itemKey[i]) & DEFAULT_SIZE;
key *= 32;
i++;
}
return key % DEFAULT_SIZE;*/
}
void display()
{
int i = 0;
while (i < hashTableSize)
{
if (hashTable[i] != nullptr)
{
HashedEntry<KeyType, ItemType>* nextEntry = hashTable[i];
while (nextEntry != nullptr)
{
cout << nextEntry->getItem() << " ";
nextEntry = nextEntry->getNext();
}
cout << endl;
nextEntry = nullptr;
delete nextEntry;
}
i++;
}
}
};
#endif
入口.h：
/** A class of entry objects for an array-based implementation of the ADT dictionary.
Listing 18-2.
@file Entry.h */
#ifndef _ENTRY
#define _ENTRY
template <class KeyType, class ItemType>
class Entry
{
private:
ItemType item;
KeyType searchKey;
protected:
void setKey(const KeyType& itemKey)
{
searchKey = itemKey;
}
public:
Entry()
{
item = ItemType();
searchKey = KeyType();
}
Entry(ItemType newEntry, KeyType itemKey)
{
item = newEntry;
searchKey = itemKey;
}
ItemType getItem() const
{
return item;
}
KeyType getKey() const
{
return searchKey;
}
void setItem(const ItemType& newEntry)
{
item = newEntry;
}
}; // end Entry
//#include "Entry.cpp"
#endif
字典接口.h：
#ifndef _DICTIONARY_INTERFACE
#define _DICTIONARY_INTERFACE
template<class KeyType, class ItemType>
class DictionaryInterface
{
public:
/** Sees whether this dictionary is empty.
@return True if the dictionary is empty;
otherwise returns false. */
virtual bool isEmpty() const = 0;
/** Gets the number of items in this dictionary.
@return The number of items in the dictionary. */
virtual int getNumberOfItems() const = 0;
/** Inserts an item into this dictionary according to the item’s search key.
@pre The search key of the new item differs from all search
keys presently in the dictionary.
@post If the insertion is successful, newItem is in its
proper position within the dictionary.
@param searchKey The search key associated with the item to be inserted.
@param newItem The item to add to the dictionary.
@return True if item was successfully added, or false if not. */
virtual bool add(const KeyType& searchKey, const ItemType& newItem) = 0;
/** Removes an item with the given search key from this dictionary.
@post If the item whose search key equals searchKey existed in the dictionary,
the item was removed.
@param searchKey The search key of the item to be removed.
@return True if the item was successfully removed, or false if not. */
virtual bool remove(const KeyType& searchKey) = 0;
/** Removes all entries from this dictionary. */
virtual void clear() = 0;
/** Retrieves an item with a given search key from a dictionary.
@post If the retrieval is successful, the item is returned.
@param searchKey The search key of the item to be retrieved.
@return The item associated with the search key.
@throw NotFoundException if the item does not exist. */
virtual ItemType getItem(const KeyType& searchKey) const = 0;
/** Sees whether this dictionary contains an item with a given
search key.
@post The dictionary is unchanged.
@param searchKey The search key of the item to be retrieved.
@return True if an item with the given search key exists in the dictionary. */
virtual bool contains(const KeyType& searchKey) const = 0;
/** Traverses this dictionary and calls a given client function once for each item.
@post The given function’s action occurs once for each item in the
dictionary and possibly alters the item.
@param visit A client function. */
//virtual void traverse(void visit(ItemType&)) const = 0;
}; // end DictionaryInterface
#endif
解决方案
推荐阅读
- git - 如何在 Windows 10 上为 git 编辑和打开 core.editor？
- mysql - 如何优化数据库中的架构
- ruby-on-rails - 使用 Rails 设置 Shopify 定期计费 API
- angular6 - 如何使用 Angular Router 在 Ionic 4 中导航到带有选项卡的页面？
- three.js - 使用 SVGLoader 时能否获取 SVG 节点/父节点的属性信息？
- javascript - 从 mysql 字段中获取单行数据
- c# - Xamarin 表单中的可重用 ContentView
- scala - 使用 scala 从 EventHub 读取数据到 DataBricks 中的表
- excel - 运行时错误 438（工作中的继承宏）
- ios - 在 Objective-C 中快速解析联系人对象的电话号码