~~~~     有需求才有供应，很多东西，都是为了解决实际问题才出现的，项目中出现了很多稀疏矩阵，而且需要对他们进行运算，而十字链表就是为了解决稀疏矩阵而出现的一种数据结构。

稀疏矩阵

     ~~~~     稀疏矩阵（英语：sparse matrix），在数值分析中，是其元素大部分为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密的，通常这个系数被认为是5%。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。
     ~~~~     在使用计算机存储和操作稀疏矩阵时，经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是，由于过大的尺寸，标准的算法经常无法操作这些稀疏矩阵。

三元组

     ~~~~     对于矩阵，我们第一想法就是使用二维数组来存储，但是稀疏矩阵的元素大部分都是零，而且稀疏矩阵的尺寸一般都比较大，这个时候我们如果直接使用二维数组，会浪费很多的空间，所有通常我们需要对稀疏矩阵进行压缩，三元组就是一种稀疏矩阵压缩保存的方法。
     ~~~~     三元组是指形如$((x,y),z)$的集合（这就是说，三元组是这样的偶，其第一个射影亦是一个偶），常简记为$(x,y,z)$。
     ~~~~     三元组是计算机专业的一门公共基础课程——数据结构里的概念。主要是用来存储稀疏矩阵的一种压缩方式，也叫三元组表。
     ~~~~     三元组有不同的实现方法，假设以顺序表存储结构来表示三元组，称为三元组顺序表。
结构如下

#defube NAXSIZE 2500
typedef struct{
    int i, j; //该非零元的行下标和列下标
    ElemType e;
}Triple;
typedef struct{
    Triple data[MAXSIZE + 1];//非零三元数组标，data[0]没有使用
    int mu, nu, tu;//矩阵的行数，列数，非零元个数
}TSMatrix;

     ~~~~     注意，data域中表示非零元的三元组是以行序为主序顺序排列的，如果不排序，你会发现你操作和访问数据时，时间基本都花在查询数据上了。对于三元组，我们可以进行一些运算，都是很容易实现的，比如转置，相加，相减。
     ~~~~     三元组相比十字链表的缺点（暂时只能想到这些）

• 1、增加或减少矩阵中的非零元素，都需要进行数据的移动
• 2、大小固定，非零数据很少时，会浪费很多的空间，过多时无法保存
• 3、查找元素比较慢（时间复杂度）
• 4、矩阵的运算数据较慢（时间复杂度）

十字链表

     ~~~~     十字链表（英语：Orthogonal linked list）是计算机科学中的一种高级数据结构，在Linux内核中应用广泛。具体说，一个二维十字链表是链表的元素同时链接左右水平邻结点与上下垂直邻结点。
     ~~~~     当稀疏矩阵的非零元个数和位置在操作过程中变化较大时，就不宜使用顺序表存储结构的三元组来保存稀疏矩阵；这个时候我们采用的时十字链表。
十字链表节点结构

typedef struct OLNode {    
     int  LineNumber, ColumneNumber;          //行号与列号     
     ElemType value;        //值     
     struct OLNode *right, *down;  //同行、同列下一个元素的指针     
}OLNode, *OList;
typedef struct{
    OList *rhead, *chead;    //行和列链表头指针向量基址
    int mu,nu,tu;            //稀疏矩阵的行数，列数和非零元个数
}CrossList;

     ~~~~     每一个非零元可用一个含5个域的节点表示，其中i，j和e这3个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行中下一个非零元，向下域down用来链接同一列下一个非零元，同一行的非零元通过right链接形成一个线性链表，同一列的非零元通过down链接形成一个线性表，每个非零元既是某个行链表中的节点，也是某一个列链表中的节点，整个矩阵构成了一个十字交叉的链表，而样的链表存储结构称为十字链表。

附上十字链表实现（百度抄的）

