首页 / 算法 / 数据结构与算法--跳跃链表
数据结构与算法--跳跃链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法--跳跃链表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5734字,纯文字阅读大概需要9分钟。
内容图文
![数据结构与算法--跳跃链表](/upload/InfoBanner/zyjiaocheng/839/85a6ac4be14845199c29acad8acf60a1.jpg)
一、什么是跳表
跳跃列表(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。
基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表,因此得名。所有操作都以对数随机化的时间进行。
跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”,这里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起来,每个元素都在 1/(1-p) 个列表中出现,而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在 O(log1/pn) 个列表中出现。例如在下面的跳表中寻找元素12:
二、具体实现
ps:此实现中跳表的层数我假设从1层开始,但是存储的时候由于使用的是数组,因此与实际相差1.
/*节点类*/ class SlipNode { public: SlipNode() { }; SlipNode(int level, int k, int value); ~SlipNode(); public: int m_k; int m_value; int m_level; SlipNode** m_ppforward; //可变前向指针数组 }; SlipNode::SlipNode(int level, int k, int value) :m_k(k), m_value(value) { m_level = level < 1 ? 1 : level; m_ppforward = new SlipNode*[m_level]; for (int i = 0; i < m_level; ++i) { m_ppforward[i] = NULL; } } SlipNode::~SlipNode() { cout << "index:" << m_k << " is deleted!" << endl; if (m_ppforward) delete[] m_ppforward; m_ppforward = NULL; }
/*跳表*/ class SlipList { public: SlipList(const int maxlevel = 16, const int maxbit = 32); ~SlipList(); void Insert(const int& key, const int& value); void Delete(const int& key); void Display(); int Random(); int SearchValue(const int& k); //根据索引关键字返回值,如果不存在则返回-1 SlipNode* SearchNode(const int& value); //根据值返回节点,如果不存在则返回NULL private: int RandomLevel(); private: SlipNode* m_phead; int m_level; //这是实际的层数,总比数组中存储的值大一 const int MAX_LEVEL; const int MAX_BIT; int m_random_bit; int m_bit_left; }; SlipList::SlipList(const int maxlevel, const int maxbit) :m_level(1), MAX_LEVEL(maxlevel), MAX_BIT(maxbit), m_bit_left(MAX_BIT) { m_phead = new SlipNode(MAX_LEVEL, -1, -1); m_random_bit = Random(); } SlipList::~SlipList() { if (m_phead) { SlipNode* p = m_phead; while (p) { m_phead = p->m_ppforward[0]; delete p; p = m_phead; } } } int SlipList::Random() { srand(time(0)); return rand(); } int SlipList::RandomLevel() { int level = 1; int b; do { b = m_random_bit & 3; //1/4概率为0,也就是说层数增加的概率是(1/4)^n if (!b) level++; m_random_bit >>= 2; m_bit_left -= 2; if (m_bit_left == 0) { m_random_bit = Random(); m_bit_left = MAX_BIT; } } while (!b); return (level > (MAX_LEVEL - 1) ? (MAX_LEVEL - 1) : level); } int SlipList::SearchValue(const int& k) { int l = m_level; SlipNode* p = m_phead; SlipNode* q = NULL; while (l > 0) { while ((p = p->m_ppforward[l-1]) && (p->m_k < k)) q = p; l--; } if (!q || q->m_k != k) { return -1; } return q->m_value; } SlipNode* SlipList::SearchNode(const int& value) { int l = m_level; SlipNode* p = m_phead; SlipNode* q = NULL; while (l > 0) { while ((q = p->m_ppforward[l-1]) && (q->m_value < value)) p = q; l--; } if (!q || q->m_value != value) { return NULL; } return q; } void SlipList::Insert(const int& key, const int& value) { int l = m_level; SlipNode** update = new SlipNode*[MAX_LEVEL]; SlipNode* p = m_phead; SlipNode* q = NULL; int level = RandomLevel(); while (l > 0) { while (q = p->m_ppforward[l - 1]) { if(q->m_value < value) p = q; } update[l-1] = p; l--; } if (q && q->m_value == value) { q->m_value = value; delete[] update; update = NULL; return; } if (level > m_level) { level = ++m_level; //这个地方有小问题,因为毕竟层次是有限的,如果m_level+1后大于MAX_LEVEL update[level-1] = m_phead; //就会出错,但是层数越大概率越小,因此可近乎认为不可能超过MAX_LEVEL } q = new SlipNode(level, key, value); while (level > 0) { p = update[level-1]; q->m_ppforward[level-1] = p->m_ppforward[level-1]; p->m_ppforward[level-1] = q; level--; } delete[] update; update = NULL; } void SlipList::Delete(const int& key) { int level = m_level; int curlevel = m_level; SlipNode** update = new SlipNode*[MAX_LEVEL]; SlipNode* p = m_phead; SlipNode* q = NULL; while (level > 0) { while ((q = p->m_ppforward[level-1]) && (q->m_k < key)) p = q; update[level-1] = p; level--; } if (q->m_k != key) { delete[] update; update = NULL; return; } for (level = 1; level <= curlevel && (p = update[level-1])->m_ppforward[level-1] == q; ++level) { p->m_ppforward[level-1] = q->m_ppforward[level-1]; } delete q; while (curlevel > 0 && m_phead->m_ppforward[curlevel-1] == NULL) { curlevel--; } m_level = curlevel; delete[] update; update = NULL; } void SlipList::Display() { cout << "list level:" << m_level << endl; for (SlipNode* p = m_phead->m_ppforward[0]; p; p = p->m_ppforward[0]) { cout << "key: " << p->m_k << " value: " << p->m_value << " level: " << p->m_level << endl; } }
上述代码在vs2015环境下测试通过,一下是测试代码:
/*测试*/ int main(int argc, char* argv[]) { SlipList* list = new SlipList(); for (int i = 1; i <= 5; ++i) { list->Insert(i, i + 100); } list->Display(); list->Delete(2); cout << "delete key = 2:" << endl; list->Display(); delete list; list = NULL; system("pause"); return 0; }
三、总结:
从这个程序我认识到:
1、指针数组在堆中分配后,必须手动销毁每一个指针,不能指望delete[]整个数组来释放所有内存;
2、使用类的初始化表达式时,不能假设编译器先对哪个变量的赋值,血的教训!!
3、同时我也学会了动态申请指针数组
出彩的地方:
使用 “&” 方法来模拟概率:如任意数和3(二进制)相与,只用四分之一的可能的到0.
问题:
指针变量在生命周期结束后不会自动调用析构函数???
问题的解:
重新回顾对象析构函数何时调用:
1、对象生命周期结束后(对于在栈中创建的对象)
2、指针所指向的在堆中分配的对象,必须手动调用delete来释放内存,此时才会调用析构函数
3、如果a是b的成员,那么当b的析构函数被调用时,a的析构函数也会被调用。
四、资料引用
条目一(什么是跳表)内容来自于 《作者:xiao囡囡 来源:CSDN 原文:https://blog.csdn.net/kuaile123/article/details/22584477》
内容总结
以上是互联网集市为您收集整理的数据结构与算法--跳跃链表全部内容,希望文章能够帮你解决数据结构与算法--跳跃链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。