链表的“二分查找” |
您所在的位置:网站首页 › 二分查找用什么数据类型 › 链表的“二分查找” |
二分查找是一种效率很高的查找方法,但是二分查找要求数据结构必须是顺序表,也就是类似于数组的连续存储,因为只有这样才能一下定位出数组的中间位置(直接使用类似a[len / 2]),然后就可以把数组一分为二,进行后面的操作。 但是对于链表,由于存储是离散的,不能像数组一样,快速定位中间位置,来把链表一分为二,所以一般的二分查找不能直接应用于链表。 本文要说的跳跃表其实也可以算是一种新的数据结构,采用空间换时间的方式来达到近似二分查找的效率。 其中存放的数据也是有序的。 平衡二叉树也是一种查找方式,但是这种查找方式为了维持树的平衡,需要进行复杂的操作(旋转等),学习和使用难度很大。 而本文要说的跳跃表就是一种较为简单的方式来达到替代平衡二叉树的效果。 对于平衡二叉树不多做介绍。 先复习一下二分查找的过程,一个简单的顺序表如下: 那么对于离散存放的数据怎么办呢?我们无法直接取出中间元素。 这简单,我们找个变量把中间的位置存起来不就行了吗?如下:
还需要把同一层的元素链接起来(不然怎么说是同一层呢),如果与本层第一个元素比较后,大于第一个元素,那么就可以取后面的元素来继续比较。 最终情况类似: 根据上面的描述,我们先分析一下跳跃表节点需要哪些成员,存放数据的区域(value,可以是需要的数据类型,这里使用int方便演示), 一个分值(score, 用于排序),还需要一个向右指的指针(right,来寻找本层下一个元素),还需要一个向下的指针(down,确定本元素在下一层的位置,在下一层查询过程中,直接以本元素的位置为基准)。 有一些实现是使用上面这几个成员,但是这里我们直接采用论文中节点的形式: 所以这里我们需要的成员有value, score, 还有一堆right, 如下 跳跃表本身的结构直接给出: 初始化: 查找 伪代码如下: 然后下一行代码 x = x->forward[1], 就是把最后一层的下一元素(大于等于待查找数值的,当前元素是小于待查找数值的),赋值给x,进行最后的比较。 可以看到这种查找是类似于二分查找的过程的。 C++代码如下:尽可能与伪代码描述符合。 删除: 没有看,如果读者想实现的话,可以参考文末的论文链接,自行实现。 主要是光写查询,插入就花了很长时间,还有bug,实在是没精力去研究删除了。 本文代码: #include #include #include #define MAX_LEVEL 20 struct Node { Node* right[20]; int score; int value; }; class SkipList { private: Node *header; int max_level; public: SkipList() { max_level = -1; header = new Node; for (int i=0; iright[i] = nullptr; } Node* search(int score_search) { std::cout =0; i--) { while (x->right[i]->score < score_search) { std::cout score; if ((nullptr == x->right[i]) || (nullptr == x->right[i]->right[i])) break; x = x->right[i]; } std::cout right[0]) x = x->right[0]; if (x->score == score_search) return x; return nullptr; } void insert(int score, int value) { Node *update[MAX_LEVEL]; int new_level = random_level(); Node *x = header; for (int i=max_level; i>=0; i--) { while ((nullptr != x->right[i]) && (x->right[i]->score < score)) x = x->right[i]; update[i] = x; } if (nullptr != x) x = x->right[0]; if (nullptr != x) { if ((x->score == score)) { x->value = value; return; } } if (new_level > max_level) { for (int i=max_level; ivalue = value; x->score = score; for (int i=0; iright[i] = update[i]->right[i]; update[i]->right[i] = x; } } int random_level() { /* srand不能放在这里 */ int r = 0; while (rand() % 2) ++r; return r; } void traverse() { Node *t = nullptr; for (int i=max_level; i>=0; i--) { t = header->right[i]; if (nullptr != t) { std::cout insert(6, 66); skip_list->insert(3, 33); skip_list->traverse(); Node *f = skip_list->search(8); std::cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |