C: Двоичный поиск и двоичная вставка

Один логический недостаток, который определенно может вызвать такие проблемы, как дамп ядра, связан со следующим разделом кода в вашей функции 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 , который «... инициализирует все байты в выделенном хранилище нулевыми значениями», является вариантом, но, как говорится в комментарии Нила,

Даже calloc не гарантирует инициализацию нулевых указателей; это работает на большинстве компьютеров, потому что null, скорее всего, равен 0 (5.13).

Таким образом, чтобы повысить надежность, лучше добавить строку newNode->previous = NULL; сразу после строки memcpy(newNode->data, arr, size * sizeof(int)); в указанном мной разделе вашего кода.

Кроме того, чтобы при случайном чтении кода было более понятно, что newNode->next всегда инициализируется, и чтобы последующие изменения кода не нарушили ваш код, я предлагаю также добавить строку newNode->next = NULL; изначально.

Общие комментарии

Вы используете двоичный поиск в связанном списке, чтобы найти точку вставки для следующего узла. Бинарный поиск эффективен, когда у вас есть произвольный доступ к элементам, но гораздо менее эффективен, когда у вас его нет. Линейный поиск в вашем случае будет проще реализовать и, возможно, быстрее.

Даже если ваш связанный список не использует фиктивный головной узел, вы можете временно предоставить его для операций со связанным списком. Это могло бы обеспечить более чистый код, устранив необходимость специальной обработки пустого списка.

Вы используете неэффективное представление для простых факторизаций: массив показателей A_MAX. Однако ненулевые показатели степени будут только для простых чисел, поэтому вы можете легко обойтись гораздо более короткими массивами, где каждый элемент соответствует простому числу.

Главный вопрос

Во многих случаях вашей программе не удается инициализировать указатели previous своих динамически выделяемых узлов списка. В некоторых случаях не удается инициализировать указатель next. malloc() не инициализирует за вас выделенную память. calloc() инициализирует его нулевым байтом, но C не определяет, что это означает как представление указателя, поэтому даже с calloc() вам нужно будет явно присвоить значения членам-указателям выделенных вами узлов.

Дополнительные соображения

Вам вообще не нужно хранить или сравнивать факторизации, хотя я бы все равно их вычислил. Вы можете непосредственно определить по каждой факторизации a^b, будет ли она также считаться как a'^b', где a' < a:

• вычислите наибольший общий знаменатель d(a) всех ненулевых показателей степени в простой факторизации числа a. Часто это будет 1.

• Тогда существует целое положительное число a₀ такое, что a₀^d(a) = a. Не существует меньшего натурального числа r такого, что a является целой степенью r.

• a^b, конечно, также является целой степенью a₀: a₀^d(a)b.

• Пусть x(a) = d(a)b. Вы избежите подсчета дубликатов, если будете считать только те a^b, где b — наименьший делитель x(a), такой что x(a) / b <= b_max. Если это не так, существует некоторая степень a₀ меньшая, чем a, для которой будет учитываться a^b.

вот как выглядит мой код с предложениями Джона Омилана! Невозможность инициализировать атрибут узла является основной причиной дампа ядра.

void insertSorted(struct Node **head, const int *arr, int size, int *listLength) {
    int comparison = -1;
    // unchanged code goes here.
    if (comparison != 0) {
        // more unchanges code goes here.
        if (comparison == -1) { // perform insert left
            newNode->next = current;
            if (current == NULL) {
                newNode->next = NULL;
            }else{
                newNode->next = current;                
                current->previous = newNode;
            }
            if (prev == NULL) {
                newNode->previous = NULL;
                *head = newNode;
            } else {
                newNode->previous = prev;
                prev->next = newNode;
            }
        } else if (comparison == 1) { // perform insert right
            newNode->next = nxt;
            if (current == NULL) {
                newNode->previous = NULL;
                *head = newNode;
            }else{
                newNode->previous = current;
                current->next = newNode;
            }

            if (nxt == NULL) {
                newNode->next = NULL;
            }else{
                newNode->next = nxt;
                nxt->previous = newNode;
            }
        }

        (*listLength)++;
    }
}