WEB开发网
开发学院软件开发C++ C++中的23种算法 阅读

C++中的23种算法

 2012-05-29 11:10:16 来源:WEB开发网   
核心提示:「以列(Row)为主」或「以行(Column)为主」,由于C/C++、Java等的记忆体配置方式都是以列为主,C++中的23种算法(16),所以您可能会比较熟悉前者(Fortran的记忆体配置方式是以行为主),以列为主的二维阵列要转为一维阵列时,其公式为:loc = j*(j-1)/2 + i下三角矩阵化为一维阵列,若

「以列(Row)为主」或「以行(Column)为主」。由于C/C++、Java等的记忆体配置方式都是

以列为主,所以您可能会比较熟悉前者(Fortran的记忆体配置方式是以行为主)。

以列为主的二维阵列要转为一维阵列时,是将二维阵列由上往下一列一列读入一维阵列,此时

索引的对应公式如下所示,其中row与column是二维阵列索引,loc表示对应的一维阵列索引:

loc = column + row*行数

以行为主的二维阵列要转为一维阵列时,是将二维阵列由左往右一行一行读入一维阵列,此时

索引的对应公式如下所示:

loc = row + column*列数

公式的推导您画图看看就知道了,如果是三维阵列,则公式如下所示,其中i(个数u1)、j(个

数u2)、k(个数u3)分别表示三维阵列的三个索引:

以列为主:loc = i*u2*u3 + j*u3 + k

以行为主:loc = k*u1*u2 + j*u1 + i

更高维度的可以自行依此类推,但通常更高维度的建议使用其它资料结构(例如物件包装)会

比较具体,也不易搞错。

在C/C++中若使用到指标时,会遇到指标运算与记忆体空间位址的处理问题,此时也是用到这

边的公式,不过必须在每一个项上乘上资料型态的记忆体大小。

#include <stdio.h>

#include <stdlib.h>

int main(void) {

int arr1[3][4] = {{1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12}};

int arr2[12] = {0};

int row, column, i;

printf("原二维资料:\n");

for(row = 0; row < 3; row++) {

for(column = 0; column < 4; column++) {

printf("%4d", arr1[row][column]);

}

printf("\n");

}

printf("\n以列为主:");

for(row = 0; row < 3; row++) {

for(column = 0; column < 4; column++) {

i = column + row * 4;

arr2[i] = arr1[row][column];

}

}

for(i = 0; i < 12; i++)

printf("%d ", arr2[i]);

printf("\n以行为主:");

for(row = 0; row < 3; row++) {

for(column = 0; column < 4; column++) {

i = row + column * 3;

arr2[i] = arr1[row][column];

}

}

for(i = 0; i < 12; i++)

printf("%d ", arr2[i]);

printf("\n");

return 0;

}

21.上三角、下三角、对称矩阵

说明

上三角矩阵是矩阵在对角线以下的元素均为0,即Aij = 0,i > j,例如:

1 2 3 4 5

0 6 7 8 9

0 0 10 11 12

0 0 0 13 14

0 0 0 0 15

下三角矩阵是矩阵在对角线以上的元素均为0,即Aij = 0,i < j,例如:

1 0 0 0 0

2 6 0 0 0

3 7 10 0 0

4 8 11 13 0

5 9 12 14 15

对称矩阵是矩阵元素对称于对角线,例如:

1 2 3 4 5

2 6 7 8 9

3 7 10 11 12

4 8 11 13 14

5 9 12 14 15

上三角或下三角矩阵也有大部份的元素不储存值(为0),我们可以将它们使用一维阵列来储存

以节省储存空间,而对称矩阵因为对称于对角线,所以可以视为上三角或下三角矩阵来储存。

解法

假设矩阵为nxn,为了计算方便,我们让阵列索引由1开始,上三角矩阵化为一维阵列,若以

列为主,其公式为:loc = n*(i-1) - i*(i-1)/2 + j

化为以行为主,其公式为:loc = j*(j-1)/2 + i

下三角矩阵化为一维阵列,若以列为主,其公式为:loc = i*(i-1)/2 + j

若以行为主,其公式为:loc = n*(j-1) - j*(j-1)/2 + i

上一页  11 12 13 14 15 16 17 18  下一页

Tags:算法

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接