Дважды связанный список с пропуском списка для вставки в отсортированном виде
Я прочитал о пропущенном списке в Интернете, и я только что получил представление о том, как он работает с различными структурами данных и все такое. Но я действительно хочу реализовать список пропусков с двусвязным списком, так как я хочу отсортировать двусвязный список во время вставки. Означает, что когда элемент вставляется в то время, он должен быть вставлен только отсортированным способом.
Здесь я реализую метод для вставки данных в двусвязный список в отсортированном виде, но это занимает много времени, чтобы вставить данные и составить список в отсортированном виде, когда количество элементов очень велико.
Скажите, пожалуйста, как я могу добавить список пропущенных Algo в мою существующую функцию, или мне нужно переписать все заново? Любая помощь с внедрением будет оценена
Вот код:
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);
}
}
}
1
Решение
Прелесть списка пропусков состоит в том, что он сортирует элементы данных, а также предлагает o (log n) вставить и удалить сложность по времени. Чтобы сделать его более понятным, представьте, что в вашем связанном списке имеются сокращения или якоря, так что вам не нужно обходить весь список, чтобы найти позицию для вставки элемента. Вы просто следуете за якорями, таким образом, это двойной список с якорями быстрого доступа.
Что касается реализации, если вы не намерены использовать список пропусков для многопоточного доступа, его реализация становится тривиальной. Нет причин объединять список пропусков со списком с двойной связью, но вы можете реализовать список пропусков как список с двумя связями
смотреть на
http://www.sanfoundry.com/cpp-program-implement-skip-list/
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
1
Web-Answers © 2024
Наверх