-4

私はこのコードを持っており、二次プローブ法を使用して再実装することを想定しています.私が持っているアルゴリズムは i = (i + count) % CAPACITY;. これをどうすればいいのかわからないので、助けていただければ幸いです。ハッシュ関数と next_index 関数を変更するだけだと思いますが、よくわかりません。再実装する必要があるコードは次のとおりです。ヘッダー ファイルは上部にあり、テンプレートは下部にあります。

#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib>    // Provides size_t

namespace main_savitch_12A
{
template <class RecordType>
class table
{
public:
    // MEMBER CONSTANT -- See Appendix E if this fails to compile.
    static const std::size_t CAPACITY = 811;
    // CONSTRUCTOR
    table( );
    // MODIFICATION MEMBER FUNCTIONS
    void insert(const RecordType& entry);
    void remove(int key);
    // CONSTANT MEMBER FUNCTIONS
    bool is_present(int key) const;
    void find(int key, bool& found, RecordType& result) const;
    std::size_t size( ) const { return used; }
private:
    // MEMBER CONSTANTS -- These are used in the key field of special records.
    static const int NEVER_USED = -1;
    static const int PREVIOUSLY_USED = -2;
    // MEMBER VARIABLES
    RecordType data[CAPACITY];
    std::size_t used;
    // HELPER FUNCTIONS
    std::size_t hash(int key) const;
    std::size_t next_index(std::size_t index) const;
    void find_index(int key, bool& found, std::size_t& index) const;
    bool never_used(std::size_t index) const;
    bool is_vacant(std::size_t index) const;
};
}
 #include "table1.template" // Include the implementation.
 #endif
 //End Of Header




#include <cassert>  // Provides assert
#include <cstdlib>  // Provides size_t

namespace main_savitch_12A
{
template <class RecordType>
const std::size_t table<RecordType>::CAPACITY; 

template <class RecordType>
const int table<RecordType>::NEVER_USED;

template <class RecordType>
const int table<RecordType>::PREVIOUSLY_USED;

template <class RecordType>
table<RecordType>::table( )
{
    std::size_t i;

    used = 0;
    for (i = 0; i < CAPACITY; ++i)
        data[i].key = NEVER_USED;  // Indicates a spot that's never been used.
}

template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
// Library facilities used: cassert
{
    bool already_present;   // True if entry.key is already in the table
    std::size_t index;        // data[index] is location for the new entry

    assert(entry.key >= 0);

    // Set index so that data[index] is the spot to place the new entry.
    find_index(entry.key, already_present, index);

    // If the key wasn't already there, then find the location for the new entry.
    if (!already_present)
    {
        assert(size( ) < CAPACITY);
        index = hash(entry.key);
        while (!is_vacant(index))
            index = next_index(index);
        ++used;
    }

    data[index] = entry;
}

template <class RecordType>
void table<RecordType>::remove(int key)
// Library facilities used: cassert
{
    bool found;        // True if key occurs somewhere in the table
    std::size_t index;   // Spot where data[index].key == key

    assert(key >= 0);

    find_index(key, found, index);
    if (found)
    {   // The key was found, so remove this record and reduce used by 1.
        data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.
        --used;
    }
}

template <class RecordType>
bool table<RecordType>::is_present(int key) const
// Library facilities used: assert.h
{
    bool found;
    std::size_t index;

    assert(key >= 0);

    find_index(key, found, index);
    return found;
}

template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
// Library facilities used: cassert.h
{
    std::size_t index;

    assert(key >= 0);

    find_index(key, found, index);
    if (found)
        result = data[index];
}

template <class RecordType>
inline std::size_t table<RecordType>::hash(int key) const
{
    return (key % CAPACITY);
}

template <class RecordType>
inline std::size_t table<RecordType>::next_index(std::size_t index) const
// Library facilities used: cstdlib
{
    return ((index+1) % CAPACITY);
}

template <class RecordType>
void table<RecordType>::find_index(int key, bool& found, std::size_t& i) const
// Library facilities used: cstdlib
{
std::size_t count; // Number of entries that have been examined

count = 0;
i = hash(key);
while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key))
{
    ++count;
    i = next_index(i);
}
found = (data[i].key == key);
}

template <class RecordType>
inline bool table<RecordType>::never_used(std::size_t index) const
{
return (data[index].key == NEVER_USED);
}

template <class RecordType>
inline bool table<RecordType>::is_vacant(std::size_t index) const
{
return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);
}
}
4

1 に答える 1

2

このコードを使用すると、線形プローブを実行できます

    index = hash(entry.key);
    while (!is_vacant(index))
        index = next_index(index);

template <class RecordType>
inline std::size_t table<RecordType>::next_index(std::size_t index) const
// Library facilities used: cstdlib
{
    return ((index+1) % CAPACITY);
}

マップがほぼいっぱいで、ハッシュが 23 を返したとします。次にテストするスロットは 24、25、26、27 などになります。

二次プロービングの違いは、スロットがいっぱいになったときにテストするスロットのパターンだけです。ハッシュが 23 を返すと仮定すると、テストする次のスロットは 23 + 1 = 24、次は 23 + 4 = 27、次は 23 + 9 = 32、次は 23 + 16 = 39 になります。パターンが見えますか？23 + n*n をテストするたびに。それが二次プロービングです。もちろん、現在行っているように、すべての値は mod CAPACITY にする必要があります。

つまり、ハッシュ関数を変更する必要はなく、insert 内の while ループだけです。

于 2013-04-24T05:48:51.713 に答える