logo标签列表

多维数组（例如在C/C++中）是不规则数组的特殊情况吗？

arrayslanguage-agnosticmultidimensional-array
4
我和朋友讨论了C++和C的多维数组是否是不规则数组的特例。一种观点是，多维数组不是不规则数组，因为多维数组的每个元素都具有相同的大小。在不规则数组中，至少有一个元素与同一数组中的另一个元素大小不同。（“如果没有可能成为不规则数组，那么它就不是不规则数组。”）另一种观点是，多维数组是不规则数组的一个特例，其中每个元素都具有相同的大小。不规则数组可以有不同大小的行，但也可以没有。（“圆是椭圆的一种。”）我想知道计算机科学中“不规则数组”的常见定义及C和C ++多维数组是否属于不规则数组。
4
就编程而言，我想知道术语是否真的很重要。我认为并不是这样。 - Nawaz
2
在我看来，对于计算机科学专业的学生或程序员而言，术语是他们所使用的语言的一部分。 - Mahesh
1
@Mahesh：C++标准是否将数组定义为“Ragged”？那么我不明白这对C++程序员有什么影响。 - Alok Save
1
@Nawaz：我不同意。C++标准并未规定“FIFO队列”是什么，但对于C++程序员而言，这个术语指代的内容仍然非常重要，因为他们需要用英语互相交流。如果我在谈论一个后进先出的数据结构，然后选择称之为“FIFO队列”，那么从形式上讲，我有权定义自己的术语在自己的论文/源代码/其他方面中，但我表达得很差，因为我与广泛接受的“FIFO”常见含义相矛盾。 - Steve Jessop
2
@Nawaz：如果你还在想它为什么重要，我已经告诉过你了。此外，Mahesh说，“对于一个……程序员来说，术语是他所使用的语言的一部分。”你回答说，“只有在标准中定义了才是如此。”这个说法是错误的。最后，术语是否很重要，即足够重要以便向同行核实是否有共同的用法？我认为是的。它不必非常重要，但值得尝试不误用具有广泛使用含义的术语，因此你需要知道哪些术语有这种含义，哪些没有。 - Steve Jessop
显示剩余6条评论
5个回答
1

如果将C多维数组声明为多维数组，则不能是不规则的。例如，2D数组是“数组的数组”，每行的长度相同，即使您没有使用数组中的每个条目。

int a1[2][3]; // two rows, three columns
int a2[5][8]; // five rows, eight columns

关于 C 语言的一件事是，你可以使用指向指针的指针，就好像它是一个二维数组一样：
int **a3 = malloc(4);
for (i = 0; i < 4; i++)
  a3[i] = malloc(i);

现在a3可以像2D数组一样在很多情况下使用，但肯定是不规则的。

我认为，真正的数组不能被称为不规则的，但如果必须的话，你肯定可以假装它是不规则的...从这个角度来看，你使用的术语似乎并不那么重要。

如果我用malloc(3)代替malloc(i)，那么它就不再是一个不规则数组了吗？还是说它是不规则数组的一种特殊情况？ - Johannes Schaub - litb
3
严格来说，第二个例子并没有创建一个多维数组，而是创建了一个数据结构，有时可以与多维数组互换使用。因此，如果我们非常挑剔语言语义，问它是不是一个不规则数组或非不规则数组是没有意义的，因为它根本不是一个数组。话虽如此，如果您想把这样的结构包括在“数组”讨论的范畴内，并且您认同原贴提到的“其他观点”，那么是的——每个非不规则数组都是不规则数组的一种特殊情况。 - Carl Norum
1

我认为区别在于概念上的不同。一个多维数组

T x[d_1][d_2]...[d_N];

表示大小为 $\prod_i d_i$ 的连续内存区域，如果您原谅TeX，它是通过步长寻址的：x[i_1]...[i_N] 是位置 $i_N + i_{N-1} d_N + i_{n-2} d_{N-1} d_N + ... + i_1 d_2 ... d_N$ 处的元素。中间索引可以作为指向相应子数组的指针。

另一方面，不规则数组将内部“维度”与外部维度在内存中解耦：

T * r[M];
for (size_t i = 0; i != M; ++i)
  r[M] = new T[get_size_at_row(i)];

在这里，实际大小是否有所不同并不重要，但概念上的区别在于，不规则数组是一个数组的数组，而多维数组是一个更为严格和协调的对象。

