深圳住建网站,大连建设工程信息网官网首页,青岛品牌,做外贸一般上哪些网站一、跳表数据结构 跳表是有序表的一种#xff0c;其底层是通过链表实现的。链表的特点是插入删除效率高#xff0c;但是查找节点效率很低#xff0c;最坏的时间复杂度是O(N)#xff0c;那么跳表就是解决这一痛点而生的。 为了提高查询效率#xff0c;我们可以给链表加上索…一、跳表数据结构 跳表是有序表的一种其底层是通过链表实现的。链表的特点是插入删除效率高但是查找节点效率很低最坏的时间复杂度是O(N)那么跳表就是解决这一痛点而生的。 为了提高查询效率我们可以给链表加上索引利用二分查找的思路每两个节点抽取一个索引根据数据规模提升索引的高度索引的最高层级为logN,那么跳跃表支持平均0 (1ogN)这样可以快读提高节点访问速度。由于在原始链表的基础上加索引这些索引需要额外的存储空间所以这是典型的通过空间换时间。下图简单描述跳跃表原理 如果要访问8这个歌节点元素在没有索引的情况下需要遍历链表8次才能找到目标节点但是通过跳表访问(1 - 5 - 7- 7-7 - 8) ,只需要访问6次数据规模越大优势越明显。 对于提取索引理论上每隔两个元素生成一个索引节点但是在具体情况下链表是动态的删除和增加节点的时机很难确定通过两个节点维护索引的方式开销成本很大。那么如何添加索引一个新增节点要不要加索引索引加到第几层为了解决这个问题可以通过投掷硬币的方式随机数模2连续投掷正面几次那么这个次数就是索引的层级。
二、跳表代码实现 1、跳表结构、操作函数声明
#ifndef SKIPLINKLIST_H__
#define SKIPLINKLIST_H__#include stdio.h
#include stdlib.h
#include stdbool.h
#include time.h
#include math.h
#include unistd.h#define MAX_LEVEL 8//定义数据域
typedef int SkipLinkListData;typedef struct skiplinklistnode
{int level;SkipLinkListData data;struct skiplinklistnode* next;struct skiplinklistnode* down;} SkipLinkListNode;/*** 创建链表节点
*/
SkipLinkListNode* create_skiplinklist_node(SkipLinkListData data,int level);/*** 插入节点
*/
void insert_skiplinklist_node(SkipLinkListNode* head,SkipLinkListData data);/*** 维护索引
*/
void create_skiplinklist_index(SkipLinkListNode** index,SkipLinkListNode* node);/*** 随机数投硬币获取索引层高
*/
int random_skiplinklistnode_level();/*** 遍历跳表
*/
void show_skiplinglistnode_all(SkipLinkListNode* head);/*** 查询节点
*/
SkipLinkListNode* search_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data);/*** 删除跳表元素 重组索引 s* 删除的过程其实也是查找
*/
void delete_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data);#endif
2、跳表增删查操作定义 #include ./skiplinklist.hSkipLinkListNode* create_skiplinklist_node(SkipLinkListData data,int level){SkipLinkListNode* node (SkipLinkListNode*) malloc(sizeof(SkipLinkListNode));if(nodeNULL){perror(create node fail);return NULL;}node-level level;node-data data;node-next NULL;node-down NULL;return node;
}void insert_skiplinklist_node(SkipLinkListNode *head, SkipLinkListData data)
{SkipLinkListNode *down_ptr head-down;if (down_ptr NULL){head-down create_skiplinklist_node(data, 0);return;}int level random_skiplinklistnode_level(); if(down_ptr-levellevel){level down_ptr-level 1;}SkipLinkListNode* index_node NULL;/// 当前层级小于随机高度时候需要升级索引if(down_ptr-levellevel){/// 向上升级一层索引level down_ptr-level 1;SkipLinkListNode* down_node create_skiplinklist_node(down_ptr-data,level);index_node create_skiplinklist_node(data,level);down_node-next index_node;down_node-down down_ptr;head-down down_node;} /// 搜索节点while (down_ptr! NULL down_ptr-datadata down_ptr-level0){SkipLinkListNode* next_ptr down_ptr-next;// 查找当前层级索引定位到离当前数值的最大索引值while (next_ptr ! NULL next_ptr-datadata next_ptr-next!NULL){next_ptr next_ptr-next;}/// 维护索引if(down_ptr-levellevel){SkipLinkListNode* new_node create_skiplinklist_node(data, down_ptr-level);if(next_ptrNULL){/// 如果当前层索引到达最后一个值则跳到下一层索引down_ptr-nextnew_node;}else{new_node-next next_ptr-next;next_ptr-next new_node; }create_skiplinklist_index(index_node,new_node);}///跳转下一层索引down_ptr next_ptr ! NULL?next_ptr-down:down_ptr-down; }/// 遍历链表 数据插入链表while (down_ptr ! NULLdown_ptr-next!NULLdown_ptr-next-datadata){down_ptr down_ptr-next;}SkipLinkListNode* node create_skiplinklist_node(data, 0);SkipLinkListNode* next_node down_ptr-next;down_ptr-next node;node-next next_node;if(index_node!NULL){create_skiplinklist_index(index_node,node);}
}void create_skiplinklist_index(SkipLinkListNode** index_node,SkipLinkListNode* new_node)
{if ((*index_node) NULL){(*index_node) new_node;}else{SkipLinkListNode* tmp_node (*index_node);while (tmp_node ! NULL){if (tmp_node-down NULL){tmp_node-down new_node;break;}tmp_node tmp_node-down;}}
}int random_skiplinklistnode_level()
{int level 0;int mod 2;while (rand() % mod 0 ){level;}return levelMAX_LEVEL?MAX_LEVEL:level;
}void show_skiplinglistnode_all(SkipLinkListNode* head)
{SkipLinkListNode* down_ptr head-down;while (down_ptr!NULL){if(down_ptr-level0){printf(原 始链表: %d ,down_ptr-data);}else{printf(第%d层索引: %d ,down_ptr-level,down_ptr-data);}SkipLinkListNode* next_ptr down_ptr-next;while (next_ptr!NULL){printf(%d ,next_ptr-data);next_ptr next_ptr-next;}down_ptr down_ptr-down; printf(\n);}printf(\n);
}SkipLinkListNode* search_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data)
{SkipLinkListNode* down_ptr head-down;/// 索引查找while (down_ptr!NULL down_ptr-datadata down_ptr-level0){printf(遍历第%d层次节点:%d\n,down_ptr-level,down_ptr-data);if(down_ptr-next!NULL down_ptr-next-datadata){down_ptr down_ptr-down;continue;}SkipLinkListNode* next_ptr down_ptr-next;while (next_ptr ! NULL next_ptr-datadata next_ptr-next!NULL next_ptr-next-datadata){next_ptr next_ptr-next;printf(遍历第%d层次节点:%d\n,next_ptr-level,next_ptr-data);}///跳转下一层索引down_ptr next_ptr ! NULL?next_ptr-down:down_ptr-down; }//到达底层链表 遍历目标值while (down_ptr!NULL){if(down_ptr-datadata){printf(遍历第%d层次节点,命中目标%d\n,down_ptr-level,down_ptr-data);return down_ptr;}down_ptr down_ptr-next;}printf(遍历结束目标节点%d不存在\n,data);printf(\n);return NULL;
}void delete_skiplinklistnode(SkipLinkListNode *head, SkipLinkListData data)
{printf(删除元素开始\n);SkipLinkListNode *down_ptr head-down;while (down_ptr ! NULL down_ptr-data data down_ptr-level 0){printf(遍历第%d层次节点:%d\n, down_ptr-level, down_ptr-data);if (down_ptr-next ! NULL down_ptr-next-datadata){/// 处理要删除的节点存在索引节点if(down_ptr-next-datadata){SkipLinkListNode* index_ptr down_ptr-next;down_ptr-next down_ptr-next-next;printf(删除第%d层索引%d\n,index_ptr-level,index_ptr-data);free(index_ptr);}down_ptr down_ptr-down;continue;}SkipLinkListNode *next_ptr down_ptr-next;while (next_ptr ! NULL next_ptr-data data next_ptr-next ! NULL next_ptr-next-data data){if(next_ptr-next-datadata){SkipLinkListNode* index_node next_ptr-next;next_ptr-next next_ptr-next-next;free(index_node);continue;}next_ptr next_ptr-next;printf(遍历第%d层次节点:%d\n, next_ptr-level, next_ptr-data);}/// 跳转下一层索引down_ptr next_ptr ! NULL ? next_ptr-down : down_ptr-down;}while (down_ptr!NULL){if(down_ptr-next!NULL down_ptr-next-datadata){SkipLinkListNode* traget_node down_ptr-next;down_ptr-next down_ptr-next-next;free(traget_node);}down_ptrdown_ptr-next;}printf(删除元素结束\n);}
三、跳表测试 void test_skiplinklist()
{SkipLinkListNode* head create_skiplinklist_node(0,0);SkipLinkListData i;int c 30;for(i1;ic;i){insert_skiplinklist_node(head,i); }show_skiplinglistnode_all(head);search_skiplinklistnode(head,28);delete_skiplinklistnode(head,15);show_skiplinglistnode_all(head);}
