跳表概念以及跳表增刪查規(guī)則
跳表比較好理解，但是實(shí)際用代碼來(lái)表示，還是有點(diǎn)復(fù)雜的。
實(shí)現(xiàn)的方法不唯一
1. 什么是跳表
跳表是鏈表+索引的一種數(shù)據(jù)結(jié)構(gòu) ，是以空間換取時(shí)間的方式，關(guān)于跳表參考:https://baike.baidu.com/item/跳表/22819833?fr=aladdin
2. 跳表概念
跳表在原有鏈表的基礎(chǔ)上，增加索引，從而可以進(jìn)行二分查找，提高搜尋效率。
原始鏈表
Head ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL
新增了索引的鏈表(跳表)
Head2 ————————> 8 ———————————————————————> NULL
Head1 ————————> 8 —————————> 23 —————————> NULL
Head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL
Head0 , Head1 , Head2 上都是真實(shí)的節(jié)點(diǎn)，這就是以空間換取時(shí)間
例如算上Head, 元素?cái)?shù)據(jù)一共有 6 個(gè)，而添加索引后，元素一共有 11 個(gè)
3. 跳表增刪查規(guī)則
3.1 跳表數(shù)據(jù)節(jié)點(diǎn)
數(shù)據(jù)節(jié)點(diǎn)可以和鏈表節(jié)點(diǎn)一致 ，也可以定義如下節(jié)點(diǎn)，除了數(shù)據(jù)外，有指針指向 前一個(gè)/后一個(gè)/上一個(gè)/下一個(gè) 節(jié)點(diǎn)，以便后續(xù)查找操作。
typedef struct {
int data;
struct Node *next; // 后一個(gè)節(jié)點(diǎn)
struct Node *last; // 前一個(gè)節(jié)點(diǎn)
struct Node *up; // 上一個(gè)節(jié)點(diǎn)
struct Node *down; // 下一個(gè)節(jié)點(diǎn)
} Node;
3.2 跳表初始化
當(dāng)跳表有多少層的時(shí)候，應(yīng)當(dāng)建立多少個(gè)頭結(jié)點(diǎn)，例如: 跳表為3層
Head2 ——> NULL
Head1 ——> NULL
Head0 ——> NULL
3.3 查找
刪除/新增 都會(huì)進(jìn)行查詢才操作，無(wú)非是刪除/新增索引而已。
例如有如下數(shù)據(jù)
Head2 —————————————————————> 23 —————————> NULL
Head1 ————————> 8 —————————> 23 —————————> NULL
Head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL
要查找13這個(gè)節(jié)點(diǎn)
去除無(wú)效層
例如:Head2后面第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)23， 而23大于13, 所以Head2沒(méi)有數(shù)據(jù)匹配查詢，故需要跳到下面一層，至Head1上進(jìn)行查詢。
查詢至Head0層
去除無(wú)效層后數(shù)據(jù)進(jìn)入了Head1, 在Head1上進(jìn)行匹配，當(dāng)匹配到23時(shí)，23大于13，將23標(biāo)記為 查詢結(jié)束點(diǎn)，對(duì)23的上一個(gè)節(jié)點(diǎn) 8 進(jìn)行 向下指針操作，進(jìn)入Head0層的8節(jié)點(diǎn)。
查找實(shí)際數(shù)據(jù)
從Head0層的8 進(jìn)行查找，直至查詢結(jié)束標(biāo)記點(diǎn)(head1 23), 查詢的數(shù)據(jù)分別為 8 ， 12 ，23 查詢結(jié)束，未找到數(shù)據(jù)。
3.4 新增
新增操作需要記錄索引尋址過(guò)程，以便后續(xù)新增索引。
頭結(jié)點(diǎn)插入
頭結(jié)點(diǎn)插入一定是去除無(wú)效層至Head0 , 且Head0的第一個(gè)節(jié)點(diǎn)都比插入節(jié)點(diǎn)要大的情況下
例如:
如下跳表，插入 2
Head2 —————————————————————> 23 —————————> NULL
Head1 ————————> 8 —————————> 23 —————————> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL
尾結(jié)點(diǎn)插入
頭結(jié)點(diǎn)插入一定是去除無(wú)效層至Head0 , 且Head0的第一個(gè)節(jié)點(diǎn)都比插入節(jié)點(diǎn)要小，直至NULL節(jié)點(diǎn)的情況下
例如:
如下跳表，插入 65
Head2 —————————————————————> 23 —————————> NULL
Head1 ————————> 8 —————————> 23 —————————> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL
中間節(jié)點(diǎn)插入
除開(kāi)以上2種情況，其余情況為 中間節(jié)點(diǎn)插入
新增索引
拋硬幣的方法，當(dāng)數(shù)據(jù)量達(dá)到一定規(guī)模的時(shí)候，一定是趨近于 50%的。
所以跳表會(huì)越來(lái)越趨向于如下形式
3
3 7
1 3 5 7 9
1 2 3 4 5 6 7 8 9
判斷是否需要新增索引，采取拋硬幣的方法來(lái)判斷，即: 隨機(jī)數(shù) 取余 為 0 則需要新增，否則不需要。
例如如下跳表，插入 65
Head2 —————————————————————> 23 —————————> NULL
Head1 ————————> 8 —————————> 23 —————————> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL
尋址應(yīng)該為
Head2: 23
Head1: 23
元素?cái)?shù)據(jù)插入后為
Head2 —————————————————————> 23 ———————————————> NULL
Head1 ————————> 8 —————————> 23 ———————————————> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL
當(dāng)插入65節(jié)點(diǎn)后，若判斷需要索引的時(shí)候，則先為 Head1 添加索引，添加位置為 尋址地址之后，寄 Head1: 23
Head2 —————————————————————> 23 ———————————————> NULL
Head1 ————————> 8 —————————> 23 —————————> 65 —> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL
繼續(xù)判斷，若不需要添加索引，則插入結(jié)束
若還需要添加索引，則繼續(xù)上述操作，直至 索引層 達(dá)到最高層
3.5 刪除
刪除首先是查找操作【3.3 查找】
若未找到該節(jié)點(diǎn)，則刪除失敗
若找到了該節(jié)點(diǎn)，則應(yīng)當(dāng)提到該數(shù)據(jù)最高索引層，再?gòu)母叩降蛣h除
例如:
如下跳表，刪除 23
Head2 —————————————————————> 23 ———————————————> NULL
Head1 ————————> 8 —————————> 23 —————————> 65 —> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL
找到 Head0 23 后，應(yīng)該向上找到 Head2 23 ,然后從高向低刪除，若刪除后，該索引沒(méi)有數(shù)據(jù)了，則索引層減1
則刪除Head2 23 后數(shù)據(jù)如下
Head1 ————————> 8 —————————> 23 —————————> 65 —> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL
刪除Head1 23 后數(shù)據(jù)如下
Head1 ————————> 8 ———————————————————————> 65 —> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL
刪除Head0 23后數(shù)據(jù)如下
Head1 ————————> 8 ————————————————> 65 —> NULL
Head0 ——> 3 ——> 8 ——> 12 ——> 55 ——> 65 —> NULL
4. 代碼
skipList.c
# include
# include
# include
int MaxLevel = 8; // 最大層數(shù)
int currLevel = 0; // 當(dāng)前層數(shù)
// 數(shù)據(jù)節(jié)點(diǎn)
typedef struct {
int data;
struct Node *next;
struct Node *last;
struct Node *up;
struct Node *down;
} Node;
// 記錄索引尋址過(guò)程
typedef struct {
int level;
struct Node *node;
} skipStep;
// 判斷是否需要新增索引, 拋硬幣
bool randNum() {
if(0 == (rand() % 2))
return true;
return false;
}
// 新增節(jié)點(diǎn)
bool add(Node *SL[] , int data) {
printf("新增節(jié)點(diǎn): %d
",data);
int level = currLevel;
Node *Head = NULL;
Node *tmp = NULL;
Node *last = NULL;
// 初始化索引 數(shù)據(jù)為 Head 地址
skipStep steps[MaxLevel];
int i;
for (i=0;i0;
steps[i].node = SL[i];
Node *ss = steps[i].node;
}
// 賽選無(wú)效層
Head = SL[level];
tmp = Head->next;
while ((level > 0) && (data < tmp->data)) {
level--;
Head = SL[level];
tmp = Head->next;
}
// 根據(jù)索引尋找Head0數(shù)據(jù)節(jié)點(diǎn)
while ((level > 0)) {
while (tmp != NULL) {
if (data < tmp->data) {
steps[level].level = level;
if (NULL != last)
steps[level].node = last;
tmp = last->down;
level--;
break;
}
last = tmp;
tmp = tmp->next;
}
if (NULL == tmp) {
steps[level].level = level;
if (NULL != last)
steps[level].node = last;
tmp = last->down;
level--;
}
}
// Head0 數(shù)據(jù)合適的節(jié)點(diǎn)
while (tmp != NULL) {
if (data < tmp->data) {
break;
}
last = tmp;
tmp = tmp->next;
}
// 新增節(jié)點(diǎn)
Node *newData = (Node *)malloc(sizeof(Node));
newData->data = data;
newData->up = NULL;
newData->down = NULL;
newData->last = NULL;
newData->next = NULL;
int k = 0;
// Head0 插入原始數(shù)據(jù)
if (NULL == last ) {
// 頭結(jié)點(diǎn)
Head = SL[0];
Node *headNext = Head->next;
if (NULL != headNext) {
newData->next = headNext;
headNext->last = newData;
newData->last = Head;
}
Head->next = newData;
newData->last = Head;
} else if ( NULL == tmp) {
// 尾節(jié)點(diǎn)
last->next = newData;
newData->last = last;
} else {
// 中間節(jié)點(diǎn)
newData->next = tmp;
tmp->last = newData;
newData->last = last;
last->next = newData;
}
// 構(gòu)建索引
while (randNum()) {
k++;
if (k >= MaxLevel) break;
// 新增索引數(shù)據(jù)
Node *newIndex = (Node *)malloc(sizeof(Node));
newIndex->data = data;
newIndex->up = NULL;
newIndex->down = NULL;
newIndex->next = NULL;
newIndex->last = NULL;
// 建立上下級(jí)關(guān)系
newIndex->down = newData;
newData->up = newIndex;
Node *node = steps[k].node;
// node->next
Node *nextIndex = node->next;
node->next = newIndex;
newIndex->last = node;
newIndex->next = nextIndex;
if (NULL != nextIndex)
nextIndex->last = newIndex;
newData = newIndex;
// 判斷是否需要新增索引層數(shù)
if (k > currLevel)
currLevel = k;
}
}
// 初始化頭結(jié)點(diǎn)
Node *initSkipList(Node *skipList[]) {
int i;
for (i=0;imalloc(sizeof(Node));
if (NULL == newHead) {
printf("%d 層 頭結(jié)點(diǎn)申請(qǐng)失敗
");
return NULL;
}
newHead->data = -1-i;
newHead->down = NULL;
newHead->up = NULL;
newHead->next = NULL;
newHead->last = NULL;
skipList[i] = newHead;
}
return skipList;
}
// 打印跳表數(shù)據(jù)
void PrintSkipList(Node *SL[]) {
if (NULL == SL) {
return;
};
int level = currLevel;
//int level = MaxLevel;
int i;
for (i=level;i>=0;i--) {
Node *Head = SL[i];
Node *tmp = Head->next;
printf("第%d層 ",i);
while (NULL != tmp) {
printf(" %d ",tmp->data);
tmp = tmp->next;
}
printf("
");
}
}
// 查詢數(shù)據(jù)
Node *query(Node *SL[] , int data) {
printf("查詢數(shù)據(jù): %d
",data);
int level = currLevel;
Node *Head = NULL;
Node *tmp = NULL;
Node *last = NULL;
Head = SL[level];
tmp = Head->next;
int endQuery = -1;
// 篩除無(wú)效層
while ((level > 0) && (data < tmp->data)) {
level--;
endQuery = tmp->data;
Head = SL[level];
tmp = Head->next;
}
// 根據(jù)索引定位到Head0層
while ((level > 0 )) {
while (tmp != NULL) {
if (data < (tmp->data)) {
level--;
endQuery = tmp->data;
tmp = last->down;
break;
}
last = tmp;
tmp = tmp->next;
}
if (NULL == tmp) {
tmp = last->down;
endQuery = -1;
level--;
}
}
// 查詢實(shí)際數(shù)據(jù)
while (NULL != tmp) {
if (endQuery != -1)
if (tmp->data > endQuery) {
tmp = NULL;
break;
}
if (tmp->data == data) {
break;
}
tmp = tmp->next;
}
// 返回查詢的數(shù)據(jù)節(jié)點(diǎn)，若沒(méi)有查詢到，應(yīng)當(dāng)返回NULL ,否則返回實(shí)際的地址
return tmp;
}
// 刪除數(shù)據(jù)
bool del(Node *SL[],int data) {
printf("刪除數(shù)據(jù): %d
",data);
// 找到節(jié)點(diǎn)地址
Node *tmp = query(SL,data);
if (NULL == tmp) {
printf("未找到節(jié)點(diǎn),刪除失敗
");
return false;
}
int level = 0;
Node *t_last = NULL;
Node *t_next = NULL;
// 找到該數(shù)據(jù)最高索引
while (NULL != tmp->up) {
level++;
tmp = tmp->up;
}
// 由上至下刪除索引/數(shù)據(jù)
while (tmp != NULL) {
t_last = tmp->last;
t_next = tmp->next;
Node *t_down = tmp->down;
if (t_last == NULL) {
printf("上一個(gè)節(jié)點(diǎn)不可能為空，刪除失敗,層數(shù): %d
",level);
return false;
}
t_last->next = t_next;
if (NULL != t_next)
t_next->last = t_last;
else
t_last->next = NULL;
if ((t_last == SL[level]) && (NULL == t_next)) {
currLevel--;
}
free(tmp);
tmp = t_down;
level--;
}
return true;
}
int main() {
Node *SL[MaxLevel];
Node *skipList = initSkipList(SL);
if (NULL == SL) {
printf("skipList 申請(qǐng)失敗
");
return -1;
}
// 測(cè)試新增
int num[] = {1,3,2,10,8,9,22,30,29,120,99,78,55,76,21};
int i;
for (i=0;i<sizeof(num)/sizeof(int);i++) {
add(skipList,num[i]);
}
PrintSkipList(SL);
// 測(cè)試刪除
int delNum[] = {99,9,78,55,3,1,28,78};
for (i=0;i<sizeof(delNum)/sizeof(int);i++) {
del(skipList,delNum[i]);
}
PrintSkipList(SL);
printf("
");
return 0;
}
;i++)>;i++)>
執(zhí)行結(jié)果
# gcc skipList.c -w -g
# ./a.out
新增節(jié)點(diǎn): 1
新增節(jié)點(diǎn): 3
新增節(jié)點(diǎn): 2
新增節(jié)點(diǎn): 10
新增節(jié)點(diǎn): 8
新增節(jié)點(diǎn): 9
新增節(jié)點(diǎn): 22
新增節(jié)點(diǎn): 30
新增節(jié)點(diǎn): 29
新增節(jié)點(diǎn): 120
新增節(jié)點(diǎn): 99
新增節(jié)點(diǎn): 78
新增節(jié)點(diǎn): 55
新增節(jié)點(diǎn): 76
新增節(jié)點(diǎn): 21
第5層 99
第4層 99
第3層 76 99
第2層 9 76 99
第1層 3 9 29 30 76 78 99
第0層 1 2 3 8 9 10 21 22 29 30 55 76 78 99 120
刪除數(shù)據(jù): 99
查詢數(shù)據(jù): 99
刪除數(shù)據(jù): 9
查詢數(shù)據(jù): 9
刪除數(shù)據(jù): 78
查詢數(shù)據(jù): 78
刪除數(shù)據(jù): 55
查詢數(shù)據(jù): 55
刪除數(shù)據(jù): 3
查詢數(shù)據(jù): 3
刪除數(shù)據(jù): 1
查詢數(shù)據(jù): 1
刪除數(shù)據(jù): 28
查詢數(shù)據(jù): 28
未找到節(jié)點(diǎn),刪除失敗
刪除數(shù)據(jù): 78
查詢數(shù)據(jù): 78
未找到節(jié)點(diǎn),刪除失敗
第3層 76
第2層 76
第1層 29 30 76
第0層 2 8 10 21 22 29 30 76 120
#
審核編輯：湯梓紅
聲明：本文內(nèi)容及配圖由入駐作者撰寫(xiě)或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。
舉報(bào)投訴
-
編程
+關(guān)注
關(guān)注
88文章
3521瀏覽量
93276 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
568瀏覽量
40030 -
鏈表
+關(guān)注
關(guān)注
0文章
80瀏覽量
10520
原文標(biāo)題：讓你的代碼更加優(yōu)雅的編程技巧-跳轉(zhuǎn)表
文章出處：【微信號(hào)：技術(shù)讓夢(mèng)想更偉大，微信公眾號(hào)：技術(shù)讓夢(mèng)想更偉大】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
Mybatis自動(dòng)生成增刪改查代碼
使用 mybatis generator 自動(dòng)生成代碼，實(shí)現(xiàn)數(shù)據(jù)庫(kù)的增刪改查。 1 配置Mybatis插件 在pom文件添加依賴： pluginsplugin
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之跳表詳解
大家好，今天分享一篇C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)相關(guān)的文章--跳表。
外部FLASH的數(shù)據(jù)要如何進(jìn)行增刪查改？
如題：怎么對(duì)外部FLASH的數(shù)據(jù)進(jìn)行增刪查改？最近比較困惑的一件事情，單片機(jī)怎么去對(duì)FLASH的數(shù)據(jù)進(jìn)行增刪查改？在考慮FLASH的使用壽命的情況下。有大神知道的嗎？或者告訴我思路也好
發(fā)表于 12-03 09:31
如何用php調(diào)用mysql數(shù)據(jù)庫(kù)實(shí)現(xiàn)增刪改查
php調(diào)用mysql數(shù)據(jù)庫(kù)實(shí)現(xiàn)增刪改查
發(fā)表于 04-09 12:53
python是如何實(shí)現(xiàn)hbase增刪改查的
hbase shell是怎樣去創(chuàng)建命名空間的？python是如何實(shí)現(xiàn)hbase增刪改查的？求解
發(fā)表于 10-19 07:26
PHP數(shù)據(jù)庫(kù)教程之增刪改查的數(shù)據(jù)高級(jí)操作資料免費(fèi)下載
本文檔的主要內(nèi)容詳細(xì)介紹的是PHP數(shù)據(jù)庫(kù)教程之增刪改查的數(shù)據(jù)高級(jí)操作資料免費(fèi)下載。
發(fā)表于 07-02 17:40
?1次下載
跳表的基本概念和實(shí)際應(yīng)用
跳躍鏈表及其應(yīng)用是非常熱門的問(wèn)題，面試時(shí)也非常常問(wèn)，深入了解其中奧秘大有裨益，不吹了，直接開(kāi)始！ 跳躍鏈表的基本概念 初識(shí)跳表 跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它允許快速查詢一個(gè)有序連續(xù)元素的數(shù)據(jù)鏈表。跳躍
跳表是用來(lái)干什么的
跳表這一數(shù)據(jù)結(jié)構(gòu)，已經(jīng)成為了Redis面試的高頻考點(diǎn)。前兩年沒(méi)這么卷的時(shí)候，可能大家從開(kāi)始學(xué)習(xí)，到拿到大廠offer這一過(guò)程，都可能沒(méi)聽(tīng)說(shuō)過(guò)跳表這一數(shù)據(jù)結(jié)構(gòu)。 那什么是跳表呢？它是用來(lái)干啥的？AVL
面向數(shù)據(jù)特征的內(nèi)存跳表優(yōu)化技術(shù)
摘 要:跳表作為數(shù)據(jù)庫(kù)中被廣泛采用的索引技術(shù),優(yōu)點(diǎn)在于可以達(dá)到類似折半查找的復(fù)雜度O(log(n)).但是標(biāo)準(zhǔn)跳表算法中,結(jié)點(diǎn)的層數(shù)是通過(guò)隨機(jī)算法生成的,這就導(dǎo)致跳表的性能是不穩(wěn)定的.在極端情況下
SQLite數(shù)據(jù)庫(kù)增刪改查
SQLite數(shù)據(jù)庫(kù)增刪改查? SQLite是一種輕量級(jí)的RDBMS（關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)），具有速度快、易用性高等優(yōu)點(diǎn)。雖然SQLite數(shù)據(jù)庫(kù)相對(duì)于一些大型數(shù)據(jù)庫(kù)管理系統(tǒng)而言功能上存在較多的限制
mysql增刪改查語(yǔ)句以及常用方法
MySQL是一種熱門的關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)，廣泛用于各種Web應(yīng)用程序和企業(yè)級(jí)應(yīng)用程序中。本文將詳細(xì)介紹MySQL中的增刪改查語(yǔ)句以及常用方法。 一、增加數(shù)據(jù) 在MySQL中，我們可以
數(shù)據(jù)庫(kù)mysql基本增刪改查
MySQL是一種開(kāi)源的關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)，常用于Web應(yīng)用程序的數(shù)據(jù)存儲(chǔ)和管理。通過(guò)使用MySQL，用戶可以進(jìn)行數(shù)據(jù)的增刪改查操作，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的有效管理。下面將詳細(xì)介紹MySQL數(shù)據(jù)庫(kù)
mysql數(shù)據(jù)庫(kù)增刪改查基本語(yǔ)句
MySQL是一種關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)，提供了豐富的功能和語(yǔ)法，來(lái)支持?jǐn)?shù)據(jù)的增刪改查。在本文中，將詳細(xì)介紹MySQL數(shù)據(jù)庫(kù)的增、刪、改、查基本語(yǔ)句，以及一些常見(jiàn)用例。 一、數(shù)據(jù)的增加 在
工商網(wǎng)監(jiān)
評(píng)論