什么是数组存储结构

什么是数组存储结构

前面学习数据结构的过程中，总是使用数组作为顺序表的底层实现，给我们一种 "数据结构中，数组的作用就是实现顺序表" 的错误认识。其实，数组的作用远不止于此。 本节将从数据结构的角度讲解数组存储结构。

本节所讲的数组，要将其视为一种存储结构，与平时使用的数组基本数据类型区分开。

一说起数组，我们的印象中数组往往是某一门编程语言中包含的具体数据类型，其实不然。 从本质上讲，数组与顺序表、链表、栈和队列一样，都用来存储具有 "一对一" 逻辑关系数据的线性存储结构。只因各编程语言都默认将数组作为基本数据类型，使初学者对数组有了 "只是基本数据类型，不是存储结构" 的误解。 不仅如此，数组和其他线性存储结构不同，顺序表、链表、栈和队列存储的都是不可再分的数据元素（如数字 5、字符 'a' 等），而数组既可以用来存储不可再分的数据元素，也可以用来存储像顺序表、链表这样的数据结构。 比如说，数组可以直接存储多个顺序表。我们知道，顺序表的底层实现还是数组，因此等价于数组中继续存储数组。这与平时使用的二维数组类似。 根据数组中存储数据之间逻辑结构的不同，数组可细分为一维数组、二维数组、...、n 维数组：

• 一维数组，指的是存储不可再分数据元素的数组，如图 1 所示；

一维数组存储结构示意图

图 1 一维数组存储结构示意图

• 二维数组，指的存储一维数组的一维数组，如图 2 所示；

二维数组存储结构示意图

图 2 二维数组存储结构示意图

• n 维数组，指的是存储 n-1 维数组的一维数组；

注意，无论数组的维数是多少，数组中的数据类型都必须一致。

由此，我们可以得出这样一个结论，一维数组结构是线性表的基本表现形式，而 n 维数组可理解为是对线性存储结构的一种扩展。

数组的顺序存储（C语言版）

数组作为一种线性存储结构，对存储的数据通常只做查找和修改操作，因此数组结构的实现使用的是顺序存储结构。

要知道，对数组中存储的数据做插入和删除操作，算法的效率是很差的。

由于数组可以是多维的，而顺序存储结构是一维的，因此数组中数据的存储要制定一个先后次序。通常，数组中数据的存储有两种先后存储方式：

1. 以列序为主（先列后行）：按照行号从小到大的顺序，依次存储每一列的元素
2. 以行序为主（先行后序）：按照列号从小到大的顺序，依次存储每一行的元素。

多维数组中，我们最常用的是二维数组。比如说，当二维数组 a[6][6] 按照列序为主的次序顺序存储时，数组在内存中的存储状态如图 1 所示：

图 1 以列序为主的二维数组存储状态

同样，当二维数组 a[6][6] 按照行序为主的次序顺序存储时，数组在内存中的存储状态如图 2 所示：

图 2 以行序为主的二维数组存储状态

C 语言中，多维数组的存储采用的是以行序为主的顺序存储方式。

通过以上内容，我们掌握了将多维数组存储在一维内存空间的方法。那么，后期如何对指定的数据进行查找和修改操作呢？

多维数组查找指定元素

当需要在顺序存储的多维数组中查找某个指定元素时，需知道以下信息：

• 多维数组的存储方式；
• 多维数组在内存中存放的起始地址；
• 该指定元素在原多维数组的坐标（比如说，二维数组中是通过行标和列标来表明数据元素的具体位置的）；
• 数组中数组的具体类型，即数组中单个数据元素所占内存的大小，通常用字母 L 表示；

根据存储方式的不同，查找目标元素的方式也不同。如果二维数组采用以行序为主的方式，则在二维数组 anm 中查找 aij 存放位置的公式为：

LOC(i,j) = LOC(0,0) + (i*m + j) * L;

其中，LOC(i,j) 为 aij 在内存中的地址，LOC(0,0) 为二维数组在内存中存放的起始位置（也就是 a00 的位置）。 而如果采用以列存储的方式，在 anm 中查找 aij 的方式为：

LOC(i,j) = LOC(0,0) + (i*n + j) * L;

以下给出了采用以行序为主的方式存储三维数组 a[3][4][2] 的 C 语言代码实现，这里不再对该代码进行分析（代码中有详细注释），有兴趣的读者可以自行拷贝运行：

