让你的代码更加优雅的编程技巧跳转表

　　跳表比较好理解，但是实际用代码来表示，还是有点复杂的。
　　实现的方法不唯一1。什么是跳表
　　跳表是链表索引的一种数据结构，是以空间换取时间的方式，关于跳表参考：https：baike。baidu。comitem跳表22819833？fraladdin2。跳表概念
　　跳表在原有链表的基础上，增加索引，从而可以进行二分查找，提高搜寻效率。
　　原始链表Head18122355NULL
　　新增了索引的链表（跳表）Head28NULLHead1823NULLHead018122355NULL
　　Head0，Head1，Head2上都是真实的节点，这就是以空间换取时间
　　例如算上Head，元素数据一共有6个，而添加索引后，元素一共有11个3。跳表增删查规则
　　3。1跳表数据节点
　　数据节点可以和链表节点一致，也可以定义如下节点，除了数据外，有指针指向前一个后一个上一个下一个节点，以便后续查找操作。typedefstruct｛structN后一个节点structN前一个节点structN上一个节点structN下一个节点｝N
　　3。2跳表初始化
　　当跳表有多少层的时候，应当建立多少个头结点，例如：跳表为3层Head2NULLHead1NULLHead0NULL3。3查找
　　删除新增都会进行查询才操作，无非是删除新增索引而已。
　　例如有如下数据Head223NULLHead1823NULLHead018122355NULL
　　要查找13这个节点
　　去除无效层
　　例如：Head2后面第一个节点的数据23，而23大于13，所以Head2没有数据匹配查询，故需要跳到下面一层，至Head1上进行查询。
　　查询至Head0层
　　去除无效层后数据进入了Head1，在Head1上进行匹配，当匹配到23时，23大于13，将23标记为查询结束点，对23的上一个节点8进行向下指针操作，进入Head0层的8节点。
　　查找实际数据
　　从Head0层的8进行查找，直至查询结束标记点（head123），查询的数据分别为8，12，23查询结束，未找到数据。
　　嵌入式物联网需要学的东西真的非常多，千万不要学错了路线和内容，导致工资要不上去！
　　无偿分享大家一个资料包，差不多150多G。里面学习内容、面经、项目都比较新也比较全！某鱼上买估计至少要好几十。
　　点击这里找小助理0元领取：嵌入式物联网学习资料（头条）
　　3。4新增
　　新增操作需要记录索引寻址过程，以便后续新增索引。
　　头结点插入
　　头结点插入一定是去除无效层至Head0，且Head0的第一个节点都比插入节点要大的情况下
　　例如：
　　如下跳表，插入2Head223NULLHead1823NULLHead038122355NULL
　　尾结点插入
　　头结点插入一定是去除无效层至Head0，且Head0的第一个节点都比插入节点要小，直至NULL节点的情况下
　　例如：
　　如下跳表，插入65Head223NULLHead1823NULLHead038122355NULL
　　中间节点插入
　　除开以上2种情况，其余情况为中间节点插入
　　新增索引
　　抛硬币的方法，当数据量达到一定规模的时候，一定是趋近于50的。
　　所以跳表会越来越趋向于如下形式33713579123456789
　　判断是否需要新增索引，采取抛硬币的方法来判断，即：随机数取余为0则需要新增，否则不需要。
　　例如如下跳表，插入65Head223NULLHead1823NULLHead038122355NULL
　　寻址应该为
　　Head2：23
　　Head1：23
　　元素数据插入后为Head223NULLHead1823NULLHead03812235565NULL
　　当插入65节点后，若判断需要索引的时候，则先为Head1添加索引，添加位置为寻址地址之后，寄Head1：23Head223NULLHead182365NULLHead03812235565NULL
　　继续判断，若不需要添加索引，则插入结束
　　若还需要添加索引，则继续上述操作，直至索引层达到最高层
　　3。5删除
　　删除首先是查找操作【3。3查找】
　　若未找到该节点，则删除失败
　　若找到了该节点，则应当提到该数据最高索引层，再从高到低删除
　　例如：
　　如下跳表，删除23Head223NULLHead182365NULLHead03812235565NULL
　　找到Head023后，应该向上找到Head223，然后从高向低删除，若删除后，该索引没有数据了，则索引层减1
　　则删除Head223后数据如下Head182365NULLHead03812235565NULL
　　删除Head123后数据如下Head1865NULLHead03812235565NULL
　　删除Head023后数据如下Head1865NULLHead038125565NULL4。代码
　　skipList。cincludestdio。hincludestdlib。hincludestdbool。hintMaxLevel8；最大层数intcurrLevel0；当前层数数据节点typedefstruct｛structNstructNstructNstructN｝N记录索引寻址过程typedefstruct｛structN｝skipS判断是否需要新增索引，抛硬币boolrandNum（）｛if（0（rand（）2））｝新增节点booladd（NodeSL〔〕，intdata）｛printf（新增节点：d，data）；intlevelcurrLNodeHeadNULL；NodetmpNULL；NodelastNULL；初始化索引数据为Head地址skipStepsteps〔MaxLevel〕；for（i0；iMaxLi）｛steps〔i〕。level0；steps〔i〕。nodeSL〔i〕；Nodesssteps〔i〕。｝赛选无效层HeadSL〔level〕；tmpHwhile（（level0）（datatmpdata））｛HeadSL〔level〕；tmpH｝根据索引寻找Head0数据节点while（（level0））｛while（tmp！NULL）｛if（datatmpdata）｛steps〔level〕。if（NULL！last）steps〔level〕。｝｝if（NULLtmp）｛steps〔level〕。if（NULL！last）steps〔level〕。｝｝Head0数据合适的节点while（tmp！NULL）｛if（datatmpdata）｛｝｝新增节点NodenewData（Node）malloc（sizeof（Node））；newDnewDataupNULL；newDatadownNULL；newDatalastNULL；newDatanextNULL；intk0；Head0插入原始数据if（NULLlast）｛头结点HeadSL〔0〕；NodeheadNextHif（NULL！headNext）｛newDatanextheadNheadNextlastnewDnewDatalastH｝HeadnextnewDnewDatalastH｝elseif（NULLtmp）｛尾节点lastnextnewDnewD｝else｛中间节点newDtmplastnewDnewDlastnextnewD｝构建索引while（randNum（））｛k；if（kMaxLevel）新增索引数据NodenewIndex（Node）malloc（sizeof（Node））；newInewIndexupNULL；newIndexdownNULL；newIndexnextNULL；newIndexlastNULL；建立上下级关系newIndexdownnewDnewDataupnewINodenodesteps〔k〕。nodenextNodenextInodenextnewInewInewIndexnextnextIif（NULL！nextIndex）nextIndexlastnewInewDatanewI判断是否需要新增索引层数if（kcurrLevel）currL｝｝初始化头结点NodeinitSkipList（NodeskipList〔〕）｛for（i0；iMaxLi）｛NodenewHead（Node）malloc（sizeof（Node））；if（NULLnewHead）｛printf（d层头结点申请失败）；returnNULL；｝newHeaddata1i；newHeaddownNULL；newHeadupNULL；newHeadnextNULL；newHeadlastNULL；skipList〔i〕newH｝returnskipL｝打印跳表数据voidPrintSkipList（NodeSL〔〕）｛if（NULLSL）｛｝；intlevelcurrLintlevelMaxLfor（i0；i）｛NodeHeadSL〔i〕；NodetmpHprintf（第d层，i）；while（NULL！tmp）｛printf（d，tmpdata）；｝printf（）；｝｝查询数据Nodequery（NodeSL〔〕，intdata）｛printf（查询数据：d，data）；intlevelcurrLNodeHeadNULL；NodetmpNULL；NodelastNULL；HeadSL〔level〕；tmpHintendQuery1；筛除无效层while（（level0）（datatmpdata））｛endQHeadSL〔level〕；tmpH｝根据索引定位到Head0层while（（level0））｛while（tmp！NULL）｛if（data（tmpdata））｛endQ｝｝if（NULLtmp）｛endQuery1；｝｝查询实际数据while（NULL！tmp）｛if（endQuery！1）if（tmpdataendQuery）｛tmpNULL；｝if（tmpdatadata）｛｝｝返回查询的数据节点，若没有查询到，应当返回NULL，否则返回实际的地址｝删除数据booldel（NodeSL〔〕，intdata）｛printf（删除数据：d，data）；找到节点地址Nodetmpquery（SL，data）；if（NULLtmp）｛printf（未找到节点，删除失败）；｝intlevel0；NodetlastNULL；NodetnextNULL；找到该数据最高索引while（NULL！tmpup）｛｝由上至下删除索引数据while（tmp！NULL）｛Nif（tlastNULL）｛printf（上一个节点不可能为空，删除失败，层数：d，level）；｝if（NULL！tnext）elsetlastnextNULL；if（（tlastSL〔level〕）（NULLtnext））｛currL｝free（tmp）；｝｝intmain（）｛NodeSL〔MaxLevel〕；NodeskipListinitSkipList（SL）；if（NULLSL）｛printf（skipList申请失败）；return1；｝测试新增intnum〔〕｛1，3，2，10，8，9，22，30，29，120，99，78，55，76，21｝；for（i0；isizeof（num）sizeof（int）；i）｛add（skipList，num〔i〕）；｝PrintSkipList（SL）；测试删除intdelNum〔〕｛99，9，78，55，3，1，28，78｝；for（i0；isizeof（delNum）sizeof（int）；i）｛del（skipList，delNum〔i〕）；｝PrintSkipList（SL）；printf（）；return0；｝
　　执行结果gccskipList。cwg。a。out新增节点：1新增节点：3新增节点：2新增节点：10新增节点：8新增节点：9新增节点：22新增节点：30新增节点：29新增节点：120新增节点：99新增节点：78新增节点：55新增节点：76新增节点：21第5层99第4层99第3层7699第2层97699第1层392930767899第0层12389102122293055767899120删除数据：99查询数据：99删除数据：9查询数据：9删除数据：78查询数据：78删除数据：55查询数据：55删除数据：3查询数据：3删除数据：1查询数据：1删除数据：28查询数据：28未找到节点，删除失败删除数据：78查询数据：78未找到节点，删除失败第3层76第2层76第1层293076第0层28102122293076120
　　END
　　文章链接：https：mp。weixin。qq。comsdDmuTosbtBHVd4Z5umw
　　转载自：技术让梦想更伟大
　　文章来源：让你的代码更加优雅的编程技巧跳转表
　　版权申明：本文来源于网络，免费传达知识，版权归原作者所有。如涉及作品版权问题，请联系我进行删除。