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

loading...


2

我正在尝试以与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

    我如何找到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.
    

  • 3

    如何在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* 上的算术 . 由你决定是否可以/将使用它 .

loading...

评论

暂时没有评论!