1. #include<stdarg.h>
2. #include<malloc.h>
3. #include<stdio.h>
4. #include<stdlib.h> // atoi()
5. #include<io.h> // eof()
6. #include<math.h>
7. #define TRUE 1
8. #define FALSE 0
9. #define OK 1
10. #define ERROR 0
11. #define INFEASIBLE -1
12. #define OVERFLOW 3
13. #define UNDERFLOW 4
14. typedef int Status; //Status是函数的类型,其值是函数结果状态代码，如OK等
15. typedef int Boolean; //Boolean是布尔类型,其值是TRUE或FALSE
16. typedef int ElemType;
18. #define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8
19. typedef struct
20. {
21. ElemType *base; //数组元素基址，由InitArray分配
22. int dim; //数组维数
23. int *bounds; //数组维界基址，由InitArray分配
24. int *constants; // 数组映象函数常量基址，由InitArray分配
25. } Array;
27. Status InitArray(Array *A,int dim,...)
28. {
29. //若维数dim和各维长度合法，则构造相应的数组A，并返回OK
30. int elemtotal=1,i; // elemtotal是元素总值
31. va_list ap;
32. if(dim<1||dim>MAX_ARRAY_DIM)
33. return ERROR;
34. (*A).dim=dim;
35. (*A).bounds=(int *)malloc(dim*sizeof(int));
36. if(!(*A).bounds)
37. exit(OVERFLOW);
38. va_start(ap,dim);
39. for(i=0; i<dim; ++i)
40. {
41. (*A).bounds[i]=va_arg(ap,int);
42. if((*A).bounds[i]<0)
43. return UNDERFLOW;
44. elemtotal*=(*A).bounds[i];
45. }
46. va_end(ap);
47. (*A).base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
48. if(!(*A).base)
49. exit(OVERFLOW);
50. (*A).constants=(int *)malloc(dim*sizeof(int));
51. if(!(*A).constants)
52. exit(OVERFLOW);
53. (*A).constants[dim-1]=1;
54. for(i=dim-2; i>=0; --i)
55. (*A).constants[i]=(*A).bounds[i+1]*(*A).constants[i+1];
56. return OK;
57. }
58. Status DestroyArray(Array *A)
59. {
60. //销毁数组A
61. if((*A).base)
62. {
63. free((*A).base);
64. (*A).base=NULL;
65. }
66. else
67. return ERROR;
68. if((*A).bounds)
69. {
70. free((*A).bounds);
71. (*A).bounds=NULL;
72. }
73. else
74. return ERROR;
75. if((*A).constants)
76. {
77. free((*A).constants);
78. (*A).constants=NULL;
79. }
80. else
81. return ERROR;
82. return OK;
83. }
84. Status Locate(Array A,va_list ap,int *off) // Value()、Assign()调用此函数 */
85. {
86. //若ap指示的各下标值合法，则求出该元素在A中的相对地址off
87. int i,ind;
88. *off=0;
89. for(i=0; i<A.dim; i++)
90. {
91. ind=va_arg(ap,int);
92. if(ind<0||ind>=A.bounds[i])
93. return OVERFLOW;
94. *off+=A.constants[i]*ind;
95. }
96. return OK;
97. }
98. Status Value(ElemType *e,Array A,...) //在VC++中，...之前的形参不能是引用类型
99. {
100. //依次为各维的下标值，若各下标合法，则e被赋值为A的相应的元素值
101. va_list ap;
102. Status result;
103. int off;
104. va_start(ap,A);
105. if((result=Locate(A,ap,&off))==OVERFLOW) //调用Locate()
106. return result;
107. *e=*(A.base+off);
108. return OK;
109. }
110. Status Assign(Array *A,ElemType e,...)
111. {
112. //依次为各维的下标值，若各下标合法，则将e的值赋给A的指定的元素
113. va_list ap;
114. Status result;
115. int off;
116. va_start(ap,e);
117. if((result=Locate(*A,ap,&off))==OVERFLOW) //调用Locate()
118. return result;
119. *((*A).base+off)=e;
120. return OK;
121. }
123. int main()
124. {
125. Array A;
126. int i,j,k,*p,dim=3,bound1=3,bound2=4,bound3=2; //a[3][4][2]数组
127. ElemType e,*p1;
128. InitArray(&A,dim,bound1,bound2,bound3); //构造3＊4＊2的3维数组A
129. p=A.bounds;
130. printf("A.bounds=");
131. for(i=0; i<dim; i++) //顺序输出A.bounds
132. printf("%d ",*(p+i));
133. p=A.constants;
134. printf("\nA.constants=");
135. for(i=0; i<dim; i++) //顺序输出A.constants
136. printf("%d ",*(p+i));
137. printf("\n%d页%d行%d列矩阵元素如下:\n",bound1,bound2,bound3);
138. for(i=0; i<bound1; i++)
139. {
140. for(j=0; j<bound2; j++)
141. {
142. for(k=0; k<bound3; k++)
143. {
144. Assign(&A,i*100+j*10+k,i,j,k); // 将i*100+j*10+k赋值给A[i][j][k]
145. Value(&e,A,i,j,k); //将A[i][j][k]的值赋给e
146. printf("A[%d][%d][%d]=%2d ",i,j,k,e); //输出A[i][j][k]
147. }
148. printf("\n");
149. }
150. printf("\n");
151. }
152. p1=A.base;
153. printf("A.base=\n");
154. for(i=0; i<bound1*bound2*bound3; i++) //顺序输出A.base
155. {
156. printf("%4d",*(p1+i));
157. if(i%(bound2*bound3)==bound2*bound3-1)
158. printf("\n");
159. }
160. DestroyArray(&A);
161. return 0;
162. }

