2020-11-12 跳表

#include <limits.h>
#include <vector>
#include <iostream>
using namespace std;

struct SKNode
{
	int key;
	int value;
	int level;
	SKNode **next;
	SKNode(int iKey, int iValue, int iLevel) :key(iKey), value(iValue), level(iLevel)
	{
		next = new SKNode *[iLevel];
	}
	void print()
	{
		std::cout << "--------------" << std::endl;
		std::cout << "key = " << key << ", value = " << value << std::endl;
		std::cout << "--------------" << std::endl;
	}
};

class SkipList
{
public:
	SkipList(double iProb, int iMaxLevel);
	~SkipList();
	SKNode *find(int iKey);
	void insert(int iKey, int iValue);
	void erase(int iKey);
	void print();
private:
	int getLevel();
	SKNode *search(int iKey,vector<SKNode *>&ovNodes);
private:
	int m_curLevel;         //当前最大层数
	const int m_maxLevel;   //跳表最大层数
	double m_probability;   //生成下一层的概率
	SKNode *m_pHeadNode;    //跳表头结点,头结点的key最小
	SKNode *m_pTailNode;    //跳表尾部结点,尾结点的key最大
};

SkipList::SkipList(double iProb=0.5, int iMaxLevel=10)
	:m_probability(iProb), m_maxLevel(iMaxLevel), m_curLevel(0)
{
	m_pHeadNode = new SKNode(INT_MIN, 0, m_maxLevel);
	m_pTailNode = new SKNode(INT_MAX, 0, m_maxLevel);
	//将头尾结点连结起来
	for (int i = 0; i < m_maxLevel;++i)
	{
		m_pHeadNode->next[i] = m_pTailNode;
	}
}

SkipList::~SkipList()
{
	SKNode *pNext = nullptr;
	while (m_pHeadNode!=m_pTailNode)
	{
		pNext = m_pHeadNode->next[0];
		delete m_pHeadNode;
		m_pHeadNode = pNext;
	}
	delete m_pTailNode;
}

int SkipList::getLevel()
{
	int iCutNum = 1000 * m_probability;
	int iRandNum = rand() % 1001;
	int iLevel = 1;
	while (iRandNum<=iCutNum)
	{
		iLevel++;
		iRandNum = rand() % 1001;
	}
	return iLevel;
}

SKNode *SkipList::search(int iKey, vector<SKNode *>&ovNodes)
{
	//逐层从上向下查找，直到找到第一个不小于指定key的节点
	ovNodes.resize(m_curLevel);
	SKNode *node = m_pHeadNode;
	for (int i = m_curLevel-1; i >= 0; --i)
	{
		
		while (node->next[i]->key < iKey)
		{
			int temp = node->next[i]->key;
			node = node->next[i];
		}
		ovNodes[i]=node;
	}
	return node->next[0];
}

SKNode *SkipList::find(int iKey)
{
	//逐层从上向下查找，直到找到第一个不小于指定key的节点
	vector<SKNode *>vNodes;
	SKNode *node = search(iKey, vNodes);
	if (node->key == iKey)
	{
		return node;
	}
	return nullptr;
}

void SkipList::insert(int iKey, int iValue)
{
	vector<SKNode *>vNodes;
	SKNode *node = search(iKey, vNodes);
	if (node->key == iKey)
	{
		node->value=iValue;
		return;
	}
	int iLevel = getLevel();
	SKNode *pNewNode = new SKNode(iKey, iValue, iLevel);
	if (iLevel>m_maxLevel)
	{
		iLevel = m_maxLevel;
	}
	if (iLevel>m_curLevel)
	{
		for (int i = m_curLevel; i < iLevel;++i)
		{
			vNodes.push_back(m_pHeadNode);
		}
		m_curLevel = iLevel;
	}
	for (int i = 0; i < iLevel; ++i)
	{
		pNewNode->next[i] = vNodes[i]->next[i];
		vNodes[i]->next[i] = pNewNode;
	}
}

void SkipList::erase(int iKey)
{
	vector<SKNode *>vNodes;
	SKNode *node = search(iKey, vNodes);
	if (node->key != iKey)
	{
		return;
	}
	for (int i = 0; i < m_curLevel&&vNodes[i]->next[i]==node; ++i)
	{
		vNodes[i]->next[i] = node->next[i];
	}
	while (m_curLevel>=0&&m_pHeadNode->next[m_curLevel]==m_pTailNode)
	{
		--m_curLevel;
	}
	delete node;
}

void SkipList::print()
{
	cout << "output all node->" << endl;
	SKNode* node, *nextNode;
	for (int i = m_curLevel-1; i >= 0; i--)
	{
		node = m_pHeadNode->next[0];
		cout << "第" << i+1 << "层" << "->";
		while (node != m_pTailNode) {
			cout << "(k=" << node->key << " , v=" << node->value << ")";
			if (node->next[0]!=m_pTailNode)
			{
				cout << " -> ";
			}
			node = node->next[i];
		}
		cout << endl;
	}
	cout << "--------------" << endl;
}

int main()
{
	SkipList list;
	list.insert(1, 100);
	list.insert(3, 300);
	list.insert(2, 200);
	list.insert(7, 700);
	list.insert(6, 600);
	list.insert(4, 400);
	list.insert(5, 500);
	list.print();

	SKNode* node = list.find(3);
	if (node)
		node->print();
	else
		cout << "find node not exist" << endl;

	list.erase(3);
	list.print();

	node = list.find(3);
	if (node)
		node->print();
	else
		cout << "find node not exist" << endl;
	system("pause");
}