多维数组（数据结构）

1. 多维数组

1.1多维数组的存储：

$$LOC(A[j_1][j_2]\cdots [j_n])=LOC(A[c_1][c_2]\cdots [c_n])+\sum _{i=1}^n{\alpha }_i\ast (j_i)-c_i(1\le i\le n)$$
其中 $$a_i=size\ast \prod _{k=i+1}^n(d_k-c_k+1),(1\le i\le n)$$
所以可得到某数据元素存储位置为：

# include <iostream>
# include <algorithm>
# include <cstring>
using namespace std;
const int MAXSIZE = 100001;
int main(void)
{
int n, size = 2;
int c[MAXSIZE] = {0}, d[MAXSIZE] = {0}, j[MAXSIZE], a[MAXSIZE] = {0};
int LOC_1 = 0, LOC_2 = 0;
cout << "请输入数组的维数：" << endl;
cin >> n;
cout << "请输入数组的上下限：" << endl;
cout << "上限为：" << endl;
for(int i = 1;
i <= n; i++){
cin >> c[i];
}
cout << "下限为：" << endl;
for(int i = 1;
i <= n; i++){
cin >> d[i];
}
cout << "请输入下线地址" << endl;
cin >> LOC_1;
cout << "请输入计算元素的下标：" << endl;
for(int i = 1; i <= n; i++){
cin >> j[i];
}
for(int i = 1; i <= n; i++){
int sum = 1;
for(int k = i+1; k <= n; k++){
sum *= (d[k] - c[k] + 1);
}
a[i] = size*sum;
}
int sum = 0;
for(int i = 1; i <= n; i++){
sum += a[i] * (j[i] - c[i]);
}
LOC_2 = LOC_1 + sum;
cout << LOC_2 << endl;
system("pause");
return 0;
}

1.2 特殊矩阵：
（1）三角矩阵：
  三角矩阵分为上三角矩阵和下三角矩阵两种。由于三角矩阵有一半元素为0或者为常数，所以如果用普通二维数组存储三角矩阵会浪费很多空间，因此我们可以将矩阵压缩。可以将三角矩阵中的有效元素放在一维数组中，常数项仅需存到一维数组中的最后一个单元即可。
 可得到上三角矩阵按行序为主序的存储地址：
$$LOC(A[i][j])=LOC(A[1][1])+((i-1)(2n-i+2)/2+(j-i))\ast size$$
 同理可得到下三角矩阵按行序为主序的存储地址为：
$$LOC(a[i][j])=LOC(A[1][1])+(i(i-1)/2+(j-1))\ast size$$

1.3 稀疏矩阵：
（1）三元组顺序表示法：
  稀疏矩阵中的有效元素数量少且分布零散，所以用普通数组存储必然会浪费空间，所以可以建立一个顺序表，包含了有效元素的行、列、数值；
 可建立结构体如下：

typedef int ElementType;
typedef struct {
int row, col;
ElementType value;
}Triple;
typedef struct {
Triple data[MAXSIZE];
int rows, cols, nums;
}TSMatrix;

(2)转置运算：
1.按列序递增进行转置：$$按列序递增进行转置：O(A.col\ast A.nums)$$

void TransposeTSMatrix(TSMatrix A, TSMatrix * B){
int i, j, k = 1;
B->cols = A.cols;
B->rows = A.rows;
B->nums = A.nums;
if(B->nums <= 0) return;
for(i = 1; i <= A.cols; i++){
for(j = 1; j <= A.nums; j++){
if(A.data[j].col == i){
B->data[k].col = A.data[j].row;
B->data[k].row = A.data[j].col;
B->data[k].value = A.data[j].value;
k++;
}
}
}
return;
}

2. 控制元素个数，减少第一种算法多余步骤：

void TransposeTSMatrix2(TSMatrix A, TSMatrix *B){
int count = 0;
B->cols = A.cols;
B->rows = A.rows;
B->nums = A.nums;
if(B->nums <= 0) return;
for(int i = 0; i < A.cols; i++){
for(int j = 0; j < A.nums; j++){
if(A.data[j].col == i+1){
B->data[count].col = A.data[j].row;
B->data[count].row = A.data[j].col;
B->data[count++].value = A.data[j].value;
if(count > A.nums) return ; //count > A中元素个数，说明已完成转置
}
}
}
return;
}

3. 对于列分布跨度较大的矩阵：
    可以对原三元组进行查找最小列，然后存进转置三元组中，这样可减少循环次数；
   $$改进后：O(A.nums\ast A.nums)$$

void TransposeTSMatrix3(TSMatrix A, TSMatrix *B){
int count = 0, min = 0;
B->cols = A.cols;
B->rows = A.rows;
B->nums = A.nums;
if(B->nums <= 0) return;
for(int i = 0; i < A.nums; i++){
min = 0;
for(int j = 1; j < A.nums; j++){
if(A.data[j].col < A.data[min].col) min = j;
}
B->data[i].col = A.data[min].row;
B->data[i].row = A.data[min].col;
B->data[i].value = A.data[min].value;
A.data[min].col = A.cols+1;
}
return;
}

4. 一次定位快速转置：
   $$O(A.cols)$$

void TransposeTSMatrix4(TSMatrix *A, TSMatrix *B){
int num[MAXSIZE] = {0}, position[MAXSIZE];
B->cols = A->cols;
B->rows = A->rows;
B->nums = A->nums;
if(B->nums <= 0) return;
for(int i = 1; i <= A->nums; i++){
num[A->data[i].col]++;
//存放每一列非零元素的个数
}
position[1] = 1;
for(int i = 2; i <= A->cols; i++){
position[i] = position[i - 1] + num[i - 1];
//存放转置矩阵中，每一行在三元表中的位置；
} // position[col] 表示第col列在三元表中的位置；
for(int i = 1; i <= A->nums; i++){
int col = A->data[i].col;
int q = position[col];
B->data[q].row = A->data[i].col;
B->data[q].col = A->data[i].row;
B->data[q].value = A->data[i].value;
position[col]++;
}
}

最后

以上就是美好微笑为你收集整理的多维数组（数据结构）的全部内容，希望文章能够帮你解决多维数组（数据结构）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。