#include <malloc.h>
#include <stdio.h>
/*十字链表的结构类型定义如下：*/
typedef struct OLNode
{
    int row,col; /*非零元素的行和列下标*/
    int value;
    struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
    struct OLNode *down;
} OLNode, *OLink;
typedef struct
{
    OLink *row_head; /*行、列链表的头指针向量*/
    OLink *col_head;
    int m,n,len; /*稀疏矩阵的行数、列数、非零元素的个数*/
} CrossList;
/*建立稀疏矩阵的十字链表的算法*/
void CreateCrossList(CrossList *M)
{
    int m, n, t, i, j, e;
    OLNode* p;
    OLNode* q;
    /*采用十字链表存储结构，创建稀疏矩阵M*/
     
scanf("%d%d%d", &m,&n,&t); /*输入M的行数,列数和非零元素的个数*/
    M->m=m;
    M->n=n;
    M->len=t;
    if(!(M->row_head=(OLink *)malloc(m*sizeof(OLink))))
        exit(OVERFLOW);
    if(!(M->col_head=(OLink * )malloc(n*sizeof(OLink))))
        exit(OVERFLOW);
    /*初始化行、列，头指针指向量，各行、列链表为空的链表*/
    for(int h=0; h<m+1; h++)
    {
        M->row_head[h] = NULL;
    }
    for(int t=0; t<n+1; t++)
    {
        M->col_head[t] = NULL;
    }
    for(
scanf("%d%d%d", &i,&j,&e); e!=0; scanf("%d%d%d", &i,&j,&e))
    {
        if(!(p=(OLNode *)malloc(sizeof(OLNode))))
            exit(
OVERFLOW);
        p->row=i;
        p->col=j;
        p->value=e; /*生成结点*/
        if(M->row_head[i]==NULL)
            M->row_head[i]=p;
        p->right=NULL;
        else
        {
            /*寻找行表中的插入位置*/
            for(q=M->row_head[i]; q->right&&q->right->col<j; q=q->right); /*空循环体*/
            p->right=q->right;
            q->right=p; /*完成插入*/
        }
        if(M->col_head[j]==NULL)
            M->col_head[j]=p;
        p->down=NULL;
        else
        {
            /*寻找列表中的插入位置*/
            for(q=M->col_head[j]; q->down&&q->down->row<i; q=q->down); /*空循环体*/
            p->down=q->down;
            q->down=p; /*完成插入*/
        }
    }
}

注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明

目录

前言：

一、关于十字链表

1.特殊情况下邻接表的局限

2.十字链表的结构与特点

二、十字链表的代码实现

1.基本属性

2.出边链接

3.入边链接

4.打印操作

三、数据测试

总结

前言：

最近到毕业季了，各种毕业需要处理的东西太多了，所以昨天时间又被耽误了没法继续更新文章，今天略得空闲，便更新下今日之内容。

一、关于十字链表

1.特殊情况下邻接表的局限

         下图是我们昨日提到的邻接表对于图的表示，这样的邻接表的链表部分连接的基础是以结点的出边为依据的，又名出边邻接表。在已知一个结点后我们通过邻接表的链表部分实现对于出边的访问，这个复杂度视具体的结点边的个数而定。但是在计算入边个数时，这样针对出边的邻接表似乎就显得有些笨拙了。我们需要遍历全部顺序表结构的顶点集然后逐步查看邻边，总的复杂度是确定的\(O(|V|+|E|)\)。但是由于现实问题中，大多数利用有向图时我们都讨论由出边引导的通向性问题；而无向图因为边的对偶特性，没有出边入边之分，所以往往不会担忧这种问题。

        但是如果说需要优化这种担忧，我们可以采用以入边为构造基础的入边邻接表。当然这样的方案有点因为芝麻丢了西瓜的味道，因为只考虑入边专门构造个数据结构而丢弃出边引导这种更为普遍的结构的方案有些冗余。因此，一种兼顾出边和入边的数据结构——十字链表出现了。

2.十字链表的结构与特点

        今天描述这个数据结构关系时我改变昨日的那种存理论与代码分割的思路，今天我就直接按照今天代码会采用的结构来说明这个结构。在十字链表中，仿照邻接表，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点，但是我们代码为方便我们统一采用一种统一结构：

       这里的弧具有4个域，也是十字链表至少需要的参数域数目，其中尾域（row）和头域（column）分别表示弧的弧头与弧尾，但因为在图中其直观的指针指向具有方向性，所以这里以row / column命名从而体现一种直观性。链域nextIn指向弧头相同的下一条弧，简单来说就是指向我们的入边，并且多个入边相连构成入边链表。链域nextOut指向弧尾相同的下一条弧，简单来说就是指向我们的出边，并且多个出边相连构成出边链表。

        要理解十字链表这部分不能只靠文字，以图辅助，你就能恍然大悟：

         只要去掉链域nextIn，可以发现十字链表就变成了一个完全的出边邻接表（这个重要思想）而补上入边的指针后你就会发现：其实其实十字链表就是在出边邻接表的基础上给每个结点扩充了入边的链域，你可以在观看某个指针域的时候屏蔽其余指针域，这样全体的构造就变得清晰了。画图时，因为出边邻接表已经占据的横向的指针，所以我们在图示的时候入边指针域是纵向示意的，这就构成了指针之间纵横交错的感觉，可能这就是十字链表命名的来源。

        同时，因为边结点兼顾出边与入边的两重功能，自然的，结点自身所寄予的数值域空间也不能只是出边所代表的弧尾节点，还需要额外记录弧头以方便入边。

        通过十字链表，结点的入边和出边的访问就比较容易实现了，在特定情况采用十字链表能优化特定的问题。

