java - 避免数组中的重复条目

我正在写一个将Vertex对象添加到数组的方法。我需要检查要添加的顶点是否已存在于数组中。我不确定我要去哪里错。这是我的方法：

public void addVertex(Vertex v) {
    if (activeVertices >= maxVertices) {
        System.out.println("Graph full");
        return;
    }
    for(int i=1; i<vertices.length; i++) {
        if(vertices[i] != vertices[i-1]){
            vertices[activeVertices] = v; // add vertex to list of vertices
            v.graphIndex = activeVertices; // record index of vertex in graph
            activeVertices++;  // increment vertex count
        }
    }
}

顶点类：

public class Vertex {
    public String name;
    public int graphIndex; // index of adjacency matrix position of node in graph

    public Vertex (String s) {
        name = s;
        graphIndex = -1; // invalid position by default
    }

    public String toString() {
        return name;
    }

}

包含addVertex（）方法的类：

public class Graph {
    private int maxVertices;
    private Vertex[] vertices; // array of nodes
    private int[][] edges; // adjacency matrix
    int activeVertices;


    public Graph(int maxSize) {
        maxVertices = maxSize;
        vertices = new Vertex[maxVertices];
        activeVertices = 0;
    }


    public void addVertex(Vertex v) {
        if (activeVertices >= maxVertices) {
            System.out.println("Graph full");
            return;
        }
        for(int i=1; i<vertices.length; i++) {
            if(vertices[i] != vertices[i-1]){
                vertices[activeVertices] = v; // add vertex to list of vertices
                v.graphIndex = activeVertices; // record index of vertex in graph
                activeVertices++;  // increment vertex count
            }
        }
    }
    public void addEdge(Vertex v1, Vertex v2, int w) {
        edges[v1.graphIndex][v2.graphIndex] = w;
        edges[v2.graphIndex][v1.graphIndex] = w;
    }

    public Graph minimumSpanningTree() {
        Graph mst = new Graph(maxVertices); // create new graph
        int[] set = new int[activeVertices];
        for (int i=0; i<activeVertices; i++) { // copy nodes to graph
            mst.addVertex(vertices[i]);
            set[i]=i; // assign each node to its own set
        }
        PriorityQueue q = new PriorityQueue(maxVertices*maxVertices); // create priority queue
        for (int i=0; i<activeVertices; i++) { // copy edges to queue
            for (int j=0; j<activeVertices; j++) {
                if (edges[i][j]!=0) {
                    q.enqueue(new Edge(vertices[i],vertices[j],edges[i][j]));
                }
            }
        }

        while (!q.isEmpty()) { // iterate over all edges in priority order
            Edge e = q.dequeue(); // consider next edge
            if (set[e.source.graphIndex]!=set[e.destination.graphIndex]) { // skip edges not connecting different sets
                mst.addEdge(e.source, e.destination, e.weight); // add edge to MST
                System.out.println("adding "+e);
                int setToMerge=set[e.destination.graphIndex]; // rename nodes from "other" set
                for (int i=0; i<activeVertices; i++) {
                    if (set[i]==setToMerge) { // find nodes from "other" set
                        set[i]=set[e.source.graphIndex]; // reassign nodes
                    }
                }
            }
        }
        return mst;
    }

    public void print() {
        System.out.format("    ");
        for (int i=0; i<activeVertices; i++) {
            System.out.format("%3s ", vertices[i].name);
        }
        System.out.format("\n");
        for (int j=0; j<activeVertices; j++) {
            System.out.format("%3s ", vertices[j].name);
            for (int i=0; i<activeVertices; i++) {
                System.out.format("%3d ", edges[i][j]);
            }
            System.out.format("\n");
        }
    }
}

最佳答案

首先，您应该使用equals而不是==。您应该在equals类中编写适当的Vertex方法（使用Google查找有关如何执行此操作的大量教程）。

例如，如果您希望两个顶点对象仅在它们的名称相同时才被视为相等，那么equals方法将如下所示：

public boolean equals(Object obj) {
    if(obj == null) {
        return false;
    }

    if(obj instanceof Vertex) {
        Vertex otherVertex = (Vertex) obj;
        if(this.name.equals(otherVertex.name)) {
            return true;
        }
    }
    return false;
}

如果您也想比较graphIndex，则还需要在equals方法中进行检查。

假设您在equals类中有一个正确的Vertex方法，最简单的解决方案是使用Apache Commons库中的ArrayUtils.contains方法（Apache Commons具有大量有用的方法，可以为您节省很多时间。您应该检查一下）。此方法接受一个数组和一个Object，然后检查该数组是否包含该对象。