本文主要是介绍Implement Set using Array.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考链接：http://faculty.washington.edu/moishe/javademos/ch03%20Code/jss2/ArraySet.java
被Pivotal的面试官给问到了，trick的地方在于remove的那一块，要把最后的元素跟自己remove的元素进行互换，然后count--；还有，自动扩容那块，构造函数需要两个，一个默认的，一个是可以限定side的。然后扩容的时候，阔完了，需要把larger 给contents。这都是容易错的地方，我当时就忘记赋值了。两个地方没有做好，然后就挂掉了。
//********************************************************************
// ArraySet.java Author: Lewis/Chase
//
// Represents an array implementation of a set.
//********************************************************************package jss2;
import jss2.exceptions.*;
import java.util.*;public class ArraySet<T> implements SetADT<T>
{private static Random rand = new Random();private final int DEFAULT_CAPACITY = 100;private final int NOT_FOUND = -1;private int count; // the current number of elements in the set private T[] contents; //-----------------------------------------------------------------// Creates an empty set using the default capacity.//-----------------------------------------------------------------public ArraySet(){count = 0;contents = (T[])(new Object[DEFAULT_CAPACITY]);}//-----------------------------------------------------------------// Creates an empty set using the specified capacity.//-----------------------------------------------------------------public ArraySet (int initialCapacity){count = 0;contents = (T[])(new Object[initialCapacity]);}//-----------------------------------------------------------------// Adds the specified element to the set if it's not already// present. Expands the capacity of the set array if necessary.//-----------------------------------------------------------------public void add (T element){if (!(contains(element))){if (size() == contents.length) expandCapacity();contents[count] = element;count++;}}//-----------------------------------------------------------------// Adds the contents of the parameter to this set.//-----------------------------------------------------------------public void addAll (SetADT<T> set){Iterator<T> scan = set.iterator();while (scan.hasNext())add (scan.next());}//-----------------------------------------------------------------// Removes a random element from the set and returns it. Throws// an EmptySetException if the set is empty.//-----------------------------------------------------------------public T removeRandom() throws EmptySetException{if (isEmpty())throw new EmptySetException();int choice = rand.nextInt(count);T result = contents[choice];contents[choice] = contents[count-1]; // fill the gapcontents[count-1] = null;count--;return result;}//-----------------------------------------------------------------// Removes the specified element from the set and returns it.// Throws an EmptySetException if the set is empty and a// NoSuchElementException if the target is not in the set.//-----------------------------------------------------------------public T remove (T target) throws EmptySetException,NoSuchElementException{int search = NOT_FOUND;if (isEmpty())throw new EmptySetException();for (int index=0; index < count && search == NOT_FOUND; index++)if (contents[index].equals(target))search = index;if (search == NOT_FOUND)throw new NoSuchElementException();T result = contents[search];contents[search] = contents[count-1];contents[count-1] = null;count--;return result;}//-----------------------------------------------------------------// Returns a new set that is the union of this set and the// parameter.//-----------------------------------------------------------------public SetADT<T> union (SetADT<T> set){ArraySet<T> both = new ArraySet<T>();for (int index = 0; index < count; index++)both.add (contents[index]);Iterator<T> scan = set.iterator();while (scan.hasNext())both.add (scan.next());return both;}//-----------------------------------------------------------------// Returns true if this set contains the specified target// element.//-----------------------------------------------------------------public boolean contains (T target){int search = NOT_FOUND;for (int index=0; index < count && search == NOT_FOUND; index++)if (contents[index].equals(target))search = index;return (search != NOT_FOUND);}//-----------------------------------------------------------------// Returns true if this set contains exactly the same elements// as the parameter.//-----------------------------------------------------------------public boolean equals (SetADT<T> set){boolean result = false;ArraySet<T> temp1 = new ArraySet<T>();ArraySet<T> temp2 = new ArraySet<T>();T obj;if (size() == set.size()){ temp1.addAll(this);temp2.addAll(set);Iterator<T> scan = set.iterator();while (scan.hasNext()){obj = scan.next(); if (temp1.contains(obj)){temp1.remove(obj);temp2.remove(obj);}}result = (temp1.isEmpty() && temp2.isEmpty());}return result;}//-----------------------------------------------------------------// Returns true if this set is empty and false otherwise. //-----------------------------------------------------------------public boolean isEmpty(){return (count == 0);}//-----------------------------------------------------------------// Returns the number of elements currently in this set.//-----------------------------------------------------------------public int size(){return count;}//-----------------------------------------------------------------// Returns an iterator for the elements currently in this set.//-----------------------------------------------------------------public Iterator<T> iterator(){return new ArrayIterator<T> (contents, count);}//-----------------------------------------------------------------// Returns a string representation of this set. //-----------------------------------------------------------------public String toString(){String result = "";for (int index=0; index < count; index++) result = result + contents[index].toString() + "\n";return result;}//-----------------------------------------------------------------// Creates a new array to store the contents of the set with// twice the capacity of the old one.//-----------------------------------------------------------------private void expandCapacity(){T[] larger = (T[])(new Object[contents.length*2]);for (int index=0; index < contents.length; index++)larger[index] = contents[index];contents = larger;}
}这篇关于Implement Set using Array.的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
