数组和广义表

由于数组可以是多维的，而顺序存储结构是一维的，因此数组中数据的存储要制定一个先后次序。通常，数组中数据的存储有两种先后存储方式：

以列序为主（先列后行）：按照行号从小到大的顺序，依次存储每一列的元素
以行序为主（先行后序）：按照列号从小到大的顺序，依次存储每一行的元素。

多维数组查找指定元素

当需要在顺序存储的多维数组中查找某个指定元素时，需知道以下信息：

多维数组的存储方式；
多维数组在内存中存放的起始地址；
该指定元素在原多维数组的坐标（比如说，二维数组中是通过行标和列标来表明数据元素的具体位置的）；
数组中数组的具体类型，即数组中单个数据元素所占内存的大小，通常用字母 L 表示；

根据存储方式的不同，查找目标元素的方式也不同。如果二维数组采用以行序为主的方式，则在二维数组 anm 中查找 aij 存放位置的公式为：

LOC(i,j) = LOC(0,0) + (i*m + j) * L;

其中，LOC(i,j) 为 aij 在内存中的地址，LOC(0,0) 为二维数组在内存中存放的起始位置（也就是 a00 的位置）。

而如果采用以列存储的方式，在 anm 中查找 aij 的方式为：

LOC(i,j) = LOC(0,0) + (i*n + j) * L;

矩阵（稀疏矩阵）压缩存储（3种方式）

主要分为以下两类的特殊矩阵：，

含有大量相同数据元素的矩阵，比如对称矩阵；

含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；

针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：

存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式：

最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。

上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

压缩存储稀疏矩阵的方法是：只存储矩阵中的非 0 元素，与前面的存储方法不同，稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。

稀疏矩阵的压缩存储，数据结构提供有 3 种具体实现方式：

三元组顺序表；行逻辑链接的顺序表；十字链表；

三元组（即由 3 部分数据组成的集合），组中数据分别表示（行标，列标，元素值）。

C 语言中，三元组需要用结构体实现，如下所示：

//三元组结构体
typedef struct {
    int i,j;//行标i，列标j
    int data;//元素值
}triple;

由于稀疏矩阵中非 0 元素有多个，因此需要建立 triple 数组存储各个元素的三元组。除此之外，考虑到还要存储矩阵的总行数和总列数，因此可以采用以下结构表示整个稀疏矩阵：

#define number 20
//矩阵的结构表示
typedef struct {
    triple data[number];//存储该矩阵中所有非0元素的三元组
    int n,m,num;//n和m分别记录矩阵的行数和列数，num记录矩阵中所有的非0元素的个数
}TSMatrix;

可以看到，TSMatrix 是一个结构体，其包含一个三元组数组，以及用于存储矩阵总行数、总列数和非 0 元素个数的变量。

行逻辑链接的顺序表和三元组顺序表的实现过程类似，它们存储矩阵的过程完全相同，都是将矩阵中非 0 元素的三元组（行标、列标和元素值）存储在一维数组中。但为了提高提取数据的效率，前者在存储矩阵时比后者多使用了一个数组，专门记录矩阵中每行第一个非 0 元素在一维数组中的位置。

用十字链表存储稀疏矩阵，该存储方式采用的是 “链表+数组” 结构，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组（rhead），所有列链表的表头存储到另一个数组（chead）中。

链表中节点的 C 语言代码表示应为：

typedef struct OLNode{
    int i,j;//元素的行标和列标
    int data;//元素的值
    struct OLNode * right,*down;//两个指针域
}OLNode;

矩阵转置的实现过程需完成以下 3 步：

将矩阵的行数和列数互换；
将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；
以 j 列为序，重新排列三元组表中存储各三元组的先后顺序；
此 3 步中，前两步比较简单，关键在于最后一步的实现。

矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组，互换行标和列标的值，并按次序存储到一个新三元组表中，。

广义表

广义表，又称列表，也是一种线性存储结构。

同数组类似，广义表中既可以存储不可再分的元素，也可以存储广义表，记作：
LS = (a1,a2,…,an)

