使用Java實現十字鏈表數據結構

存在著3個自定義類——Graph2、Data2、Vertex2，Graph用于定義圖，Data2用于表示頂點節點的Struct，Vertex用于表示弧節點的Struct，定義同教材。

文件1-Graph2.java

package orthogonallist;public class Graph2 {//自定義圖，可存儲50個節點Data2[] dianArray = new Data2[50];//記錄定點數和邊數int verNum=0;int edgeNum=0; }

文件2-Data2.java

package orthogonallist;public class Data2{//元素，首弧String data; //頂點名Vertex2 inArc,outArc; //入弧與出弧 }

文件3-Vertex2.java

package orthogonallist;public class Vertex2{//弧頭元素，弧尾元素，同弧頭指針，同弧尾指針String vh,vt; //VertexHead VertexTailVertex2 SimilarHeadVer,SimilarTailVer;//int info; //權值 }

文件4-OLtest.java

package orthogonallist;import java.util.Scanner;public class OLtest {public Data2 getVertex(Graph2 graph, String str) {for (int i = 0; i < graph.verNum; i++) {if (graph.dianArray[i].data.equals(str)) { return graph.dianArray[i];}}return null;}public void initialGraph(Graph2 graph) {// 初始化十字鏈表Scanner scan = new Scanner(System.in);System.out.println("請輸入頂點數和邊數：");try {graph.verNum = scan.nextInt();graph.edgeNum = scan.nextInt();} catch (Exception e) {System.out.println(e);return;}System.out.println("請依次輸入頂點名稱：");for (int i = 0; i < graph.verNum; i++) {String name = scan.next();Data2 dian = new Data2();dian.data = name;dian.inArc = null;dian.outArc = null;graph.dianArray[i] = dian;}System.out.println("請依次輸入圖的邊：(格式為 ‘a b’ 表示存在邊 a—>b )");for (int i = 0; i < graph.edgeNum; i++) {String preV = scan.next();String folV = scan.next();Data2 d1 = getVertex(graph, preV);Vertex2 current = new Vertex2();// 當指針用，記錄當前尋找到到最后的弧節點if (d1 == null) {System.out.println("輸入邊存在圖中沒有的頂點！");return;} else {Vertex2 v2 = new Vertex2();v2.vh = folV;v2.vt = preV;if (d1.outArc == null) {d1.outArc = v2;v2.SimilarTailVer = null;v2.SimilarHeadVer = null;} else {current = d1.outArc;while (current != null) {if(current.SimilarTailVer == null)break;current = current.SimilarTailVer;}current.SimilarTailVer = v2;v2.SimilarTailVer = null;v2.SimilarHeadVer = null;current = v2;//方便設置弧頭調用當前的Vertex}}Data2 d2 = getVertex(graph, folV);if (d2 == null) {System.out.println("輸入邊存在圖中沒有的頂點！");return;} else {if (d2.inArc == null)d2.inArc = current;else {Vertex2 v2 = new Vertex2();v2 = d2.inArc;while (v2.SimilarHeadVer != null) {v2 = v2.SimilarHeadVer;}v2.SimilarHeadVer = current;}}}}public void outputGraph(Graph2 graph) {// 輸出十字鏈表//直接通過SimilarHeadVer與SimilarTailVer不斷追查即可System.out.println("輸出圖的十字鏈表為：");for (int i = 0; i < graph.verNum; i++) {Data2 dt = graph.dianArray[i];System.out.print(dt.data);Vertex2 current = dt.outArc;while (current != null) {System.out.print("->" + current.vh);if(current.SimilarTailVer == null)break;current = current.SimilarTailVer;}System.out.println();}System.out.println("十字鏈表各節點詳細信息如下：");int count = 0;for(int i = 0; i < graph.verNum; i++){Data2 dt = graph.dianArray[i];System.out.print(dt.data+"頂點的入度為：");Vertex2 current = new Vertex2();if(dt.inArc != null){current = dt.inArc;count++;while(current.SimilarHeadVer != null){count++;current = current.SimilarHeadVer;}}System.out.print(count + ", ");count = 0;System.out.print(dt.data+"頂點的出度為：");Vertex2 current1 = new Vertex2();if(dt.outArc != null){current1 = dt.outArc;count++;while(current1.SimilarTailVer != null){count++;current1 = current1.SimilarTailVer;}}System.out.println(count);count = 0;}}public static void main(String[] args) {Graph2 graph = new Graph2();OLtest createGraph = new OLtest();createGraph.initialGraph(graph);createGraph.outputGraph(graph);} }

?

總結

以上是生活随笔為你收集整理的Java实现十字链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。