эффективная индексация массива

Question

Предположим, что у меня есть

z[7]={0, 0, 2, 0, 1, 2, 1}

, что означает - первое наблюдение распределено в группе 0, вторая группа наблюдателей 0, третья группа 2 и т. Д. и я хочу написать эффективный код, чтобы получить массив 3X? так, что в первом ряду у меня есть все наблюдения, выделенные в первой группе, во втором ряду все объекты, выделенные во второй группе и т. д. что-то вроде

0, 1, 3
4, 6 
2, 5

и это должно быть общим, может быть, я мог бы иметь

z={0, 0, 2, 0, 1, 2, 1, 3, 4, 2, 0, 4, 5, 5, 6, 7, 0}

поэтому число столбцов неизвестно

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

#include <stdio.h>
int main(){
  int z[7]={0, 0, 2, 0, 1, 2, 1}, nj[3], iz[3][7], ip[3], i, j;


for(j=0; j<3; j++){
    ip[j] = 0;
    nj[j] = 0;
  }

  for(i=0; i <7; i++ ){
    nj[z[i]] = nj[z[i]] + 1;
    iz[z[i]][ip[z[i]]] = i;
    ip[z[i]] = ip[z[i]] + 1;    
  }  

  for(j=0; j<3 ;j++){
    for(i=0; i < nj[j]; i++){
      printf("%d\t", iz[j][i]);
    }
    printf("\n");    
  }
  return 0;  
}

Answer 1

Похоже, у вас есть две задачи.

1. Для подсчета количества вхождений каждого индекса в z и выделения структуры данных правильного размера и конфигурации.
2. Чтобы перебрать данные и скопировать их в правильные места.

В настоящий момент вы, кажется, наивно решили (1), выделив большой двумерный массив iz. Это прекрасно работает, если вы заранее знаете пределы его размера (и у вашей машины будет достаточно памяти), исправлять это не нужно позже.

Мне не ясно, как именно следует подходить к (2). Гарантируется, что данные, поступающие в iz, состоят из [0, 1, ... n]?

---

Если вы не заранее знаете пределы размера iz, то вам придется выделить динамическую структуру. Я бы предложил рваный массив, хотя это означает два (или даже три) прохода над z.

Что я подразумеваю под рваным массивом? Объект, подобный аргументу argv для main, но в этом случае типа int **. По памяти это выглядит так:

+----+     +---+     +---+---+---+--
| iz |---->|   |---->|   |   |   ...
+----+     +---+     +---+---+---+--
           |   |--
           +---+  \    +---+---+---+--
           | . |   --->|   |   |   ...
             .         +---+---+---+--
             .

Доступ к разбитому массиву можно получить с помощью iz[][], точно так же, как это был двумерный массив (но это другой тип объекта), что хорошо для ваших целей, потому что вы можете настроить свой алгоритм с помощью имеющегося кода. сейчас, а затем шлепнуть один из них на место.

---

Как его настроить.

1. Повторяйте z, чтобы найти наибольшее число, maxZ, присутствует.

2. Выделите массив размером int* maxZ+1: iz=callac(maxZ+1,sizeof(int*));.

   Я выбрал calloc, потому что он обнуляет память, что делает все эти указатели NULL, но вы можете использовать malloc и обнулять их самостоятельно. Если сделать массив слишком большим, мы получим NULL-завершение, которое может пригодиться позже.

3. Выделите массив счетчиков размером maxZ: int *cz = calloc(maxZ,sizeof(int));

4. итерация по z, заполнение cz количеством записей, необходимых в каждой строке.

5. Для каждой строки выделите массив целых чисел: for(i=0; i<maxZ; ++i){ iz[i] = malloc(sizeof(int)*cz[i]; }

6. Итерируйте по z в последний раз, вставляя цифры в iz, как вы уже делаете. Вы можете повторно использовать cz на этом этапе, чтобы отслеживать, сколько фигур уже помещено в каждую строку, но вы можете выделить отдельный массив для этой цели, потому что у вас есть запись о размере каждого выделенного массива.

Примечание: Каждый вызов malloc или calloc должен сопровождаться проверкой, чтобы убедиться, что распределение работает. Я оставил это как упражнение для студента.

---

Это повторное прохождение через z бизнеса можно полностью избежать с помощью динамических массивов, но я подозреваю, что вам это не нужно и вы не хотите дополнительной сложности.