文章链接：日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
day37 十字链表
37.1 思路整理
（1）十字链表的数据结构：
由弧节点和顶点节点组成。其中每个节点的含义一定要清楚，不然很容易就晕了（如下图）
?（2）手动模拟十字链表
在知道了数据结构后手动模拟画出十字链表（十字链表我觉得画都很麻烦，所以一定要先弄懂他是怎么画的再去理解代码可能会更好些）其中起点和弧尾是相同表达意思，终点和弧头是相同表达意思
先画出度
先将每个顶点的firstOut指向以该顶点为弧尾的第一个节点（如a节点，以a节点为弧尾的有b和c，其中a节点的fisrtOut指向以a为起点b为终点的弧节点），而在指向弧节点的4个域中，第4个域tlink,指的是链接弧尾相同的顶点（以a为弧尾b为弧头的弧节点的第4个域指向以a为弧尾c为弧头的弧节点），所以就有如下图：
再画入度?
上面只画出了弧尾的指向，现在画弧头的指向，画法和上面画弧尾指向类似。每个顶点的firstIn指向以该顶点为弧头的第一个节点（如a节点，以a节点为弧头的有c,d, 其中a节点的firstOut指向以c为起点a为终点的弧节点）而在指向弧节点的4个域中，第3个域hlink,指的是链接弧头相同的顶点（以c为弧尾a为弧头的弧节点的第3个域指向以d为弧尾a为弧头的弧节点）
37.2 代码分析
（1）java之数组引用
int[] a = new int[10];
int[] b;
b = a;
b[0] = 1;
b[1] = 2;
b[3] = 3;
System.out.println("a数组引用地址 " + a);
System.out.println("a数组引用地址 " + b);打印输出：
a数组引用地址 [I@3339ad8e
a数组引用地址 [I@3339ad8e赋值内容：?
?所以让数组b直接指向数组a,(我们就可以理解为将a数组起个别名b,他们指向的是同一个对象，这就类似c语言中的指针)所以当b=a实际上是将a的引用地址赋值给b,所以b改动a也会随之改动。
在代码中这里的tempColumnNodes和headers数组就是引用传递，当修改tempColumnNodes时，headers也会随之改动
OrthogonalNode[] tempColumnNodes = new OrthogonalNode[numNodes];
for (int i = 0; i < numNodes; i++) {
tempColumnNodes[i] = headers[i];
}（2）十字链表的构造
我觉得十字链表的初始化比之前邻接矩阵和邻接表的初始化都更难，相比领接表容易找到出度，逆邻接表容易找到入度。十字链表即能很容易找到入度也很容易找到出度，所以他的数据结构也复杂一些。结合上面的知识和代码，可以将十字链表的初始化分为两部分，先初始化他的出度的链接，再初始化他入度的链接。
对于初始化出度的链接，判断出度是否为0，可以借助矩阵paraMatrix[i][j] == 0，i行j列表示i是否指向j（即是否以i顶点为弧尾）
对于初始化入度的链接,是遍历每一个头节点所链接的弧节点，使每个弧节点的第三个域去链接弧头相同的节点，其中第一个链接的一定是从头节点出发，其中弧节点的第二个域（即代码中的column）代表的是头节点的位置。如代码中的tempColumnNodes[tempNode.column].nextIn。
链接一个节点后要及时移动位置。感觉这段代码用语言不好描述，一定要图上模拟才更容易理解。
public OrthogonalList(int[][] paraMatrix) {
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;
}
tempNode = new OrthogonalNode(i,j);
tempPreviousNode.nextOut = tempNode;
tempPreviousNode = tempNode;
}
}
//Step3. 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];
}
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;
}
}
}测试：
?结合图画出的十字链表
?程序运行的结果：
The data are:
(0, 1)
(1, 3)
(2, 0)
(3, 1) (3, 2)
In arcs: (2, 0)
(0, 1) (3, 1)
(3, 2)
(1, 3)?总结：
今天的十字链表我感觉比之前的存储结构都复杂，也花了一些时间去理解，在理解十字链表的过程中，画图很重要，如果直接去看代码可能会很吃力，在今天的代码中对节点入度的初始化，只用了几行代码就实现了，但理解时我还是结合图去理解。