C++ Skip List实现段错误及插入/搜索异常排查求助

Hey there! Let's work through your skip list troubles and get things sorted before your deadline. I’ll break this down into troubleshooting the original segmentation fault, fixing the post-fix insertion/search glitches, and sharing some optimization tips.

The segfault here is almost certainly tied to invalid memory access. Common culprits include:

• Out-of-bounds array access: If your initial code used 1-based level indexing but your update array or node forward pointers were sized for 0-based, you’d hit this when accessing non-existent indexes. For example, a loop going up to MAX_LEVEL (1-based) would try to access index MAX_LEVEL in an array that only goes to MAX_LEVEL - 1.
• Uninitialized pointers: If your update array (used to track predecessor nodes for insertion) wasn’t properly allocated, or the head node’s forward pointers weren’t set to NULL, the loop could dereference a wild pointer.
• Mismatched level limits: If your loop didn’t cap traversal at the skip list’s current maximum level, you might try to access a level that hadn’t been initialized yet.

Now that you’ve switched to 0-based indexing (starting level at 0), inconsistent behavior usually stems from mixed indexing logic or broken node linkages. Here’s what to check:

1. Ensure Consistent Level Indexing Everywhere #

Double-check every part of your code that references levels:

• When traversing for insertion/search, start from the current highest level minus 1 (since 0-based) and loop down to 0.
• Make sure your random level generator doesn’t produce levels beyond MAX_LEVEL - 1. A correct generator looks like this:

int random_level() {
    int level = 0;
    // Flip "coins" until we get tails, or hit the max level
    while (rand() % 2 == 0 && level < MAX_LEVEL - 1) {
        level++;
    }
    return level;
}

• Confirm your update array is sized to MAX_LEVEL so it can hold a predecessor for every possible level.

2. Verify Insertion Linkage Logic #

Insertion glitches usually happen because the update array isn’t capturing the right predecessors, or you’re linking the new node incorrectly. Here’s a solid 0-based insertion flow:

// Initialize update array with head node
Node *update[MAX_LEVEL];
Node *current = head;

// Traverse from top level down to bottom
for (int i = current_highest_level - 1; i >= 0; i--) {
    while (current->forward[i] != NULL && current->forward[i]->value < new_val) {
        current = current->forward[i];
    }
    update[i] = current;
}

// Generate random level for new node
int new_level = random_level();

// If new level exceeds current highest, update head links and current level
if (new_level > current_highest_level - 1) {
    for (int i = current_highest_level; i <= new_level; i++) {
        update[i] = head;
    }
    current_highest_level = new_level + 1;
}

// Create new node and link it into the skip list
Node *new_node = create_node(new_val, new_level);
for (int i = 0; i <= new_level; i++) {
    new_node->forward[i] = update[i]->forward[i];
    update[i]->forward[i] = new_node;
}

Key checks here:

• When the new node’s level is higher than the current maximum, populate the update array for those new levels with the head node.
• Link the new node’s forward pointers before updating the predecessor’s pointers—this avoids breaking the existing chain.

3. Fix Search Function Logic #

Your search function must mirror the insertion traversal logic to find nodes correctly. A working 0-based search looks like this:

Node *search(int target) {
    Node *current = head;
    // Traverse from top level down
    for (int i = current_highest_level - 1; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->value < target) {
            current = current->forward[i];
        }
    }
    // Move to the bottom level to check for a match (bottom has all nodes)
    current = current->forward[0];
    return (current != NULL && current->value == target) ? current : NULL;
}

If your search skipped levels or didn’t check the bottom level, it would miss valid entries.

To polish your skip list before the deadline:

• Add a print helper: Write a function to print each level of the skip list. This lets you visually verify if nodes are linked correctly. Example:

void print_skip_list() {
    printf("Skip List Structure:\n");
    for (int i = current_highest_level - 1; i >= 0; i--) {
        printf("Level %d: ", i);
        Node *current = head->forward[i];
        while (current != NULL) {
            printf("%d ", current->value);
            current = current->forward[i];
        }
        printf("\n");
    }
}

• Seed the random number generator: Call srand(time(NULL)) at the start of your program—without this, you’ll get the same random level sequence every run, turning your skip list into a plain linked list.
• Add memory cleanup: Write a destroy_skip_list function to free all nodes and avoid memory leaks, especially if you’re running multiple test cases.
• Dynamic max level: Instead of a fixed MAX_LEVEL, calculate it based on the number of elements (e.g., MAX_LEVEL = log2(total_elements) + 1) to optimize space and performance.

If you’re still stuck, sharing the specific code around line 59 (and the insertion/random level functions) would help narrow things down even faster.

内容的提问来源于stack exchange，提问作者Maray97