邻接多重表和十字链表

邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构虽然邻接表是无向图的一种很有效的存储结构，在邻接表中容易求得顶点和边的各种信息但是，在邻接表中每一条边(vi , vj)有两个结点，分别在第i个和第j个链表中，这给某些图的操作带来不便[例如]，在某些图的应用问题中需要对边进行某种操作，如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜 邻接多重表的结构和十字链表类似在邻接多重表中，每一条边用一个结点表示，它由如下所示的六个域组成：其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点 jvex的边，info为指向和边相关的各种信息的指针域每一个顶点也用一个结点表示，它由如下所示的两个域组成：其中，data域存储和该顶点相关的信息，firstedge域指示第一条依附于该顶点的边[例如]，图7.12所示为无向图G2的邻接多重表十字链表十字链表     对稀疏矩阵实施某些操作（例如A=A+B），可能会引起矩阵中非零元素的个数和位置的变化，如果用顺序方式（三元组表）来存储稀疏矩阵的非零元素，那么这些变化将引起与矩阵A对应的三元组表中大量结点的移动，效率较低，而采用链接存储结构则会避免这些问题.     用链接存储实现稀疏矩阵有几种方式，我们介绍其中的一种：十字链表. 在稀疏矩阵的十字链表中，矩阵的每一行都设置为由一个表头结点引导的循环链表（简称为行链表），矩阵的每一列也都设置为由一个表头结点引导的循环链表（简称为列链表）.    矩阵的元素结构如下：    其中LEFT，UP，ROW，COL，VAL分别表示该元素的左邻非零元素、上邻非零元素、所在的行、所在的列和它的值。

    下图给出一个稀疏矩阵和它的十字链表：图5.2 正交链表    这里，每一行和每一列都有一个表头结点：     BASEROW[i]，i=1，2，…，m（m行）     BASECOL[j]， j=1，2，…，n（n列）    它们有如下特点：     -1 = COL（Loc（BASEROW[i]））< 0     -1 = ROW（Loc（BASECOL[j]））< 0     因为行或列都是一个循环链表，所以行表头BASEROW[i]中的LEFT指针循环地链接到该行最右边的非零元素， 列表头BASECOL[j]中的UP指针循环地链接到该列最下边的非零元素.下面，我们将用一个例子来说明十字链表的使用. 在解线性方程组、求矩阵的逆以及求解线性规划等实际问题中，都需要施行一种“主步骤”操作，即如下的矩阵变换:    处于主行主列的元素a被称为主元素，主元素必须是非零元素 ：（5.1）所示的矩阵A，如以A[1][0]为主元素，即第1行为主行，第0列为主列，经主步骤操作后，就得到如下稀疏矩阵:    读者或许已经注意到，变换前主行别列上元素b若为0，变换后该列的元素不变；同样，若别行主列元素c为0，变换后该行的元素不变.     对于别行别列元素，事实上，若设某个主行非零元素c所在的列是j，某个主列非零元素b所在的行是i，那么整个矩阵中，只有这些A[i][j]需要处理.     (1)变换前：A[i][j]=0;变换后：在十字链表中合适的位置插入一个新结点，该结点行号为i，列号为j，值为-b*c/a；   (2)变换前：d=A[i][j]≠0；变换后：考察d-b*c/a=0是否成立？若不成立，则将该结点的value值更新为d-b*c/a；若成立，则将该结点从十字链表中删除.     不难给出如下的主步骤操作算法. 该算法的控制过程是：首先处理主行，然后从下向上逐个处理别行.。