Как я могу объединить два массива, объявленных как недействительные указатели?

В настоящее время у меня есть программа, которую я пишу, где я реализую Mergesort массива. Массив состоит из неизвестных переменных - это пустой указатель, поэтому я на самом деле не знаю, какие объекты я сортирую (для фактического сравнения передается функция сравнения).

Как я могу пройти по массиву, если он является пустым указателем? Я узнал, что не могу просто использовать типичный формат массива (т.е. arr[3]), так как это пустой указатель. В мои функции передается параметр, который содержит размер загадочных элементов, поэтому я полагаю, что мне это понадобится. Есть ли способ, которым я мог бы привести его в зависимости от предоставленного размера, чтобы я мог использовать этот типичный формат массива, или мне нужно использовать арифметику указателя (опять же, нужно каким-то образом привести его к чему-то предоставленного размера)?

Спасибо всем, кто вносит свой вклад! :)


void-pointers
person Community    schedule 02.05.2014    source источник
comment
Почему вы удалили свой код ›.›   -  person M.M    schedule 08.05.2014

Ответы (2)


arrow_upward
2
arrow_downward

В мои функции передается параметр, который содержит размер загадочных элементов.

Хорошо - это именно то, что вам нужно для правильной арифметики указателей. Это тот же подход, что и библиотечная функция qsort.

void merge_sort(void *array, size_t N, size_t size, int (*compare)(const void *, const void *));

Как только вы приведете указатель void* к char*, вы сможете вычислить местоположение таинственного элемента i следующим образом:

size_t size; // Element size
void *array; // The address of the array
size_t N;    // Count of elements in the array
char *base = array;
for (int i = 0 ; i != N ; i++) {
    void *elementAtPositionI = &base[i * size];
    ...
}

Чтобы найти точку, в которой вы разделяете массив для сортировки отдельно, вы можете использовать ту же технику:

void *secondHalf = &base[N * size / 2];

Однако я не могу заставить его работать... кажется, что я пропускаю значения и захожу в память мимо массива!

В вашем коде остается пара основных проблем:

  • Ваш код пропускает значения, потому что вы неправильно вычисляете размеры левой и правой частей: вы предполагаете, что они обе равны num_elem/2, тогда как на самом деле одна из них равна num_elem/2+1, когда num_elem нечетно. Используйте num_elem/2 для левой стороны и num_elem-num_elem/2 для правой стороны. Найдите все места, где сделано ваше предположение, и исправьте их (их больше одного места).
  • Ваш код попадает в неправильную память, потому что вы неправильно вычисляете положение середины. Вам нужно исправить эту строку: merge(carr, carr + (num_elem/2) /* <<== HERE */, num_elem/2, num_elem/2, elem_size, cmp);
  • Вы неправильно копируете элементы в helper. Вместо helper[helper_place * elem_size] = *a_temp; вам нужно вызвать memcpy и использовать elem_size для количества копируемых байтов. Есть несколько мест, где вам нужно сделать это исправление.

Это должно значительно приблизить вас к рабочему решению.

person Sergey Kalinichenko    schedule 02.05.2014
comment
Спасибо за вашу помощь! Я переписал весь свой код, чтобы использовать указатели на символы. Однако я не могу заставить его работать... кажется, что я пропускаю значения и захожу в память мимо массива! - person ; 02.05.2014
comment
Это было именно так! Большое спасибо. Пустые указатели, как правило, моя слабость. XD К счастью, мне не приходится иметь с ними дело, по крайней мере, в этой конкретной программе :) - person ; 03.05.2014

arrow_upward
1
arrow_downward

В mergesort вам нужно обрабатывать указатели как char*. Вам нужно будет передать размер объектов, чтобы вы знали, как правильно выполнять арифметику указателя.

void mergesort(void* a, void* b, size_t objectSize, size_t objectCount)
{
   char* ac = (char*)a;
   char* bc = (char*)b;

   //.....

   mergesort(ac, ac+objectSize*objectCount/2);
}
person R Sahu    schedule 02.05.2014
comment
Это имеет смысл — я даже не думал, что мне придется настраивать весь алгоритм сортировки, но это имело смысл. - person ; 02.05.2014