二、十字链表的代码实现

1.基本属性

        基本属性与邻接表类似，只需要额外补充一些新的数据域即可。

    /**
	 * An inner class for adjacent node.
	 */
	class OrthogonalNode {
		/**
		 * The row index.
		 */
		int row;

		/**
		 * The column index.
		 */
		int column;

		/**
		 * The next out node.
		 */
		OrthogonalNode nextOut;

		/**
		 * The next in node.
		 */
		OrthogonalNode nextIn;

		/**
		 *********************
		 * The first constructor.
		 * 
		 * @param paraRow    The row.
		 * @param paraColumn The column.
		 *********************
		 */
		public OrthogonalNode(int paraRow, int paraColumn) {
			row = paraRow;
			column = paraColumn;
			nextOut = null;
			nextIn = null;
		}// Of OrthogonalNode
	}// Of class OrthogonalNode

	/**
	 * The number of nodes. This member variable may be redundant since it is always
	 * equal to headers.length.
	 */
	int numNodes;

	/**
	 * The headers for each row.
	 */
	OrthogonalNode[] headers;

2.出边链接

         之前在文中提到了十字链表的一个特性：去掉链域nextIn，可以发现十字链表就变成了一个完全的出边邻接表。那么我们可以在构造的前半部分完全无视nextIn域，模仿昨天的邻接表构造方法完成这部分：        

    numNodes = paraMatrix.length;

	// Step 1. Initialize. The data in the headers are not meaningful.
	OrthogonalNode tempPreviousNode, tempNode;
	headers = new OrthogonalNode[numNodes];

	// Step 2. Link to its out nodes.
	for (int i = 0; i < numNodes; i++) {
		headers[i] = new OrthogonalNode(i, -1);
		tempPreviousNode = headers[i];
		for (int j = 0; j < numNodes; j++) {
			if (paraMatrix[i][j] == 0) {
				continue;
			} // Of if

			// Create a new node.
			tempNode = new OrthogonalNode(i, j);

			// Link.
			tempPreviousNode.nextOut = tempNode;
			tempPreviousNode = tempNode;
		} // Of for j
	} // Of for i

        初始化不再赘述， 初始tempPreviousNode变量作为每条入边链的链表头（tempPreviousNode = headers[i];），同时，在遍历中不断迭代，持续作为尾节点的身份出现，以方便每次读取邻接矩阵而生成的新结点能插入到尾节点后以扩展链表。 注意结点创建初始化是以基础结点（也就基于哪个顶点来讨论邻边）为弧头，得到的邻边为弧尾，因此有代码：tempNode = new OrthogonalNode(i, j); 这里记录的弧尾值是后续定义入边的关键。

