学习笔记
数组
数组：按一定格式排列起来的具有相同类型的数据元素的集合。
数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组。
一维数组的逻辑结构：线性结构。定长的线性表。
声明格式：数据类型 变量名称【长度】
二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组
把每行看作一个元素组成的线性表，每个元素也是一个线性表。
把每列看作一个元素组成的线性表，每个元素也是一个线性表。
二维数组的逻辑结构：
非线性结构：每一个数据元素既在一个行表中，又在一个列表中线性结构，定长的线性表：该线性表的每个数据元素也是一个定长的线性表
声明格式：数据类型 变量名称【行数】【列数】
数组特点：结构固定——定义后，维数和维界不再改变
数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作
数组的顺序存储
数组特点：结构固定，维数和维界不变。
数组基本操作：初始化、销毁、取元素、修改元素值。一般不做插入和删除操作。
所以：一般都是采用顺序存储结构来表示数组。
注意：数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。
一维数组
例，int a[5]；每个元素占用4字节，假设a[0]存储在2000单元，a[3]地址是多少？
二维数组
二维数组有行列之分，因此，有两种顺序存储方式
以行序为主序（低下标优先）BASIC、COBOL和PASCAL以列序为主序（高下标优先）FORTRAN
存储单元是一维结构，而数组是个多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。
以行序为主序（C，PASCAL，JAVA，Basic）
比如现在有这么一个二维数组
按行序为主序的顺序存储方式
这里
设数组开始存储位置为 l o c ( 0.0 ) loc(0.0) loc(0.0)，存储每个元素需要 L L L 个存储单元数组元素 a [ i ] [ j ] a[i][j] a[i][j] 的存储位置是： l o c ( i , j ) = l o c ( 0.0 ) + ( n ∗ i + j ） ∗ L loc(i,j) = loc(0.0) +(n*i+j）*L loc(i,j)=loc(0.0)+(n∗i+j）∗L
以列序为主序（FORTRAN）
比如现在有这么一个二维数组
按列序为主序的顺序存储方式
广义表
广义表（又称列表Lists）是 n ≥ 0 n\ge 0 n≥0 个元素 a 0 ， a 1 … … a n a_0，a_1……a_n a0，a1……an 的有限序列，其中每一个 a i a_i ai或者是原子，或者是一个广义表。
广义表通常记作： L S = ( a 1 ， a 2 , … , a n ） LS=(a_1，a_2,…,a_n） LS=(a1，a2,…,an）
其中： L S LS LS 为表名， n n n 为表的长度，每一个 a i a_i ai 为表的元素。
习惯上，一般用大写字母表示广义表，小写字母表示原子。
表头：若 L S LS LS 非空，则其第一个元素 a 1 a_1 a1 就是表头。
记作 h e a d ( L S ) = a 1 head(LS)=a_1 head(LS)=a1
注：表头可以是原子，也可以是子表。
表尾除表头之外的其它元素组成的表。
记作 t a i l ( L S ) = ( a 2 , … , a n ） tail(LS)=(a_2,…,a_n） tail(LS)=(a2,…,an）
注：表尾不是最后一个元素，而是一个子表。
例子：
广义表的性质
广义表的特性：有次序性，有长度，有深度，可共享，可递归。
（1）广义表中的数据元素有相对次序；一个直接前驱和一个直接后驱
（2）广义表的长度定义为最外层所包含元素的个数；如： C = ( a , ( b , d ) C=(a,(b,d) C=(a,(b,d) 是长度为2的广义表。
（3）广义表的深度本质上就是广义表表达式中括号的最大嵌套层数。例如 A = ( b , d ) A=(b,d) A=(b,d) 的深度为1， B = ( A , d ) B=(A,d) B=(A,d) 的深度为2， C = ( f , B , h ) C=(f,B,h) C=(f,B,h) 的深度为3。
注意：“原子”的深度为0；“空表”的深度为1。
（4）广义表可以为其他广义表共享；如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用， B = ( A ) B=(A) B=(A) 。
（5）广义表可以是一个递归的表。如： F = ( a ， F ) = ( a , ( a , （ a . … ) ) F=(a，F)=(a,(a,（a.…)) F=(a，F)=(a,(a,（a.…))
注意：递归表的深度是无穷值，长度是有限值。
（6）广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。
广义表与线性表的区别？
广义表可以看成是线性表的推广，线性表是广义表的特例。
广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。
当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。
另外，树和有向图也可以用广义表来表示。
由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。
广义表的存储结构
由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。
通常采用链表存储方式。
引用数法广义表：每一个表结点由三个域组成，结点三分三类：
