我不确定为什么我的 C 代码免费给我一个分割错误，有什么想法吗？-解网

问：

所以这是我的代码，它一直运行到免费（右）;更像是它完成了合并排序然后出现错误，有什么解决方案吗？

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

void bubble_sort(int *l, int len) {
    // Iterate through the list
    for (int i = 0; i < len; i++) {
        // Iterate through the list
        for (int j = 0; j < len - 1; j++) {
            // If the current element is greater than the next element, swap them
            if (l[j] > l[j + 1]) {
                // Swap the elements
                int temp = l[j];
                l[j] = l[j + 1];
                l[j + 1] = temp;
                // Print the list
                for (int k = 0; k < len; k++) {
                    printf("%d ", l[k]);
                }
                printf("\n");
            }
        }
    }
}

void selection_sort(int *l, int len) {
    // Iterate through the list
    for (int i = 0; i < len; i++) {
        // Set the minimum index to the current index
        int min_index = i;
        // Iterate through the list
        for (int j = i + 1; j < len; j++) {
            // If the current element is less than the minimum element, set the minimum index to the current index
            if (l[j] < l[min_index]) {
                min_index = j;
            }
        }
        // Swap the elements
        int temp = l[i];
        l[i] = l[min_index];
        l[min_index] = temp;
        // Print the list
        for (int k = 0; k < len; k++) {
            printf("%d ", l[k]);
        }
        printf("\n");
    }
}

void insertion_sort(int *l, int len) {
    // Iterate through the list
    for (int i = 1; i < len; i++) {
        // Set the current index to the current index
        int j = i;
        // While the current index is greater than 0 and the previous element is greater than the current element, swap them
        while (j > 0 && l[j - 1] > l[j]) {
            // Swap the elements
            int temp = l[j - 1];
            l[j - 1] = l[j];
            l[j] = temp;
            // Decrement the current index
            j--;
        }
        // Print the list
        for (int k = 0; k < len; k++) {
            printf("%d ", l[k]);
        }
        printf("\n");
    }
}
void merge(int *left, int left_len, int *right, int right_len) {
    // Create a new list
    int *result = malloc((left_len + right_len) * sizeof(int));
    // Set the left index to 0 and the right index to 0
    int i = 0;
    int j = 0;
    // While the left index is less than the length of the left list and the right index is less than the length of the right list
    while (i < left_len && j < right_len) {
        // If the left element is less than or equal to the right element, append the left element to the result list and increment the left index
        if (left[i] <= right[j]) {
            result[i + j] = left[i];
            i++;
        }
        // Else, append the right element to the result list and increment the right index
        else {
            result[i + j] = right[j];
            j++;
        }
    }
    // Append the remaining elements in the left list to the result list
    for (int k = i; k < left_len; k++) {
        result[k + j] = left[k];
    }
    // Append the remaining elements in the right list to the result list
    for (int k = j; k < right_len; k++) {
        result[k + i] = right[k];
    }
    // Print the result list
    for (int k = 0; k < left_len + right_len; k++) {
        printf("%d ", result[k]);
    }
    printf("\n");
    // Copy the result list to the original list
    for (int k = 0; k < left_len + right_len; k++) {
        left[k] = result[k];
    }
    // Free the result list
    free(result);
}
void merge_sort(int *l, int len) {
    // If the list is empty or has one element, return the list
    if (len <= 1) {
        return;
    }
    // Set the middle index to the length of the list divided by 2
    int mid = len / 2;
    // Set the left list to the first half of the list
    int *left = malloc(mid * sizeof(int));
    for (int i = 0; i < mid; i++) {
        left[i] = l[i];
    }
    // Set the right list to the second half of the list
    int *right = malloc((len - mid) * sizeof(int));
    for (int i = mid; i < len; i++) {
        right[i - mid] = l[i];
    }
    // Sort the left list
    merge_sort(left, mid);
    // Sort the right list
    merge_sort(right, len - mid);
    // Merge the left list and the right list
    merge(left, mid, right, len - mid);
    // Free the left list and the right list
    free(left);
    free(right);                                       //Error ln 142, in picture below
}

int binary_search(int *l, int len, int target) {
    // Set the low index to 0 and the high index to the length of the list minus 1
    int low = 0;
    int high = len - 1;
    // While the low index is less than or equal to the high index
    while (low <= high) {
        // Set the middle index to the sum of the low index and the high index divided by 2
        int mid = (low + high) / 2;
        // If the middle element is equal to the target, return the middle index
        if (l[mid] == target) {
            return mid;
        }
        // Else if the middle element is less than the target, set the low index to the middle index plus 1
        else if (l[mid] < target) {
            low = mid + 1;
        }
        // Else, set the high index to the middle index minus 1
        else {
            high = mid - 1;
        }
    }
    // If the target is not found, return -1
    return -1;
}

