跳表c++实现

原理：https://blog.csdn.net/u013011841/article/details/39158585

一.跳表结构

一种插入、查询、删除时间效率为O（log n）空间效率为O（n）的数据结构，效率堪比红黑树，但是实现起来更加简易，内存空间使用更小，便于调试。

1.节点

//节点 class node { int val; int level;//节点的高度(层次) node* forword[MAXLEVEL];//指向node*的数组 };

2.skiplist（管理整个表的一个数据结构）

class skiplist { private: node* head;//指向跳表的头结点 int max_length;//计算跳表的最大节点个数 }

随机生成level算法

//随机生成level算法 int randomLevel() { int k = 1; while (rand() % 2) { k++; } k = (k < MAXLEVEL) ? k : MAXLEVEL; return k; }

二、具体实现

class node { public: node(int val,int level) { this->val = val; this->level = level; //初始化节点指针 //forword = (node**)malloc(sizeof(node*) * level); for (int i = 0; i < MAXLEVEL; i++) { forword[i] = NULL; } } ~node() { } int val; int level; node* forword[MAXLEVEL];//指向node*的数组 }; class skiplist { public: skiplist() { //head = NULL; max_length = 0; //初始化head为一个5层的val(0)的node node* p = new node(0, 5); head = p; } //注：所有方法都是跳过第一个节点（5层的val(0)）， void insert(int val) { int level = randomLevel(); max_length++; //如果目前还没有节点 if (head == NULL) { //第一个节点的高度为max node* p = new node(val,MAXLEVEL); head = p; max_length++; } else { //指向第一个节点 node* cur = head; //p是新加入的节点 node* p = new node(val, level); //保存每一层插入的最近前面节点 //node** last=(node**)malloc(MAXLEVEL*sizeof(node*)); node* last[MAXLEVEL]; for (int i = MAXLEVEL-1; i >= 0; i--) { //在第i层找到最后一个比val小的节点 while (cur->forword[i] != NULL && cur->forword[i]->val < val) { cur = cur->forword[i]; } last[i] = cur; } //找到了 if(cur->forword[0]==NULL){ //插入到最后 for (int i = p->level-1; i >= 0; i--) { last[i]->forword[i] = p; } } else if (cur->forword[0]->val > val) { //插入 for (int i = p->level-1; i >= 0; i--) { //p的后面指针=p前面的指针的后续指针 p->forword[i] = last[i]->forword[i]; //改变p前面的指针的后续指针 last[i]->forword[i] = p; } } } } //从最高level开始找，若最高level找不到则level-- 直到level==0若还是找不到 则真找不到(cout<<"not find")。 void search(int val) { node* cur = head; for (int i = MAXLEVEL - 1; i >= 0; i--) { while (cur->forword[i]!=NULL&&cur->forword[i]->val<val) { cur = cur->forword[i]; } if (cur->forword[i]!=NULL&&cur->forword[i]->val == val) { cout << "i search it " << endl; return; } //else cout << "not find" << endl; } cout << "not find" << endl; } //方法与search一样，先找到要删除的值，若找到了改变前面的指针 void delete_val(int val) { node* cur = head; node* ask=NULL;//要找到的节点 node* last[MAXLEVEL]; for (int i = MAXLEVEL - 1; i >= 0; i--) { while (cur->forword[i] != NULL && cur->forword[i]->val < val) { cur = cur->forword[i]; } //保留每个level的前面的指针 last[i] = cur; if (cur->forword[i] != NULL && cur->forword[i]->val == val) { //找到了但是得保存前面的指针所以继续往下扫描 //保存找到的节点 ask = cur->forword[i]; } //else cout << "not find" << endl; } for (int i = ask->level - 1; i >= 0; i--) { //删除的节点前面的指针替换成删除的节点所指 last[i]->forword[i] = ask->forword[i]; } //释放内存 delete(ask); } //测试打印 void print() { for (int i = MAXLEVEL-1; i >= 0; i--) { node* cur = head; /*cout << cur->val;*/ while (cur->forword[i]) { cur = cur->forword[i]; cout << cur->val; } cout << endl; } //cout << head->get_val() << endl; //cout << max_length; } int get_max_length() { return max_length; } private: node* head; int max_length; };

三、测试

int main() { skiplist t1; t1.insert(3); t1.insert(7); t1.insert(4); t1.insert(6); t1.insert(5); t1.insert(-1); t1.delete_val(4); //cout << t1.get_max_length()<<endl; t1.search(8); //cout << endl; //t1.insert(10); //t1.insert(100); //t1.search(6); //t1.delete_val(4); t1.print(); system("pause"); return 0; }

运行结果： 注：print()函数打印的为跳表从最左节点打到最后，从上往下打。 跳表实现成功！

四、反思

编写的时候出现了两个bug：

二级指针的建立 我想用二级指针node** last来保存前面的节点（node*），或者是保存每个节点的forword指针，以便减少内存。结果导致debug时间一个小时，整个程序都是乱的。

错误的初始化:

node** forword; forword = (node**)malloc(sizeof(node*) * level);

应当改为: 其中forword为node数组，node[0]:node,node[1]:node*… 数组的大小为level

forword=new node*[level]; //forword为node*数组 level下标越界 for循环写成for(int i=level;i>=0;i++),应当为i=level-1