Создать d-мерный указатель

Question

Мы используем для указания указателя с символом *. Итерируя процедуру, мы получаем «двойной» указатель **, «тройной» указатель *** и, в более общем смысле, «d-мерный» указатель (для каждого d положительного натурального числа).

Задача: учитывая такой d, как вход, определите S как d-мерный указатель.

Поскольку я начал изучать динамические структуры только несколько дней назад, я, к сожалению, немного не в порядке с этой проблемой. У кого-нибудь есть предложение/подсказка?

Спасибо заранее, и мои извинения за мой, вероятно, слишком основной вопрос.

Ps: Я использовал слово «указатель» без указания его типа только для краткости.

Answer 1

Эта проблема имеет решение в С тех пор, как будут выполнены два условия:

• Значение d известно во время компиляции, а
• d имеет заранее определенный предел, например, 10

Вы можете решить эту проблему, определив ряд макросов и «склеивание» Значение d в качестве маркера:

#define D_PTR(d,T) D_PTR##d(T) 
#define D_PTR0(T) T 
#define D_PTR1(T) T* 
#define D_PTR2(T) T** 
#define D_PTR3(T) T*** 
... 
#define D_PTR10(T) T********** 

Теперь вы можете объявить d -размерности указатели, как это:

D_PTR(5,int) ptr5 = NULL; 

Demo.

Answer 2

Задача: учитывая такой d, как ввод, определите S как d-мерный указатель .

В C возможно функционально представлять N-мерный массив во время выполнения, если не указатель с произвольным числом уровней косвенности. Это может быть началом (неоткомпилированные, и это совершенно игнорирует любые возможные проблемы с выравниванием):

void *allocateArray(unsigned int N, size_t elemSize, unsigned int *dimensions) 
{ 
    if (N == 1U) 
    { 
     return(malloc(elemSize * dimensions[ 0 ])) 
    } 

    void *array = malloc(sizeof(void *) * dimensions[ 0 ]); 
    for (unsigned ii = 0; ii < dimensions[ 0 ]; ii++) 
    { 
     array[ ii ] = allocateArray(N - 1, elemSize, &(dimensions[ 1 ])); 
    } 

    return(array); 
} 

Отметим, что это не очень эффективный способ выделения N-мерный массив.

Вы могли бы назвать это так:

unsigned dims[] = { 5,7,8,9 }; 
unsigned d = sizeof(dims)/sizeof(dims[ 0 ]); 
size_t elemSize = sizeof(double); 

void *array = allocateArray(d, elemSize, dims); 

решение переменной длины, вероятно, возможно, тоже.

Выделение массива потребует чего-то подобного. Это возвращает адрес элемента разыменовываются:

void *dereferenceArray(void *array, unsigned int N, 
    size_t elemSize, unsigned int *element) 
{ 
    if (N == 1U) 
    { 
     char *tmp = array; 
     return(tmp + (elemSize * element[ 0 ])); 
    } 
    else 
    { 
     void **tmp = array; 
     return(dereferenceArray(tmp[ element[ 0 ] ], 
      N - 1, elemSize, &(element[ 1 ]))); 
    } 
} 

Было бы намного проще в C++, как вы могли бы обеспечить [] оператора к объекту массива и гнездо их, чтобы построить N-мерные массивы.

Answer 3

В общем случае число * представляет собой количество косвенностей для достижения переменной. Поэтому вам нужно создать d. Я предполагаю, что это не имеет практического применения - это ответ на рекреационную проблему.

Косвенное обозначение на C - это адрес, указатель. Создание объектов d означает создание адресов d для доступа к переменным данным (пространство, присвоенное переменной типа T).

p(d) -> p(d-1) -> ... -> p(1) -> variable 

Чтобы создать динамически такую ​​структуру, вы можете сделать это с помощью таНоса (заменить T с любым известным типом), и - так как вы не можете указать количество * динамически к указателю - требует некоторого C взлом.

Итак, опять же, это не то, что рекомендуется и особенно плохой дизайн, особенно для неопытных разработчиков C. Цель состоит в том, чтобы показать, что это можно сделать динамически, независимо от значения d.

Скажет Т представляет собой двойного

int d = ...; // from input (d >= 1) 
double variable; 

double **S = malloc(sizeof(double *) * d); // array of pointers to pointer 

S[d-1] = &variable; // last address points to target 
int i; 
for(i=d-2 ; i>=0 ; i--) S[i] = (double *)&S[i+1]; // previous address 
                // points to next location 

Там нет никакого способа, чтобы представить произвольное число indirections в C, так что S лишь ** для удовлетворения требований компилятора и отливает в случае необходимости.

Давайте попробуем с д набора для и применение алгоритма выше (скажем, T является двойным), имеющим

