我正在用C/c++程序处理我的数据，这是二维的。这里我的值是成对计算的，这里foo[i][j]和foo[j][i]的值是一样的。
认为,
如果你有N个项目，那么没有主对角线的下三角形数组将有(N - 1) * N/2个元素，或(N + 1) * N/2个元素与主对角线。没有主对角线，(I,J) (I,J∈0..)N-1, I> J)⇒(I * (I -1)/2 + J).对于主对角线，(I,J∈0..)N-1, I≥J)⇒((I + 1) * I/2 + J).
(是的，当您在2.5 gb的机器上分配4gb时，将其减半确实会产生巨大的差异。)
真的，你最好只用一个普通的二维矩阵。RAM相当便宜。如果您真的不想这样做，那么您可以构建一个具有适当数量元素的一维数组，然后弄清楚如何访问每个元素。例如，如果数组的结构如下:
j
1234
i 1 A
2 BC
3 DEF
4 GHIJ
，你把它存储为一个一维数组，从左到右，你可以用array[3]访问元素C (2, 2)。你可以算出从[i][j]到[n]的函数，但我不会破坏你的乐趣。但你不必这么做除非这个三角形数组非常大或者你非常关心空间
如Dan和Praxeolitic提出的具有对角线但修正了过渡规则的下三角矩阵
对于n × n矩阵，需要数组(n+1)*n/2长度，转换规则为Matrix[i][j] = Array[i*(i+1)/2+j]。
#include<iostream>
#include<cstring>
struct lowerMatrix {
double* matArray;
int sizeArray;
int matDim;
lowerMatrix(int matDim) {
this->matDim = matDim;
sizeArray = (matDim + 1)*matDim/2;
matArray = new double[sizeArray];
memset(matArray, .0, sizeArray*sizeof(double));
};
double &operator()(int i, int j) {
int position = i*(i+1)/2+j;
return matArray[position];
};
};
我用double做了，但你可以把它做成template。这只是一个基本的框架，所以不要忘记实现析构函数
使用锯齿数组:
int N;
// populate N with size
int **Array = new Array[N];
for(int i = 0; i < N; i++)
{
Array[i] = new Array[N - i];
}
它会创建一个像
这样的数组 0 1 2 3 4 5
0 [ ]
1 [ ]
2 [ ]
3 [ ]
4 [ ]
5 [ ]
需要在n × n对称矩阵中表示的唯一元素的个数m:
与主对角线
m = (n*(n + 1))/2
没有对角线(对于OP描述的对称矩阵，需要主对角线，但只是为了更好地测量…)
m = (n*(n - 1))/2 .
如果使用带截断的整数算术，在最后一个运算之前不除以2是很重要的。
您还需要做一些算术来查找对角矩阵中x行y列对应的已分配内存中的索引i。
上对角矩阵第x行第y列分配内存索引i:
与对角线
i = (y*(2*n - y + 1))/2 + (x - y - 1)
没有对角线
i = (y*(2*n - y - 1))/2 + (x - y -1)
对于下对角矩阵，翻转方程中的x和y。对于对称矩阵，只需在内部选择x>=y或y>=x，并根据需要让成员函数翻转。
重复Dani的回答…
不要分配许多不同大小的数组，这会导致内存碎片或奇怪的缓存访问模式，你可以分配一个数组来保存数据，一个小数组来保存指向第一个分配的行的指针。
const int side = ...;
T *backing_data = new T[side * (side + 1) / 2]; // watch for overflow
T **table = new T*[side];
auto p = backing_data;
for (int row = 0; row < side; ++row) {
table[row] = p;
p += side - row;
}
现在你可以使用table，好像它是一个锯齿数组，如Dani的回答所示:
table[row][col] = foo;
但是所有的数据都在一个单独的块中，否则它可能不会取决于您的分配器的策略。
使用行指针表可能比使用Praxeolitic公式计算偏移量更快，也可能更快。
#include <stdio.h>
// Large math problems running on massively parallel systems sometimes use a lot
// of upper triangular matrices. Implemented naively, these waste 50% of the memory
// in the machine, which is not recoverable by virtual memory techniques because it
// is interspersed with data on each row. By mapping the array elements into an
// array that is half the size and not actually storing the zeroes, we can do twice
// the computation in the same machine or use half as many machines in total.
// To implement a safety feature of making the zero-part of an upper triangular matrix
// read-only, we place all the zeroes in write-protected memory and cause a memory violation
// if the programmer attempts to write to them. System dependent but relatively portable.
// Requires that you compile with the -Wno-discarded-qualifiers option.
// for the awkward case (an even-sized array bound):
// +--------/
// row 0, 40 items -> |0 /
// row 1, 39 items -> | /
// row 19, 21 items -> | /
// row 20, 20 items -> |----/ <------ cut and rotate here to form a rectangle.
// row 21, 19 items -> | /
// | /
// row 39, 1 item -> | /
// row 40, 0 items -> |/
// /
// x y x y
// 0,0 39,0
// +----/ | +--------/
// | / | row 0, 40 items -> |0 /| <-- row 40, 0 items
// | / - 20,18 | row 1, 39 items -> | /0| <-- row 39, 1 item
// | / | row 19, 21 items -> | / | <-- row 21, 19 items
// |/ 19,19 | row 20, 20 items -> | /???| <-- row 20, 20 items half of row 20 is wasted...
//0,39 v | ~~~~~~~~~~
// | |
// for odd-sized array bounds, there is no need for the wasted half-row marked '???' above...
// And once the mapping above is done, mirror the indexes in x to get a proper Upper Triangular Matrix which
// looks like this...
// ____
// |
// |
// |
//
// Rather than store the underlying data in a 2D array, if we use a 1-D array,
// and map the indexes ourselves, it is possible to recover that final half-row...
// The implementation allows for the matrix elements to be any scalar type.
#define DECLARE_TRIANGULAR_MATRIX(type, name, bound, zero)
type _##name[bound * (bound+1) / 2 + 1]; /* +1 is for a debugging tombstone */
type *__##name(int x, int y) {
static const type Zero = zero; /* writing to the lower half of the matrix will segfault */
x = (bound-1)-x; /* mirror */
if (x+y >= bound) return &Zero; /* requires cc -Wno-discarded-qualifiers */
if (y > bound/2) {x = (bound-1)-x; y = bound-y;}
return &_##name[y*bound+x]; /* standard mapping of x,y -> X */
}
#define TRIANGULAR_MATRIX(name, x, y) *__##name(x,y)
// ----------------------------------------------------------------------------------------
// Simulate 'int fred[11][11];' as an upper triangular matrix:
#define ARRAYSIZE 11
DECLARE_TRIANGULAR_MATRIX(int, fred, ARRAYSIZE, 0)
#define fred(x, y) TRIANGULAR_MATRIX(fred, x, y)
/* unfortunately we can't #define fred[x][y] here ... In the Imp language which used () both
for array indexes and procedure parameters, we could write a mapping function fred(x,y)
which made the indirected function call indistinguishable from a normal array access.
We attempt to do something similar here using macros, but C is not as cooperative. */
int main(int argc, char **argv) {
int x,y, element;
// treat as fully populated 2D array...
for (y = 0; y < ARRAYSIZE; y++) {
for (x = 0; x < ARRAYSIZE; x++) {
if (y <= x) fred(x,y) = (x+1) * 100 + (y+1); // upper triangle test
}
}
fprintf(stdout, "Upper Triangular matrix:nn");
fprintf(stdout, " ");
for (x = 0; x < ARRAYSIZE; x++) fprintf(stdout, "%5d", x);
fprintf(stdout, "n ");
for (x = 0; x < ARRAYSIZE; x++) fprintf(stdout, "_____");
fprintf(stdout, "n");
for (y = 0; y < ARRAYSIZE; y++) {
fprintf(stdout, "%2d |", y);
for (x = 0; x < ARRAYSIZE; x++) {
element = fred(x,y);
fprintf(stdout, "%5d", element);
if (y <= x) { // upper triangle test
if (element != (x+1) * 100 + (y+1)) {
fflush(stdout); fprintf(stderr, "Mismatch! at %d,%d (%d != %d)n", x, y, element, x * 100 + y);
}
} else if (element != 0) {
fflush(stdout); fprintf(stderr, "Mismatch! at %d,%d (%d != 0)n", x, y, element);
}
}
fprintf(stdout, "n");
}
return 0;
}