C/C++ 数据结构与算法【数组】 数组详细解析【日常学习，考研必备】带图+详细代码
一、介绍
**数组：**按一定格式排列起来的，具有租同类型的数据元素的集合。
1）一维数组：
若线性表中的数据元素为非结构的简单元素则称为一维数组。
**一维数组的逻辑结构：**线性结构。定长的线性表。
声明格式：
数据类型 变量名称[长度];
int num[5] = {0,1,2,3,4};
2）二维数组：
若一维数组中的数据元素又是一维数组结构，则称为二维数组。
二维数组的逻辑结构：
非线性结构：每一个数据元素既在一个行表中，非线性结构又在一个列表中。
线性结构（定长的线性表）：该线性表的每个数据元素也是一定长的线性表个定长的线性表。
声明格式：
数据类型 变量名称[行数][列数];
int num[5][8];
在C语言中，一个二维数组类型也可以定义为一维数据类型。（其分量类型为一维数组类型）。
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
3）n维数组:
三维数组：若二维数组中的元素又是一个一维数组，则称作三维数组。
…
n维数组：若 n-1 维数组中的元素又是一个一维数组结构则称作 n维数组。
结论：
线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展
数组特点:
结构固定——定义后，维数和维界不再改变。
二、数组的抽象数据类型定义
三、数组的顺序存储
因为
- 数组特点：结构固定维数和维界不变。
- 数组基本操作：初始化、销毁、取元素、修改元素值。一般不做插入和删除操作。
所以：一般都是采用顺序存储结构来表示数组。
注意：数组可以是多维的但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。
1）一维数组
2）二维数组
1、以行为主序
2、以列为主序
3、两者对比
4、行序列优先表示
这里的i是行索引，j是列索引，假设数组的起始地址为BaseAddress，每行有n个元素，每个元素占用ElementSize字节。
Position = BaseAddress + (i × n + j) × ElementSize
5、列序列优先表示
这里的i是行索引，j是列索引，假设数组的起始地址为BaseAddress，每行有n个元素，每个元素占用ElementSize字节。
Position = BaseAddress + (j × n + i) × ElementSize
3）三维数组
四、特殊矩阵的压缩存储
1.什么是压缩存储?
若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。
2.什么样的矩阵能够压缩?
一些特殊矩阵，如:对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
3.什么叫稀疏矩阵?
矩阵中非零元素的个数较少(一般小于5%)。
1）对称矩阵
2）三角矩阵
3）对角矩阵
4）稀疏矩阵
1、三元组顺序表
三元组顺序表又称有序的双下标法。
**三元组顺序表的优点：**非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。
**三元组顺序表的缺点：**不能随机存取。若按行号存取某一行中的非零元，则需从头开始进行查找。
2、链式存储：十字链表
例如：