1
虽然我同意你的观点，但是我不同意“不规则数组是一个数组的数组”的说法，因为不规则数组实际上是一个数组指针和相关子数组存储的数组，而多维数组则确切地是一个数组的数组。 - dmckee --- ex-moderator kitten
1

我不知道“不规则数组”的“确切定义”是什么，但我相信C/C++多维数组绝对不是不规则的。原因如下：

  • 不规则数组是一个术语，指的是一种数组的“存储方式”，使得至少有一对行/单元格具有不同的大小。
  • C/C++中的数组非常直观。数组只是为结构（数组）保留的“连续块”内存。
  • 其他高级语言可能有不同的实现来节省内存等，但C/C++数组没有。

所以我认为我们不能称C/C++数组为不规则数组。

（个人观点）。

编辑：

这也严重取决于“不规则”的“定义”。因此，这不是一个明确定义的术语，因此很难得出结论。（应避免无生产力的争论）。

1

在讨论数学对象时，我认为“ragged”可能是用作“array”的修饰语，特指具有不匹配次要维度的数组。因此，这是第一个意思，而不是第二个。考虑单词的来源-我们不会说全新的手帕“是ragged”，因为它有可能在边缘处磨损，但它还没有磨损。它根本不是ragged。因此，如果我们称特定的数组为“ragged”，我会认为那意味着“不整齐”。

然而，在某些情况下，定义“ragged array”为“潜在ragged array”而不是实际存在不匹配的数组也是值得的。例如，如果您要编写一个“RaggedArray”类，您不会设计一个类不变量，保证某个地方一定会有大小不匹配，并确保如果有人尝试创建所有大小相等的数组，则抛出异常。尽管事实上如此，您将调用此类的实例“ragged arrays”。因此，在这种情况下，所有元素大小相等的数组是“ragged array”的特殊情况。这是第二个意思，而不是第一个。

当然，C或C ++的多维数组仍然不是这个类的实例，但它可能满足称为“RaggedArray”的某些通用接口的至少只读部分。这基本上是一种捷径，即使我们知道“ragged”意味着“大小不匹配”，但出于大多数目的，您简单地无法打扰调用那个类或通用接口“PotentiallyRaggedArray”，以明确表明您不会强制执行必须有一个约束。

特定类型的特定实例是否具有特定属性之间存在差异，以及该类型是否允许其实例具有该属性，我们经常忽略这种差异，当我们说类型X的实例“是X”时。类型X的实例可能具有该属性，但该实例没有该属性，因此该实例实际上也不可能具有该属性。您对“ragged array”的两种含义可以看作是这种差异的例子。参见E-Prime群众以及Wittgenstein哲学，了解我们在说一个东西“是”另一件不同的东西时所造成的混乱。实例“不是”类型，具体示例与其示例的潜在属性不同。

具体回答你的问题，我怀疑在计算机科学文献中没有普遍接受的偏好，认为一个含义优于另一个。这是其中一些术语，当你将其引入到特定工作（学术论文、特定库的文档等）中时，必须为自己的目的定义它。如果我能找到两篇论文，一篇使用每个术语，那么我就可以证明它了，但我不想费心去找。;-)
0

我的立场是，不规则数组与多维数组有所区别，因为它必须具有指示每个子数组开始位置的索引。（不规则数组还需要一些机制来跟踪每个子数组的大小，虽然知道子数组的大小是相同的可以解决问题，但并不是很通用）

原则上，您可以构建一个索引，连接到标准多维数组的子数组。

int arr[6][10];                         // <=== Multi-dimensional array
int **ragged = calloc(6,sizeof(int*));  // <=== Ragged array (initially empty)
for (int i=0; i<6 ++i) {
   ragged[i] = arr[i];                  // <=== make the ragged array alias arr
}

现在我有一个二维数组和一个使用相同数据的二维不规则数组。

因此，语言中的多维数组并不是不规则数组的特例。

这似乎假设一个不规则数组是指指针数组。但从英语单词“ragged”（意为“不直”的）来看，我认为不规则数组的定义特征是子数组可能具有不同的大小，而不一定是通过指针保持子数组可见（我可以想象一个不规则数组，其中没有指针，但行索引依赖于数学函数计算连续缓冲区中的偏移量）。 - Johannes Schaub - litb
@Johannes：如果你指的是一个具有两个（或多个）索引但可能具有非矩形“形状”的抽象实体，那么矩形多维数组就是一种特殊情况。我一直使用“不规则数组”来表示指向指针构造的指针（即一种实现而不是抽象）。你会去哪里寻找权威定义呢？ - dmckee --- ex-moderator kitten
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接