使用void指针管理不确定类型的数组

我正在尝试以与C的qsort函数相同的方式编写自己的Mergesort函数 . 如果我为一系列已知项目编写MergeSort,我就不会有问题,但是因为我不知道它们会是什么,所以它会让我失去一个循环 .

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

  • void* base - 指向要排序的数组的第一个元素的指针

  • size_t nel - 数组中的元素数

  • size_t width - 每个元素的大小

  • int (*compar)( const void*, const void* ) - 一个告诉您如何比较每个元素的函数

我看到的问题是使用了一个临时数组来存储项目,而不是那些曾经使用过无效指针的项目,而我发现的最大障碍是移动并将值分配给数组 . 如何在 base 指向的数组中的第二个索引处找到该值?如何将该数组中的值分配给临时数组?我该如何创建该临时数组?

如果我将void指针转换为char,并将它们增加宽度,它会工作吗?不过,我不确定任务是如何工作的 .

回答(2)

2 years ago

我如何找到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]);

EDIT:

要进一步解释复制数据,您需要执行以下操作:

for (int n=0;n<width;n++) {
  adressTo[n] = addressFrom[n];
}
// This will copy the contents of pointer addressFrom to addressTo.

2 years ago

如何在base指向的数组中的第二个索引处找到该值?如果我将void指针转换为char,并将它们增加宽度,它会工作吗?

恩,那就对了 . char的大小由标准定义为1,因此根据定义,您给出的“宽度”是字符中每个元素的大小 . 所以你可以找到如下地址:

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

你无法找到这个值,因为你不了解它占用的内存 . 但是's OK, to sort objects in C with this interface you don't需要知道它们的值:你需要指向它们的指针,你可以传递给比较器函数,并且你需要能够复制周围的对象 .

如何将该数组中的值分配给临时数组?

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支持 void* 上的算术作为编译器扩展,将其视为 char* 上的算术 . 由你决定是否可以/将使用它 .