graph.java

这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦。 一个正则表达式就是由普通字符（例如字符 a 到 z）以及特殊字符（称为元字

 package reg2nfa;

public class Graph {
  EdgeLink[] graphEdge;        //图的边集
  private GraphNode start, end;  //图的起始结点和终止结点
  private EdgeLink currentLink;
  private int i = 0;

  public Graph(int n) {
    GraphNode.resetID();
    graphEdge = new EdgeLink[n];
    for(int i = 0; i < n; i++)
      graphEdge[i] = null;
  }

  public void setStart(GraphNode start) {
    this.start = start;
  }

  public void setEnd(GraphNode end) {
    this.end = end;
  }

  public GraphNode getStart() {
    return start;
  }

  public void setCurrent(int i) {
    this.i = i;
    currentLink = graphEdge[0];
  }

  public EdgeLink getNext() {
    EdgeLink nextLink;
    if(currentLink == null) return null;
      nextLink = currentLink;

    if(nextLink.linked != null) currentLink = nextLink.linked;
    else currentLink = graphEdge[++i];
    return nextLink;
  }

  public boolean hasNext() {
    if(i < 0 || i >= graphEdge.length - 1)
      return false;
    return true;
  }

  public void addEdge(GraphNode n1, GraphNode n2, String label) {
    //把边加在图形结构上
    int n = n1.getID();
    EdgeLink tempLink = new EdgeLink(n1, n2, label);
    if(graphEdge[n] == null)  {graphEdge[n] = tempLink; return;}
    EdgeLink currentLink = graphEdge[n];

    while(currentLink.linked != null)
      currentLink = currentLink.linked;
    currentLink.linked = tempLink;
  }

  public void addAppositiveEdge(GraphNode n1, GraphNode n2) {
    //并置处理
    int n = n1.getID();
    EdgeLink tempLink = new EdgeLink(n1, n2);
    EdgeLink currentLink;

    if(graphEdge[n] == null)  graphEdge[n] = tempLink;
    else {currentLink = graphEdge[n];
      while (currentLink.linked != null)
        currentLink = currentLink.linked;
      currentLink = tempLink;
    }
  }

  public void addChoiceEdge(GraphNode n1, GraphNode n2,
                            GraphNode n3, GraphNode n4,
                            GraphNode n5, GraphNode n6) {
    //选择处理
    EdgeLink tempLink1, tempLink2, tempLink3, tempLink4;
    tempLink1 = new EdgeLink(n5, n1);
    tempLink2 = new EdgeLink(n5, n3);
    tempLink3 = new EdgeLink(n2, n6);
    tempLink4 = new EdgeLink(n4, n6);
    EdgeLink currentLink;

    int n = n5.getID();
    if(graphEdge[n] == null)  graphEdge[n] = tempLink1;
    else {
      currentLink = graphEdge[n];
      while (currentLink.linked != null)
        currentLink = currentLink.linked;
      currentLink.linked = tempLink1;
    }
    tempLink1.linked = tempLink2;

    n = n2.getID();
    if(graphEdge[n] == null)  graphEdge[n] = tempLink3;
    else {
      currentLink = graphEdge[n];
      while (currentLink.linked != null)
        currentLink = currentLink.linked;
      currentLink.linked = tempLink3;
    }

    n = n4.getID();
    if(graphEdge[n] == null)  graphEdge[n] = tempLink4;
    else {
      currentLink = graphEdge[n];
      while (currentLink.linked != null)
        currentLink = currentLink.linked;
      currentLink.linked = tempLink4;
    }
  }

  public void addRepeatEdge(GraphNode n1, GraphNode n2,
                            GraphNode n3, GraphNode n4) {
    //重复处理
    EdgeLink tempLink1, tempLink2, tempLink3, tempLink4;
    tempLink1 = new EdgeLink(n3, n1);
    tempLink2 = new EdgeLink(n3, n4);
    tempLink3 = new EdgeLink(n2, n1);
    tempLink4 = new EdgeLink(n2, n4);
    EdgeLink currentLink;

    int n = n3.getID();
    if(graphEdge[n] == null)  graphEdge[n] = tempLink1;
    else {
      currentLink = graphEdge[n];

      while (currentLink.linked != null)
        currentLink = currentLink.linked;
      currentLink.linked = tempLink1;
    }
    tempLink1.linked = tempLink2;

    n = n2.getID();
    if(graphEdge[n] == null)  graphEdge[n] = tempLink3;
    else {
      currentLink = graphEdge[n];

      while (currentLink.linked != null)
        currentLink = currentLink.linked;
      currentLink.linked = tempLink3;
    }
    tempLink3.linked = tempLink4;
  }
}