运行结果为：

A.bounds=3 4 2 A.constants=8 2 1 3页4行2列矩阵元素如下: A[0][0][0]= 0 A[0][0][1]= 1 A[0][1][0]=10 A[0][1][1]=11 A[0][2][0]=20 A[0][2][1]=21 A[0][3][0]=30 A[0][3][1]=31 A[1][0][0]=100 A[1][0][1]=101 A[1][1][0]=110 A[1][1][1]=111 A[1][2][0]=120 A[1][2][1]=121 A[1][3][0]=130 A[1][3][1]=131 A[2][0][0]=200 A[2][0][1]=201 A[2][1][0]=210 A[2][1][1]=211 A[2][2][0]=220 A[2][2][1]=221 A[2][3][0]=230 A[2][3][1]=231 A.base= 0 1 10 11 20 21 30 31 100 101 110 111 120 121 130 131 200 201 210 211 220 221 230 231

数据结构中，提供针对某些特殊矩阵的压缩存储结构。 这里所说的特殊矩阵，主要分为以下两类：

• 含有大量相同数据元素的矩阵，比如对称矩阵；
• 含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

对称矩阵

对称矩阵示意图

图 1 对称矩阵示意图

图 1 的矩阵中，数据元素沿主对角线对应相等，这类矩阵称为对称矩阵。

矩阵中有两条对角线，其中图 1 中的对角线称为主对角线，另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。

结合数据结构压缩存储的思想，我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据即可。 对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：

存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式：

最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。 例如，在数组 skr[6] 中存储图 1 中的对称矩阵，则矩阵的压缩存储状态如图 3 所示（存储上三角和下三角的结果相同）：

对称矩阵的压缩存储示意图

图 3 对称矩阵的压缩存储示意图

注意，以上两个公式既是用来存储矩阵中元素的，也用来从数组中提取矩阵相应位置的元素。例如，如果想从图 3 中的数组提取矩阵中位于 (3,1) 处的元素，由于该元素位于下三角，需用下三角公式获取元素在数组中的位置，即：

结合图 3，数组下标为 3 的位置存储的是元素 3，与图 1 对应。

上（下）三角矩阵

上(下)三角矩阵

图 4 上(下)三角矩阵

如图 4 所示，主对角线下的数据元素全部相同的矩阵为上三角矩阵（图 4a)），主对角线上元素全部相同的矩阵为下三角矩阵（图 4b)）。 对于这类特殊的矩阵，压缩存储的方式是：上（下）三角矩阵采用对称矩阵的方式存储上（下）三角的数据（元素 0 不用存储）。 例如，压缩存储图 4a) 中的上三角矩阵，矩阵最终的存储状态同图 3 相同。因此可以得出这样一个结论，上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

稀疏矩阵

稀疏矩阵示意图

图 5 稀疏矩阵示意图

如图 5 所示，如果矩阵中分布有大量的元素 0，即非 0 元素非常少，这类矩阵称为稀疏矩阵。 压缩存储稀疏矩阵的方法是：只存储矩阵中的非 0 元素，与前面的存储方法不同，稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。 例如，存储图 5 中的稀疏矩阵，需存储以下信息：

• (1,1,1)：数据元素为 1，在矩阵中的位置为 (1,1)；
• (3,3,1)：数据元素为 3，在矩阵中的位置为 (3,1)；
• (5,2,3)：数据元素为 5，在矩阵中的位置为 (2,3)；
• 除此之外，还要存储矩阵的行数 3 和列数 3；

由此，可以成功存储一个稀疏矩阵。

注意，以上 3 种特殊矩阵的压缩存储，除了将数据元素存储起来，还要存储矩阵的行数值和列数值，具体的实现方式后续会介绍 3 种，本节仅需了解矩阵压缩存储的原理。

矩阵压缩存储的 3 种方式

对于以上 3 种特殊的矩阵，对阵矩阵和上下三角矩阵的实现方法是相同的，且实现过程比较容易，仅需套用上面给出的公式即可。 稀疏矩阵的压缩存储，数据结构提供有 3 种具体实现方式：

1. 三元组顺序表；
2. 行逻辑链接的顺序表；
3. 十字链表；