下面关于二分查找的叙述中正确的是： 关于债券的叙述错误的是

我来解释一下跳表

一个普通有序列表的结构如下：

跳表是个概率性数据结构，可以被看作是二叉树的一个变种。跳表是由William Pugh在1990年发明的。它是一种用户维护有序元素的数据结构。

跳表的构造过程是： 1、给定一个有序的链表。 2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。 3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素 4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。

一个跳表，应该具有以下特征：

一个跳表应该有几个层（level）组成； 跳表的第一层包含所有的元素； 每一层都是一个有序的链表； 如果元素x出现在第i层，则所有比i小的层都包含x； 第i层的元素通过一个down指针指向下一层拥有相同值的元素； 在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)； Top指针指向最高层的第一个元素。

让我们用一个跳表来重新构建开头的有序链表：

通过图我们可以看出，整个跳表分为三层，每一层都是一个有序链表，第一层包含所有的元素。top指针指向最高层的-1元素，较高层的元素都能在较低的层里找到，并且较高层的元素含有一个指针指向下一层值相同的元素。

在结构清晰之后，我们需要明白的是 跳表为什么要这样设计？这么存储的好处是什么呢？ 让我们通过对跳表操作来寻找答案。

首先是查找操作。在跳表中查找一个元素x的算法如下： p=top;While(1){ while (p->next->key < x ) p=p->next; If (p->down == NULL ) return p->next; p=p->down ;}

接着是插入算法。假设要插入一个元素“119”，我们设定需要插入该元素的层数为“k”（即我们需要在所有的[1,k]范围内的层里都插入元素。k的值我们会在下文中叙述），则插入算法是： int insert(val x){ int i; int j = n; //n是当前表所拥有的level数 cell *p[k]; //指针数组，用来保存每一层要插入元素的前驱 cell *p1; p1 = top->next; while(p1){ while(p1->next->val < x) p1=p1->next; if(j down; //指向下一层 j--; } } //下面的代码是将x插入到各层 for (i = 0; in的情况，需要创建一个层 //创建层的第一个元素，并将top指向它 cell *elementhead = (cell *) malloc(sizeof(cell)); element->val = -1; element->down = top; top = elementhead; //创建最后一个元素 cell *elementtail = (cell *) malloc(sizeof(cell)); elementtail->val = 1; elementtail->next = elementtail->down = NULL; //在该层中创建并插入x cell *element = (cell *) malloc(sizeof(cell)); element->val = x; elementhead->next = element; element->next = elementtail; element->down = p[i-1]->next; } //正常插入一个元素 cell *element = (cell *) malloc(sizeof(cell)); element->val = x; element->next = p[i]->next; element->down = (i=0?NULL:(p[i-1]->next)); p[i]->next = element; } return 0;} 最后是删除操作。 删除一个元素x，如果x被删除后某层只剩下头尾两个节点，则删除这一层。具体算法如下： int delete(val x){ int i = n; //n表示当前总层数 cell *p, *p1; p = top; while(n>0){ while(p->next->val < x) p=p->next; if(p->next->val == x){//假如当前层存在节点x,删除 if(p = top && p->next->next->val == INT_MAX){//该层之存在一个节点 top = p->down; free(p->next->next); free(p->next); free(p); p = top; } else{ p1 = p->next; p->next = p1->next; free(p1); } } p = p->down; n--; }} 好了，我们可以看到，无论查找、插入、删除，跳表的时间复杂度都是O(lgn)！这就是为什么我们要引入跳表。