问题：
如何合并排序结构数组
充栋
我有一个结构数组
typedef struct BinaryTreeNode {
BSTElementType userID;
BSTElementType count;
struct BinaryTreeNode *left;
struct BinaryTreeNode *right;
}BinaryTreeNode;
typedef BinaryTreeNode BSTNode;
我希望合并并按升序排序数组。然而，当我执行合并时，没有任何变化。这是我用来创建struct数组的代码，以及MergeSort的函数调用。最大用户数是我从二叉树中转换节点数得到的整数，它应该是数组的最大数量。
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个答案
孟雪风
需要做出两个关键的改变：
>
在main（）-或至少在调用MergeSort（）的代码中，您有MergeSort（arr，0，maxUsers）
但是你需要合并排序（arr，0，maxUsers-1）
和arr[hi]都是数组中的有效项，当你传递maxUsers时，你告诉它arr[maxUsers]无效。
第三个重要变化是在退出MergeSort（）之前添加free（temp）。
我还选择用简单的单行结构作业取代多行作业。
这是一个调试版本的代码，但调试打印都被注释掉了。当我解决问题时，一切都很活跃。在调试时，尽管我使用了rand（）来生成数据，但我并没有刻意使用srand（），所以每次运行时都使用相同的数据。当我确信代码是干净的时，我使用了srand（时间（0）） 并改变阵列的大小，但在调试时，稳定性很重要。
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
typedef int BSTElementType;
typedef struct BinaryTreeNode
{
BSTElementType userID;
BSTElementType count;
struct BinaryTreeNode *left;
struct BinaryTreeNode *right;
} BinaryTreeNode;
typedef BinaryTreeNode BSTNode;
static void PrintArray(const char *tag, int n, BSTNode *array)
{
printf("%s:\n", tag);
for (int i = 0; i < n; i++)
printf("%2d: u = %4d, c = %2d\n", i, array[i].userID, array[i].count);
putchar('\n');
fflush(stdout);
}
static
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 = low;
int rightPos = mid + 1;
//printf("-->> %s: lo = %d, md = %d, hi = %d, sz = %d\n", __func__, low, mid, high, mergedSize);
//printf("L = %d, M = %d; R = %d, H = %d\n", leftPos, mid, rightPos, high);
while (leftPos <= mid && rightPos <= high) // Key change
{
//printf("a[%d].c = %d <=> a[%d].c = %d\n", leftPos, arr[leftPos].count,
// rightPos, arr[rightPos].count);
if (arr[leftPos].count < arr[rightPos].count)
{
//printf("L1: a[%d].c = %d\n", leftPos, arr[leftPos].count);
temp[mergePos++] = arr[leftPos++];
}
else
{
//printf("R1: a[%d].c = %d\n", rightPos, arr[rightPos].count);
temp[mergePos++] = arr[rightPos++];
}
//printf("L = %d, M = %d; R = %d, H = %d\n", leftPos, mid, rightPos, high);
}
while (leftPos <= mid)
{
//printf("L2: a[%d].c = %d\n", leftPos, arr[leftPos].count);
temp[mergePos++] = arr[leftPos++];
}
while (rightPos <= high)
{
//printf("R2: a[%d].c = %d\n", rightPos, arr[rightPos].count);
temp[mergePos++] = arr[rightPos++];
}
assert(mergePos == mergedSize);
//PrintArray("merged", mergedSize, temp);
for (mergePos = 0; mergePos < mergedSize; ++mergePos)
arr[low + mergePos] = temp[mergePos];
free(temp); // Key change
//printf("<<-- %s: lo = %d, md = %d, hi = %d, sz = %d\n", __func__, low, mid, high, mergedSize);
}
static
void MergeSort(BSTNode *arr, int low, int high)
{
if (low < high)
{
int mid = (low + high) / 2;
//printf("-->> %s: lo = %d, md = %d, hi = %d\n", __func__, low, mid, high);
MergeSort(arr, low, mid);
MergeSort(arr, mid + 1, high);
Merge(arr, low, mid, high);
//printf("<<-- %s: lo = %d, md = %d, hi = %d\n", __func__, low, mid, high);
}
}
int main(void)
{
/* Unstable when testing */
//srand(time(0));
//int maxUsers = rand() % 20 + 5;
/* Stable while debugging */
int maxUsers = 10;
BSTNode *arr = (BSTNode *)malloc(maxUsers * sizeof(BSTNode));
for (int i = 0; i < maxUsers; i++)
{
arr[i].userID = rand() % 100 * 100;
arr[i].count = rand() % 10;
arr[i].left = 0;
arr[i].right = 0;
}
PrintArray("Before", maxUsers, arr);
MergeSort(arr, 0, maxUsers - 1); // Key change
PrintArray("After", maxUsers, arr);
free(arr);
return 0;
}
一个关键的调试观察结果是，Merge（）中的主循环从未进入；这是对第一个问题的有力暗示。奇怪的数据有力地说明了第二个问题。主要数据都在范围内得到了很好的控制。
示例输出（YMMV，因为您可能没有使用完全相同的PRNG）：
Before:
0: u = 7900, c = 9
1: u = 3900, c = 5
2: u = 5500, c = 3
3: u = 4300, c = 4
4: u = 3600, c = 6
5: u = 900, c = 2
6: u = 5300, c = 9
7: u = 6300, c = 1
8: u = 7900, c = 8
9: u = 4400, c = 3
10: u = 9400, c = 0
After:
0: u = 9400, c = 0
1: u = 6300, c = 1
2: u = 900, c = 2
3: u = 4400, c = 3
4: u = 5500, c = 3
5: u = 4300, c = 4
6: u = 3900, c = 5
7: u = 3600, c = 6
8: u = 7900, c = 8
9: u = 5300, c = 9
10: u = 7900, c = 9
样本运行（随机数据量）：
Before:
0: u = 3300, c = 1
1: u = 200, c = 8
2: u = 7500, c = 6
3: u = 2700, c = 8
4: u = 8300, c = 3
5: u = 6900, c = 3
6: u = 400, c = 3
7: u = 1100, c = 6
8: u = 3600, c = 5
9: u = 2100, c = 7
10: u = 9400, c = 9
11: u = 7300, c = 0
12: u = 1800, c = 4
13: u = 8200, c = 9
14: u = 8400, c = 4
15: u = 9600, c = 0
16: u = 4400, c = 7
17: u = 2900, c = 0
18: u = 4300, c = 4
19: u = 6500, c = 9
20: u = 6800, c = 6
21: u = 8000, c = 2
22: u = 6000, c = 5
After:
0: u = 2900, c = 0
1: u = 9600, c = 0
2: u = 7300, c = 0
3: u = 3300, c = 1
4: u = 8000, c = 2
5: u = 400, c = 3
6: u = 6900, c = 3
7: u = 8300, c = 3
8: u = 4300, c = 4
9: u = 8400, c = 4
10: u = 1800, c = 4
11: u = 6000, c = 5
12: u = 3600, c = 5
13: u = 6800, c = 6
14: u = 1100, c = 6
15: u = 7500, c = 6
16: u = 4400, c = 7
17: u = 2100, c = 7
18: u = 2700, c = 8
19: u = 200, c = 8
20: u = 6500, c = 9
21: u = 8200, c = 9
22: u = 9400, c = 9
已启用调试，固定大小运行：
Before:
0: u = 700, c = 9
1: u = 7300, c = 8
2: u = 3000, c = 2
3: u = 4400, c = 8
4: u = 2300, c = 9
5: u = 4000, c = 5
6: u = 9200, c = 2
7: u = 8700, c = 3
8: u = 2700, c = 9
9: u = 4000, c = 2
-->> MergeSort: lo = 0, md = 4, hi = 9
-->> MergeSort: lo = 0, md = 2, hi = 4
-->> MergeSort: lo = 0, md = 1, hi = 2
-->> MergeSort: lo = 0, md = 0, hi = 1
-->> Merge: lo = 0, md = 0, hi = 1, sz = 2
L = 0, M = 0; R = 1, H = 1
a[0].c = 9 <=> a[1].c = 8
R1: a[1].c = 8
L = 0, M = 0; R = 2, H = 1
L2: a[0].c = 9
<<-- Merge: lo = 0, md = 0, hi = 1, sz = 2
<<-- MergeSort: lo = 0, md = 0, hi = 1
-->> Merge: lo = 0, md = 1, hi = 2, sz = 3
L = 0, M = 1; R = 2, H = 2
a[0].c = 8 <=> a[2].c = 2
R1: a[2].c = 2
L = 0, M = 1; R = 3, H = 2
L2: a[0].c = 8
L2: a[1].c = 9
<<-- Merge: lo = 0, md = 1, hi = 2, sz = 3
<<-- MergeSort: lo = 0, md = 1, hi = 2
-->> MergeSort: lo = 3, md = 3, hi = 4
-->> Merge: lo = 3, md = 3, hi = 4, sz = 2
L = 3, M = 3; R = 4, H = 4
a[3].c = 8 <=> a[4].c = 9
L1: a[3].c = 8
L = 4, M = 3; R = 4, H = 4
R2: a[4].c = 9
<<-- Merge: lo = 3, md = 3, hi = 4, sz = 2
<<-- MergeSort: lo = 3, md = 3, hi = 4
-->> Merge: lo = 0, md = 2, hi = 4, sz = 5
L = 0, M = 2; R = 3, H = 4
a[0].c = 2 <=> a[3].c = 8
L1: a[0].c = 2
L = 1, M = 2; R = 3, H = 4
a[1].c = 8 <=> a[3].c = 8
R1: a[3].c = 8
L = 1, M = 2; R = 4, H = 4
a[1].c = 8 <=> a[4].c = 9
L1: a[1].c = 8
L = 2, M = 2; R = 4, H = 4
a[2].c = 9 <=> a[4].c = 9
R1: a[4].c = 9
L = 2, M = 2; R = 5, H = 4
L2: a[2].c = 9
<<-- Merge: lo = 0, md = 2, hi = 4, sz = 5
<<-- MergeSort: lo = 0, md = 2, hi = 4
-->> MergeSort: lo = 5, md = 7, hi = 9
-->> MergeSort: lo = 5, md = 6, hi = 7
-->> MergeSort: lo = 5, md = 5, hi = 6
-->> Merge: lo = 5, md = 5, hi = 6, sz = 2
L = 5, M = 5; R = 6, H = 6
a[5].c = 5 <=> a[6].c = 2
R1: a[6].c = 2
L = 5, M = 5; R = 7, H = 6
L2: a[5].c = 5
<<-- Merge: lo = 5, md = 5, hi = 6, sz = 2
<<-- MergeSort: lo = 5, md = 5, hi = 6
-->> Merge: lo = 5, md = 6, hi = 7, sz = 3
L = 5, M = 6; R = 7, H = 7
a[5].c = 2 <=> a[7].c = 3
L1: a[5].c = 2
L = 6, M = 6; R = 7, H = 7
a[6].c = 5 <=> a[7].c = 3
R1: a[7].c = 3
L = 6, M = 6; R = 8, H = 7
L2: a[6].c = 5
<<-- Merge: lo = 5, md = 6, hi = 7, sz = 3
<<-- MergeSort: lo = 5, md = 6, hi = 7
-->> MergeSort: lo = 8, md = 8, hi = 9
-->> Merge: lo = 8, md = 8, hi = 9, sz = 2
L = 8, M = 8; R = 9, H = 9
a[8].c = 9 <=> a[9].c = 2
R1: a[9].c = 2
L = 8, M = 8; R = 10, H = 9
L2: a[8].c = 9
<<-- Merge: lo = 8, md = 8, hi = 9, sz = 2
<<-- MergeSort: lo = 8, md = 8, hi = 9
-->> Merge: lo = 5, md = 7, hi = 9, sz = 5
L = 5, M = 7; R = 8, H = 9
a[5].c = 2 <=> a[8].c = 2
R1: a[8].c = 2
L = 5, M = 7; R = 9, H = 9
a[5].c = 2 <=> a[9].c = 9
L1: a[5].c = 2
L = 6, M = 7; R = 9, H = 9
a[6].c = 3 <=> a[9].c = 9
L1: a[6].c = 3
L = 7, M = 7; R = 9, H = 9
a[7].c = 5 <=> a[9].c = 9
L1: a[7].c = 5
L = 8, M = 7; R = 9, H = 9
R2: a[9].c = 9
<<-- Merge: lo = 5, md = 7, hi = 9, sz = 5
<<-- MergeSort: lo = 5, md = 7, hi = 9
-->> Merge: lo = 0, md = 4, hi = 9, sz = 10
L = 0, M = 4; R = 5, H = 9
a[0].c = 2 <=> a[5].c = 2
R1: a[5].c = 2
L = 0, M = 4; R = 6, H = 9
a[0].c = 2 <=> a[6].c = 2
R1: a[6].c = 2
L = 0, M = 4; R = 7, H = 9
a[0].c = 2 <=> a[7].c = 3
L1: a[0].c = 2
L = 1, M = 4; R = 7, H = 9
a[1].c = 8 <=> a[7].c = 3
R1: a[7].c = 3
L = 1, M = 4; R = 8, H = 9
a[1].c = 8 <=> a[8].c = 5
R1: a[8].c = 5
L = 1, M = 4; R = 9, H = 9
a[1].c = 8 <=> a[9].c = 9
L1: a[1].c = 8
L = 2, M = 4; R = 9, H = 9
a[2].c = 8 <=> a[9].c = 9
L1: a[2].c = 8
L = 3, M = 4; R = 9, H = 9
a[3].c = 9 <=> a[9].c = 9
R1: a[9].c = 9
L = 3, M = 4; R = 10, H = 9
L2: a[3].c = 9
L2: a[4].c = 9
<<-- Merge: lo = 0, md = 4, hi = 9, sz = 10
<<-- MergeSort: lo = 0, md = 4, hi = 9
After:
0: u = 4000, c = 2
1: u = 9200, c = 2
2: u = 3000, c = 2
3: u = 8700, c = 3
4: u = 4000, c = 5
5: u = 4400, c = 8
6: u = 7300, c = 8
7: u = 2700, c = 9
8: u = 2300, c = 9
9: u = 700, c = 9
该代码在Mac OS X 10.11.6上的GCC 6.1.0和Valgrind 3.12-SVN下编译并运行良好。
类似资料：
-
问题内容： 给定两个排序数组，如下所示： 我希望输出为： 要么： 我知道我可以执行以下操作： 我只是想知道是否有一种更快的方法，因为我要处理的数组具有数百万个元素。 任何想法都欢迎。谢谢 问题答案： 由于您使用numpy，因此我怀疑bisec根本不会对您有所帮助。因此，我建议您做两件事： 千万 不能 使用，使用方法，而不是这种种取代阵列，避免了复制。 必须使用没有到位的。因此，不要手动使用逻辑。I
-
问题是== 将nums1和nums2合并到一个按非递减顺序排序的数组中。 最终排序的数组不应由函数返回，而应存储在数组 nums1 中。为了适应这种情况，nums1 的长度为 m n，其中前 m 个元素表示应合并的元素，最后 n 个元素设置为 0 并应忽略。nums2 的长度为 n。 我的代码中有什么错误？？？ 您的意见 我的产出 预期产出
-
我有三个排序数组，如下所示 这些数组根据数组中每个对象的名称属性进行排序。下面是我从Java转换为合并两个排序数组的方法 这里是两个数组的工作小提琴http://jsfiddle.net/euRn5/.什么是最好的方法来实现相同的n个数组，我目前的想法是一个接一个，合并它与以前合并到最后项目，像n=i的东西。这是最好的方法吗？
-
我试图实现合并排序树结构，但每当我试图将子向量合并到父向量时，就会出现编译错误。我被困在这里了。 在包含的文件中，从c：\ming w\lib\gcc\ming w32\6.3.0\包括\c\bit\stl_algobase. h： 71:0，从c：\ming w\lib\gcc\ming w32\6.3.0\包括\c\bit\char_traits. h： 39，从c：\ming w\lib\g
-
问题内容： 我在Redis商店中使用type。我为每个用户创建一个自己的 KEY 并将数据放在此处： KEY 示例 ： 我想从Redis中为用户键选择数据：1、2、3，并按得分（时间戳）进行排序。 如果只是简单地看问题，我需要跨时从任何KEY中选择一个数据，然后将按分数排序的所有结果组合在一起。 问题答案： 有两种方法可以执行此操作，但是正确的方法取决于您要执行的操作。例如： 您可以在代码中为每个
-
双向合并排序与递归合并排序有何不同？ 假设在合并排序中有5个数字需要排序8,9,1,6,4，我们按如下步骤1进行划分：{8,9,1}{6,4} 步骤2：{8,9}{1}{6}{4} 步骤3：{8}{9}{1}{6}{4} 现在合并 步骤4：{8,9}{1}{4,6} 步骤5：{1,8,9}{4,6} 第六步：{1,4,6,8,9} 但在双向合并排序中，我们将数组分为两个元素（但根据维基百科，在合并