一、数组的定义及特点

数组

• 按照一定格式排列起来的，具有
  
  相同类型
  
  的数据元素的集合。

一维数组

• 若线性表中的数据元素为非结构的简单元素，则称为一维数组。
• 
  逻辑结构
  
  ：
  
  线性结构
  
  。定长的线性表
• 
  声明格式
  
  ：数据类型 变量名 [数组长度]。
  • 
    如：int num [5] = {0，1，2，3，4};

二维数组

• 若一维数组中的数据元素又是一维数组结构，则称为二维数组。
• 
  逻辑结构
  
  ：
  • 
    
    非线性结构
    
    ：每一个数据元素既在一个行表中，又在一个列表中。
  • 
    
    线性结构
    
    （定长的线性表）：该线性表的每个数据元素也是一个固定长度的线性表。
• 
  声明格式
  
  ：数据类型 变量名[行数][列数]；
  • 
    如 int A [3][4]，这样就定义了一个名为A的数组内每个元素都是 int 类型的三行四列的二维数组出来了。

• 除了4个角落的元素之外，每个元素都有不止一个前趋和后继，比如说这里的 a11，在它所在的这一行有前趋 a10 和后继 a12，在它所在的这一列里，又有 a01 这个前趋和 。。。这个后继。

三维数组

• 若二维数组中的元素又是一个一维数组，则称之为三维数组。

n 维数组

• 若 n-1 维数组中的元素又是一个一维数组结构，则称作 n 维数组。

结论

• 
  线性表结构时数组结构的一个特立，而数组结构又是线性表结构的扩展
  
  。

数组特点

• 
  结构固定
  
  —— 定义后，维数和维界不再改变。

数组基本操作

• 除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。
• 不会说有什么插入或者删除数组中的某个元素的操作。

二、数组的抽象数据类型定义

n 维数组的抽象数据类型

• n 为数组的维数（一维数组、二维数组…）。
• bi 为数组第 i 维的长度。
• ji 为数组元素第 i 维的下标。

举个例子

：

• 
  二维数组
  
  的抽象数据类型的数据对象和数据关系的定义。

  • 
    n = 2（维数为2，二维数组）。
  • 
    b₁：第 1 维长度（行数）；b₂：第 2 维长度（列数）。
  • 
    aj₁j₂：第 1 维下标为 j₁，第 2 维下标为 j₂。

基本操作

1. 
   构造数组 A
   
   ：==InitArray(&A,n,bound1,…boundn)。
2. 
   销毁数组 A
   
   ：DestroyArray(&A)。
3. 
   取数组元素值
   
   ：Value(A,&e,index1,…,indexn)。
4. 
   给数组元素赋值
   
   ：Assign(A,&e,index1…,indexn)。

三、数组的顺序存储

数组特点

• 
  结构固定
  
  ，固定以后，维数和维界不再改变，所以比较适合采用
  
  顺序存储结构
  
  。

数组基本操作

• 除了结构的初始化和销毁之外，只有取元素合修改元素值的操作。
• 不会说有什么插入或者删除数组中的某个元素的操作。

注意

• 数组可以是多维的，但存储数据元素的内存单元地址是一维的；
• 因此，在存储数据结构之前，需要解决将多维关系映射到一维关系的问题。

1. 一维数组

• 例，有数组定义：
  
  int a [5]
  
  ;
  • 
    每个元素占用4个字节，假设 a[0] 存储在2000单元的位置，a[3] 应该在 2012 的位置上，2000 + （3 – 0）* 4。

• 下标为 3 的元素前面有 3 个元素，如果是下标为 i 的元素，则前面有 i 个元素，第 i 个元素的位置应该是首元素的地址+i * 每个元素的大小——>
  
  LOC(i) = a + i * L
  
  。

2. 二维数组

• 假设一个 m 行 n 列的二维数组，每一行都有 n 个元素，每列都有 m 个元素。

• 这样一个二维数组可以看成是由若干行组成的，每一行都是一个一维数组。

• 也可以看成是由若干列组成的，每一列都是一个一维数组。

两种顺序存储方式

• 
  以行为主序
  
  （低下标优先）BASIC、COBOL 和 PASCAL。
• 
  以列为主序
  
  （高下标优先）FORTRAN。