int main() {
    // Create a list
    int l[] = {17, 36, 3, 10, 29, 42, 34, 8};
    int len = sizeof(l) / sizeof(l[0]);
    // Print the list
    printf("Bubble Sort:\n");
    // Sort the list using bubble sort
    bubble_sort(l, len);
    // Print the list
    printf("Selection Sort:\n");
    // Sort the list using selection sort
    selection_sort(l, len);
    // Print the list
    printf("Insertion Sort:\n");
    // Sort the list using insertion sort
    insertion_sort(l, len);
    // Print the list
    printf("Merge Sort:\n");
    // Sort the list using merge sort
    merge_sort(l, len);
    // Print the list
    printf("Binary Search:\n");
    // Search for the target in the list using binary search
    printf("%d\n", binary_search(l, len, 42));
    return 0;
}

所以我将代码从 python 重写为 C，在 GDB 中调试给了我屏幕截图中的错误。

GDB ss

我试图编辑函数本身以纠正内存问题，但它不起作用，所以我又回到了这个，希望有人有更多的见解。

C 分段故障 GDB malloc

void merge_sort(int *l, int len) {
    if (len <= 1) {
        return;
    }
    int mid = len / 2;
    int *left = malloc(len * sizeof(int));
    for (int i = 0; i < mid; i++) {
        left[i] = l[i];
    }
    int *right = left + mid;
    for (int i = mid; i < len; i++) {
        right[i - mid] = l[i];
    }
    merge_sort(left, mid);
    merge_sort(right, len - mid);
    merge(left, mid, right, len - mid);
    free(left);
}

更好的解决方案是：

严格区分受测代码和测试工具。在本例中，您希望委托给复制输入数组的任务，而不是在排序算法中执行此操作。这允许就地对输入数组进行操作（仍然使用临时数组）。main()merge_sort()merge()
消除指向的数组指针参数。这记录了左数组和右数组是同一数组的一部分。rightmerge()
重构 and 接口，使 length 参数位于数组参数之前，以便您可以记录它们之间的关系。merge()merge_sort()
（不固定）。您可以分配合并所需的临时空间，并将其传递给和。这样一来，您就只有空间开销，而不是 .值得指出的是，可能需要内核上下文切换，这反过来又是 + 实现中最昂贵的操作。执行 1 而不是 n*log（n）调用可能是运行时的一个重要（常量）因素。但是，共享临时空间是有成本的，因为您将无法再并行执行其他不重叠的合并排序。merge_sort()merge_sort2()merge2()O(n)O(n*log(n))malloc()merge()merge_sort()malloc()
首选类型而不是长度。sizeof（）尤其返回一个值，并且对于大于的大小，转换为（signed）将是有问题的。size_tintsize_tintINTMAX
如果可能，首选而不是显式循环。经过高度优化，简洁地表达了意图。memcpy()memcpy()
首选将变量而不是类型传递给。如果更改变量的类型，则前者是可靠的，而后者在未使用 a 作为类型时需要更改代码。sizeof()typedef
最后，我添加了一个函数，因此您不需要在排序函数本身中使用debug print语句。print()

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

void merge(size_t left_len, size_t right_len, int l[left_len + right_len]) {
    int *result = malloc((left_len + right_len) * sizeof(*l));
    int i = 0;
    int j = 0;
    while (i < left_len && j < right_len) {
        if (l[i] <= l[left_len + j]) {
            result[i + j] = l[i];
            i++;
        } else {
            result[i + j] = l[left_len + j];
            j++;
        }
    }
    memcpy(result + i + j, l + i, (left_len - i) * sizeof(*l));
    memcpy(result + left_len + j, l + left_len + j, (right_len - j) * sizeof(*l));
    memcpy(l, result, (left_len + right_len) * sizeof(*l));
    free(result);
}

void merge_sort(size_t len, int l[len]) {
    if (len < 2) return;
    int mid = len / 2;
    merge_sort(mid, l);
    merge_sort(len - mid, l + mid);
    merge(mid, len - mid, l);
}

void print(size_t len, int a[len]) {
    for(size_t i = 0; i < len; i++) {
        printf("%d%s", a[i], i + 1 < len ? ", " : "\n");
    }
}

int main() {
    int l[] = {17, 36, 3, 10, 29, 42, 34, 8};
    size_t len = sizeof(l) / sizeof(*l);
    int l2[len];
    memcpy(l2, l, sizeof(l));
    merge_sort(len, l2);
    print(len, l2);
}

它返回：

3, 8, 10, 17, 29, 34, 36, 42

Valgrind 很高兴：

ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

上一个：在 C 中为多个测试用例返回 -11

下一个：C 在函数中分配内存后无法释放内存

我不确定为什么我的 C 代码免费给我一个分割错误，有什么想法吗？

I'm not sure why my code in C is giving me a segmentation fault at free, any ideas?

评论