c++ - 字符串下标超出范围，使用散列 ADT

Question

我的散列程序遇到了问题，我不断收到字符串下标超出范围错误，但它没有告诉我它是在哪一行引起的。我想知道是什么导致了这个错误并阻止我正确输出我的文件。

下图显示了我的错误。

这是我编译程序的文件：

客户端.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：

#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;
       //nextPtr->setItem(newEntry);
       //nextPtr->setKey(itemKey);
   }
   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);
        }


        int getHashIndex(const KeyType& itemKey) const
        {
            int key = 0;
            int i = 0;
            while (isalpha(searchKey[i]))
            {
                key += searchKey[i];
                i++;
            }
            return key % hashTableSize;
        }

        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：

#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

标签： c++oophashadt

Answer 1

1. 当您启动程序时，运行调试器。
2. 当出现该错误对话框时，单击Retry。这将使您进入调试器，显示标准库中捕获错误的代码。但这并不是你真正感兴趣的。
3. 在 Visual Studio 中单击调试 → Windows → 调用堆栈。这将显示当前正在运行的函数以及调用了其他函数的列表。您的代码将在此堆栈上。
4. 单击显示代码的行，调试器将显示出现问题的代码。这也会将调试上下文更改为该函数。
5. 然后，您可以使用 Debug → Windows → Locals 来查看当时的变量是什么。

这是一项重要的调试技术，您将非常需要它并且很快就会记住它。