数据结构——数组（c）
可以看作是线性表的推广。
文章目录
前言
基于C语言实现数据结构中数组的相关定义与实现。
提示：以下是本篇文章正文内容，可供参考
一、数组的定义
数组：作为一种数据结构。
特点：结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。
数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界。
多维数组是一维数组的推广：
一维数组可以看作一个线性表。
二维数组可以看作“数据元素是一维数组”的一维数组。
三维数组可以看作“数据元素是二维数组”的一维数组。
以此类推
逻辑上是多维的，但存储在一维的数据结构中。（计算机的内存结构是一维的）
思考：如何将二维的，三维的数组存放在一维的数组中？
必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。
数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般采用顺序存储的方法来表示数组。
举个例子：
二维数组A可以看成由m个行向量组成的向量，也可以看成是n个列向量组成的向量。
1. 行优先顺序或以行为主序存储方式：将数组元素按行向量排列，第 i+1 个行向量紧接在第 i 个行向量后面。
多维时：先排最右的下标，从右到左，最后排最左下标。
举个二维的例子：
a
11
\displaystyle a_{11}
a11,
a
12
\displaystyle a_{12}
a12, … ,
a
1
n
\displaystyle a_{1n}
a1n,
a
21
\displaystyle a_{21}
a21,
a
22
\displaystyle a_{22}
a22, … ,
a
2
n
\displaystyle a_{2n}
a2n, … … ,
a
m
1
\displaystyle a_{m1}
am1,
a
m
2
\displaystyle a_{m2}
am2, … ,
a
m
n
\displaystyle a_{mn}
amn
LOC(
a
i
j
\displaystyle a_{ij}
aij)=LOC(
a
11
\displaystyle a_{11}
a11)+[(i-1)*n+j-1]*d
PASCAL、C
2. 列优先顺序或以列为主序存储方式：将数组元素按列向量排放，第 j+1 个列向量紧接在第 j 个向量之后。
多维时：先排最左的下标，从右向左，最后排最左下标。
举个二维的例子：
a
11
\displaystyle a_{11}
a11,
a
21
\displaystyle a_{21}
a21, … ,
a
m
1
\displaystyle a_{m1}
am1,
a
12
\displaystyle a_{12}
a12,
a
22
\displaystyle a_{22}
a22, … ,
a
m
2
\displaystyle a_{m2}
am2, … … ,
a
1
n
\displaystyle a_{1n}
a1n,
a
2
n
\displaystyle a_{2n}
a2n, … ,
a
m
n
\displaystyle a_{mn}
amn
LOC(
a
i
j
\displaystyle a_{ij}
aij)=LOC(
a
11
\displaystyle a_{11}
a11)+[(j-1)*m+i-1]*d
FORTRAN 语言中，数组按列优先顺序存储。
一般不强调，默认行优先。
数组存储的特点：数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结果。（只要知道开始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数）
数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
二、顺序表示和实现
三、矩阵的压缩存储
压缩存储为多个值相同的非零元素只分配一个存储空间。（对零元素不分配空间）
1.特殊矩阵的压缩存储
特殊矩阵：非零元素按照一定的规律分布。
常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。
（1）对称矩阵：元素的值按照主对角线对称压缩存储
（2）三角矩阵：上（下）三角矩阵是指矩阵的下（上）三角（不包括对角线）中的元素均为常数或零的n阶矩阵，即非零元素的分布在矩阵中呈现为三角形。
（3）对角矩阵：是指所有的非零元素都集中在以主对角线为中心的带状区域中。
eg. 三对角矩阵
上述各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一维数组中，并且一般都能找到矩阵中的元素与该一维数组元素的对应关系，仍能对矩阵的元素进行随机存储
2.稀疏矩阵的压缩存储
稀疏矩阵：简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即 s ≦ m*n），则称A为稀疏矩阵。
设矩阵A中有s个非零元素。令ｅ＝ｓ/( ｍ×ｎ) 为矩阵的稀疏因子。
通常ｅ≦0.05 时称之为稀疏矩阵。
①如何进行稀疏矩阵的压缩存储呢？ （只存储稀疏矩阵的非零元）
因为稀疏矩阵的非零元分布一般是没有规律的，所以用一个三元组 (i，j，
a
i
j
\displaystyle a_{ij}
aij)唯一确定了矩阵A的一个非零元。
故稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
//三元组结构体
typedef struct{
int i, j; //该非零元的行下标和列下标
int e; //该非零元的值
}Triple;
//矩阵的结构表示
typedef struct{
Triple data[MAXSIZE]; //非零元三元组表
int m, n, t; //矩阵的行数，列数和非零元个数
}TripleTable;
②三元组顺序表上的转置
转置运算 是一种最简单的矩阵运算。对于一个m×n的矩阵M，它的转置矩阵T是一个n×m的矩阵，且T(i, j) = M(j, i) , 1 ≦ i ≦ n, 1 ≦ j ≦ m。
③十字链表
四、广义表的定义
广义表是线性表的推广。
广义表中数据元素可以具有不同的结构（或是原子，或是列表），每个数据元素可用一个结点表示。
列如：
A = ( ) A是一个空表。（长度为0，深度为1）
B =（e） B只有一个原子。 （长度为1，深度为1）
C = ( a, (b, c, d) ） C有一个原子和一个子表。 （长度为2，深度为2）
D = ( A, B, C ) =（A，B， ( a, (b, c, d) ）） D有3个子表。 （长度为3，深度为3）
E = (a, E) = ( a, (a, (a, …, ) ) ) E是一个递归的表。 （长度为2，深度为无穷大）
广义表的结构特点：
广义表中的数据元素有相对次序（因为是线性表）
广义表的长度定义为表中的元素个数
广义表的深度定义为表的嵌套层数（“原子”的深度为0，“空表”的深度为1）
广义表可以共享
广义表可以是一个递归的表（深度是无穷值，长度是有限值）
广义表是一个多层次的线性结构
任何一个非空广义表LS均可分解为表头和表尾两部分。
表头（Head） 第一个元素
表尾（Tail） 除第一个元素外其余元素构成的表
举个例子：
D = ( E, F ) = ( ( a, ( b, c ) ), F )
Head(D) = E, Tail(D) = ( F )
Head(E) = a, Tail(E) = ( ( b, c ) )
Head( (( b, c )) ) = ( b,c ), Tail( (( b, c )) ) = ( )
Head( ( b, c ) ) = b, Tail( ( b, c ) ) = ( c )
1. 基本操作
- 结构的创建和销毁
- 状态函数
- 插入和删除操作
- 遍历
2. 存储结构
链表存储
由于广义表中数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。
链表结点结构
①表结点 （由3个域组成，标志域、指示表头的指针域、指示表尾的指针域）
②原子结构 （由2个域组成，标志域、值域）
3. 应用
m元多项式的表示