2

我正在尝试用 C 编写作业代码，该代码将从用户输入中获取 10 个整数到一个数组中，并使用递归合并排序对其进行排序。我们还没有讨论过指针，所以我想避免在我的代码中使用它（许多在线示例使用指针）。

这是我的代码：

/* This code will take input for 10 integers given by the user
into an array, sort them with a recursive merge function
and print the updated array in ascending order. */

#include <stdio.h>
#define ARRSIZE 10

void merge_sort (int arr[], int temp[], int left, int right);
void merge (int arr[], int temp[], int left, int mid, int right);

int main (void){
    int arr[ARRSIZE], temp[ARRSIZE], left, right, i;

    printf("Enter 10 integers for an array:");
    for(i=0;i<ARRSIZE;i++){
        printf("\narray value %d:", i+1);
        scanf("%d", &arr[i]);
    }
    left = 0;
    right = ARRSIZE-1;

    merge_sort(arr, temp, left, right);

    printf("\nHere is your updated array:");
    printf("\n{");
    for(i=0;i<ARRSIZE;i++){
        printf("%d,", arr[i]);
    }
    printf("}");

    return 0;
}

void merge_sort (int arr[], int temp[], int left, int right){
    if(left<right){
        int mid = (right-left)/2;
        merge_sort(arr, temp, left, mid);
        merge_sort(arr, temp, mid+1, right);
        merge(arr, temp, left, mid, right);
    }
}

void merge (int arr[], int temp[], int left, int mid, int right){
    int i, j, tempi = 0;
    for(i=left, j=mid+1; i<=mid && j<=right ;){
        // mid+1 is the start of the right array
        if(arr[i]<arr[j] && i<=mid){
            temp[tempi] = arr[i];
            tempi++;
            i++;
        }
        else if(arr[i]>arr[j] && j<=right){
                temp[tempi] = arr[j];
                tempi++;
                j++;
             }
    }
    for(i=0,j=right; i<=j; i++){
        arr[i] = temp[i];
    }
}

当我在我的 linux shell 中运行它时，我不断收到分段错误。有什么建议么？

4

1 回答 1

2

好吧，我已经发现了一个微妙的错误：int mid = (right-left)/2;应该是int mid = (left+right)/2;

另外，我发现了什么流程：

  1. 为了简单起见，您应该使用tempi = left。只需将数组的传入部分复制到临时数组的相应部分。

  2. 在合并周期中，您可以在定义中放置递增 tempi for：

    for( ...; ...; ++tempi)

  3. 在该循环中，您在从该位置读取值后检查边界。这真是太糟了。非常。虽然，您在这里没有遇到任何问题，只是因为您正在检查for定义内的边界:) 只需删除它们：

    for (i = left, j = 1 + mid; i <= mid && j <= right; ++tempi)
{  
    if (arr[i] < arr[j])        temp[tempi] = arr[i++];
    else /* arr[j] <= arr[i] */ temp[tempi] = arr[j++];
}

  4. 因为当任一子数组到达结束时此循环退出，您必须将其余项目从另一个子数组复制到 temp[]：

    if (i > mid) i = j; /* if we need to copy right subarray */
for (; tempi <= right; ++tempi, ++i) temp[tempi] = arr[i];

  5. 所以，你从临时数组复制回来看起来像

     for (i = left; i <= right; ++i) arr[i] = temp[i];
于 2013-02-18T01:29:17.323 回答