其中，LS 代表广义表的名称，an 表示广义表存储的数据。广义表中每个 ai 既可以代表单个元素，也可以代表另一个广义表。

原子和子表

通常，广义表中存储的单个元素称为 “原子”，而存储的广义表称为 “子表”。

例如创建一个广义表 LS = {1,{1,2,3}} ，我们可以这样解释此广义表的构成：广义表 LS 存储了一个原子 1 和子表 {1,2,3} 。

以下是广义表存储数据的一些常用形式：

A = ()：A 表示一个广义表，只不过表是空的。
B = (e)：广义表 B 中只有一个原子 e。
C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

注意，A = () 和 A = (()) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。

广义表的表头和表尾

当广义表不是空表时，称第一个数据（原子或子表）为”表头”，剩下的数据构成的新广义表为”表尾”。
强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

例如在广义表中 LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。

再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用 {} 表示

一般来说，广义表具有如下重要的特性：

（1）广义表中的数据元素有相对次序

（2）广义表的长度定义为最外层包含元素个数

（3）广义表的深度定义为所含括弧的重数。其中原子的深度为0，空表的深度为1

（4）广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表

（5）广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值

（6）任何一个非空广义表GL均可分解为表头head(GL) = a1和表尾tail(GL) = ( a2,…,an) 两部分。

广义表是一种不定规模的数据结构，很难为之分配具体的空间，因此创建的方法采用动态的链式方法，动态的创建空间。

tag	atom/node	link

对于每一个结点而言由如上三大部分组成，其中Tag域为标志字段，其只有两个参数，0或者1（Tag域使用int类型，在某些情况下因为只需要简单判断也可以使用更短的类型，如bool）；Atom/Node域的内容由tag标志决定，当Tag为0时表示该节点是原子结点（即存放原子数据），当Tag为1时表示该节点为指向下一个广义表的指针（即表结点），Link域存放与本元素同一层的下一个元素所在的结点地址，当本元素时所在层的最后一个元素时，Link域为NULL；

链式法设计：

#define AtomType int
typedef enum{ATOM,LIST}ElemTag; //ATOM = 0：原子；LIST = 1:子表 
/*结点设计*/
typedef struct GLNode{
    ElemTag tag; //枚举类型的标志域，只能取定义了的枚举值
    //或者直接写数字 int tag;//标志域
    union{   
        //union联合体，下面两部分只能取其一；要么取AtomType;要么取结构体ptr,ptr包括两个指针hp,tp 
        AtomType atom;
        struct{
            struct GLNode *hp,*tp;
        }ptr;
    }; 
}*GList; //定义广义表类型，GList为指针

下面是子表法设计：

/*线性表存储之扩展线性表 = 子表法*/ 
typedef struct GLNode{
    ElemTag tag;
    //或者直接写数字 int tag;//标志域
    union{
        AtomType atom;
        struct GLNode *hp;   //对于列表，hp指向本列表内部第一个元素，而tp是指向本层次上的下一个元素 
    };                        
    struct GLNode *tp;
} *GList;

对于任意一个非空广义表来说，都是由两部分组成：表头和表尾。反之，只要确定的一个广义表的表头和表尾，那么这个广义表就可以唯一确定下来。

复制一个广义表，也是不断的复制表头和表尾的过程。如果表头或者表尾同样是一个广义表，依旧复制其表头和表尾。

所以，复制广义表的过程，其实就是不断的递归，复制广义表中表头和表尾的过程。

递归的出口有两个：

如果当前遍历的数据元素为空表，则直接返回空表。
如果当前遍历的数据元素为该表的一个原子，那么直接复制，返回即可。

在实现复制广义表的过程中，实现函数为：

void copyGlist(Glist C, Glist *T);

其中，Glist *T，等同于: struct GLNode* *T，此为二级指针，不是一级指针。在主函数中，调用此函数时，传入的是指针 T 的地址，而不是 T 。

这里使用的是地址传递，而不是值传递。如果在这里使用值传递，会导致广义表 T 丢失结点，复制失败。