n*n的二维四向链表，初始化、遍历、最短路径、旋转
一、定义四向链表节点类Node：
public class Node<T> {
private T value;
private Node<T> up;
private Node<T> down;
private Node<T> left;
private Node<T> right;
public Node() {
}
public Node(T value) {
this.value = value;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node<T> getUp() {
return up;
}
public void setUp(Node<T> up) {
this.up = up;
}
public Node<T> getDown() {
return down;
}
public void setDown(Node<T> down) {
this.down = down;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public String toString() {
String s = "{v:"+this.value+", u:"+
(up==null?null:up.value) +", d:"+
(down==null?null:down.value)+", l:"+
(left==null?null:left.value)+",r:"+
(right==null?null:right.value)+
"}";
return s;
}
}二、初始化n*n二维四向链表：genNode
public class NodeUtil {
//生成n*n的二维四向链表，节点的value从1开始递增
//节点的up、down、right、left和二维的结构相对应关联
public Node<Integer> genNode(Integer n){
Node<Integer> head;
if(n<=0) return null;
Integer val = 1;
Node<Integer>[][] nodes = new Node[n][n];
//new
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
nodes[i][j] = new Node<Integer>(val++);
if(i>0) {
nodes[i][j].setUp(nodes[i-1][j]);
nodes[i-1][j].setDown(nodes[i][j]);
}
if(j>0) {
nodes[i][j].setLeft(nodes[i][j-1]);
nodes[i][j-1].setRight(nodes[i][j]);
}
}
}
head = nodes[0][0];
return head;
}
}三、遍历右下
在类NodeUtil里增加方法printToRightDown，打印该节点和它右下部分的二维节点
//打印该节点和它右下部分的二维节点
public void printToRightDown(Node<Integer> node) {
Node<Integer> rowNode,colNode;
System.out.println("#打印节点以及右下的二维节点：");
rowNode = node;
while(rowNode!=null) {
colNode=rowNode;
while(colNode!=null) {
System.out.print(colNode.getValue()+"\t");
colNode = colNode.getRight();
}
System.out.println("");
rowNode = rowNode.getDown();
}
}四、遍历全部
从任意节点出发，遍历所有节点，不可重复遍历
在类NodeUtil里增加方法：visitWhole方法、visitNode方法
private void visitNode(Node<Integer> node) {
if (node != null) {
System.out.println(node.getValue());
}
}
//给任意节点，遍历所有节点，不可重复遍历
public void visitWhole(Node<Integer> node) {
System.out.println("#遍历所有节点：");
if(node!=null) this.visitNode(node);
Node<Integer> up, down, left, right;
up = node.getUp();
while(up!=null) {
this.visitNode(up);
up = up.getUp();
}
down = node.getDown();
while(down!=null) {
this.visitNode(down);
down = down.getDown();
}
left = node.getLeft();
while(left!=null) {
this.visitNode(left);
up = left.getUp();
while(up!=null) {
this.visitNode(up);
up = up.getUp();
}
down = left.getDown();
while(down!=null) {
this.visitNode(down);
down = down.getDown();
}
left = left.getLeft();
}
right = node.getRight();
while(right!=null) {
this.visitNode(right);
up = right.getUp();
while(up!=null) {
this.visitNode(up);
up = up.getUp();
}
down = right.getDown();
while(down!=null) {
this.visitNode(down);
down = down.getDown();
}
right = right.getRight();
}
}五、路径
给任意两节点，找出两点之间的所有最短路径，打印出所有这些最短路径
如下图，4x4的矩阵，从5到16的最短路线有10种
规律：5->16的所有最短路径 = 5->6->16, 5->9->16（这两种的合集）
在类NodeUtil里增加方法：minPath，findAllMinPath
//递归算全部最短路径
//全部的最短路径：A->B = A-A1 & A1->B + A-A2 & A2->B
//A A1 # #
//A2 # # #
//# # # B
//# # # #
private void findAllMinPath(Node<Integer> start ,Node<Integer> end,
int startRow, int startColumn,
int endRow, int endColumn,
Integer[] paths, int curpos) {
Node<Integer> p = start;
int pos;
paths[curpos] = p.getValue(); //在路径上记下当前节点
//达到终点
if(startRow==endRow && startColumn==endColumn) {
//打印路径
for(int i=0;i<paths.length;i++) {
System.out.print(paths[i]+"\t");
}
System.out.println("");
return;
}
//根据相对位置，往左或往右
pos = curpos;
if(startColumn < endColumn ) { //往右一格
findAllMinPath(p.getRight(),end,
startRow,startColumn+1,
endRow,endColumn,
paths, pos+1);
}else if(startColumn > endColumn) { //往左一格
findAllMinPath(p.getLeft(),end,
startRow,startColumn-1,
endRow,endColumn,
paths, pos+1);
}
//根据相对位置，往上或往下
pos = curpos;
if(startRow < endRow ) { //往下一格
findAllMinPath(p.getDown(),end,
startRow+1,startColumn,
endRow,endColumn,
paths, pos+1);
}else if(startRow > endRow ) { //往上一格
findAllMinPath(p.getUp(),end,
startRow-1,startColumn,
endRow,endColumn,
paths, pos+1);
}
}
public void minPath(Node<Integer> start ,Node<Integer> end) {
Integer[] paths; //路径
Node<Integer> p ;
int startRow,startColumn; // 起点坐标
int endRow,endColumn; //终点坐标
//起点坐标
p = start;
startColumn = 0;
while(p!=null) {
startColumn++;
p = p.getLeft();
}
startColumn--;
p = start;
startRow = 0;
while(p!=null) {
startRow++;
p = p.getUp();
}
startRow--;
//终点的坐标
p = end;
endColumn = 0;
while(p!=null) {
endColumn++;
p = p.getLeft();
}
endColumn--;
p = end;
endRow = 0;
while(p!=null) {
endRow++;
p = p.getUp();
}
endRow--;
//最短路径长度=行差+列差+1
int pathlength = (startRow<endRow?endRow-
startRow:startRow-endRow) +
(startColumn<endColumn?endColumn-
startColumn:startColumn-endColumn)+1;
//创建路径数组
paths = new Integer[pathlength];
//打印起点、终点的值和坐标
System.out.println("#全部最短路径"+
start.getValue() +
":("+startRow+","+startColumn+") ->"+
end.getValue() +
":("+endRow+","+endColumn+")" );
//全部最短路径
this.findAllMinPath(start, end,
startRow, startColumn,
endRow, endColumn,
paths, 0);
}六、顺时针旋转90度
举例：n*n(n=4)二维表，右转90°，如下图：
找出规律：节点坐标 [i][j] -> [j][n-i-1]
//向右旋转90度
public Node<Integer> turnRight90(Node<Integer> node){
if(node==null) return null;
int n = 0;
Node<Integer> head, tmp ,rowNode, colNode;
head = node;
while(head.getLeft()!=null) head = head.getLeft();
while(head.getUp()!=null) head = head.getUp();
tmp = head;
while(tmp!=null) {
tmp = tmp.getRight();
n++;
}
Node<Integer> nodes[][] = new Node[n][n];
rowNode = head;
for(int i=0;i<n;i++) {
colNode = rowNode;
for(int j=0;j<n;j++) {
nodes[j][n-i-1] = colNode;
colNode = colNode.getRight();
}
rowNode = rowNode.getDown();
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i==0) {
nodes[i][j].setUp(null);
}
if(i>0) {
nodes[i][j].setUp(nodes[i-1][j]);
nodes[i-1][j].setDown(nodes[i][j]);
}
if(i==n-1) {
nodes[i][j].setDown(null);
}
if(j==0) {
nodes[i][j].setLeft(null);
}
if(j>0) {
nodes[i][j].setLeft(nodes[i][j-1]);
nodes[i][j-1].setRight(nodes[i][j]);
}
if(j==n-1) {
nodes[i][j].setRight(null);
}
}
}
return nodes[0][0];
}七、写个main方法执行下
public static void main(String[] args) {
NodeUtil util = new NodeUtil();
//创建4x4二维四项链表
Node<Integer> head = util.genNode(4);
//打印
util.printToRightDown(head);
//取其中两节点
Node<Integer> startNode = head.getDown();
Node<Integer> endNode = head.getRight().getDown().getRight().getRight().getDown().getDown();
//遍历，以startNode为起点遍历所有节点
util.visitWhole(startNode);
//从startNode到endNode的所有最短路径
util.minPath(startNode, endNode);
//从endNode到startNode的所有最短路径
util.minPath(endNode, startNode);
//向右旋转90度
Node<Integer> newhead = util.turnRight90(startNode);
//打印出旋转后的
util.printToRightDown(newhead);
}