2.1 以行序为主序

• 存储单元是
  
  一维
  
  结构，而数组是个
  
  多维
  
  结构，则用一组连续存储单元存放数组的数据元素就有个
  
  次序约定
  
  问题。
• 按照行来存储，存储完第一行之后再存储第二行，以此类推。
• 要查找某个元素的话就要找到对应的行列位置，如：第一行一列的元素就在 [0][0] 的位置，第二行第二列的元素就在下标为 [1][1] 的位置。

• 每一行都从第一个元素开始存储直到存储到下标为 n – 1 的位置然后就换下一行存储。
• 第一行的首元素下表为 [0][0]，最后一行的首元素下标则为 [m – 1][0]。

以行序为主序的存储位置计算

• 设数组开始存储位置为LOC(0,0)，存储每个元素需要 L 个存储单元（字节）。
• 数组元素 a[i][j] 的存储位置是：
  
  LOC(i,j) = LOC(0,0) + (n * i + j) * L
  
  。
  • 
    
    （数组总列数 * i 行 + j 列）* 元素大小
    
    。

2.2 以列序为主序

• 按照列来存储，存储好一列之后再存储下一列。

• 先从第一列开始存，第一列的首元素存到最后一个元素的下标应该是 a[0][0]（首行首列），a[1][0]（二行一列）a[2][0]）（三行一列）以此类推直到 a[m – 1][0]（m行1列）。

四、特殊矩阵的压缩存储

矩阵

• 一个由 m * n 个元素排成的 m 行 n 列的表。
• 有时为了节省存储空间，可以对这类矩阵进行
  
  压缩存储
  
  。

矩阵的常规存储

• 将矩阵描述为一个二维数组。

矩阵的常规存储的特点

• 可以对其元素进行随机存取。
• 矩阵运算非常简单，存储的密度为1。
  • 
    不需要额外的空间存放地址，分配100个字节的空间就能存储100字节的数据。

不适合常规存储的矩阵

• 值相同的元素很多且呈某种归路分布；
  
  零元较多
  
  。

矩阵的压缩存储

• 为多哥相同的非零元素只分配一个存储空间；
  
  对零元素不分配空间
  
  。

1. 什么是压缩存储

• 若多个数据元素的
  
  值都相同
  
  ，则只分配一个元素值的存储空间，且零元素不占存储空间。

2. 什么样的矩阵能够压缩？

• 一些分布有规律的矩阵；
• 
  对称矩阵、对角矩阵、三角矩阵、稀疏矩阵
  
  等。

3. 什么是稀疏矩阵

• 矩阵中非零元素的个数较少（一般小于 5%）
• 有 95% 以上的元素是零，不需要给这些元素分配空间，一下节省 95% 的空间。

1. 对称矩阵

• 沿着对角线相等的矩阵就称为
  
  对称矩阵
  
  。

特点

• 在 n x n 的矩阵 a 中，满足如下性质：aij = aji (1 <= i,j <= n)。
• 比如说上图中 a[4][1] = a[1][4]

对称矩阵的存储方式

• 因为元素是按照对角线来存储的，另一半是一样的元素，不需要全部存；
• 只存储下（或者上）三角（包括主对角线）的数据元素。
  • 
    共占用
    
    n(n + 1) / 2
    
    ，
    
    项数 *（首项 + 末项）/ 2
    
    个元素空间。

对称矩阵的存储结构

• 对称矩阵上下三角中的元素数均为：
  
  n(n + 1) / 2
  
  。
• 可以
  
  以行序为主序
  
  将元素存放在一个一维数组 sa[
  
  n(n + 1) / 2
  
  ]中。

• 下标用 k 来表示，第一行放1个元素进a[0]中，第二行放两个进a[1]，a[2]中，以此类推。

2. 三角矩阵

特点

• 对角线以下（或以上）的数据元素（不包括对角线）全部为常数 C (所有值一样)。

三角矩阵的存储方式

• 重复元素 C 共享一个元素存储空间，总共占用
  
  n(n + 1) / 2 + 1
  
  个元素空间：sa[1…n(n+1) / 2+1]。
• 
  上三角矩阵
  
  sa[k] 和矩阵元 aij 之间的对应关系为：

