# 二、代码编写

``````package datastructure.graph;

/**
* Orthogonal List for directed graph.
*
* @author Wei Ze 1025976860@qq.com.
*/
public class OrthogonalList {

/**
* 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
*/
int numNodes;

/**
* The headers for each row.
*/

/**
*********************
* The first constructor.
*
* @param paraMatrix The matrix indicating the graph.
*********************
*/
public OrthogonalList(int[][] paraMatrix) {
numNodes = paraMatrix.length;

// Step 1. Initialize. The data in the headers are not meaningful.
OrthogonalNode tempPreviousNode, tempNode;

// Step 2. Link to its out nodes.
for (int i = 0; i < numNodes; 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);

tempPreviousNode.nextOut = tempNode;
tempPreviousNode = 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++) {
} // Of for i

for (int i = 0; i < numNodes; i++) {
while (tempNode != null) {
tempColumnNodes[tempNode.column].nextIn = tempNode;
tempColumnNodes[tempNode.column] = tempNode;

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

/**
*********************
* 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++) {

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++) {

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
}// Of class OrthogonalList``````