时间戳

首页 > 解决方案 > 合并中的段错误 - 在 C 中排序

c - 合并中的段错误 - 在 C 中排序

问题描述

我正在尝试使用归并排序对大小为 5500 的结构数组进行排序。但是，我很快就遇到了分段错误，因为我不允许使用 VLA。所以每次我递归地调用合并排序时，我都必须创建 2 个大小为 5500 的额外数组。

我希望能解决我的问题。我将在这里提供我的代码：

void merge(Student rightArr[], Student leftArr[], Student mergedArr[], int sizeOfRight, int sizeOfLeft) {
    int rightArrIndex = 0;
    int leftArrIndex = 0;
    int mergedArrIndex = 0;

    while (leftArrIndex < sizeOfLeft && rightArrIndex < sizeOfRight) {
        char *ptrLeft, *ptrRight;
        long gradeLeft = strtol(leftArr[leftArrIndex].grade, &ptrLeft, BASE_COUNT);
        long gradeRight = strtol(rightArr[rightArrIndex].grade, &ptrRight, BASE_COUNT);
        if (gradeLeft > gradeRight) {
            mergedArr[mergedArrIndex] = rightArr[rightArrIndex];
            rightArrIndex++;
        } else {
            mergedArr[mergedArrIndex] = leftArr[leftArrIndex];
            leftArrIndex++;
        }
        mergedArrIndex++;
    }
    if (leftArrIndex == sizeOfLeft) {
        for (int i = mergedArrIndex; i < (sizeOfLeft + sizeOfRight); i++) {
            mergedArr[i] = rightArr[rightArrIndex];
            rightArr++;
        }
    } else {
        for (int i = mergedArrIndex; i < (sizeOfLeft + sizeOfRight); i++) {
            mergedArr[i] = leftArr[leftArrIndex];
            leftArr++;
        }
    }
}

void mergeSort(Student studentsArray[], int amountOfStudents) {
    if (amountOfStudents <= 1) {
        return;
    }
    int leftSize = (amountOfStudents / 2);
    int rightSize = (amountOfStudents - leftSize);
    Student leftArr[5500], rightArr[5500];
    for (int i = 0; i < leftSize; i++) {
        leftArr[i] = studentsArray[i];
    }
    for (int i = 0; i < rightSize; i++) {
        rightArr[i] = studentsArray[i + leftSize];
    }
    mergeSort(leftArr, leftSize);
    mergeSort(rightArr, rightSize);
    merge(rightArr, leftArr, studentsArray, rightSize, leftSize);
}

标签： cmergesort

解决方案

好的，我认为这应该做你想要的。它假设Student并且BASE_COUNT已经定义：

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

void merge(Student studentsArr[],
           int leftSize, int rightSize,
           Student scratchArr[])
{
    Student *leftArr = studentsArr;
    Student *rightArr = studentsArr + leftSize;
    int leftIx = 0, rightIx = 0, mergeIx = 0, ix;

    while (leftIx < leftSize && rightIx < rightSize) {
        long gradeLeft = strtol(leftArr[leftIx].grade, NULL, BASE_COUNT);
        long gradeRight = strtol(rightArr[rightIx].grade, NULL, BASE_COUNT);

        if (gradeLeft <= gradeRight) {
            scratchArr[mergeIx++] = leftArr[leftIx++];
        }
        else {
            scratchArr[mergeIx++] = rightArr[rightIx++];
        }
    }

    while (leftIx < leftSize) {
        scratchArr[mergeIx++] = leftArr[leftIx++];
    }

    // Copy the merged values from scratchArr back to studentsArr.
    // The remaining values from rightArr (if any) are already in
    // their proper place at the end of studentsArr, so we stop
    // copying when we reach that point.

    for (ix = 0; ix < mergeIx; ix++) {
        studentsArr[ix] = scratchArr[ix];
    }

}

void mergeSortInternal(Student studentsArray[],
                       int amountOfStudents,
                       Student scratchArr[])
{
    if (amountOfStudents <= 1) {
        return;
    }

    int leftSize = amountOfStudents / 2;
    int rightSize = amountOfStudents - leftSize;

    mergeSortInternal(studentsArray, leftSize, scratchArr);
    mergeSortInternal(studentsArray + leftSize, rightSize, scratchArr);

    merge(studentsArray, leftSize, rightSize, scratchArr);
}

#define MAX_ARR_SIZE    5500

void mergeSort(Student studentsArray[], int amountOfStudents)
{
    if (amountOfStudents <= 1) {
        return;
    }

    if (amountOfStudents > MAX_ARR_SIZE) {
        fprintf(stderr, "Array too large to sort.\n");
        return;
    }

    Student scratchArr[MAX_ARR_SIZE];

    mergeSortInternal(studentsArray, amountOfStudents, scratchArr);
}

顶级排序函数是mergeSort，如原始帖子中定义的那样。它声明了一个大小为 的临时数组MAX_ARR_SIZE，定义为5500。顶层函数本身不是递归的，所以这个临时数组只分配一次。

推荐阅读