当我使用 mergeSort
对我的 void**
数组进行排序时(该数组包含指向整数的 void*
指针),一个额外的1
(新元素)似乎已添加到数组中。我几乎可以肯定问题出在 mergeSort
或 merge
中,因为在调用 mergeSort
之前打印我的 void**
数组>,数据正确(只是未排序)。这是代码。
#define SIZE 10
void mergeSort(void**, int, int);
void merge(void**, int, int, int);
int compare(void*, void*);
int main(void) {
int array[SIZE] = { 5, 6, 3, 2, 5, 6, 7, 4, 9, 3 };
void *voidArray[SIZE];
int query = 1;
void *queryPointer = &query;
for (int j = 0; j < SIZE; j++) {
voidArray[j] = &array[j];
}
printArray(voidArray);
mergeSort(voidArray, 0, SIZE);
printArray(voidArray);
result = binarySearch(voidArray, 0, SIZE, queryPointer);
if (result == -1) {
puts("Query not found.");
return(0);
}
printf("Query found at index %d.\n", result);
return(0);
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void mergeSort(void **array, int head, int tail) {
if (head < tail) {
int middle = (head + ((tail - head) / 2));
mergeSort(array, head, middle);
mergeSort(array, (middle + 1), tail);
merge(array, head, middle, tail);
}
}
void merge(void **array, int head, int middle, int tail) {
int headLength = (middle - head + 1);
int tailLength = (tail - middle);
void *headSide[headLength];
void *tailSide[tailLength];
for (int i = 0; i < headLength; i++) {
headSide[i] = array[head + i];
}
for (int j = 0; j < tailLength; j++) {
tailSide[j] = array[middle + 1 + j];
}
int k = head;
int l = 0;
int m = 0;
while (l < headLength && m < tailLength) {
if (compare(headSide[l], tailSide[m]) == -1) {
array[k] = headSide[l];
l++;
} else {
array[k] = tailSide[m];
m++;
}
k++;
}
while (l < headLength) {
array[k] = headSide[l];
l++;
k++;
}
while (m < tailLength) {
array[k] = tailSide[m];
m++;
k++;
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int compare(void *index, void *query) {
if (*((int *)index) == *((int *)query)) {
return (0);
}
if (*((int*)index) > *((int*)query)) {
return (1);
}
return (-1);
}
输出应该有未排序的数组、排序的数组以及是否找到查询。未排序的数组中没有1
,但是排序后的数组中有一个1
;此外,排序结果中缺少数字 9
(有趣的是,如果我对 9
执行二进制搜索,它会告诉我 9
在索引 10
处找到。
示例输出(对于 1
的查询):
5 6 3 2 5 6 7 4 9 3
1 2 3 3 4 5 5 6 6 7
在索引 0
处找到查询。
最佳答案
检查你的数组下标。
int tailLength = (tail - middle)
tail是数组的大小,我认为tailLength不正确。
关于c - 为什么在我使用归并排序时,一个额外的元素被添加到我的 void** 数组中?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55564769/