2

インターネットでスキップリストについて読んだところ、さまざまなデータ構造とすべてでそれがどのように機能するかがわかった. しかし、挿入時に二重連結リストをソートしたいので、二重連結リストでスキップリストを実装したいと本当に思っています。その時点で要素を挿入するときは、ソートされた方法でのみ挿入する必要があることを意味します。

ここでは、二重連結リストにデータをソートして挿入するメソッドを実装していますが、要素数が非常に多い場合、データを挿入してリストをソートして作成するのに時間がかかります。

既存の関数にスキップ リスト アルゴを追加する方法を教えてください。または、すべてを書き直す必要がありますか? 実装の助けをいただければ幸いです

コードは次のとおりです。

void DoubleList::addSorted(int value)
{
    IDoubleNode * tempNode = new DoubleNode();
    tempNode->setValue(value);
    // if double link list is empty 
    if(getHead() == NULL)
    {
        // temp node already has NULL value in next and prev.
        setHead(tempNode);
        setTail(tempNode);
    }
    else if(value <= getHead()->getValue())
    {
        tempNode->setNext(getHead());// set tempnode next as current head.
        tempNode->setPrev(getHead()->getPrev()); // set previous
        getHead()->setPrev(tempNode); // set previous pointer of head to tempnode which we just inserted
        setHead(tempNode); // set head
        getHead()->setPrev(NULL);// for safer side. we already done this.
    }
    else
    {
        int found = 0;
        IDoubleNode *currNode = getHead();
        while(currNode->getNext() != NULL && found == 0)
        {
            if(currNode->getNext()->getValue() > tempNode->getValue())
            {
                found = 1;
            }
            else
            {
                currNode = currNode->getNext();
            }
        }
        if(found)
        {
            tempNode->setNext(currNode->getNext());
            currNode->getNext()->setPrev(tempNode);
            currNode->setNext(tempNode);
            tempNode->setPrev(currNode);
        }
        else
        {
            currNode->setNext(tempNode);
            tempNode->setPrev(currNode);
            tempNode->setNext(NULL);
            setTail(tempNode);
        }
    }
}
4

2 に答える 2

1

スキップリストの優れた点は、データ項目をソートし、o(log n) の挿入と削除の時間の複雑さを提供することです。わかりやすくするために、項目を挿入する位置を見つけるためにリスト全体をトラバースする必要がないように、リンクされたリストにショートカットまたはアンカーがあると想像してください。アンカーをたどるだけなので、クイック アクセス アンカーを含む二重リンク リストです。

実装に関しては、マルチスレッド アクセスにスキップ リストを使用するつもりがない場合、実装は簡単になります。スキップリストを二重リンクリストと組み合わせる理由はありませんが、スキップリストを二重リンクリストとして実装できます

http://www.sanfoundry.com/cpp-program-implement-skip-list/を見て ください。

于 2015-02-14T16:42:05.180 に答える
1

これがお役に立てば幸いです。

#ifndef SkipList_h
#define SkipList_h
///////////////////////////////////////////////////////////////////////////////

template<typename K, typename V, int MAXLEVEL>
class SkipListNode
{

public:
    SkipListNode()
    {
        for(int i=1; i<=MAXLEVEL;i++){
            next[i] = nullptr;
            prev[i] = nullptr;
        }
    }

    SkipListNode(K searchKey):key(searchKey)
    {
        for(int i=1; i<=MAXLEVEL;i++){
            next[i] = nullptr;
            prev[i] = nullptr;
        }
    }

    SkipListNode(K searchKey, V val):key(searchKey),value(val)
    {
        for(int i=1; i<=MAXLEVEL;i++){
            next[i] = nullptr;
            prev[i] = nullptr;
        }
    }

    // custom memory management
   // static void * operator new(size_t size);

  //  static void operator delete( void *deadObject, size_t size );


    K key;
    V value;
    SkipListNode<K, V, MAXLEVEL>* next[MAXLEVEL+1];
    SkipListNode<K, V, MAXLEVEL>* prev[MAXLEVEL+1];
private:
   // static MemoryPool<SkipListNode> memPool; // memory pool for SkipListNode
};

// template<typename K, typename V, int MAXLEVEL>
// MemoryPool< SkipListNode<K, V, MAXLEVEL> > SkipListNode<K, V, MAXLEVEL>::memPool;

// template<typename K, typename V, int MAXLEVEL>
// inline void * SkipListNode<K, V, MAXLEVEL>::operator new ( size_t size )
// {
//     return memPool.allocate();
// }

// template<typename K, typename V, int MAXLEVEL>
// inline void SkipListNode<K, V, MAXLEVEL>::operator delete( void *p, size_t size )
 //{
 //    memPool.deallocate( static_cast<SkipListNode<K, V, MAXLEVEL> *>(p) );
 //}


///////////////////////////////////////////////////////////////////////////////

template<typename K, typename V, int MAXLEVEL = 16>
class SkipList
{
public:
    typedef K keyType;
    typedef V ValueType;
    typedef SkipListNode<K, V, MAXLEVEL> NodeType;
    const int maxLevel;

