2

我正在尝试以与 C 的 qsort 函数相同的方式编写自己的 Mergesort 函数。如果我正在为一组已知项目编写 MergeSort，我不会有问题，但由于我不知道它们会是什么，这让我陷入了循环。

我的教授给出的规范不希望我使用单独的函数进行合并，所以我在 Mergesort 函数本身中编写了该实现。这意味着我将拥有与 qsort() 相同的信息：

  • void* base- 指向要排序的数组的第一个元素的指针
  • size_t nel- 数组中的元素数量
  • size_t width- 每个元素的大小
  • int (*compar)( const void*, const void* )- 告诉您如何比较每个元素的功能

我遇到的问题是合并部分。我见过的每个实现都使用一个临时数组来存储排序的项目。我不习惯使用 void 指针，我发现的最大障碍是遍历数组并将值分配给数组。如何在 指向的数组中的第二个索引处找到值base？如何将该数组中的值分配到临时数组中？我将如何创建该临时数组？

如果我将 void 指针转换为 char，然后将它们增加宽度，它会起作用吗？不过，我不确定分配将如何工作。

4

2 回答 2

3

如何在 base 指向的数组中的第二个索引处找到值？

使用(char *)base + (width*i). 这将为您提供第 i 个元素的地址。

如何将该数组中的值分配到临时数组中？

您只需复制数据。for (int n=0;n<width;n++) { //copy one byte from }

我将如何创建临时数组？

就像是：

C -void* tempArray = malloc(width*elementsNeeded);

c++ -void* tempArray = (void*) (new char[width*elementsNeeded]);

编辑：

为了进一步解释复制数据，您需要执行以下操作：

for (int n=0;n<width;n++) {
  adressTo[n] = addressFrom[n];
}
// This will copy the contents of pointer addressFrom to addressTo.
于 2010-10-03T02:05:56.850 回答
2

如何在 base 指向的数组中的第二个索引处找到值？如果我将 void 指针转换为 char，然后将它们增加宽度，它会起作用吗？

是的，这是正确的。char 的大小由标准定义为 1，因此根据定义，您给出的“宽度”是 chars 中每个元素的大小。所以你可以找到如下地址：

void *second_element_ptr = ((char*)base) + width;

你找不到value，因为你不知道它的类型，所以你无法理解它占用的内存。但是没关系，用这个接口在 C 中对对象进行排序你不需要知道它们的值：你需要指向它们的指针，你可以将它传递给比较器函数，并且你需要能够复制对象。

如何将该数组中的值分配到临时数组中？

char temporary_array[width]; // this is a C99 VLA, you might want to 
                             // allocate the array differently
memcpy(temporary_array, second_element_ptr, width);

我将如何创建该临时数组？

哦，我想我把这些问题按错了顺序。对于包含单个元素的小数组，您可以尝试使用 VLA。或者你可以使用 malloc 如下：

// an array half the size of the input
// using char*, since unlike void* we can do arithmetic on it
char *big_temp_array = malloc(width * (nel + 1)/2);

顺便说一句，gcc 支持算术 onvoid*作为编译器扩展，将其视为算术 on char*。由您决定是否可以/将使用它。

于 2010-10-03T02:05:23.710 回答