跳跃表原理及实现

一、跳表数据结构

         跳表是有序表的一种，其底层是通过链表实现的。链表的特点是插入删除效率高，但是查找节点效率很低，最坏的时间复杂度是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.h"


SkipLinkListNode* create_skiplinklist_node(SkipLinkListData data,int level){
   SkipLinkListNode*  node = (SkipLinkListNode*) malloc(sizeof(SkipLinkListNode));
   if(node==NULL)
   {
    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->level<level)
  {
     level = down_ptr->level +1;
  }
  SkipLinkListNode* index_node = NULL;
   /// 当前层级小于随机高度时候，需要升级索引
  if(down_ptr->level<level){
      /// 向上升级一层索引
      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->data<=data && down_ptr->level>0)
  {
      SkipLinkListNode* next_ptr  = down_ptr->next;
      // 查找当前层级索引，定位到离当前数值的最大索引值
      while (next_ptr != NULL && next_ptr->data<=data && next_ptr->next!=NULL)
      {
         next_ptr = next_ptr->next;
      }
      /// 维护索引
      if(down_ptr->level<=level){
          SkipLinkListNode* new_node = create_skiplinklist_node(data, down_ptr->level);
          if(next_ptr==NULL)
          {
            /// 如果当前层索引到达最后一个值，则跳到下一层索引
            down_ptr->next=new_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 != NULL&&down_ptr->next!=NULL&&down_ptr->next->data<data)
    {
         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 level>=MAX_LEVEL?MAX_LEVEL:level;
}

void  show_skiplinglistnode_all(SkipLinkListNode* head)
{
 SkipLinkListNode*  down_ptr = head->down;
 while (down_ptr!=NULL)
 {
    if(down_ptr->level==0)
    {
        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->data<=data && down_ptr->level>0)
    {
      printf("遍历第%d层次节点:%d\n",down_ptr->level,down_ptr->data);
      if(down_ptr->next!=NULL && down_ptr->next->data>data)
      {
         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)
      {
         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->data==data)
       {
          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->data>=data)
    {
      /// 处理要删除的节点存在索引节点
      if(down_ptr->next->data==data)
      {
         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->data==data)
      {
        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->data==data)
     {
        SkipLinkListNode* traget_node =  down_ptr->next;
        down_ptr->next =  down_ptr->next->next;
        free(traget_node);
     }
     down_ptr=down_ptr->next;
  }
  printf("删除元素结束\n");

}

三、跳表测试


void  test_skiplinklist()
{

 SkipLinkListNode*  head = create_skiplinklist_node(0,0);
 SkipLinkListData  i;
 int c = 30;
 for(i=1;i<c;i++)
 {
    insert_skiplinklist_node(head,i);   
 }
 
 show_skiplinglistnode_all(head);
 search_skiplinklistnode(head,28);
 delete_skiplinklistnode(head,15);
 show_skiplinglistnode_all(head);
 
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/283201.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

打破成本壁垒，免费SSL证书为中小企业保驾护航

打破成本壁垒，免费SSL证书为中小企业保驾护航

HTTPS&#xff0c;这个曾经看似遥远的技术词汇&#xff0c;如今已与我们每个人的网络生活息息相关。而实现HTTPS加密传输的关键一环——SSL证书&#xff0c;正以其独特的安全性能&#xff0c;为网站筑起一道坚实的防护墙。更令人惊喜的是&#xff0c;免费SSL证书服务已经到来&a…
阅读更多...
数据结构与算法教程，数据结构C语言版教程！（第二部分、线性表详解：数据结构线性表10分钟入门）三

数据结构与算法教程，数据结构C语言版教程！（第二部分、线性表详解：数据结构线性表10分钟入门）三

第二部分、线性表详解&#xff1a;数据结构线性表10分钟入门 线性表&#xff0c;数据结构中最简单的一种存储结构&#xff0c;专门用于存储逻辑关系为"一对一"的数据。 线性表&#xff0c;基于数据在实际物理空间中的存储状态&#xff0c;又可细分为顺序表&#xff…
阅读更多...
自动化网络故障修复管理

自动化网络故障修复管理

什么是故障管理 故障管理是网络管理的组成部分&#xff0c;涉及检测、隔离和解决问题。如果实施得当&#xff0c;网络故障管理可以使连接、应用程序和服务保持在最佳水平&#xff0c;提供容错能力并最大限度地减少停机时间。专门为此目的设计的平台或工具称为故障管理系统。 …
阅读更多...
JavaScript setTimeout和setInterval的用法与区别详解

JavaScript setTimeout和setInterval的用法与区别详解

目录 I. 总述 II. setTimeout()函数 III. setInterval()函数 IV. 新年倒计时案例 Javascript的setTimeOut和setInterval函数应用非常广泛&#xff0c;它们都用来处理延时和定时任务&#xff0c;下面这篇文章主要给大家介绍了关于JavaScript setTimeout和setInterval的用法与…
阅读更多...
解决 Nginx 反向代理中的 DNS 解析问题：从挑战到突破20231228

解决 Nginx 反向代理中的 DNS 解析问题：从挑战到突破20231228

引言 在使用 Nginx 作为反向代理服务器时&#xff0c;我们可能会遇到各种配置和网络问题。最近&#xff0c;我遇到了一个有趣的挑战&#xff1a;Nginx 在反向代理配置中无法解析特定的域名&#xff0c;导致 502 错误。这个问题的解决过程不仅揭示了 Nginx 的一个不太为人知的功…
阅读更多...
分布式【雪花算法】

分布式【雪花算法】

雪花算法 背景&#xff1a;在分布式系统中&#xff0c;需要使用全局唯一ID&#xff0c;期待ID能够按照时间有序生成。 **原理&#xff1a;**雪花算法是 64 位 的二进制&#xff0c;一共包含了四部分&#xff1a; 1位是符号位&#xff0c;也就是最高位&#xff0c;始终是0&am…
阅读更多...
MySQL存储过程、创建、调用、查看、删除、存储过程与函数的额区别、缺陷等、存储过程写分页等

MySQL存储过程、创建、调用、查看、删除、存储过程与函数的额区别、缺陷等、存储过程写分页等

MySQL存储过程 1、存储过程的定义2、存储过程使用的意义3、存储过程的创建4、存储过程的调用5、存储过程的查看6、存储过程的删除7、存储及过程与函数的区别8、存储过程的缺陷9、存储过程写分页 1、存储过程的定义 存储过程&#xff1a;存储过程&#xff08;Stored Procedure&…
阅读更多...
redis 从0到1完整学习 （十二）：RedisObject 之 List 类型

redis 从0到1完整学习 （十二）：RedisObject 之 List 类型

文章目录 1. 引言2. redis 源码下载3. redisObject 管理 List 类型的数据结构3.1 redisObject 管理 List 类型3.2 List PUSH 源码 4. 参考 1. 引言 前情提要&#xff1a; 《redis 从0到1完整学习 &#xff08;一&#xff09;&#xff1a;安装&初识 redis》 《redis 从0到1…
阅读更多...
pytest --collectonly 收集测试案例

pytest --collectonly 收集测试案例

pytest --collectonly 是一条命令行指令&#xff0c;用于在运行 pytest 测试时仅收集测试项而不执行它们。它会显示出所有可用的测试项列表&#xff0c;包括测试模块、测试类和测试函数&#xff0c;但不会执行任何实际的测试代码。 这个命令对于查看项目中的测试结构和确保所有…
阅读更多...
千里马2023年终总结-android framework实战

千里马2023年终总结-android framework实战

背景&#xff1a; hi粉丝朋友们&#xff1a; 2023年马上就过去了&#xff0c;很多学员朋友也都希望马哥这边写个年终总结&#xff0c;因为这几个月时间都忙于新课程halsystracesurfaceflinger专题的开发&#xff0c;差点都忘记了这个事情了&#xff0c;今天特别花时间来写个bl…
阅读更多...
思维链COT原理探究

思维链COT原理探究

要进行因果分析&#xff0c;需要把思维链中的不同元素拆解开来&#xff0c;然后通过控制变量实验&#xff0c;来研究不同元素对COT效果的影响。以下两篇论文的核心差异就在于: COT的变量拆解&#xff0c;以及控制变量的实验方式。 结合两篇论文的实验结论&#xff0c;可能导致…
阅读更多...
【深度学习：Convolutional Neural Networks】卷积神经网络入门指南

【深度学习：Convolutional Neural Networks】卷积神经网络入门指南

卷积神经网络&#xff08;CNN&#xff09;是深度学习领域最引人注目的成就之一。自从LeCun等人在20世纪90年代初引入以来&#xff0c;CNN在图像处理、视频分析和自然语言处理等领域取得了显著的成就。在这篇博客中&#xff0c;我们将探讨CNN的基本原理、结构和一些实际应用案例…
阅读更多...
实验3 vTPM相关

实验3 vTPM相关

一、实验目的 1.了解vTPM原理和相关知识&#xff1b;2.创建具备vTPM的虚拟机&#xff1b;3.加深对可信计算技术的理解。 二、实验内容 安装seabios&#xff0c;libtpms&#xff0c;swtpm&#xff0c;qemu‐tpm&#xff1b;启动vTPM&#xff1b;安装虚拟机。 三、实验环境 …
阅读更多...
2013年第二届数学建模国际赛小美赛B题寄居蟹进化出人类的就业模式解题全过程文档及程序

2013年第二届数学建模国际赛小美赛B题寄居蟹进化出人类的就业模式解题全过程文档及程序

2013年第二届数学建模国际赛小美赛 B题 寄居蟹进化出人类的就业模式 原题再现&#xff1a; 寄居蟹是美国最受欢迎的宠物品种&#xff0c;依靠其他动物的壳来保护。剥去寄居蟹的壳&#xff0c;你会看到它柔软、粉红色的腹部卷曲在头状的蕨类叶子后面。大多数寄居蟹喜欢蜗牛壳&…
阅读更多...
Unity Window安装包制作

Unity Window安装包制作

Unity Window安装包制作 介绍一、RAR自解压方式1、找到Unity打包的可执行程序2.创建自解压文件3.配置设置4、最后点击确定等待压缩完成即可&#xff08;默认生成位置为你选中文件右键点击添加到压缩文件时的路径&#xff09; 二、Setup Factory工具安装制作Window安装包相关常用…
阅读更多...
2023年成都市中等职业学校学生技能大赛“网络搭建及应用”赛项竞赛样卷

2023年成都市中等职业学校学生技能大赛“网络搭建及应用”赛项竞赛样卷

2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 &#xff08;总分1000分&#xff09; 目录 2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 网络建设与调试项目&#xff08;500分&#xff09; 服务器搭建与运维项目&#xff08;…
阅读更多...
每日一题----删除指定数字

每日一题----删除指定数字

大家好今天是1月1号&#xff0c;我在这里祝大家元旦快乐&#xff0c;感谢大家的支持&#xff0c;新的一年我会更加努力。谢谢大家。&#xff01;&#xff01;&#xff01; 文章目录 目录 文章目录 题目演示 题⽬描述&#xff1a; 先输⼊10个整数存放在数组中&#xff0c;再输⼊…
阅读更多...
华为云创新中心，引领浙南的数字化腾飞

华为云创新中心，引领浙南的数字化腾飞

编辑&#xff1a;阿冒 设计&#xff1a;沐由 县域经济是我国国民经济的重要组成部分&#xff0c;是推动经济社会全面发展的核心力量之一。在推进中国式现代化的征程中&#xff0c;县域经济扮演的角色也越来越重要。 毫无疑问&#xff0c;县域经济的良性发展&#xff0c;需要多方…
阅读更多...
阿里后端实习一面面经

阿里后端实习一面面经

阿里后端实习一面面经 项目中使用到了es&#xff0c;es的作用&#xff1f; elasticsearch是一款非常强大的开源搜索引擎&#xff0c;具备非常多强大功能&#xff0c;可以帮助我们从海量数据中快速找到需要的内容 es中的重要概念&#xff1f; 群集&#xff1a;一个或多个节点…
阅读更多...
【HarmonyOs Arkts笔记】Arkts ForEach循环使用

【HarmonyOs Arkts笔记】Arkts ForEach循环使用

说明 ForEach循环数组对象时 要指定对象的唯一标识 例如 id&#xff0c;否则只会显示第一个 State tabsList: object[] [{ name: 砍价活动, id: 1, icon: https://php-b2c.likeshop.cn/uploads/images/2022062414322367e6a5479.png },{ name: 拼团活动, id: 2, icon: https:…
阅读更多...
最新文章

Copyright @ 2022~2023