    SkipList(K min_key, K max_key)
                                :pHeader(nullptr), pTail(nullptr),
                                maxCurrLevel(1), maxLevel(MAXLEVEL),
                                minKey(min_key), maxKey(max_key)
    {
        pHeader = new NodeType(minKey);
        pTail = new NodeType(maxKey);

        for( int i = 1; i<=MAXLEVEL; i++){
            pHeader->next[i] = pTail;
            pTail->prev[i] = pHeader;
        }
    }

    virtual ~SkipList()
    {

        delete pHeader;
        delete pTail;
    }

    void removeAll()
    {
        NodeType* curNode = pHeader->next[1];
        while(curNode != pTail){
            NodeType* temp = curNode;
            curNode = curNode->next[1];
            delete temp;
        }
    }

    std::string printList()
    {
        std::stringstream sstr;
        NodeType* currNode = pHeader->next[1];
        while ( currNode != pTail ) {
            sstr << "(" << currNode->key << "," << currNode->value << ")" << std::endl;
            currNode = currNode->next[1];
        }
        return sstr.str();
    }

    NodeType* insert( K searchKey, V newValue );

    void removeKey( K searchKey );
    void removeKey( NodeType* curNode );

    NodeType* search(const K& key, NodeType** prev   );

private:
    K minKey;
    K maxKey;
    int maxCurrLevel;
    SkipListNode<K, V, MAXLEVEL>* pHeader;
    SkipListNode<K, V, MAXLEVEL>* pTail;

    double uniformRandom()
    {
        return rand() / double(RAND_MAX);
    }

    int randomLevel() {
        int level = 1;
        double p = 0.5;
        while ( uniformRandom() < p && level < MAXLEVEL ) {
            level++;
        }
        return level;
    }
};

template<typename K, typename V, int MAXLEVEL>
typename SkipList<K, V, MAXLEVEL>::NodeType* SkipList<K, V, MAXLEVEL>::search(const K& searchKey, NodeType** prev )
{
    NodeType* currNode = nullptr;

    currNode = pHeader;
    for (int level=maxCurrLevel; level>=1; level--) {
        // Start our search at previous level's predecessor

        while (currNode->next[level]->key < searchKey) {
            currNode = currNode->next[level];

        }
        if ( prev != nullptr) {
            prev[level] = currNode;
        }

        //currNode = currNode->next[level];
        /*
        if ( next != nullptr) {
            next[level] = currNode;
        }*/
    }

    currNode = currNode->next[1];
    return currNode;
}

template<typename K, typename V, int MAXLEVEL>
typename SkipList<K, V, MAXLEVEL>::NodeType*  SkipList<K, V, MAXLEVEL>::insert( K searchKey, V newValue )
{
    SkipListNode<K, V, MAXLEVEL>** next = nullptr;
    SkipListNode<K, V, MAXLEVEL>* prev[MAXLEVEL];

    auto foundNode = search(searchKey, prev);


    int newLevel = randomLevel();
    //std::cout<< "Level: "<<newLevel<< std::endl;

    if ( newLevel > maxCurrLevel ) {
        for ( int level = maxCurrLevel+1; level <= newLevel; level++ ) {
            prev[level] = pHeader;
        }

        maxCurrLevel = newLevel;
    }

    NodeType* curNode = new NodeType(searchKey, newValue);

    for ( int level = 1; level<=maxCurrLevel; level++ ) {
        curNode->next[level] = prev[level]->next[level];
        curNode->prev[level] = prev[level];
        prev[level]->next[level]->prev[level] = curNode;
        prev[level]->next[level] = curNode;
    }
    return curNode;
}

template<typename K, typename V, int MAXLEVEL>
void SkipList<K, V, MAXLEVEL>::removeKey( K searchKey)
{

    SkipListNode<K, V, MAXLEVEL>** prev1 = nullptr;

    auto curNode = search(searchKey, prev1);


    //std::cout<<curNode <<" -> "<< curNode->key<< std::endl;
    if ( curNode && curNode->key == searchKey ) {

        auto prev = curNode->prev;

        for ( int level = 1; level<=maxCurrLevel; level++ ) {

            if ( prev[level]->next[level] != curNode ) {
                break;
            }

            prev[level]->next[level] = curNode->next[level];
            curNode->next[level]->prev[level] = prev[level];
        }

        delete curNode;

        while ( maxCurrLevel > 1 && pHeader->next[maxCurrLevel] == pTail) {
            maxCurrLevel--;
        }

        //std::cout << "maxCurrLevel: "<<maxCurrLevel<<std::endl;
    }

}


template<typename K, typename V, int MAXLEVEL>
void SkipList<K, V, MAXLEVEL>::removeKey( typename SkipList<K, V, MAXLEVEL>::NodeType* curNode )
{
    if ( curNode && curNode == curNode->next[1]->prev[1] && curNode == curNode->prev[1]->next[1] ) {
       // std::cout<<curNode <<" -> "<< curNode->key<< std::endl;

        auto prev = curNode->prev;

        for ( int level = 1; level<=maxCurrLevel; level++ ) {

            if ( prev[level]->next[level] != curNode ) {
                break;
            }

            prev[level]->next[level] = curNode->next[level];
            curNode->next[level]->prev[level] = prev[level];
        }

        delete curNode;

        while ( maxCurrLevel > 1 && pHeader->next[maxCurrLevel] == pTail ) {
            maxCurrLevel--;
        }
    }
}


#endif
于 2015-02-24T17:32:37.363 に答える