2014山东春季高考网站建设,南阳做网站推广,千万别去代理记账公司,做网站的盈利模式目录 作者有话说 为何要学习跳表#xff1f;为了快#xff0c;为了更快#xff0c;为了折磨自己..... 跳表作用场景 1.不少公司自己会设计哈希表#xff0c;如果解决哈希冲突是不可避免的事情。通常情况下会使用链址#xff0c;很好理解#xff0c;当有冲突产生时#…目录 作者有话说 为何要学习跳表为了快为了更快为了折磨自己..... 跳表作用场景 1.不少公司自己会设计哈希表如果解决哈希冲突是不可避免的事情。通常情况下会使用链址很好理解当有冲突产生时我们在附加的链表中添加一位(如果使用的循环双链表没直接在后面加效率很高O(1)。如果是单链表也可以使用头插法直接在头部添加效率很高O(1)如果使用跳表需要O(logN))。 2.看到这里不少朋友会觉得那需要什么跳表呀还变慢了。不要着急我们继续往下看首先使用简单的头差法得到的序列可以认为是乱序(不考虑依次插入是有序的)那么查找起来会变得比较费劲需要O(N)。但是使用跳表查找的平均效率是O(logN),插入O(logN),删除O(logN)。 【注意这里写的是平均情况如果跳表设计不好很容易导致跳表退化成链表】 3.跳表有时候可以代替红黑树和AVL树甚至说跳表的插入和删除的维护比AVL树代价低与红黑树差不多。 跳表的主要思想 二分二分还是二分 接触了这么久的编程会发现很多比较优秀的算法都是基于二分思想演变而来的。 至于算法如何选择需要结合具体的业务情况一个算法的最好时间复杂度、平均时间复杂度、最坏时间复杂度都是需要考虑的。两个相同功能的算法在不同应用场景下会有很大是差距即使平时我们都认为他们的时间复杂度都是O(logN). 与时间复杂度具有类似概念的就是空间复杂度了空间复杂度也是需要考虑的问题。一个占据CPU、一个占据内存.... 空间复杂度总是与时间复杂度此消彼长他们向一对冤家。但是通常情况下我们普遍接受在允许的内存消耗内选择最快的算法。天下武功为快不破.... 跳表的特点 1.单向链表(这个不是绝对的如果想居于范围查找使用双向链表会更快 未测试过) 2.有序保存(二分的前提条件) 3.支持添加、删除和查找 4.查找效率 O(logN) 跳表与普通链表的区别 普通单链表 对于普通的单链表越靠前的节点查找快。对于越靠后的节点查找效率越低。其平均效率 (1 2 3 ... n) / n (1/2 * n(a1an))/n (1 n) / 2 O(N) 简单的跳表 跳表的结构是通过建立高纬度的索引来减少低纬度从而达到任何元素的检索接近线性时间的目的O(logN)。其实跳表的思想并不复杂为了提高查找效率将中间节点提高维度在查找过程中逐步的对半减小查找过程。 跳表的建立 我们知道了跳表的基本思想后我们来手动模拟建立一个跳表。现在我们依次顺序插入1 5 8 3 2 7 9 这七个元素。 【我们采用间隔一个的方式提取高纬度的节点】 1.初始化 准备一个头部节点我们知道链表有两种方式(一种是有头节点的、一种是没有头节点的为了方便对第一个节点的操作我们统一使用有头节点的)。 注意指针域这里没有画出来 2.插入 1 像单链表一样直接将节点插入到右边就可以了。 注意: 空白部分代表指针指向NULL,防止野指针 3.插入 5 这里考虑将向上提取元素(也可以不提取)先查找需要查找的位置5 1所以插入到1的后面就可以了。 为了保证隔一个的一致性和写代码时少考虑一种情况我们还是向上提取 5 注意: 空白部分代表指针指向NULL,防止野指针 4. 插入 8 还是同样的道理我们需要提取查找8所需要查找的位置。8 5因为提前做了5的提升我们不需要比较1然后再比较5我们直接拿到5就可以知道8应该插入到5的后面跳表的优势就表现出来了。 【这个过程插入过程分成了两个步骤先在1维链表中插入8】 注意空白部分代表指针指向NULL,防止野指针 注意: 空白部分代表指针指向NULL,防止野指针 5.插入 3 我们先比较 5 3那么整个范围变成了 【1-5】然后 1 3 5 。那么需要将3插入到1和5之间 【将3插入按两个提取的原则需要将3提升然后 3、5在同一层需要将5提升】 注意空白部分代表指针指向NULL,防止野指针 6.插入 2 过程同上面一样。不做过多的解释了.... 【画图不易点个关注吧....只输出优质文章:大家有什么想算法可以下方留言】 注意空白部分代表指针指向NULL,防止野指针 7.插入 7 过程同上面一样。不做过多的解释了.... 注意空白部分代表指针指向NULL,防止野指针 8.插入 9 过程同上面一样。不做过多的解释了.... 注意空白部分代表指针指向NULL,防止野指针 【以上就是跳表建立的全部过程如果不明白可以加入微信C技术交流群C技术交流群-陈达叔】 【bilibili 搜索 陈达叔视频后续会更新感谢大家关注....创作不易点个关注吧...】 跳表的查找 跳表的查找很简单就是二分查找的逻辑为了更好的了解查找的过程我们来看下示例... 示例1 查找 3 先比较 5 3 5 查找范围变成 1-5之间 然后 header向下移动一位比较 3 3 找到 3 返回 true 示例2:查找 9 跳表的删除 跳表的查找很简单就是二分查找的逻辑为了更好的了解查找的过程我们来看下示例... 示例1删除 2 为了防止不断是增加层数过高我们可以做个调整 跳表的提取维度说明 不难发现跳表的实现就是对数据做了向上的冗余操作以时间换空间的的典型。 当我们设置的冗余颗粒越小那么需要的空间越大。所以选择好的冗余颗粒度很重要这个需要根据具体情况而定。 再跳表存在一个随机函数其存在的意义是决定什么时候需要向上做冗余。实际的建造过程不会像我们示例一样的建造这样代价会比较高。为了防止跳表插入节点增加而导致退化成链表的情况我们通常通过一个随机函数来决定向上做提升的时刻。 跳表的代码 #pragma once
#ifndef SKIPLIST_ENTRY_H_
#define SKIPLIST_ENTRY_H_
/* 一个更具备代表性的泛型版本 */
#include ctime
#include cstdlibtemplatetypename T
class Entry {
private:int key; // 排序值T value; // 保存对象Entry* pNext;Entry* pDown;
public:Entry(int k, T v) :value(v), key(k), pNext(nullptr), pDown(nullptr) {}Entry(const Entry e) :value(e.value), key(e.key), pNext(nullptr), pDown(nullptr) {}public:/* 重载运算符 */bool operator(const Entry right) {return key right.key;}bool operator(const Entry right) {return key right.key;}bool operator(const Entry right) {return key right.key;}bool operator(const Entry right) {return key right.key;}bool operator(const Entry right) {return key right.key;}Entry* next() {return pNext;}Entry* down() {return pDown;}
};templatetypename T
class SkipList_Entry {
private:struct Endpoint {Endpoint* up;Endpoint* down;EntryT* right;};struct Endpoint* header;int lvl_num; // level_number 已存在的层数unsigned int seed;bool random() {srand(seed);int ret rand() % 2;seed rand();return ret 0;}
public:SkipList_Entry() :lvl_num(1), seed(time(0)) {header new Endpoint();}/* 插入新元素 */void insert(EntryT* entry) { // 插入是一系列自底向上的操作struct Endpoint* cur_header header;// 首先使用链表header到达L1while (cur_header-down ! nullptr) {cur_header cur_header-down;}/* 这里的一个简单想法是L1必定需要插入元素而在上面的各跳跃层是否插入则根据random确定因此这是一个典型的do-while循环模式 */int cur_lvl 0; // current_level 当前层数EntryT* temp_entry nullptr; // 用来临时保存一个已经完成插入的节点指针do {EntryT* cur_cp_entry new EntryT(*entry); // 拷贝新对象// 首先需要判断当前层是否已经存在如果不存在增新增cur_lvl;if (lvl_num cur_lvl) {lvl_num;Endpoint *new_header new Endpoint();new_header-down header;header-up new_header;header new_header;}// 使用cur_lvl作为判断标准!1表示cur_header需要上移并连接“同位素”指针if (cur_lvl ! 1) {cur_header cur_header-up;cur_cp_entry-down() temp_entry;}temp_entry cur_cp_entry;// 再需要判断的情况是当前所在链表是否已经有元素节点存在如果是空链表则直接对右侧指针赋值并跳出循环if (cur_header-right nullptr) {cur_header-right cur_cp_entry;break;}else {EntryT* cursor cur_header-right; // 创建一个游标指针while (true) { // 于当前链表循环向右寻找可插入点并在找到后跳出当前循环if (*cur_cp_entry *cursor) { // 元素小于当前链表所有元素插入链表头cur_header-right cur_cp_entry;cur_cp_entry-next() cursor;break;}else if (cursor-next() nullptr) { // 元素大于当前链表所有元素插入链表尾cursor-next() cur_cp_entry;break;}else if (*cur_cp_entry *cursor-next()) { // 插入链表中间cur_cp_entry-next() cursor-next();cursor-next() cur_cp_entry;break;}cursor cursor-next(); // 右移动游标}}} while(random());}/* 查询元素 */bool search(EntryT* entry) const {if (header-right nullptr) { // 判断链表头右侧空指针return false;}Endpoint* cur_header header;// 在lvl_num层中首先找到可以接入的点for (int i 0; i lvl_num; i) {if (*entry *cur_header-right) {cur_header cur_header-down;}else {EntryT* cursor cur_header-right;while (cursor-down() ! nullptr) {while (cursor-next() ! nullptr) {if (*entry *cursor-next()) {break;}cursor cursor-next();}cursor cursor-down();}while (cursor-next() ! nullptr) {if (*entry *cursor-next()) {cursor cursor-next();}else if (*entry *cursor-next()) {return true;}else {return false;}}return false; // 节点大于L1最后一个元素节点返回false}}return false; // 找不到接入点则直接返回false;}/* 删除元素 */void remove(EntryT* entry) {if (header-right nullptr) {return;}Endpoint* cur_header header;EntryT* cursor cur_header-right;int lvl_counter lvl_num; // 因为在删除的过程中跳跃表的层数会中途发生变化因此应该在进入循环之前要获取它的值。for (int i 0; i lvl_num; i) {if (*entry *cur_header-right) {EntryT* delptr cur_header-right;cur_header-right cur_header-right-next();delete delptr;}else {EntryT *cursor cur_header-right;while (cursor-next() ! nullptr) {if (*entry *cursor-next()) { // 找到节点-删除-跳出循环EntryT* delptr cursor-next();cursor-next() cursor-next()-next();delete delptr;break;}cursor cursor-next();}}// 向下移动链表头指针的时候需要先判断当前链表中是否还存在Entry节点if (cur_header-right nullptr) {Endpoint* delheader cur_header;cur_header cur_header-down;header cur_header;delete delheader;lvl_num--;}else {cur_header cur_header-down;}}}
};
#endif // !SKIPLIST_ENTRY_H_ 对于C的学习存在一个的最大问题就是很少可以交流的人甚至而言网上的资料又比较少。 如果对c有疑惑或者想要交流的朋友记得加入V Errrr113 坚持初心勇敢果断....至每一个热爱技术的朋友
文章转载自： http://www.morning.qhmhz.cn.gov.cn.qhmhz.cn http://www.morning.gediba.com.gov.cn.gediba.com http://www.morning.lfmwt.cn.gov.cn.lfmwt.cn http://www.morning.krgjc.cn.gov.cn.krgjc.cn http://www.morning.zrks.cn.gov.cn.zrks.cn http://www.morning.dcccl.cn.gov.cn.dcccl.cn http://www.morning.fxwkl.cn.gov.cn.fxwkl.cn http://www.morning.gthgf.cn.gov.cn.gthgf.cn http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.ntnml.cn.gov.cn.ntnml.cn http://www.morning.kfldw.cn.gov.cn.kfldw.cn http://www.morning.xsklp.cn.gov.cn.xsklp.cn http://www.morning.2d1bl5.cn.gov.cn.2d1bl5.cn http://www.morning.tqpnf.cn.gov.cn.tqpnf.cn http://www.morning.ryysc.cn.gov.cn.ryysc.cn http://www.morning.gmnmh.cn.gov.cn.gmnmh.cn http://www.morning.mwmxs.cn.gov.cn.mwmxs.cn http://www.morning.lyhrg.cn.gov.cn.lyhrg.cn http://www.morning.djmdk.cn.gov.cn.djmdk.cn http://www.morning.xmtzk.cn.gov.cn.xmtzk.cn http://www.morning.hpjpy.cn.gov.cn.hpjpy.cn http://www.morning.hdqqr.cn.gov.cn.hdqqr.cn http://www.morning.lwzpp.cn.gov.cn.lwzpp.cn http://www.morning.rqsnl.cn.gov.cn.rqsnl.cn http://www.morning.zzgkk.cn.gov.cn.zzgkk.cn http://www.morning.pgjyc.cn.gov.cn.pgjyc.cn http://www.morning.c7507.cn.gov.cn.c7507.cn http://www.morning.rsqpc.cn.gov.cn.rsqpc.cn http://www.morning.wrtxk.cn.gov.cn.wrtxk.cn http://www.morning.qnzpg.cn.gov.cn.qnzpg.cn http://www.morning.yrrnx.cn.gov.cn.yrrnx.cn http://www.morning.rlwcs.cn.gov.cn.rlwcs.cn http://www.morning.tkcz.cn.gov.cn.tkcz.cn http://www.morning.bppml.cn.gov.cn.bppml.cn http://www.morning.qlckc.cn.gov.cn.qlckc.cn http://www.morning.sgqw.cn.gov.cn.sgqw.cn http://www.morning.cnbdn.cn.gov.cn.cnbdn.cn http://www.morning.dfckx.cn.gov.cn.dfckx.cn http://www.morning.srsln.cn.gov.cn.srsln.cn http://www.morning.ftcrt.cn.gov.cn.ftcrt.cn http://www.morning.xbbrh.cn.gov.cn.xbbrh.cn http://www.morning.fnfxp.cn.gov.cn.fnfxp.cn http://www.morning.cgthq.cn.gov.cn.cgthq.cn http://www.morning.jwrcz.cn.gov.cn.jwrcz.cn http://www.morning.lmfxq.cn.gov.cn.lmfxq.cn http://www.morning.bpmtr.cn.gov.cn.bpmtr.cn http://www.morning.qwbht.cn.gov.cn.qwbht.cn http://www.morning.nktgj.cn.gov.cn.nktgj.cn http://www.morning.pkrtz.cn.gov.cn.pkrtz.cn http://www.morning.kscwt.cn.gov.cn.kscwt.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.hkgcx.cn.gov.cn.hkgcx.cn http://www.morning.zkqjz.cn.gov.cn.zkqjz.cn http://www.morning.lqrpk.cn.gov.cn.lqrpk.cn http://www.morning.xnymt.cn.gov.cn.xnymt.cn http://www.morning.mrttc.cn.gov.cn.mrttc.cn http://www.morning.zlgbx.cn.gov.cn.zlgbx.cn http://www.morning.mfnsn.cn.gov.cn.mfnsn.cn http://www.morning.rgdcf.cn.gov.cn.rgdcf.cn http://www.morning.xhpnp.cn.gov.cn.xhpnp.cn http://www.morning.kryr.cn.gov.cn.kryr.cn http://www.morning.xjqhh.cn.gov.cn.xjqhh.cn http://www.morning.bdtpd.cn.gov.cn.bdtpd.cn http://www.morning.gqflj.cn.gov.cn.gqflj.cn http://www.morning.sskhm.cn.gov.cn.sskhm.cn http://www.morning.tmjhy.cn.gov.cn.tmjhy.cn http://www.morning.dswtz.cn.gov.cn.dswtz.cn http://www.morning.hqgxz.cn.gov.cn.hqgxz.cn http://www.morning.wpcfm.cn.gov.cn.wpcfm.cn http://www.morning.dxgt.cn.gov.cn.dxgt.cn http://www.morning.gprzp.cn.gov.cn.gprzp.cn http://www.morning.qblcm.cn.gov.cn.qblcm.cn http://www.morning.sfdky.cn.gov.cn.sfdky.cn http://www.morning.lcwhn.cn.gov.cn.lcwhn.cn http://www.morning.ppbrq.cn.gov.cn.ppbrq.cn http://www.morning.wnhsw.cn.gov.cn.wnhsw.cn http://www.morning.krwzy.cn.gov.cn.krwzy.cn http://www.morning.ruyuaixuexi.com.gov.cn.ruyuaixuexi.com http://www.morning.ntgsg.cn.gov.cn.ntgsg.cn http://www.morning.znqztgc.cn.gov.cn.znqztgc.cn