• 
  下三角矩阵
  
  sa[k] 和矩阵元 aij 之间的对应关系为：

3. 对角矩阵

特点

• 在 n x n 的方阵中，所有
  
  非零元素都集中在以主对角线为中心的带状区域中
  
  （只在对角线和对角线旁边有值），
  
  区域外的值全是 0
  
  ，则称为
  
  对角矩阵
  
  。
• 常见的有三对角矩阵、五对角矩阵、七对角矩阵。
  • 
    如下图：只有在三条对角线的范围内有值。再加两条有值的对角线就是五对角矩阵了，依次类推。

对角矩阵的存储方式

• 为 0 的元素直接扔掉不存。
• 用二维数组的方式去存。

• 
  按对角线来存储
  
  ，第一条对角线是 3385，则将3385 存在二维数组的第一行，第二条对角线是 20612 则存在第二行，以此类推。
• 
  以主对角线为0
  
  ，看主对角线有几个元素，决定二维数组的每行要分配多少个元素的空间。
• 其余对角线进行上下对称。这样一个原本需要36个存储空间的矩阵现在就只需要30个了。

4. 稀疏矩阵

什么是稀疏矩阵?

• 矩阵中非零元素的个数较少（一般小于 5%）
• 有 95% 以上的元素是零，不需要给这些元素分配空间，一下节省 95% 的空间。
  • 
    在这样有 42 个元素的矩阵中非零元素只有 8 个，如果将零也存储起来就非常浪费空间了，存储密度只有 19.05%左右。

稀疏矩阵的存储方式

• 
  三元组
  
  ：每个非零元素由它所在的行列和它本身的值来确定（
  
  i,j,aij
  
  ）。
  • 
    比如下图的第一个元素12，它的存储就是 1 行 2 列值 12 确定。

压缩存储原则

• 存各非零元素的值，行列位置和矩阵的行列数。
  • 
    三元组的不同表示方法可以决定稀疏矩阵不同的压缩存储方法。
• 第 0 行表示存储的这个矩阵有几行几列几个非零元素，其余每行就是按顺序存储非零元素的行列值了。

还原稀疏矩阵

• 试还原出下列三元组所表示的系数矩阵。

• 第一行的 646 表示原来的稀疏矩阵有 6 行 4 列 6 个非零元素。
• 非零值按照 i 和 j 所代表的行列位置以及将 value 值存放到具体位置。
  • 
    如：第二行的 122 表示值为 2 的元素出现在1行 2 列的位置，其余同理。
• 其余所有位置全部补 0 。

• 三元组顺序表又称
  
  有序的双下标法
  
  。

三元组顺序表的优缺点

• 
  优点
  
  ：非零元素在表中按行执行有序存储，因此
  
  便于进行依行顺序处理的矩阵运算
  
  。
• 
  缺点
  
  ：缺点同样是因为按行处理的，导致不能随机存取。
  • 
    若按行号存取某一行中的非零元，则需要从头开始进行查找。
  • 
    这个时候就需要用到稀疏矩阵的链式存储结构：
    
    十字链表
    
    了。

4.1 十字链表

• 
  优点
  
  ：能够
  
  灵活地插入
  
  因运算而产生的新的非零元素，
  
  删除
  
  因运算而产生的新的零元素，实现矩阵的各种运算。

• 在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row,col,value）以外，还要有两个域。

  • 
    
    right
    
    ：用于链接同一行中的下一个非零元素。
  • 
    
    down
    
    ：用于链接同一列中的下一个非零元素。

• 十字链表中结点的结构示意图：

【例1】

• 假设有这样一个矩阵 m

• 先要存储第一个非零元素 3 ，需要知道与它同一行的下一个元素 5 的位置，以及同列的下一个元素 2 的位置。

• 此时还需要1个结点来存储 -1，同样，因为与 -1 同行同列的已经没有非零元素了，所以 right 及 dawn 域都置空。

• 此时还需要两个分别指向每行每列的头指针数组，在这样一个十字链表中，有三行，所以就需要弄一个存储三个头指针的数组，列同理。

【例2】

• 稀疏矩阵中，有几行就要有几个行头指针，有几列就要有各个列头指针。
• 这些指针都指向 行/列 中的第一个元素。