跳表SkipList

ID:77367 · 发表于 2015-4-18 20:55

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

一个测试程序示例, 下载压缩包中已经包含(这里的源代码对不齐):

// test.cpp

//

#include <iostream>

#include <iomanip>

#include <cstdlib>

#include <time.h>

#include "skiplist.h"

#include "TimeCounter.h"

#define TIME_START CTimeCounter* pT = new CTimeCounter()

#define TIME_END ShowTime(pT->GetExecutionTime())

//////////////////////////////////////////////////////////////////////////

// Show execution time (ms)

void ShowTime(__int64 nTime)

{

std::cout << "========================================" << std::endl;

std::cout << " Total time: ";

std::cout << std::fixed << std::setprecision(1) << std::setw(6);

std::cout << nTime;

std::cout << " ms" << std::endl << std::endl;

//printf("Usage time: %I64d millisecond\n\n", nTime); //在g++中对应的是<stdint.h> int64_t, 应该用%lld输出

}

int main(){

int count = 10, i;

SkipList sl;

srand((unsigned)time(NULL));

std::cout<<"### Function Test ###\n\n";

std::cout<<"\n=== Init Skip List ===\n\n";

sl.Init();

for ( i = 0; i < count; i++) {

sl.Insert(i);

}

std::cout<<"\n=== Print Skip List ===\n\n";

sl.Print();

printf("\n=== Search Skip List ===\n\n");

TIME_START;

for (i = 0; i < count; i++) {

int value = rand()%(count+10);

sl.Search(value);

}

TIME_END;

std::cout<<"\n=== Delete Skip List ===\n\n";

char buf[256], *p = buf;

for (i = 0; i < count+10; i+=2) {

sprintf_s(buf, "Delete[%d]:%s\n", i, sl.Delete(i) ? "SUCCESS":"NOT FOUND");

std::cout<<buf;

}

std::cout<<"\n\n";

sl.Print();

sl.Free();

//或者Ctrl+F5调试

getchar();

}

帐号		自动登录	找回密码
密码			立即注册

跳表SkipList

相关帖子