double variable is at address 0100 (decimal), value 3.14 
S address given by malloc at 1000 
a pointer size being    4 
a double size being    8 

variable 
v 
[8 bytes double value 3.14] 
^ 
0100 

S 
v 
[1004][1008][1012][0100] 
^    ^
1000    1012 

Теперь структура находится в месте, как использовать/проверить? Вы можете создать функцию, которая возвращает тип Т (двойной здесь), принимает значение S и D, срабатывать d indirections и возвращает переменную

double getvariable(double **S, int d) { 
    while (--d > 0) S = (double **)*S; // d-1 iterations 
    return *(double *)*S; 
} 

пытается его

printf("%lf\n", getvariable(S, d)); // 3.14 

испытать выше структуры без функции, для г == 4, можно создать

double ****p = (double ****)*S; 
printf("%lf\n", ****p);    // 3.14 

Answer 4

Есть три различных способа решить эту проблему:

1. Ваш d - это постоянная времени компиляции. Для этого случая dasblinkenlight has already given the solution.

2. Hacky-C Решение: Просто используйте слепок, чтобы вернуться к типу указателя:

   double* dereferenceDLevels(double* pointer, int d) { 
       for(; d--;) pointer = *(double**)pointer; 
       return pointer; 
   } 
   

   Я не рекомендую этот подход, хотя. Это слишком грязно.

3. Вы реализуете ваши d -LEVEL указатели, определенные пользователем типы:

   typedef struct nLevelPointer { 
       int n; 
       union { 
        nLevelPointer* pointer; 
        double value; 
       }; 
   } nLevelPointer; 
   
   double nLevelPointer_dereference(nLevelPointer* me) { 
       for(int i = me->n; i--;) me = me->pointer; 
       return me->value; 
   } 
   

   Я считаю этот подход чистым и наиболее гибким. Однако у него есть компромисс, требующий значительного количества кода шаблона, чтобы заставить его летать.

Answer 5

Вы можете создать эквивалент времени выполнения указателя d-направления, объединив столько указателей void **, сколько вам нужно. Разреженный массив может затем быть построен таким образом:

#include <assert.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 

int main(int argc, char *argv[]) 
{ 
    if (argc < 4) 
    { 
     printf("Call this passing d (dimensions), n (elements for each dim), u (used elements) as parameters\n"); 
     return 0; 
    } 
    int d = atoi(argv[1]); 
    assert(d > 0); 
    int n = atoi(argv[2]); 
    assert(n > 0); 
    int u = atoi(argv[3]); 
    assert(u < n * d); 

    // Creating 
    void *root = malloc(sizeof(void *) * n); 
    memset(root, 0, sizeof(void *) * n); 
    srand(time(NULL)); 
    int i, p, c; 
    void **cursor; 
    for (int c = 0; c < u; ++c) 
    { 
     cursor = root; 
     for (i = 0; i < d; ++i) 
     { 
      p = rand() % n; 
      if (cursor[p] == NULL) 
      { 
       cursor[p] = malloc(sizeof(void *) * n); 
       memset(cursor[p], 0, sizeof(void *) * n); 
      } 
      cursor = cursor[p]; 
     } 
     p = rand() % n; 
     if (cursor[p] == NULL) 
      cursor[p] = "Hello"; 
     else 
      --c; 
    } 
    // Traversing 
    struct SE 
    { 
     void * *s; 
     int p; 
    }; 
    struct SE *stack = malloc(sizeof(struct SE) * (d + 1)); 
    for (cursor = root, p = 0, i = 0; ; ++p) 
    { 
     if (p == n) 
     { 
      if (i == 0) 
       break; 
      cursor = stack[--i].s; 
      p = stack[i].p; 
     } 
     else if (cursor[p] != NULL) 
     { 
      if (i < d) 
      { 
       stack[i].s = cursor; 
       stack[i++].p = p; 
       cursor = cursor[p]; 
       p = -1; 
      } 
      else 
      { 
       printf("root"); 
       for (c = 0; c < i; ++c) 
        printf("[%d]->", stack[c].p); 
       printf("[%d]=\"%s\"\n", p, cursor[p]); 
      } 
     } 
    } 

    // Tearing down 
    for (cursor = root, p = 0, i = 0; ; ++p) 
    { 
     if (p == n) 
     { 
      if (i == 0) 
       break; 
      cursor = stack[--i].s; 
      p = stack[i].p; 
      free(cursor[p]); 
     } 
     else if (cursor[p] != NULL && i < d) 
     { 
      stack[i].s = cursor; 
      stack[i++].p = p; 
      cursor = cursor[p]; 
      p = -1; 
     } 
    } 
    free(root); 
    free(stack); 
    return 0; 
}