Gestire un array di tipo indeterminato con puntatori void

Question

Sto cercando di scrivere la mia propria funzione Mergesort nello stesso modo come la funzione qsort di C. Se dovessi scrivere MergeSort per una serie di elementi noti, non avrei un problema, ma dal momento che non so che cosa saranno mi sta gettando per un ciclo.

La specifica dato dal mio professore non voleva me di utilizzare una funzione separata per la fusione, per cui sto scrivendo che l'attuazione all'interno della funzione Mergesort stesso. Ciò significa che avrò la qsort stesse informazioni () avrebbe:

• void* base - un puntatore al primo elemento della matrice da ordinare
• size_t nel - il numero di elementi nella matrice
• size_t width - le dimensioni di ogni elemento
• int (*compar)( const void*, const void* ) - una funzione che ti dice come confrontare ogni elemento

Il problema che sto avendo è con la parte di unione. Ogni applicazione che ho visto ha usato un array temporaneo per memorizzare gli oggetti mentre sono ordinati. Io non sono che abituato a lavorare con i puntatori nulli, e il più grande ostacolo che ho trovato è in movimento attraverso e assegnando valori in array. Come faccio a trovare il valore al secondo indice dell'array puntato da base? Come potrei assegnare un valore da tale array in un array temporaneo? Come faccio a creare quel array temporaneo?

funzionerebbe se ho fuso i puntatori void a char, e solo li incrementato dalla larghezza? Io non sono sicuro di come l'assegnazione avrebbe funzionato, però.

Answer 1

  

Come faccio a trovare il valore al secondo indice dell'array puntato da base?

Usa (char *)base + (width*i). Questo vi darà l'indirizzo del i-esimo elemento.

  

Come potrei assegnare un valore da tale array in un array temporaneo?

Basta copiare i dati. for (int n=0;n<width;n++) { //copy one byte from }

  

Come faccio a creare l'array temporaneo?

Qualcosa di simile:

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

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

Modifica

Per spiegare la copia dei dati un po 'più avanti, è necessario fare:

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

Answer 2

Come faccio a trovare il valore al secondo indice dell'array puntato da base? Funzionerebbe se ho fuso i puntatori void a char, e solo li incrementato dalla larghezza?

Sì, che è di destra. La dimensione di un carattere è definito dallo standard per essere 1, in modo che il "larghezza" si è dato è, per definizione, la dimensione di ogni elemento in caratteri. Così si può trovare l'indirizzo nel seguente modo:

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

Non è possibile trovare il valore , in quanto non si conosce il tipo e quindi non si può dare un senso della memoria che occupa. Ma va bene, per ordinare gli oggetti in C con questa interfaccia non è necessario conoscere i loro valori: è necessario puntatori a loro, che è possibile passare alla funzione di confronto, ed è necessario essere in grado di copiare gli oggetti intorno

Come potrei assegnare un valore da tale array in un array temporaneo?

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

Come faccio a creare quel array temporaneo?

Oh, penso che ho preso queste domande nell'ordine sbagliato. Per un piccolo array contenente un singolo elemento, si potrebbe correre il rischio di un VLA. Oppure si potrebbe usare malloc come segue:

// 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);

A proposito, gcc supporta aritmetica su void* come estensione del compilatore, trattandolo come l'aritmetica su char*. Fino a voi decidere se è possibile / utilizzerà questo.