数组

线性结构的推广

数组的定义及特点

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

线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展

数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。

数组特点：结构固定 ———— 维数和维界不变

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组
一维数组的逻辑结构：线性结构，定长的线性表
声明格式：数据类型 变量名[长度]
    int num[5];

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组
二维数组的逻辑结构：
①非线性结构：每一个数据元素既在一个行表中，又在一个列表中(前驱和后继不只有一个)
②线性结构：该线性表的每一个数据元素也是一个定长的线性表
声明格式：数据类型 变量名[行数][列数]
    int num[5][8];//5行8列

int array2[m][n];
↓
int array1[n];
array1 array2[m];

数组的顺序存储

计算数组中某一个元素的存储位置：

一维数组：
求某个元素所在地址：
LOC(i) = LOC(0) = a,i = 0
      LOC(i-1) + L = a + i* L

二维数组(行序优先表示)：
数组元素a[i][j]的存储位置是：
LOC(i,j) = LOC(0,0) + (n * i + j) + L

特殊矩阵的压缩存储

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

什么样的矩阵能够压缩？
一些特殊矩阵，如：对称矩阵、对角矩阵、三角矩阵、稀疏矩阵等

1. 对称矩阵

特点：Aij = Aji
存储方法：只存储下三角(包括主对角线)的数据元素。
共占有 n(n+1)/2个元素空间

可以以行序为主序将元素放在一个一维数组Sa[n(n+1)/2]中
Aij前面有多少个元素，它就存储在什么位置(下标从0开始)

2. 三角矩阵

特点：对角线以下的数据元素(不包括对角线)全部为常数c
上三角矩阵：下面为常数
下三角矩阵:上面为常数
存储方法：重复元素c共享一个元素的存储空间，共占用n(n+1)/2 + 1个元素

3. 对角矩阵

特点：在nxn的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0.则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。
存储方法：以对角线的顺序存储

4. 稀疏矩阵

稀疏矩阵：矩阵中非零元素的个数较少(一般小于5%)
存储方法:
(1)三元组

(i,j,Aij)
(row,col,value)
存储原则：存各非零元的值、行列位置和矩阵的行列数
优点：非零元在表中按行序有序存储，便于进行依行顺序处理的矩阵运算
缺点：不能随机存取。需要从头开始进行查找
(2)十字链表

除了(row,col,value)以外，还有两个域：
right:用于链接同一行中的下一个非零元素；
down:用于链接同一列中下一个非零元素。
优点：能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的非零元素，实现矩阵的各种运算。

广义表

拓宽了的线性表就是广义表

广义表(又称列表Lists)：是n个元素的有限序列，其中每一个ai或者是原子，或者是一个广义表
通常记作：LS = (a1,a2,a3,a4,…,an)
      其中：LS为表名，n为表的长度，每一个ai为表的元素

表头：若LS非空,则其第一个元素a1就是表头
      记作head(LS)=a1
      表头可以是原子，也可以是子表
表尾：除表头之外的其他元素组成的表
      记作：tail(LS)=(a2,a3,…,an)
      表尾不是最后一个元素，而是一个子表

广义表的性质

1. 广义表的长度：最外层所包含元素的个数
         如C=(a,(b,c))是长度为2的广义表
2. 广义表的深度：该广义表展开后所包含括号的重数
         “原子”的深度为0；“空表”的深度为1
3. 广义表可以为其他广义表共享
         如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用，B=(A)
4. 广义表可以是一个递归的表
         如：F=(a,F)=(a,(a,(a,…)))
         递归表的深度是无穷值，长度是有限值
5. 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表

广义表的基本运算

1. 求表头GetHead(L):非空广义表的第一个元素，可以是一个元素，也可以是一个子表
2. 求表尾GetTail(L):非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表