Project Euler第29题：链表+二分查找实现触发核心转储求助

我正在解决Project Euler的「不同幂问题（第29题）」，目标是找出当2≤a≤100且2≤b≤100时，a^b的不同结果数量。最初的算法能完成因式分解与重复检查，但尝试用链表结合二分查找优化性能时，程序触发核心转储，无法定位逻辑缺陷。以下是相关代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define A_MIN 2
#define A_MAX 100
#define B_MIN 2
#define B_MAX 100

struct Node {
    int *data;
    struct Node *next;
    struct Node *previous;
};

void primeFactor(int *arr, int num) {
    for (int k = 2; k <= num; ++k) {
        while (num % k == 0) {
            num /= k;
            arr[k] += 1;
        }
    }
}

int compareArrays(const int *arr1, const int *arr2, int size) {
    for (int k = 0; k < size; ++k) {
        if (arr2[k] < arr1[k]) {
            return -1; // arr2在arr1左侧
        } else if (arr1[k] < arr2[k]) {
            return 1; // arr2在arr1右侧
        }
    }
    return 0; // 两个数组相等
}

void insertSorted(struct Node **head, const int *arr, int size, int *listLength) {
    struct Node *current = *head;

    int pos = 0;
    int left = 0;
    int right = *listLength;

    int comparison = -3;
    
    while (current != NULL && left < right) {
        int mid = (left + right) / 2;
        while (pos < mid) {
            current = current->next;
            pos++;
        }
        while (pos > mid) {
            current = current->previous;
            pos--;
        }
        comparison = compareArrays(current->data, arr, size);
        if (comparison == 1) { // arr2在arr1右侧，往右找
            left = mid + 1;
        } else if (comparison == -1) { // arr2在arr1左侧，往左找
            right = mid;
        } else {
            break;
        }
    }

    struct Node *prev = (current != NULL) ? current->previous : NULL;
    struct Node *nxt = (current != NULL) ? current->next : NULL;

    if (comparison != 0) {
        struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
        if (newNode == NULL) {
            perror("Memory allocation error");
            exit(EXIT_FAILURE);
        }

        newNode->data = (int *)malloc(size * sizeof(int));
        if (newNode->data == NULL) {
            perror("Memory allocation error");
            exit(EXIT_FAILURE);
        }

        memcpy(newNode->data, arr, size * sizeof(int));

        if (comparison == -1) { // 插入到current左侧
            newNode->next = current;
            if (current != NULL) {
                current->previous = newNode;
            }
            if (prev == NULL) {
                *head = newNode;
            } else {
                prev->next = newNode;
                newNode->previous = prev;
            }
        } else if (comparison == 1) { // 插入到current右侧
            newNode->next = nxt;
            if (current != NULL) {
                current->next = newNode;
            }
            if (nxt != NULL) {
                nxt->previous = newNode;
            }
        } else { // 链表为空，设为头节点
            printf("lol");
            *head = newNode;
            
        }

        (*listLength)++;
    }
}

void freeLinkedList(struct Node *head) {
    while (head != NULL) {
        struct Node *temp = head;
        head = head->next;
        free(temp->data);
        free(temp);
    }
}

int main() {
    struct Node *link_list = NULL;
    int size = A_MAX;
    int listLength = 0;

    for (int i = A_MIN; i <= A_MAX; ++i) {
        int arr[A_MAX] = {0};
        primeFactor(arr, i);

        for (int j = B_MIN; j <= B_MAX; ++j) {
            int *arr2 = (int *)malloc(size * sizeof(int));
            if (arr2 == NULL) {
                perror("Memory allocation error");
                exit(EXIT_FAILURE);
            }

            for (int k = 0; k < size; ++k) {
                arr2[k] = arr[k] * j;
            }

            insertSorted(&link_list, arr2, size, &listLength);
        }
    }

    printf("%d\n", listLength);

    freeLinkedList(link_list);

    return 0;
}

问题根源与修复方案 #

1. 二分查找的指针移动逻辑错误 #

原代码中，二分循环依赖上一次的current和pos来定位mid位置，当二分区间变化时，指针没有从链表头部重新定位，会导致指针越界（比如mid超过链表实际长度时），触发段错误。

修复：每次计算mid后，从head重新遍历到对应位置：

while (left < right) {
    int mid = (left + right) / 2;
    // 从头部重新定位到mid节点
    current = *head;
    for (int i = 0; i < mid; i++) {
        current = current->next;
    }
    comparison = compareArrays(current->data, arr, size);
    if (comparison == 1) {
        left = mid + 1;
    } else if (comparison == -1) {
        right = mid;
    } else {
        return; // 元素重复，无需插入
    }
}

2. 空链表初始插入逻辑缺失 #

当链表为空时，current为NULL，循环不会执行，comparison保持初始值-3，插入分支的逻辑会陷入未定义状态。

修复：在函数开头单独处理空链表情况：

if (*head == NULL) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    if (newNode == NULL) { perror("Memory allocation error"); exit(EXIT_FAILURE); }
    newNode->data = (int *)malloc(size * sizeof(int));
    if (newNode->data == NULL) { perror("Memory allocation error"); exit(EXIT_FAILURE); }
    memcpy(newNode->data, arr, size * sizeof(int));
    newNode->next = newNode->previous = NULL;
    *head = newNode;
    (*listLength)++;
    return;
}

3. 内存泄漏问题 #

main函数中每次分配的arr2，如果元素重复未插入，会没有被释放，造成内存泄漏。

修复：调用insertSorted后立即释放arr2：

insertSorted(&link_list, arr2, size, &listLength);
free(arr2); // 无论是否插入都释放

4. 插入位置的边界处理错误 #

原代码中插入到右侧的逻辑没有正确维护newNode的previous指针，导致链表断裂。

修复：统一插入逻辑，根据二分得到的left位置确定插入点：

// 定位到插入位置的前驱节点
current = *head;
if (left > 0) {
    for (int i = 0; i < left - 1; i++) {
        current = current->next;
    }
}

struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
// 内存分配逻辑...

if (left == 0) {
    // 插入头部
    newNode->next = *head;
    (*head)->previous = newNode;
    *head = newNode;
} else if (left == *listLength) {
    // 插入尾部
    current->next = newNode;
    newNode->previous = current;
} else {
    // 插入中间
    newNode->next = current->next;
    newNode->previous = current;
    current->next->previous = newNode;
    current->next = newNode;
}

额外建议 #

对于该题，总共有99×99=9801个候选值，重复数量有限，完全可以用哈希表（如C语言的uthash库）替代链表存储因式分解结果，实现更简单且性能足够，无需使用链表+二分查找（链表本身不适合二分，每次定位mid都需要遍历，效率低下）。

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