Я создаю реализацию списка пропуска в C ++ с четырьмя ссылками на окружающие узлы.
Вот класс узлов списка пропуска:
class SkipList_Node {
public:
int key;
string data;
//special values for infinity keys
int pos_infinity_key = 1000;
int neg_infinity_key = -1000;
//pointers to surrounding nodes
SkipList_Node *up;
SkipList_Node *down;
SkipList_Node *left;
SkipList_Node *right;
//Constructors
SkipList_Node() {};
SkipList_Node(int k, string d) {
this->key = k;
this->data = d;
up = NULL;
down = NULL;
left = NULL;
right = NULL;
}
};
Вот список пропускакласс.
class Skip_List {
public:
//first and last nodes in the list
SkipList_Node first;
SkipList_Node last;
//Number of rows in the list
int height;
//Constructor for an empty skiplist
Skip_List() {
//initialize infinity keys
SkipList_Node node1(SkipList_Node().neg_infinity_key, "");
SkipList_Node node2(SkipList_Node().pos_infinity_key, "");
//link new nodes
node1.right = &node2;
node2.left = &node1;
//update first and last key values
first = node1;
last = node2;
height = 0;
}
//Randomly determine the height of a node
int getLevel() {
//set the seed for random function
srand(time(NULL));
//Simulate coin flips and store heads into array
//Max height is 4
int flips[5];
for (int i = 0; i < 5; i++) {
flips[i] = 1 + rand() % 2;
}
//Determine height based on heads
//As soon as tails is fliped stop counting height
int height_counter = 0;
for (int n = 0; n < 5; n++) {
if (flips[n] == 2) {
height_counter += 1;
}
else {
break;
}
}
return height_counter;
}
//return height of the skip list
int getHeight() {
return height;
}
//find the largest key which is <= value of key passed
SkipList_Node searchSkipList(int k) {
//pointer to the node
SkipList_Node* ptr;
//point to the first node of the list
ptr = &first;
//move right until a key <= value of key passed is found
while (1) {
while (ptr->right->key != SkipList_Node().neg_infinity_key &&
((ptr->right->key) - k) <= 0) {
ptr = ptr->right;
}
//drop down level
if (ptr->down != NULL) {
ptr = ptr->down;
}
else {
//Lowest level of skip list reached
break;
}
}
return *ptr;
}
//Return the value of a node given the key
string getValue(int k){
SkipList_Node* ptr;
//search for the node
ptr = &searchSkipList(k);
//If key is found return its value else return null
if (k == (ptr->key)) {
return ptr->data;
}
else {
cout << "No Nodes found with that key value";
return NULL;
}
}
//Insert a new node into skip list
void insertIntoSkiplist(int k, string d) {
SkipList_Node* p;
int level;
p = &searchSkipList(k);
//if key already exists update the value
if (k == (p->key)) {
p->data = d;
return;
}
// Create and insert a new node
SkipList_Node* q = new SkipList_Node(k, d);
q->left = p;
q->right = p->right;
p->right->left = q;
p->right = q;
//Calculate the level
level = getLevel();
//insert node in each level
for (int i = 0; i <= level; i++) {
//Create new empty row if level is hiegher than the current height of the list
if (level >= height) {
SkipList_Node* node1 = new SkipList_Node(SkipList_Node().neg_infinity_key, "");
SkipList_Node* node2 = new SkipList_Node(SkipList_Node().pos_infinity_key, "");
//link inifnity nodes
node1->right = node2;
node1->down = &first;
node2->left = node1;
node2->down = &last;
first.up = node1;
last.up = node2;
first = *node1;
last = *node2;
}
while (p->up == NULL) {
p = p->left;
}
p = p->up;
SkipList_Node* z = new SkipList_Node(k, NULL);
z->left = p;
z->right = p->right;
z->down = q;
p -> right -> left = z;
p->right = z;
q->up = z;
q = z;
level += 1;
}
}
};
В основном я создаю новый объект списка пропуска.Глядя на отладчик, конструктор успешно создает node1 и node2 и использует их для обновления узлов первым и последним.В этой точке узлы first и last имеют правильные связанные значения, First.right имеет ключ 1000, а last.left имеет ключ -1000.
Затем я вызываю метод insertIntoSkipList (), который, в свою очередь, вызывает searchSkipList ()метод.Глядя на отладчик в точке, где я назначаю адрес памяти first указателю ptr, значения first.right теперь имеют значение key = -858993 и data = "Ошибка чтения символов строки".Я не уверен, почему адрес памяти первого содержит эти значения для указателя на правый узел.На данный момент я ожидаю, что first.right по-прежнему будет хранить значения key = 1000 и data = "", на которые затем будет указывать ptr-> right.
У меня нет большого опыта работы с C ++ и указателями.