3.入边链接

        入边连接是十字链表构造的一个麻烦点。因为记录入边是个连续的过程，它也是一个链表，所以我们需要有个时刻记录某类编号的上次入边的结点。简单来说，构造了编号为i顶点的入边后，下次再发现了顶点i的入边后我们需要在上次的入边结点后方进一步插入，因此需要记录对应i顶点的上一次连接的入边结点。而i是一系列值，因此可以设置一个十字链表数据项数组tempColumnNodes，初始将其按照Header赋值（最开始无任何入边连接）。

	// Step 3. Link to its in nodes. This step is harder.
	OrthogonalNode[] tempColumnNodes = new OrthogonalNode[numNodes];
	for (int i = 0; i < numNodes; i++) {
		tempColumnNodes[i] = headers[i];
	} // Of for i
	
	for (int i = 0; i < numNodes; i++) {
		tempNode = headers[i].nextOut;
		while (tempNode != null) {
			tempColumnNodes[tempNode.column].nextIn = tempNode;
			tempColumnNodes[tempNode.column] = tempNode;

			tempNode = tempNode.nextOut;
		} // Of while
	} // Of for i

        操作前，每个边结点都被一个指针所指（被兄弟边或者弧头顶点所指），并且都指出一个指针（指向兄弟边）

         但是要构成一个十字链表还差一个指向别人和别人指向自己的指针。为了同时解决这个问题，我们按照顺序对于每个边结点进行访问，并且在每次访问时，根据边的弧尾顶点值，查询到需要统计入边的结点。就那上面这次针对顶点\(v_0\)的出边遍历，我们就能在访问这两个兄弟边同时通过查询column（弧尾顶点值）域的值得到1与2，这里的含义就是说明\(v_1\)顶点与\(v_2\)顶点的入边需要讨论。

        怎么讨论呢，很简单，比如设上图中出边链的最后那个边结点为\(\alpha \)；通过查询\(\alpha \)的column（弧尾顶点值）值得到了2，这个2代表了这个弧的弧尾为\(v_2\)，故去讨论\(v_2\)的入边。这时的操作是取出\(v_2\)的入边链表的尾节点，并在这个尾节点插入边结点为\(\alpha \)，并且设置边结点为\(\alpha \)为新的尾节点。这样有什么好处呢，首先，下一次再有人发现要讨论\(v_2\)的入边时就能直接查询到\(\alpha \)这个新的尾节点并且继续尾插，从而形成一个入边链表的维护；其次，下一次再\(v_2\)讨论便需要去尾插\(\alpha \)，这样就顺利补充了\(\alpha \)边结点的额外一个被指向指针和指出指针，解决了我们的担忧。

        代码中，通过tempColumnNodes[tempNode.column]查询到顶点编号为tempNode.column的最近一次链入入边链表的尾部，从而链入，链入后由尾插原则，自身变成新尾部。

4.打印操作

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "Out arcs: ";

		OrthogonalNode tempNode;
		for (int i = 0; i < numNodes; i++) {
			tempNode = headers[i].nextOut;

			while (tempNode != null) {
				resultString += " (" + tempNode.row + ", " + tempNode.column + ")";
				tempNode = tempNode.nextOut;
			} // Of while
			resultString += "\r\n";
		} // Of for i

		resultString += "\r\nIn arcs: ";

		for (int i = 0; i < numNodes; i++) {
			tempNode = headers[i].nextIn;

			while (tempNode != null) {
				resultString += " (" + tempNode.row + ", " + tempNode.column + ")";
				tempNode = tempNode.nextIn;
			} // Of while
			resultString += "\r\n";
		} // Of for i

		return resultString;
	}// Of toString

         打印操作中分别打印了每个结点的入边链和出边链。

