我有一个结构数组
typedef struct BinaryTreeNode {
BSTElementType userID;
BSTElementType count;
struct BinaryTreeNode *left;
struct BinaryTreeNode *right;
}BinaryTreeNode;
typedef BinaryTreeNode BSTNode;
我希望按升序合并排序数组 . 但是，当我执行合并时，没有任何变化 . 这是我用来创建struct数组的代码，以及 MergeSort 的函数调用 . maxUsers 是我从转换二叉树中的节点数得到的int，它应该是数组的最大数量 .
BSTNode *arr = (BSTNode *)malloc(maxUsers * sizeof(BSTNode));
MergeSort(arr, 0, maxUsers);
void Merge(BSTNode *arr, int low, int mid, int high) {
int mergedSize = high - low + 1;
BSTNode *temp = (BSTNode *)malloc(mergedSize * sizeof(BSTNode));
int mergePos = 0;
int leftPos = 0;
int rightPos = 0;
leftPos = low;
rightPos = mid + 1;
//printf("Starting Merge\n");
while (leftPos <= high && rightPos <= mid) {
if (arr[leftPos].count < arr[rightPos].count) {
temp[mergePos].userID = arr[leftPos].userID;
temp[mergePos].count = arr[leftPos].count;
++leftPos;
}
else {
temp[mergePos].userID = arr[rightPos].userID;
temp[mergePos].count = arr[rightPos].count;
++rightPos;
}
++mergePos;
}
while (leftPos <= mid) {
temp[mergePos].userID = arr[leftPos].userID;
temp[mergePos].count = arr[leftPos].count;
++leftPos;
++mergePos;
}
while (rightPos <= high) {
temp[mergePos].userID = arr[rightPos].userID;
temp[mergePos].count = arr[rightPos].count;
++rightPos;
++mergePos;
}
for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
arr[low + mergePos].userID = temp[mergePos].userID;
arr[low + mergePos].count = temp[mergePos].count;
}
}
void MergeSort(BSTNode *arr, int low, int high) {
int mid = 0;
if (low < high) {
mid = (low + high) / 2;
MergeSort(arr, low, mid);
MergeSort(arr, mid + 1, high);
Merge(arr, low, mid, high);
}
}
任何提示或提示将不胜感激！
编辑：当我尝试编写一些printf语句时，我注意到这些值是负面的 . 但是存储在结构中的值是正数 . 出现此错误的原因是什么？
printf("Left Pos: %d, Right Pos: %d\n", leftPos, rightPos);
while (leftPos <= mid && rightPos <= high) {
printf("Left Pos count: %d, Right Pos count: %d\n", arr[leftPos].count, arr[rightPos].count);
if (arr[leftPos].count < arr[rightPos].count) {
temp[mergePos].userID = arr[leftPos].userID;
temp[mergePos].count = arr[leftPos].count;
++leftPos;
}
1 回答
需要做出两个重要的变化：
在
Merge中，您有while (leftPos <= high && rightPos <= mid)但是您需要while (leftPos <= mid && rightPos <= high)（反转左/右比较值） .在
main()中 - 或者至少是调用MergeSort()的代码，你有MergeSort(arr, 0, maxUsers);但是你需要MergeSort(arr, 0, maxUsers-1);因为传递的值必须是arr[lo]和arr[hi]都是数组中的有效条目，当你传递maxUsers时你就是在告诉它arr[maxUsers]在没有的情况下有效 .第三个重要的变化是在退出
MergeSort()之前添加free(temp).我还选择用简单的单行结构分配来替换你的多行分配 .
这是代码的调试版本，但调试打印全部被注释掉了 . 当我解决问题时，一切都很活跃 . 在我调试时，即使我使用
rand()生成数据，我也没有故意使用srand()，所以我在每次运行时都使用相同的数据 . 当我确信代码是干净的，那么我使用srand(time(0));并改变了数组的大小，但在调试时，稳定性很重要 .其中一个关键的调试观察是
Merge()中的主循环从未进入过;这是对第一个问题的强烈暗示 . Oddball数据是第二个问题的强烈暗示 . 主要数据都在很好的范围内控制 .样本输出（YMMV，因为您可能没有使用完全相同的PRNG）：
样本运行（随机数据量）：
启用调试，固定大小的运行：
该代码在Mac OS X 10.11.6上的GCC 6.1.0和Valgrind 3.12-SVN下编译和运行 .