‘壹’ 图的五种存储结构
图的邻接矩阵（Adjacency Matrix）： 图的邻接矩阵用两个数组来表示图。一个一维数组存储图中顶点信息，另一个二维数组（一般称之为邻接矩阵）来存储图中的边或者弧的信息。从邻接矩阵中我们自然知道一个顶点的度（对于无向图）或者有向图中一个顶点的入度出度信息。
假设图G有n个顶点，则邻接矩阵是一个n*n的方阵。
1.对于如果图上的每条边不带权值来说，那么我们就用真（一般为1）和假（一般为0）来表示一个顶点到另一个顶点存不存在边。下面是一个图的邻接矩阵的定义：
邻接矩阵法实现带权值的无向图的创建如下：
按照如图输入各边（不重复）
测试程序如下：
结果可得该矩阵，证明创建树成功。 假设n个顶点e条边的创建，createGraph算法的时间复杂度为O（n+n*n+e）。如果需要创建一个有向图，那么和上面一样一个一个录入边下标和权值。
邻接矩阵这种存储结构的优缺点： 缺点是对于边数相对顶点较少的稀疏图来说会存在极大的空间浪费。假设有n个顶点,优点是对于有向完全图和无向完全图来说邻接矩阵是一种不错的存储结构，浪费的话也只浪费了n个顶点的容量。
在树的存储结构一节中我们提到对于孩子表示法的第三种：用一段连续的存储单元（数组）存储树中的所有结点，利用一个单链表来存储数组中每个结点的孩子的信息。对于图的存储结构来说，我们也可以利用这种方法实现图的存储
邻接表(Adjacency List): 这种数组与链表相结合的存储方法叫做邻接表。1.为什么不也用单链表存储图的结点信息呢？原因就是数组这种顺序存储结构读取结点信息速率快。对于顶点数组中，每个数据元素还需要存储一个指向第一个邻接顶点的指针，这样才可以查找边的信息2.图中每个顶点Vi(i > 0)的所有邻接点构成一个线性表 （在无向图中这个线性表称为Vi的边表，有向图中称为顶点作为弧尾的出边表） ，由于邻接点的不确定性，所以用链表存储，有多少个邻接点就malloc一个空间存储邻接点，这样更不会造成空间的浪费（与邻接矩阵相比来说）。3.对于邻接表中的某个顶点来说，用户关心的是这个顶点的邻接点，完全可以遍历用单链表设计成的边表或者出边表得到，所以没必要设计成双链表。
邻接表的存储结构：
假设现在有一无向图G，如下图：
从邻接表结构中，知道一个顶点的度或者判断两个顶点之间是否存在边或者求一个顶点的所有邻接顶点是很容易的。
假设现在有一有向图G，如下图：
无向图的邻接表创建示例如下：
假设在上图（无向图）中的V0V1V2V3顶点值为ABCD，则依据下面测试程序可得结果：
邻接表的优缺点： 优点是：邻接表存储图，既能够知道一个顶点的度和顶点的邻接结点的信息，并且更不会造成空间的浪费。缺点是邻接表存储有向图时，如果关心的是顶点的出度问题自然用邻接表结构，但是想了解入度需要遍历图才知道（需要考虑逆邻接表）。
十字链表(Orthogonal List) ：有向图的一种存储方法，它把邻接表和逆邻接表结合起来，因此在十字链表结构中可以知道一个顶点的入度和出度情况。
重新定义顶点表的结点如下图：
现在有一有向图如下图：
则它的存储结构示意图为：
其定义如下：
十字链表是用来存储有向图的，这样可以看出一个顶点的出入度信息。对于无向图来说完全没必要用十字链表来存储。
在无向图中，因为我们关注的是顶点的信息，在考虑节约空间的情况下我们利用邻接表来存储无向图。但是如果我们关注的是边的信息，例如需要删除某条边对于邻接表来说是挺繁琐的。它需要操作两个单链表删除两个结点。因此我们仿照十字链表的方式对边表结点结构重新定义如下图：
它的邻接多重表结构为：
多重邻接表的优点：对于边的操作相比于邻接表来说更加方便。比如说我们现在需要删除(V0,V2)这条边，只需将69步骤中的指针改为nullptr即可。
边集数组(edgeset array)： 边集数组是由两个数组组成，一个存储顶点信息，另一个存储边的信息，这个边数组中的每个数据元素由起点下标，终点下标，和权组成（如果边上含有权值的话）。
边数组结构如下图：
边集数组实现图的存储的优缺点：优点是对于边的操作方便快捷，操作的只是数组元素。比如说删除某条边，只需要删除一个数组元素。缺点是：对于图的顶点信息，我们只有遍历整个边数组才知道，这个费时。因此对于关注边的操作来说，边集数组更加方便。
‘贰’ 数据结构中稀疏矩阵压缩存储十字链表存储结构，如果是一个N*N的矩阵，需多少表头，辅导书说N+1个，为什么
相同的行列共用一个表头结点，各个表头结点再链接成链表，这个链表上再用一个表头结点并存储表示行和列的数量，
N*N矩阵本身n个，再有一个表头，不就是N+1个了
‘叁’ 多维数组-矩阵的压缩存储- 稀疏矩阵（一）
稀疏矩阵
设矩阵A mn 中有s个非零元素 若s远远小于矩阵元素的总数(即s< <m×n)，则称a为稀疏矩阵。 p=""> </m×n)，则称a为稀疏矩阵。>
1、稀疏矩阵的压缩存储
为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零
元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，a ij )，并由此三元组惟一确定。
稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法【参见参考书目】。
2、三元组表
将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序
存储结构称为三元组表。
注意：
以下的讨论中，均假定三元组是按行优先顺序排列的。
【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)
(1)三元组表的类型说明
为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。.WINGwIT.其类型描述为：
#define MaxSize 10000 //由用户定义
typedef int DataType; //由用户定义
typedef struct { //三元组
int i，j;//非零元的行、列号
DataType v; //非零元的值
}TriTupleNode;
typedef struct{ //三元组表
TriTupleNode data[MaxSize]; //三元组表空间
int m,n，t; //矩阵的行数、列数及非零元个数
}TriTupleTable;
(2) 压缩存储结构上矩阵的转置运算
一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
A[i][j]=B[j][i]，0≤i <m，0≤j<n， p=""> </m，0≤j<n，>
即A的行是B的列，A的列是B的行。
【例】下图中的B和上图中的A互为转置矩阵。
①三元组表表示的矩阵转置的思想方法
第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
第二步：当三元组表非空(A矩阵的非零元不为0)时，根据A矩阵三元组表的结点空间data(以下简称为三元组表)，将A的三
元组表a->data置换为B的三元组表b->data。
②三元组表的转置
方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有
列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。具体实现参见
【 动画演示 】
③具体算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩阵A、B的三元组表表示，求A转置为B
int p，q，col;
b->m=a->n; b->n=a->m; //A和B的行列总数互换
b->t=a->t; //非零元总数
if(b->t<=0)
Error("A=0"); //A中无非零元，退出
q=0;
for(col=0;coln;col++) //对A的每一列
for(p=0;pt;p++) //扫描A的三元组表
if(a->data[p].j==col){ //找列号为col的三元组
b->data[q).i=a->data[p].j;
b->data[q].j=a->data[p].i;
b->data[q].v=a->data[p].v;
q++;
}
} //TransMatrix
④算法分析
该算法的时间主要耗费在col和p的二重循环上：
若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。
通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。
由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。
lishixin/Article/program/sjjg/201311/23897
‘肆’ 设有一稀疏图G，则G采用什么存储较省空间
G采用邻接表存储较省空间。
邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
(4)树的存储结构稀疏扩展阅读：
表示法
n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于i的邻接表中，另一次在关于j的邻接表中)。
对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
‘伍’ 数据结构，树的常用存储方式
存入文本文件，每行：孩子节点-父节点。
这样也方便用Hadoop进行处理。