算法与数据结构 --- 串，数组与广义表 --- 数组

第一部分 --- 数组的定义

 

1.二维数组可以理解为一维数组的堆叠

2.二维数组既可以看作一个线性结构，也可以看作是一个非线性结构，所以我们将二维数组看作是一个特殊的线性结构，它是线性结构的拓展

（线性结构的标准就是元素具有唯一前驱和唯一后继）

 

 线性表其实就是一维数组，它是数组的一个特例，而数组则是线性表的推广

---

第二部分 --- 数组的抽象数据类型定义

n维数组中的每一个元素具有n个前驱和n个后继

 

---

 第三部分 --- 数组的顺序存储

1.数组是多维的，但是内存地址却是一维的，那么我们该怎样将多维映射到一维呢？

L是数组中一个元素所占据的内存空间 

 

 

 

 

上面那个n是总列数，i 刚好等于前面的行数，j 刚好等于前面的元素个数

三维数组是由多个二维数组堆叠而成的

a[ K ] [ i ] [ j ]

首先组成的是 i 行 j 列的二维数组，然后是由K个二维数组组成的三维数组

 a是数组首元素的地址

1.a还是首元素地址，然后不要忘了上面求的都是元素个数，到时候真的和首地址加的时候，不要忘了将元素个数乘以一个元素占的内存空间的大小

---

第四部分 --- 特殊矩阵的压缩存储

 

矩阵的压缩存储总结起来就两句话：1.为多个相同的非零元素只分配一个存储空间；2.对零元素不分配空间

1.对称矩阵：只存上三角或下三角（包含对角线），存储的元素个数：第一行2个，第二行2个，第三行3个.....第n行n个，总元素个数就等于：1+2+3+...+n = 等差数列求和 = (n*(n+1)) / 2

2.压缩存储对称矩阵时用的是一维数组来存储元素

1.三角矩阵也是 n * n 矩阵（行数和列数相等的方形矩阵）

2.三角矩阵是矩阵的上三角 / 下三角（不包含对角线）中的元素全部为常数C，然后另一个包含对角线的上三角 / 下三角中的元素都有具体值

3.注意上面这个K数组的下标是从1开始的，然后矩阵元素也是从1开始的，这两个条件结合起来就是上面这个计算结果了

1.对角矩阵中，非零的元素只存在于主对角线和处于主对角线附近附近且和主对角线平行的线上（线在矩阵中），其它的元素全都为0.

2.对角矩阵的带状区是以主对角线为对称轴左右对称的，所以带状区中的线总数为奇数（算上主对角线），每在主对角线一边加一条线时，主对角线的另一边也要对称的加一条线

我们要用一个二维数组存储右边那个我们压缩后的五对角矩阵

 1.三元组法中的 i 是元素的行数，j 是元素的列数 ，aij 就是元素的值

2.我们可以通过一个矩阵的所有非零三元组来唯一确定这个矩阵 

1.为了存储让我们的描述更加可靠的“总体信息”，我们专门在三元组顺序表中多存储一个元素，这个元素存储在下标为0的位置，其中 第一个为总行数，第二个为总列数，第三个为非零元素总个数

 

 三元组顺序表中如果不知道某个元素的行号的话，我们只能在表中从头开始查找这个元素

 

1.如果这个与这个非零元素的同行的下一个非零元素为0，则这个非零元素结点的 right 指针域置为空指针（down指针域同理，对应的是同列的下一个元素）

2.一个矩阵的十字链表中有多个头指针，其中每一行都有一个头指针对应，每一列也都有一个头指针对应，这些头指针都指向自己对应的行 / 列 中的第一个非零元素结点，如果头指针对应的行或列中没有非零元素结点的话，则将头指针置为空

---

第五部分 --- 广义表 

1.线性表中的元素只能是单一元素，而广义表中的元素即可以是单一元素也可以是一个新的广义表 

1.在一个广义表A中，其中某一个元素为广义表的话，我们就称这个元素为广义表A的子表，并且它的元素符号要用大写表示，只是单个元素而非广义表的话则称其为原子

2.广义表的表尾指的是广义表中除表头以外的所有元素组成的新的广义表的子表

1.最后一个广义表是递归广义表，倒数第二个广义表是共享广义表（所谓的共享广义表就是指这个广义表中的元素是我们之前定义的广义表）

1.处于同一深度的多个括号只会增加一个广义表的深度（最外层也就是广义表的第一层括号）

2.所谓的共享广义表就是直接拿已经定义好的广义表的表名作为自己的元素（此时这个元素表示的就是表名对应的广义表）

 

 

1.如果没有广义表没有表头或者表尾的话，则在求表头或表尾时返回一个空表 ---（）