Chinaunix首页 | 论坛 | 博客
  • 博客访问: 359175
  • 博文数量: 60
  • 博客积分: 15
  • 博客等级: 民兵
  • 技术积分: 1138
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-20 16:18
个人简介

最多140个字

文章分类

全部博文(60)

文章存档

2016年(1)

2015年(34)

2014年(25)

分类: C/C++

2014-04-14 14:33:35

图示:


点击(此处)折叠或打开

  1. //转载
  2. //SkipList
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include<time.h>

  6. #define SKIPLIST_MAXLEVEL 8

  7. typedef struct skiplistNode
  8. {
  9.     int score;
  10.     struct skiplistNode *backward;//prev
  11.     struct skiplistLevel
  12.     {
  13.         struct skiplistNode *forward;//next。
  14.     }level[0];//学习0长度数组的妙用。
  15. }skiplistNode;

  16. typedef struct skiplist
  17. {
  18.     struct skiplistNode *header, *tail;
  19.     unsigned long length;
  20.     int level;
  21. }skiplist;

  22. skiplistNode *slCreateNode(int level, double score) //创建结点。
  23. {
  24.     skiplistNode * sn = malloc(sizeof(*sn) + level*sizeof(struct skiplistLevel));//sizeof(*sn)=8字节(注意结构体对齐),level*sizeof(struct skiplistLevel)=4*level字节.
  25.     sn->score = score;
  26.     return sn;
  27. }

  28. skiplist *slCreate() //创建表头。
  29. {
  30.     int j;
  31.     skiplist *sl;
  32.     sl = malloc(sizeof(*sl));
  33.     sl->level = 1;
  34.     sl->length = 0;
  35.     sl->header = slCreateNode(SKIPLIST_MAXLEVEL, 0);
  36.     for(j = 0; j < SKIPLIST_MAXLEVEL; j++)
  37.     {
  38.         sl->header->level[j].forward = NULL;
  39.     }
  40.     sl->header->backward = NULL;
  41.     sl->tail = NULL;
  42.     return sl;
  43. }

  44. void slFreeNode(skiplistNode *sn) //释放指针sn所指向结点的内存。
  45. {
  46.     free(sn);
  47. }

  48. void slFree(skiplist *sl)
  49. {
  50.     skiplistNode *node = sl->header->level[0].forward, *next;//即skiplistNode *node,*next; node= sl->header->level[0].forward.
  51.     free(sl->header);
  52.     while(node) //释放掉每个结点。
  53.     {
  54.         next = node->level[0].forward;
  55.         slFreeNode(node);
  56.         node = next;
  57.     }
  58.     free(sl);//释放掉表头。
  59. }

  60. int slRandomLevel(void) //随机产生level.
  61. {
  62.     int level = 1;
  63.    // while((rand()&0xFFFF) < (0.5 * 0xFFFF))
  64.     while(rand()%2)//抛硬币,如果为正面,就继续抛,否则停止。
  65.         level += 1;
  66.     return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
  67. }

  68. skiplistNode *slInsert(skiplist *sl, int score) //插入结点(双向链表)。
  69. {
  70.     int i, level;
  71.     skiplistNode *update[SKIPLIST_MAXLEVEL];
  72.     skiplistNode *node;
  73.     node = sl->header;
  74.     for ( i = sl->level-1; i >= 0; i--)
  75.     {
  76.         while(node->level[i].forward && node->level[i].forward->score < score)
  77.         {
  78.             node = node->level[i].forward;
  79.         }
  80.         update[i] = node;
  81.     }
  82.     level = slRandomLevel();
  83.     if (level > sl->level)
  84.     {
  85.         for (i = sl->level; i< level ;i++)
  86.         {
  87.             update[i] = sl->header;
  88.         }
  89.         sl->level = level;
  90.     }
  91.     node = slCreateNode(level, score);
  92.     for (i = 0; i < level; i++)
  93.     {
  94.         node->level[i].forward = update[i]->level[i].forward;
  95.         update[i]->level[i].forward = node;
  96.     }
  97.     node->backward = (update[0] == sl->header? NULL : update[0]);//跳表的第一个结点的backward为NULL。
  98.     if (node->level[0].forward)
  99.         node->level[0].forward->backward = node;
  100.     else
  101.         sl->tail = node;
  102.     sl->length++;
  103.     return node;
  104. }

  105. void slDeleteNode(skiplist *sl, skiplistNode *x, skiplistNode **update)
  106. {
  107.     int i;
  108.     for (i = 0; i < sl->level; i++)
  109.     {
  110.         if (update[i]->level[i].forward == x)
  111.         {
  112.             update[i]->level[i].forward = x->level[i].forward;
  113.         }
  114.     }
  115.     if (x->level[0].forward)
  116.     {
  117.         x->level[0].forward->backward = x->backward;
  118.     }
  119.     else
  120.     {
  121.         sl->tail = x->backward;
  122.     }

  123.     while (sl->level > 1 && sl->header->level[sl->level-1].forward == NULL)
  124.         sl->level--;
  125.     sl->length--;
  126. }

  127. int slDelete(skiplist *sl, double score)
  128. {
  129.     skiplistNode *update[SKIPLIST_MAXLEVEL], *node;
  130.     int i;
  131.     node = sl->header;
  132.     for(i = sl->level-1; i >= 0; i--)
  133.     {
  134.         while (node->level[i].forward && node->level[i].forward->score < score)
  135.         {
  136.             node = node->level[i].forward;
  137.         }
  138.         update[i] = node;
  139.     }
  140.     node = node->level[0].forward;
  141.     if (node && score == node->score)
  142.     {
  143.         slDeleteNode(sl, node, update);
  144.         slFreeNode(node);
  145.         return 1;
  146.     }
  147.     else
  148.     {
  149.         return 0;
  150.     }
  151.     return 0;
  152. }

  153. int slSearch(skiplist *sl, double score)//查找。
  154. {
  155.     skiplistNode *node;
  156.     int i;
  157.     node = sl->header;
  158.     for (i = sl->level-1; i >= 0 ;i--)
  159.     {
  160.         while(node->level[i].forward && node->level[i].forward->score < score)
  161.         {
  162.             node = node->level[i].forward;
  163.         }
  164.     }
  165.     node = node->level[0].forward;
  166.     if (node && score == node->score)
  167.     {
  168.         printf("Found %d\n", score);
  169.         return 1;
  170.     }
  171.     else
  172.     {
  173.         printf("Not found %d\n", score);
  174.         return 0;
  175.     }
  176. }

  177. void slPrint(skiplist *sl) //打印。
  178. {
  179.     skiplistNode *node;
  180.     int i;
  181.     for (i = 0; i < SKIPLIST_MAXLEVEL; i++)
  182.     {
  183.         printf("LEVEL[%d]: ", i);
  184.         node = sl->header->level[i].forward;
  185.         while(node)
  186.         {
  187.             printf("%d -> ", node->score);
  188.             node = node->level[i].forward;
  189.         }
  190.         printf("NULL\n");
  191.     }
  192. }

阅读(2093) | 评论(0) | 转发(0) |
0

上一篇:欧几里德算法

下一篇:零长度数组的妙用

给主人留下些什么吧!~~