C：二分查找和二分插入

Question

我目前正在致力于解决欧拉项目上的不同幂问题 (29)。该问题涉及查找 (a^b) 的不同乘积的数量，其中 (2 < a < 100) and (2 < b < 100). I initially created an algorithm that successfully handles factorization and checks for duplications. However, as I attempted to enhance the program's performance using linked lists and binary search, I encountered issues leading to a core dump. Despite efforts to identify logical flaws, I couldn't resolve the problem.

这是我正在使用的代码片段：

#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 is left of arr1
        } else if (arr1[k] < arr2[k]) {
            return 1; // arr2 is right of arr1
        }
    }
    return 0; // arr2 is arr1
}

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 is right of arr1
            left = mid + 1;
        } else if (comparison == -1) { // arr2 is left of 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) { // perform insert left
            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) { // perform insert right
            newNode->next = nxt;
            if (current != NULL) {
                current->next = newNode;
            }
            if (nxt != NULL) {
                nxt->previous = newNode;
            }
        } else { // no node exist yet. make node the head.
            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;
}```

Answer 1

insertSorted

函数中的以下部分代码存在一个逻辑缺陷，它肯定会导致发生核心转储等问题：

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

        if (comparison == -1) { // perform insert left
            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) { // perform insert right
            newNode->next = nxt;
            if (current != NULL) {
                current->next = newNode;
            }
            if (nxt != NULL) {
                nxt->previous = newNode;
            }
        } else { // no node exist yet. make node the head.
            printf("lol");
            *head = newNode;
            
        }

代码使用

malloc

为

newNode

分配内存，但是，如 malloc 手册页所示，

内存未初始化。

由于

comparison

只能为 0、-1 或 1，并且此代码位于条件

if (comparison != 0) {

内，因此最终的

else

永远不应该被执行。因此，

newNode->next

的值始终设置为有效值。然而，对于 newNode->previous 来说，情况并非总是如此。例如，如果

comparison == -1

，则仅当

newNode->previous

时才设置

prev != NULL

。这意味着

newNode->previous

可能未初始化，因此将其与

current = current->previous;

中前面的

insertSorted

行一起使用可能会导致访问无效内存。此问题可以轻松解决，例如将

malloc

调用替换为

calloc

，“...将分配的存储中的所有字节初始化为零”，或者在 newNode->previous = NULL; 之后添加行 memcpy(newNode->data, arr, size * sizeof(int)); 代码中我指定部分的行。另外，如果您不使用

calloc

，那么为了在随意阅读代码时更清楚

newNode->next

始终被初始化，并且为了在将来潜在的代码更改时更加稳健，我建议添加最初也是

newNode->next = NULL;

线。

Answer 2

您可以在链表上使用二分搜索来定位下一个节点的插入点。当您可以随机访问项目时，二分搜索非常有效，但当您不能随机访问时，二分搜索的效率就低得多。在您的情况下，线性搜索会更容易实现，而且可能也更快。

即使您的链表不使用虚拟头节点，您也可以临时提供一个用于链表操作的目的。通过消除对空列表的特殊情况处理的需要，可以提供更清晰的代码。

您对质因数分解使用了一种低效的表示形式：一组

A_MAX

指数。然而，仅素数才会有非零指数，因此您可以轻松地使用更短的数组，其中每个元素对应于一个素数。

主要问题

在许多情况下，您的程序无法初始化其动态分配的列表节点的

previous

指针。在某些情况下，它也无法初始化

next

指针。

malloc()

不会为您初始化分配的内存。

calloc()

将其初始化为全字节零，但 C 没有定义指针表示的含义，因此即使使用

calloc()

，您也需要显式地将值分配给已分配节点的指针成员。其他注意事项

您根本不需要存储或比较因式分解，尽管我仍然会计算它们。您可以直接从

a

b ^{的每个因式分解中确定它是否也被计为 a'}b'^{，其中 a'} a:<

计算
• a

  素因数分解中所有非零指数的最大公分母 d(a)。

则有一个正整数
• a

  0，使得 _a0d^{(a) = a}。不存在更小的正整数 r 使得 a 是 r 的整数幂。 当然，

• a

  b^也是a0的整数幂：_a0d^(a)b.

令
• x

  (a) = d(a)b。如果您只计算那些 ab^{，您将避免计算任何重复项，其中 b} 是 x(a) 的最小除数，使得 x(a) / b b<= 最大。如果情况并非如此，则 _a0 的某些幂小于 _a，因此将计算 ab^。