您可以检查在C中实现递归合并排序功能时在哪里出错吗?

问题描述 投票:0回答:1

我已经尝试完成3天了,即使多次使用调试工具,我也找不到哪里出了问题。适用于2数组的大小,但适用于输入为55、34、76、12、45、76的大小为6的数组,排序后打印的数组得到不同的值,我的代码是:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int beg, int end);
void merg(int arr[], int beg, int mid, int end);
int main(void)
{
    int n = get_int("How many numbers? ");
    int* arr = malloc(sizeof(int)*n);
    for (int i = 0; i < n; i++)
    {
        printf("Enter %i Element of array: ", i + 1);
        arr[i] = get_int("");
    }
    sort(arr, 0, n-1);
    for (int i = 0; i < n; i++)
    {
        printf("%i   ", arr[i]);
    }
    printf("\n");
}
void sort(int arr[], int beg, int end)
{
    if (beg != end)
    {
        int mid = (beg + end) / 2;
        sort(arr, beg, mid);
        sort(arr + mid + 1, mid + 1, end);
        merg(arr, beg, mid, end);
    }
}
void merg(int arr[],int beg, int mid, int end)
{
    int sizel = mid - beg + 1;
    int sizer = end - mid;
    int* left = malloc(sizeof(int) * (sizel));
    int* right = malloc(sizeof(int) * sizer);
    for (int i = 0; i < sizel; i++)
    {
        left[i] = arr[beg + i];
    }
    for (int i = 0; i < sizer; i++)
    {
        right[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = 0;
    for (k = 0; k <= end; k++)
    {
        if (i == sizel)
        {
            arr[k] = right[j];
            j++;
        }
        else if (j == sizer)
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            if (left[i] < right[j])
            {
                arr[k] = left[i];
                i++;
            }
            else
            {
                arr[k] = right [j];
                j++;
            }
        }
    }
    free(left);free(right);
    return;
}
c arrays recursion mergesort cs50
1个回答
1
投票

您的主要问题是您正在混淆符号。您可以通过start, lengthbase, lo, hi来标识子范围。

您有这个,其中一行执行一种方式,另一行执行另一种方式,但是做得不好:

    sort(arr, beg, mid);
    sort(arr + mid + 1, mid + 1, end);

您需要:

    sort(arr, beg, mid);
    sort(arr, mid + 1, end);

即始终使用start, lo, hi表示法。就目前而言,您要告诉代码访问数组之外​​的很长一段路。这并不意味着您的程序会自动崩溃,但会导致不确定的行为和错误的结果。

您应该创建一个类似“转储数组”的函数:

static void dump_array(const char *tag, int size, const int data[size])
{
    printf("%s (%d):", tag, size);
    for (int i = 0; i < size; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

这使您可以在需要时打印阵列。然后,在对sort()的第一个递归调用之后,您输入:

 dump_array("After 1st sub-sort", mid - beg + 1, &arr[beg]);

这样您就可以看到到达那里的内容,在第二次递归调用之后,在merg()之后的第三次调用之后,再看到。您也可以在其他地方打印(也可以选择输入该功能)。

在这种情况下,也许您应该对函数使用不同的设计:

static void dump_array(const char *tag, const int *data, int lo, int hi)
{
    printf("%s (%d:%d):", tag, lo, hi);
    for (int i = lo; i <= hi; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

现在您可以写:

sort(arr, beg + 0, mid);
dump_array("After 1st sub-sort", arr, beg + 0, mid);
sort(arr, mid + 1, end);
dump_array("After 2nd sub-sort", arr, mid + 1, end);

工作代码

此代码严重地重做了merg()函数,该函数存在许多问题。它也添加了我推荐的工具。

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

static void sort(int arr[], int beg, int end);
static void merg(int arr[], int beg, int mid, int end);
static void dump_array(const char *tag, const int *data, int lo, int hi);

int main(void)
{
    int n = get_int("How many numbers? ");
    int *arr = malloc(sizeof(int) * n);
    assert(arr != NULL);
    for (int i = 0; i < n; i++)
    {
        printf("Enter %i Element of array", i + 1);
        arr[i] = get_int(": ");
    }
    sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%i   ", arr[i]);
    }
    printf("\n");
}

static void sort(int arr[], int beg, int end)
{
    if (beg != end)
    {
        int mid = (beg + end) / 2;
        dump_array("-->> sort()", arr, beg, end);
        sort(arr, beg, mid);
        dump_array("After 1st sub-sort", arr, beg + 0, mid);
        sort(arr, mid + 1, end);
        dump_array("After 2nd sub-sort", arr, mid + 1, end);
        merg(arr, beg, mid, end);
        dump_array("<<-- sort()", arr, beg, end);
    }
}

static void merg(int arr[], int beg, int mid, int end)
{
    int sizel = mid - beg + 1;
    int sizer = end - mid;
    int *left = malloc(sizeof(int) * (sizel));
    int *right = malloc(sizeof(int) * sizer);
    assert(left != NULL && right != NULL);

    memcpy(left, arr + beg, sizel * sizeof(int));
    memcpy(right, arr + mid + 1, sizer * sizeof(int));

    int i = 0;
    int j = 0;
    int k = beg;
    while (i < sizel && j < sizer)
    {
        if (left[i] < right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    /* Only one of these loop bodies executes */
    while (i < sizel)
        arr[k++] = left[i++];
    while (j < sizer)
        arr[k++] = right[j++];

    free(left);
    free(right);
}

static void dump_array(const char *tag, const int *data, int lo, int hi)
{
    printf("%s (%d:%d):", tag, lo, hi);
    for (int i = lo; i <= hi; i++)
        printf(" %d", data[i]);
    putchar('\n');
}

我测试了一个名为data的文件,其中包含:

11
19
66
71
69
91
46
14
38
77
97
34

第一行11表示条目数;然后在10到99之间有11个随机数。运行ms71 < data的输出(忽略输入提示-由于从文件读取的数据未回显而显得愚蠢),输出为:

-->> sort() (0:10): 19 66 71 69 91 46 14 38 77 97 34
-->> sort() (0:5): 19 66 71 69 91 46
-->> sort() (0:2): 19 66 71
-->> sort() (0:1): 19 66
After 1st sub-sort (0:0): 19
After 2nd sub-sort (1:1): 66
<<-- sort() (0:1): 19 66
After 1st sub-sort (0:1): 19 66
After 2nd sub-sort (2:2): 71
<<-- sort() (0:2): 19 66 71
After 1st sub-sort (0:2): 19 66 71
-->> sort() (3:5): 69 91 46
-->> sort() (3:4): 69 91
After 1st sub-sort (3:3): 69
After 2nd sub-sort (4:4): 91
<<-- sort() (3:4): 69 91
After 1st sub-sort (3:4): 69 91
After 2nd sub-sort (5:5): 46
<<-- sort() (3:5): 46 69 91
After 2nd sub-sort (3:5): 46 69 91
<<-- sort() (0:5): 19 46 66 69 71 91
After 1st sub-sort (0:5): 19 46 66 69 71 91
-->> sort() (6:10): 14 38 77 97 34
-->> sort() (6:8): 14 38 77
-->> sort() (6:7): 14 38
After 1st sub-sort (6:6): 14
After 2nd sub-sort (7:7): 38
<<-- sort() (6:7): 14 38
After 1st sub-sort (6:7): 14 38
After 2nd sub-sort (8:8): 77
<<-- sort() (6:8): 14 38 77
After 1st sub-sort (6:8): 14 38 77
-->> sort() (9:10): 97 34
After 1st sub-sort (9:9): 97
After 2nd sub-sort (10:10): 34
<<-- sort() (9:10): 34 97
After 2nd sub-sort (9:10): 34 97
<<-- sort() (6:10): 14 34 38 77 97
After 2nd sub-sort (6:10): 14 34 38 77 97
<<-- sort() (0:10): 14 19 34 38 46 66 69 71 77 91 97
14   19   34   38   46   66   69   71   77   91   97   

可能有优化的空间,这样当要排序的数组只有一个元素时,代码就不会递归。

© www.soinside.com 2019 - 2024. All rights reserved.