ホップテーブルの実装
7993 ワード
授業中にジャンプテーブルというデータ構造を初めて聞きました.ジャンプテーブルの出現は主に順序チェーンテーブルの検索速度を向上させるためである(順序チェーンテーブルは二分で検索できないため).ジャンプテーブルを実現する構想はやはり簡単で、チェーンテーブルの基礎の上で、チェーンテーブル要素のインデックスを構築することである.例えば、以下のチェーンテーブル:
上記のチェーンテーブルに基づいて構築されたジャンプテーブルの1つは、次のとおりです.
ここでvalue=2のノードの「レイヤ数」を3レイヤに上げたが、他の要素は依然として1レイヤであり、検索時にHEADポインタが指すvalue=2のノードから、検索する要素が2より大きい場合は2の右側に検索される.逆に左に検索すると、二分検索のような役割を果たします.
コードは次のとおりです.
ホップテーブルノード定義:
ホップ表クラス定義:
コンストラクション/コンストラクション関数:
入力された配列に基づいてホップテーブルを初期化します.
キューに要素を挿入します.挿入時に複数の要素がある場合は、上位レベル間のリンクに注意してください.
ジャンプテーブルの要素を削除します.面倒なのは、列全体の要素を削除することです.
ジャンプテーブルの要素を検索するには、次の手順に従います.
レイヤ数をランダムに生成:
テストサンプル
ジャンプテーブルについて、私が勉強したばかりの頃、層数がランダムである以上、どのようにして調整テーブルの削除と変更の時間の複雑さを保証するのかという疑問がありました.
元々ジャンプテーブルの時間複雑度は固定されていなかったが,確率的に決定され,すなわち所望の時間複雑度があった.
ジャンプテーブルは時計回りに90度回転するのはマルチフォークツリーのようで、層数はフォーク数であるため、層数の期待値xは検索の時間複雑度の対数の底である:すなわち時間複雑度はO(logxN)である.ここにはブログがはっきりしている.http://m.blog.csdn.net/article/details?id=38706729
私がここで実現したジャンプテーブルは面倒で、多くの空間を浪費しています.この2,3日は時間を割いて最適化し、実際の層数シミュレーションの代わりにポインタ配列を使うべきで、空間を節約します.
value:1 value:2 value:3 ...... vlaue:n
pointer-->pointer-->pointer-->......-->pointer-->NULL
上記のチェーンテーブルに基づいて構築されたジャンプテーブルの1つは、次のとおりです.
HEAD-->value:2
pNext -------------------------------> NULL
pDown
|
V
value:2
pNext -------------------------------> NULL
pDown
|
V
value:1 value:2 value:3 ... vlaue:n
pNext ---> pNext ---> pNext --> ...--> pNext --> NULL
pDown:NULL pDown:NULL pDown:NULL pDown:NULL
ここでvalue=2のノードの「レイヤ数」を3レイヤに上げたが、他の要素は依然として1レイヤであり、検索時にHEADポインタが指すvalue=2のノードから、検索する要素が2より大きい場合は2の右側に検索される.逆に左に検索すると、二分検索のような役割を果たします.
コードは次のとおりです.
#pragma once
#include
#include
#include
using namespace std;
#define MAX_LEVEL 4
#define MIN 0
#define myCalloc(n) (NODE*)calloc(n,sizeof(NODE))
#define NEXT(p) p + 1
ホップテーブルノード定義:
typedef struct node{
int dat;
struct node * pNext;
struct node * pDown;
}NODE;
ホップ表クラス定義:
class skipList{
private:
NODE * pSkipL;
int higest;
int random();
void insert(int value, int level);
void myRecalloc(NODE*&p, int n);
public:
skipList();
~skipList();
void buildSkipList(int * arr, int arrSize);
void insert(int value);
void delElement(int value);
void search(int value);
};
コンストラクション/コンストラクション関数:
skipList::skipList(){
pSkipL = NULL;
higest = 1;
}
skipList::~skipList(){
if (pSkipL != NULL){
try{
free(pSkipL);
}
catch (char * e){
cout << e << endl;
}
}
}
入力された配列に基づいてホップテーブルを初期化します.
void skipList::buildSkipList( int * arr, int arrSize){
int level;
srand(time(0));
for (int i = 0; i < arrSize; i++){
level = random();
cout << level << endl;
if (pSkipL == NULL){
// ，
pSkipL = myCalloc(MAX_LEVEL);
higest = MAX_LEVEL;
// pDown
for (int j = 0; j < MAX_LEVEL - 1; j++){
pSkipL[j].dat = MIN;
pSkipL[j].pNext = NULL;
pSkipL[j].pDown = NEXT(pSkipL + j);
}
//
pSkipL[MAX_LEVEL - 1].dat = MIN;
pSkipL[MAX_LEVEL - 1].pDown = NULL;
}
insert(arr[i], level);
}
}
キューに要素を挿入します.挿入時に複数の要素がある場合は、上位レベル間のリンクに注意してください.
void skipList::insert( int value, int level){
NODE *p = myCalloc(level);
int tempLevel = higest;
NODE *pTemp = pSkipL;
// value ， level
for (int i = 0; i < level - 1; i++){
p[i].dat = value;
p[i].pDown = NEXT(p + i);
p[i].pNext = NULL;
}
p[level - 1].dat = value;
p[level - 1].pDown = NULL;
p[level - 1].pNext = NULL;
// ，
while (pTemp != NULL){
if (tempLevel > level){
// ，
pTemp = pTemp->pDown;
tempLevel--;
}
else{
//
while (pTemp->pNext != NULL && pTemp->pNext->dat < p->dat){
//
pTemp = pTemp->pNext;
}
if (pTemp->pNext != NULL&&pTemp->pNext->dat == p->dat){
cout << "Already exist" << endl;
break;// ， （ while）
}
else {
// ，
NODE* t = pTemp->pNext;
pTemp->pNext = p + (level - tempLevel);// ，
pTemp->pNext->dat = value;
p[level - tempLevel].pNext = t;
//
pTemp = pTemp->pDown;
}
tempLevel--;
}
}
}
void skipList::insert(int value){
int level = random();
cout << level << endl;
insert(value, level);
}
ジャンプテーブルの要素を削除します.面倒なのは、列全体の要素を削除することです.
void skipList::delElement(int value){
NODE * temp = pSkipL;
while (temp != NULL){
while (temp->pNext != NULL && value > temp->pNext->dat){
temp = temp->pNext;
}
if (temp->pNext != NULL && temp->pNext->dat == value){
// , ， while
NODE*t1 = temp->pNext;
int level = 0;
while (t1 != NULL){
t1 = t1->pDown;
level++;
}
t1 = temp->pNext;// ， free
for(int i = 0; i < level; i++){
temp->pNext = t1[i].pNext;
temp = temp->pDown;
if (temp != NULL){
while (temp->pNext != NULL &&temp->pNext->dat != value){
temp = temp->pNext;
}
if (temp->pNext == NULL){
free(t1);
cout << "Delete value: " << value << " successfully!" << endl;
return;
}
}
else{
free(t1);
cout << "Delete value: " << value << " successfully!" << endl;
return;
}
}
}
else{
temp = temp->pDown;
}
}
cout << "value " << value << " not found," << " Delete failed!"<ジャンプテーブルの要素を検索するには、次の手順に従います.
void skipList::search(int value){
NODE * temp = pSkipL;
while (temp != NULL){
while (temp->pNext != NULL && value > temp->pNext->dat){
temp = temp->pNext;
}
if (temp->pNext != NULL&&temp->pNext->dat == value){
cout << "Found value: " << temp->pNext->dat << endl;
return;
}
else{
temp = temp->pDown;
}
}
cout << "value " << value << " not found!" << endl;
}
レイヤ数をランダムに生成:
int skipList::random(){
int level = 1;
while (rand() % 2 == 1 && level < MAX_LEVEL){// ， 2
level++;
}
return level;
}
テストサンプル
#pragma once
#include"skipChart.h"
int main(){
skipList l;
int arr[5] = {1, 3, 5, 7, 9};
int s = sizeof(arr) / sizeof(int);
l.buildSkipList(arr,s);
l.insert(4);
l.insert(10);
l.insert(6);
l.search(1);
l.delElement(1);
l.search(1);
l.search(3);
l.delElement(3);
l.search(3);
l.search(6);
l.delElement(6);
l.search(6);
l.delElement(-1);
system("pause");
return 0;
}
ジャンプテーブルについて、私が勉強したばかりの頃、層数がランダムである以上、どのようにして調整テーブルの削除と変更の時間の複雑さを保証するのかという疑問がありました.
元々ジャンプテーブルの時間複雑度は固定されていなかったが,確率的に決定され,すなわち所望の時間複雑度があった.
ジャンプテーブルは時計回りに90度回転するのはマルチフォークツリーのようで、層数はフォーク数であるため、層数の期待値xは検索の時間複雑度の対数の底である:すなわち時間複雑度はO(logxN)である.ここにはブログがはっきりしている.http://m.blog.csdn.net/article/details?id=38706729
私がここで実現したジャンプテーブルは面倒で、多くの空間を浪費しています.この2,3日は時間を割いて最適化し、実際の層数シミュレーションの代わりにポインタ配列を使うべきで、空間を節約します.