I'm creating a skip list program for my Algorithms and Advanced Data Structure class. I was tasked
Question:
I'm creating a skip list program for my Algorithms and Advanced Data Structure class. I was tasked with implementing a find & add method for the skiplist. Here is my program, I'm running into a segmentation fault when I add my second value into the skiplist. My first issue that I fixed was that I wasn't checking the first node in the list to see if it was nullptr, but that was not my only issue apparently.
Add Method:
void SkipList::add(const ElemType &el) {
// Create a new node with the given element
Node *newNode = new Node(el);
// Get the height of the new node
int newHeight = newNode->nodeHeight;
// If the height of the new node is greater than the current list height,
// update the list height.
if (newHeight > listHeight) {
listHeight = newHeight;
}
// Array to keep track of nodes to update
Node *update[MAX_NUM_LISTS];
// Start from the top level
Node *current = head[listHeight - 1]; // Initialize current correctly
// If the list is empty, assign the first node to head
if (head[0] == nullptr) {
head[0] = newNode;
} else {
// Loop to traverse through list
for (int i = listHeight - 1; i >= 0; i--) {
// Move forward in the current level
while (current->next[i] != nullptr && current->next[i]->elem < el) {
current = current->next[i];
}
// Store the node before which the new node should be inserted
update[i] = current;
}
// Insert the new node at each level
for (int i = 0; i < newHeight; i++) {
newNode->next[i] = update[i]->next[i];
update[i]->next[i] = newNode;
}
}
}
Find Method:
bool SkipList::find(const ElemType &el) const {
// Start from the top level
Node *current = head[listHeight - 1];
bool found = false;
// Iterate through the levels of the skip list
for (int i = listHeight - 1; i >= 0; i--) {
// Move forward in the current level until reaching the end or finding a larger element
while (current->next[i] != nullptr && current->next[i]->elem < el) {
current = current->next[i];
}
// Check if the current node's next node contains the target element
if (current->next[i] != nullptr && current->next[i]->elem == el) {
found = true; // Element found
}
}
return found; // Element not found in the skip list
}
Main:
int main()
{
ElemType inputs[] = {5, 7, 8, 10, 12, 17, 19, 22, 28, 31, 33, 35, 42, 51, 59};
SkipList list1;
cout << "For list1 (same as in the slide 10 of Skip List1 Lecture Note):\n";
// for (int i=0; i for (int i = 0; i < static_cast { cout << "add " << inputs[i] << endl; list1.add(inputs[i]); cout << "list1:\n" << list1 << endl; } if (list1.find(33)) cout << "33 is found!\n"; else cout << "33 is not found!!!!\n"; if (list1.find(70)) cout << "70 is found!\n"; else cout << "70 is not found!!!!\n"; if (list1.find(10)) cout << "10 is found!\n"; else cout << "10 is not found!!!!\n"; cout << "\n===================================\n"; cout << "For list2:\n"; ElemType inputs2[] = {19, 8, 17, 59, 12, 7, 5, 22, 28, 35, 33, 31, 42, 51, 10}; SkipList list2; for (int i = 0; i < static_cast { cout << "add " << inputs2[i] << endl; list2.add(inputs2[i]); cout << "list2:\n" << list2 << endl; } if (list2.find(33)) cout << "33 is found!\n"; else cout << "33 is not found!!!!\n"; if (list2.find(70)) cout << "70 is found!\n"; else cout << "70 is not found!!!!\n"; if (list2.find(10)) cout << "10 is found!\n"; else cout << "10 is not found!!!!\n"; return 0; }
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill