数据结构（图）——十字链表（Java实现）
//十字链表
public class OrthogonalList {
private int MAXVEX;
private VertexeType[] verArr;
// 顶点数据
private class VertexeType {
String vertexe = null;
AdjacencyType fristin = null;// 入边表（顶点为弧尾）
AdjacencyType fristout = null;// 出边表（顶点为弧头）
public VertexeType(String vertexe) {
this.vertexe = vertexe;
}
public String getVertexe() {
return vertexe;
}
public AdjacencyType getFristin() {
return fristin;
}
public void setFristin(AdjacencyType fristin) {
this.fristin = fristin;
}
public AdjacencyType getFristout() {
return fristout;
}
public void setFristout(AdjacencyType fristout) {
this.fristout = fristout;
}
}
private class AdjacencyType {
int verNum = -1;// 弧的起点在顶点数组中的下标
int headVex = -1;// 弧终点在顶点数组中的下标
AdjacencyType headLink = null;// 指向下一个终点相同的邻接点
AdjacencyType adjLink = null;// 指向下一个起点相同的邻接点
public int getVerNum() {
return verNum;
}
public void setVerNum(int verNum) {
this.verNum = verNum;
}
public int getHeadVex() {
return headVex;
}
public void setHeadVex(int headVex) {
this.headVex = headVex;
}
public AdjacencyType getHeadLink() {
return headLink;
}
public void setHeadLink(AdjacencyType headLink) {
this.headLink = headLink;
}
public AdjacencyType getAdjLink() {
return adjLink;
}
public void setAdjLink(AdjacencyType adjLink) {
this.adjLink = adjLink;
}
}
// 顶点数组赋值
public OrthogonalList(String[] arr) {
this.MAXVEX = ;
this.verArr = new VertexeType[this.MAXVEX];
for (int i = 0; i < ; i++) {
this.verArr[i] = new VertexeType(arr[i]);
}
}
public void addAdj(String[][] strArr) {
for (int i = 0; i < ; i++) {
AdjacencyType temp = null;
AdjacencyType tempin = null;
int posOne = getPosition(strArr[i][0]);
int posTwo = getPosition(strArr[i][1]);
AdjacencyType adj = new AdjacencyType();
(posOne);
(posTwo);
temp = this.verArr[posOne].getFristout();
tempin = this.verArr[posTwo].getFristin();
if (temp == null) {
this.verArr[posOne].setFristout(adj);
} else {
while (true) {
if (() != null) {
temp = ();
} else {
(adj);
break;
}
}
}
if (tempin == null) {
this.verArr[posTwo].setFristin(adj);
} else {
while (true) {
if (() != null) {
tempin = ();
} else {
(adj);
break;
}
}
}
}
}
private int getPosition(String str) {
int pos = 0;
for(int i=0;i<this.MAXVEX;i++){
if(this.verArr[i].getVertexe().equals(str)){
pos=i;
break;
}
}
return pos;
}
public int getIndegree(String str) {
int i = 0;
int pos=getPosition(str);
AdjacencyType temp = this.verArr[pos].getFristin();
if (temp == null)
return i;
while (true) {
if (temp != null) {
i++;
temp = ();
} else {
break;
}
}
return i;
}
public int getOutdegree(String str) {
int i = 0;
int pos=getPosition(str);
AdjacencyType temp = this.verArr[pos].getFristout();
if (temp == null)
return i;
while (true) {
if (temp != null) {
i++;
temp = ();
} else {
break;
}
}
return i;
}
}