c - 你能检查一下我在 C 中实现递归合并排序函数时出错的地方吗？
问题描述
我已经尝试完成 3 天了，即使在多次使用调试工具后，我也找不到哪里出了问题。适用于大小为 2 的数组，但对于大小为 6 的数组，输入：55,34,76,12,45,76 在排序后打印数组时我得到不同的值，我的代码是这样的：
#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;
}
解决方案
你的主要问题是你混淆了符号。start, length您可以通过或来识别子范围base, 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
可能有优化空间，以便在要排序的数组只有一个元素时代码不会递归。
推荐阅读
- python - 如何使 kivy 工作？我安装时出错
- c# - 带有 EF Core 迁移的抽象类
- docker - 第一步创建的gitlab神器可以直接在第二步的docker中使用吗
- scala - 寻找适用于 Monad 的一些但不是所有属性的结构的示例
- html - 在移动设备中设置内容堆叠顺序（HTML 电子邮件）
- dask - 包装在 xarray 数据集中的 dask 数组子集上的并行任务
- ios - 访问 Xcode 按钮文本但未反映背景更改 UI
- javascript - 根据相对于另一个元素的滚动深度附加一个类
- javascript - 在 ejs 的帮助下从数据库中呈现 html 时，功能无法正常工作
- c++ - 在 64 位 Visual Studio 上替代 __asm _emit