时间戳

首页 > 解决方案 > Seg Fault 在指针数组上调用 mergesort

c - Seg Fault 在指针数组上调用 mergesort

问题描述

我正在尝试使用 C 中的线程。我需要我的一个线程处理整个数组的一半，并对其一半进行归并排序。为此，我为整个数组和两半数组创建了一个全局数组指针。是在运行时分配的malloc。

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

void *process1(void *arg);
void *process2(void *arg);
void *process3(void *arg);
void *process4(void *arg);
void *process5(void *arg);

void merge(int *arr, int l, int m, int r);
void mergeSort(int *arr, int l, int r);

int *array;
int *arr_first;
int *arr_second;
int arr_s;
size_t n_size;
int n_size_i;
pthread_mutex_t mutex;

main(int argc, char *argv[]) {

    arr_s = atoi(argv[1]);

    n_size = arr_s / 2;
    n_size_i = arr_s / 2;
    
    array = malloc (arr_s * sizeof (int));  
    
    arr_first = malloc(arr_s / 2 * sizeof(int));

    if (arr_s % 2 == 0)
        arr_second = malloc((n_size) * sizeof (int));
    else
        arr_second = malloc((n_size+1) * sizeof(int));
    
    pthread_t tid1, tid2, tid3, tid4, tid5;
    pthread_attr_t attr;

    pthread_attr_init(&attr);
    pthread_mutex_init(&mutex, NULL);

    pthread_create(&tid1, &attr, process1, NULL);
    pthread_join(tid1, NULL);

    printf("---------------------------------------------------------------------------THREAD 2 AND 3 ARE CURRENTLY SORTING THE NUMBERS-------------------------------------------------------------------------\n");

    pthread_create(&tid2, &attr, process2, NULL);
    pthread_create(&tid3, &attr, process3, NULL);
    
    pthread_join(tid2, NULL);
    pthread_join(tid3, NULL);

    pthread_create(&tid4, &attr, process4, NULL);   
    pthread_join(tid4, NULL);

    pthread_create(&tid5, &attr, process5, NULL);
    pthread_join(tid5, NULL);

    free(array);
    free(arr_first);
    free(arr_second);
    exit(0);    
}

这是我的线程在（线程 2）上遇到问题时该函数的样子 目前，它所做的所有事情都占用了整个数组的前半部分，并且一个接一个地取值并将其放入自己的值中。然后我打印出数组。然后最后调用mergesort数组指针。

void *process2(void *arg) {
    int j = 0;
    for (; j < (arr_s / 2); j++) {
        arr_first[j] = array[j];
    }

    int j2;
    for (j2 = 0; j2 < (arr_s / 2); j2++) {
        printf("*%d\t", arr_first[j2]);
        if ((j2 + 1) % 25 == 0 && j2 > 0)
            printf("\n");
    }   
    
    mergeSort(arr_first, 0, (arr_s / 2) - 1);
        
    pthread_exit (0);
}

这是我的合并和合并排序函数：

//Merges two subarrays of arr[]
//First subarry is arr[l..m]
//Second subarry is arr[m+1..r]
void merge(int *arr, int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    //create temp arrays
    int L[n1], R[n2];

    //copy data to temp array L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l+i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    //merge the temp arrays back in arr[l..r]
    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    //copy remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    //same for R[]
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int *arr, int l, int r) {
    if (l < r) {
        int m = 1 + (r - 1) / 2;

        //Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

出于某种原因，当我调用归并排序时，它会继续递归调用比数组中的偶数多得多的次数。我在 mergeSort 函数中的任何其他内容之前放置了一个 print 语句，并且 print 语句执行了 50000+ 次可能更多。但是，如果我在 mergeSort 内部的合并调用之前放置一个打印语句，它永远不会被执行。

标签： cpointerssegmentation-faultmergesortarray-pointer

解决方案

中点的计算不正确：和mergeSort之间存在混淆。它应该是：l1

    int m = l + (r - l) / 2;

命名变量l很容易出错。使用leftorlow代替：

void mergeSort(int *arr, int left, int right) {
    if (left < right) {
        int m = left + (right - left) / 2;

        //Sort first and second halves
        mergeSort(arr, left, m);
        mergeSort(arr, m + 1, right);

        merge(arr, left, m, right);
    }
}

推荐阅读