三、数据测试

        测试代码如下：

    /**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		int[][] tempMatrix = { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 1, 0 } };
		OrthogonalList tempList = new OrthogonalList(tempMatrix);
		System.out.println("The data are:\r\n" + tempList);
	}// Of main

        图结构如图：

        测试结果如下：

总结

        十字链表这种结构我接触的确实不算很多，准确来说，确乎是没有用过。第一次接触是在本科的数据结构的课程上。要问我对于这种结构的看法，就像是对于邻接表两种方案（入边/出边）的兼容版本。相比于一次分别创建个出边邻接表和入边邻接表，其灵活利用结点关系实现了数据的复用，避免了冗余。这个方案对于边信息比庞大的图同时又要同时考虑出边和入边的问题具有比较好的对策性。

        对于一个算法问题的数据结构改进不一定说选择一个最好的就好了，多结构组合才是更常见的方案。或者像今天所了解的十字链表这样，通过邻接表针对部分问题的局限为思路出发点，对结构不足进行改造而设计出更有针对性的结构。我随便举个组合，比如通过哈希表、链表、顺序表设计出一种复合的兼容\(O(1)\)的查询与\(O(1)\)插入删除线性结构等等。

        总之要认识到数据结构并不是独立的，他们就像积木，使用他们的过程就像搭积木，合理搭建出针对自己问题最好的结构才是好的数据结构。

十字链表

1. 图文解析

在无向图中，两个顶点之间的连接我们称之为边；

而在有向图中，两个顶点之间具有方向的连接称之为弧（英文：Arc）
如下图中弧（A->B）的权值=10，其中A为该弧的头顶点，B为该弧的尾顶点

也可以理解为在无向图中每条边都存在两条弧

十字链表的结构和邻接表的结构较为相似，同样采用了顺序表与链表结构的结合，但在十字链表中存在两个链表，分别用于表示相同头顶点和尾顶点的弧链表。

边结点结构图

顶点结点结构图

图与十字链表

1、在十字链表中，如果仅看相同头顶点的弧链表，其结构和邻接表相同，采用头插法插入弧结点
2、对于相同尾结点的弧链表，实际上就是在已插入的弧结点中，对相同尾顶点的弧结点进行链接，其操作也是链表的头插法。

2. 源代码

#include <stdio.h>
#include <stdlib.h>
#define MaxVex 20

typedef int ArcType;
typedef char VertexType;

// 弧结点结构
typedef struct ArcNode
{
    ArcType arcData;        // 弧的数据
    int headVertex, tailVertex;   // 弧的头顶点和尾顶点
    struct ArcNode *nextHeadArc, *nextTailArc;  // 指向相同头、尾顶点的弧指针 
}ArcNode, *ArcList;

// 顶点结点结构
typedef struct VertexNode
{
    VertexType vertexData;      // 顶点的数据
    ArcList headList, tailList; // 相同头、尾顶点的弧链表
}VertexNode, *VertexList;

// 十字链表结构
typedef struct
{
    VertexList vertexList;
    int numVertexs, numArcs;
}OLGraph;

// 初始化十字链表
void InitOLGraph(OLGraph *G)
{
    // 初始化顶点
    G->numVertexs = 0;
    G->numArcs = 0;
    G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));
    // 初始化顶点的两个链表头结点（也可不带头结点）
    int i;
    for (i = 0; i < MaxVex; i++)
    {
        // 相同头顶点的弧链表
        G->vertexList[i].headList = (ArcNode *)malloc(sizeof(ArcNode));
        G->vertexList[i].headList->nextHeadArc = NULL;
        G->vertexList[i].headList->nextTailArc = NULL;
        // 相同尾顶点的弧链表
        G->vertexList[i].tailList = (ArcNode *)malloc(sizeof(ArcNode));
        G->vertexList[i].tailList->nextHeadArc = NULL;
        G->vertexList[i].tailList->nextTailArc = NULL;
    }
    printf("已初始化十字链表!\n");
}

// 创建十字链表
void CreateOLGraph(OLGraph *G)
{
    printf("请输入顶点数和弧数:");
    scanf("%d %d", &G->numVertexs, &G->numArcs);
    // 输入顶点数据
    int i, j, k;
    for (i = 0; i < G->numVertexs; i++)
    {
        fflush(stdin);
        printf("请输入第%d个顶点信息:", i + 1);
        scanf("%c", &G->vertexList[i].vertexData);
    }
    // 输入弧结点数据
    ArcType w;
    for (k = 0; k < G->numArcs; k++)
    {
        printf("请输入弧(Ai, Aj)的头、尾顶点及其权值:");
        scanf("%d %d %d", &i, &j, &w);
        
        // 创建新的弧结点，并设置该弧结点的数据和头尾顶点的下标
        ArcNode *s;
        s = (ArcNode *)malloc(sizeof(ArcNode));
        s->arcData = w;
        s->headVertex = i - 1;
        s->tailVertex = j - 1;
        
        // 头插法插入相同头顶点的弧链表
        s->nextHeadArc = G->vertexList[i - 1].headList->nextHeadArc;
        G->vertexList[i - 1].headList->nextHeadArc = s;

        // 头插法插入相同尾顶点的弧链表
        s->nextTailArc = G->vertexList[j - 1].tailList->nextTailArc;
        G->vertexList[j - 1].tailList->nextTailArc = s;
    }
    printf("已完成十字链表的创建!\n");
}

void DisplayOLGraph(OLGraph G)
{
    int i;
    ArcNode *p;
    for (i = 0; i < G.numVertexs; i++)
    {
        printf("顶点:%c\n", G.vertexList[i].vertexData);
        // 相同头顶点的弧链表
        printf("\t相同头顶点的弧:");
        p = G.vertexList[i].headList;
        while (p->nextHeadArc)
        {
            p = p->nextHeadArc;
            printf("(%c)%d(%c) => ", 
            G.vertexList[p->headVertex].vertexData,
            p->arcData, 
            G.vertexList[p->tailVertex].vertexData);
        }
        printf("NULL\n");
        // 相同尾顶点的弧链表
        printf("\t相同尾顶点的弧:");
        p = G.vertexList[i].tailList;
        while (p->nextTailArc)
        {
            p = p->nextTailArc;
            printf("(%c)%d(%c) => ", 
            G.vertexList[p->headVertex].vertexData,
            p->arcData, 
            G.vertexList[p->tailVertex].vertexData);
        }
         printf("NULL\n");
    }
}

int main()
{
    OLGraph G;
    InitOLGraph(&G);
    CreateOLGraph(&G);
    DisplayOLGraph(G);
    system("pause");
    return 0;
}

3. 测试结果