《图的创建、遍历及应用》由会员分享，可在线阅读，更多相关《图的创建、遍历及应用（16页珍藏版）》请在金锄头文库上搜索。
1、结点类package ch06;public class Node private Object data; / 存放结点值private Node next; / 后继结点的引用/ 无参数时的构造函数public Node() this(null, null);/带一个参数时的构造函数public Node(Object data) / 构造值为 data 的结点this(data, null);/带两个参数时的构造函数public Node(Object data, Node next) this.data = data;this.next = next;public Object get
2、Data() return data;public void setData(Object data) this.data = data;public Node getNext() return next;public void setNext(Node next) this.next = next;栈的抽象接口类package ch06;public interface IStack public void clear();public boolean isEmpty();public int length();public Object peek();public void push(Ob
3、ject x) throws Exception;public Object pop();链栈类package ch06;import ch06.Node;public class LinkStack implements IStackprivate Node top; /栈顶元素的应用/将栈置空public void clear()top=null;/判断栈是否为空public boolean isEmpty()return top = null;/求链栈的长度public int length()Node p = top; /初始化，p 指向栈顶元素，length 为计数器int leng
4、th = 0;while (p!=null) /从栈顶元素开始向后查找，直到 p 指向空p=p.getNext(); / p 指向后继结点+length; /长度增加 1return length;/取栈顶元素并返回其值public Object peek()if(!isEmpty() /栈非空return top.getData(); /返回栈顶元素的值elsereturn null;/入栈public void push(Object x)Node p = new Node(x); /构造一个新结点p.setNext(top);top = p; /新结点成为当前的首结点/出栈public
5、Object pop()if(isEmpty()return null;elseNode p = top; /p 指向被删除的结点（栈顶结点）top = top.getNext(); /修改链指针，使栈顶结点从链栈中移去return p.getData(); /返回栈顶结点的数据域的值 /输出栈中所有数据元素（从栈顶元素到栈底元素）public void display()Node p = top; /初始化，p 指向栈顶元素while (p!= null) /输出所有非空结点的数据元素值System.out.print(p.getData().toString() + );p=p.getNe
6、xt(); /p 指针向后移队列的抽象接口类package ch06;public interface IQueue public void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x)throws Exception;public Object poll();链队列类package ch06;import ch06.Node;public class LinkQueue implements IQueueprivate Node fro
7、nt; /队首指针private Node rear; /队尾指针/链队列类的构造函数public LinkQueue()front=rear=null;/队列置空public void clear()front=rear=null;/队列判空public boolean isEmpty()return front=null;/求队列的长度public int length()if(!isEmpty() /队列非空Node p=front;int length=0;while(p!=null)p=p.getNext(); /指针下移+length; /计数器+1 return length()
8、;/取队首元素public Object peek()if(front!=null) /队列非空return front.getData(); /返回队首结点的数据域值elsereturn null;/入队public void offer(Object x)Node p =new Node(x);if(front!=null)rear.setNext(p);rear=p; /改变队列尾的位置elsefront=rear=p;/出队public Object poll()if(front !=null)Node p=front;front=front.getNext(); /队首结点出列if(
9、p=rear) /被删除的结点是队尾结点时rear=null;return p.getData(); /返回队首结点的数据域值elsereturn null;顶点结点类package ch06;public class VNode private Object data; /顶点信息private ArcNode firstArc; /指向第一条依附于该顶点的弧public VNode() this(null, null);public VNode(Object data) this(data, null);public VNode(Object data, ArcNode firstArc)
10、 this.data = data;this.firstArc = firstArc;public Object getData() return data;public ArcNode getFirstArc() return firstArc;public void setData(Object data) this.data = data;public void setFirstArc(ArcNode firstArc) this.firstArc = firstArc;边结点类package ch06;public class ArcNodeprivate int adjVex; /该
11、弧所指向的顶点位置private int value; /边或弧的权值private ArcNode nextArc; /指向下一条弧public ArcNode() this(-1,0,null);public ArcNode(int adjVex) this(adjVex,0,null);public ArcNode(int adjVex,int value) this(adjVex,value,null);public ArcNode(int adjVex,int value,ArcNode nextArc) this.value=value;this.adjVex = adjVex;t
12、his.nextArc = nextArc;public int getValue()return value;public ArcNode getNextArc() return nextArc;public int getAdjVex() return adjVex;public void setAdjVex(int adjVex) this.adjVex = adjVex;public void setValue(int value) this.value = value;public void setNextArc(ArcNode nextArc) this.nextArc = nex
13、tArc;图的类型类package ch06;public enum GraphKind UDN,DN;图的抽象类package ch06;public interface IGraphvoid createGraph();int getVexNum();int getArcNum();Object getVex(int v) throws Exception;int locateVex(Object vex);int firstAdjVex(int v) throws Exception;int nextAdjVex(int v,int w) throws Exception;图的邻接表类p
14、ackage ch06;import java.util.Scanner;public class ALGraph implements IGraphprivate GraphKind kind;private int vexNum,arcNum;private VNode vexs;public ALGraph()this(null,0,0,null);public ALGraph(GraphKind kind,int vexNum,int arcNum,VNode vexs)this.kind=kind;this.vexNum=vexNum; this.arcNum=arcNum;this.v
