c - 数组的高效索引

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. 迭代数据并将其复制到正确的位置。

目前，您似乎已经通过分配一个大的二维数组 iz 天真地解决了 (1)。如果您事先知道它可能有多大的限制(并且您的机器将有足够的内存)，那效果很好，直到以后才需要解决这个问题。

我不清楚应该如何处理 (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。使数组过大会给我们一个 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 业务，但我怀疑您不需要它并且不希望增加复杂性。