日撸代码300行：第 37 天（ 十字链表）

代码来自闵老师”日撸 Java 三百行（31-40天）“，链接：https://blog.csdn.net/minfanphd/article/details/116975772

理解参考博文：https://blog.csdn.net/xiangxizhishi/article/details/79119532
对于十字（交叉）链表，个人感觉把出度，入度和矩阵里面的上下左右结合比较好理解。博文中将出度的下一个节点定义为right，将入度的下一个节点定义为down，和矩阵更贴切。十字链表有两个头链表，分别对应行的头和列的头；头链表没有数据，只是指向该行（列）的第一个元素，只有起始指针的意义。便于理解这里借用一下原博客的图：

package datastructure.graph;



public class OrthogonalList {
	
	
	class OrthogonalNode {
		
		int row;
		
		
		int column;
		
		
		OrthogonalNode nextOut;
		
		
		OrthogonalNode nextIn;
		
		
		public OrthogonalNode(int paraRow, int paraColumn) {
			// TODO Auto-generated constructor stub
			row = paraRow;
			column = paraColumn;
			nextOut = null;
			nextIn = null;
		}//The first constructor of OrthogonalNode
		
	}//of class OrthogonalNode
	
	
	int numNodes;
	
	
	OrthogonalNode[] headers;
	
	public OrthogonalList(int[][] paraMatrix) {
		// TODO Auto-generated constructor stub
		numNodes = paraMatrix.length;
		
		// Step 1. Initialize. The data in the headers are not meaningful.
		OrthogonalNode tempPreviouNode,tempNode;
		headers = new OrthogonalNode[numNodes];
		
		//Step 2. link to its out nodes.	
		for (int i = 0; i < paraMatrix.length; i++) {
			headers[i] = new OrthogonalNode(i, -1);
			tempPreviouNode = 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.
				tempPreviouNode.nextOut = tempNode;
				tempPreviouNode = tempNode;
			}//of for j
			
		}//of for i
		
		//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]; //作用相当于tempPreviouNode
		}//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
	}//The first constructor of OrthogonalList
	
	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
		}//of for i
		
		resultString += "rnIn 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 += "rn";
		}//of for i
		
		return resultString;
	}//of toString
	
	
	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:rn" + tempList);
	}//of main

}//of class OrthogonalList

第三步连接入度节点的时候，是通过行来遍历节点，通过列来连接各个节点。其中tempNode遍历行，tempColumnNodes作用相当于第二步中的tempPreviouNode，用来连接节点。（理解起来确实有点儿头大，设计是相当巧妙的）