• Author / Uploaded
• Nhung Hoang

Citation preview

3-SET 3-1 ARRAY-SET package set; import java.util.Iterator; public interface SetADT { public boolean add(T element); public boolean addAll(SetADT set); public boolean contains(T target); public boolean equals(Object that); public boolean isEmpty(); public Iterator iterator(); public T remove(T element); public T removeRandom(); public int size(); public SetADT union(SetADT set); public SetADT intersection(SetADT set); public String toString(); } -----------------------------------------------------------------------import java.util.Iterator; public class ArrayIterator implements Iterator { private int count; private int current; private T[] items; public ArrayIterator(T[] collections, int size) { items = collections; current = 0; count = size; } public boolean hasNext() { return current < count; } public T next() { if (!hasNext()) return null; else

current++; return items[current-1]; } public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); } } -----------------------------------------------------------------------package set; import java.util.Iterator; import java.util.Random; public class private private private

ArraySet implements SetADT { int count; T[] contents; final int NOT_FOUND = -1;

public ArraySet() { count = 0; contents = (T[]) new Object[10]; } public ArraySet(int n) { count = 0; contents = (T[]) new Object[n]; } public boolean add(T element) { if (!contains(element)) { if (size() == contents.length - 1) expandCapacity(); contents[count] = element; count++; return true; } return false; } public boolean addAll(SetADT set) { if (set == null) return false; Iterator scan = set.iterator();

while (scan.hasNext()) add(scan.next()); return true; } private void expandCapacity() { T[] large = (T[]) new Object[contents.length * 2]; for (int index = 0; index < count; ++index) large[index] = contents[index]; contents = large; } public boolean contains(T target) { int search = NOT_FOUND; for (int index = 0; index < count; ++index) { if (contents[index].equals(target)) { search = index; break; } } return search != NOT_FOUND; } public boolean equals(Object that) { if ((that == null) && (!(that instanceof SetADT))) return false; SetADT set = (SetADT) that; boolean result = false; ArraySet temp1 = new ArraySet(); ArraySet temp2 = new ArraySet(); T obj; if (set.size() == this.size()) { temp1.addAll(this); temp2.addAll(set); Iterator 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;

} public boolean isEmpty() { return count == 0; } public Iterator iterator() { return new ArrayIterator(contents, count); } public T remove(T element) { int search = NOT_FOUND; if (isEmpty()) return null; for (int index = 0; index < size(); ++index) if (contents[index].equals(element)) search = index; if (search == NOT_FOUND) return null; T result = contents[search]; contents[search] = contents[count - 1]; contents[count - 1] = null; count--; return result; } @Override public T removeRandom() { if (isEmpty()) return null; Random rand = new Random(); int choice = rand.nextInt(count); T result = contents[choice]; contents[choice] = contents[count - 1]; contents[count - 1] = null; --count; return result; } @Override public int size() { return count; } public void view() { Iterator scan = this.iterator(); while (scan.hasNext()) System.out.println(scan.next()); }

@Override public SetADT union(SetADT set) { ArraySet both = new ArraySet(); for (int index = 0; index < count; index++) both.add(contents[index]); Iterator scan = set.iterator(); while (scan.hasNext()) both.add(scan.next()); return both; } public SetADT intersection(SetADT set) { T obj; ArraySet both = new ArraySet(); for (int index = 0; index < size(); ++index) { obj = contents[index]; if (set.contains(obj)) both.add(obj); } return both; } } ------------------------------------------------------------------------

3-2 LINK-SET package linkedstructure; public class LinearNode { private T element; private LinearNode next; public LinearNode(T element) { this.element = element; this.next = null; } public LinearNode() { this.element = null; this.next = null; } public T getElement() { return element; } public void setElement(T element) { this.element = element; } public LinearNode getNext() {

return next; } public void setNext(LinearNode next) { this.next = next; }} -----------------------------------------------------------------------package linkedstructure; import java.util.Iterator; public class LinkedIterator implements Iterator{ private LinearNode current; public LinkedIterator(LinearNode head) { this.current = head; } @Override public boolean hasNext() { return (current != null); } @Override public T next() { T result = current.getElement(); current = current.getNext(); return result; } @Override public void remove() { throw new IllegalArgumentException(); }} -----------------------------------------------------------------------package linkedstructure; import java.util.Iterator; import set.SetADT; public class LinkedSet implements SetADT { private LinearNode head; private int count; public LinkedSet(){ this.head = null; this.count = 0; }

@Override public boolean add(T element) { //... LinearNode node = new LinearNode(element); if(this.head != null){ node.setNext(this.head); } this.head = node; count++; return true; } @Override public boolean addAll(SetADT set) { return true; // TODO Auto-generated method stub } @Override public boolean contains(T target) { // LinearNode current = this.head; // while(current !=null){ // if(current.getElement().equals(target)) // return true; // else // current = current.getNext(); // } // return false; LinearNode current = this.head; for(int i = 0; i < count; i++, current = current.getNext()){ if(current.getElement().equals(target)) return true; } return false; } @Override public boolean isEmpty() { return (count==0); } @Override public Iterator iterator() { return new LinkedIterator(this.head); }

@Override public T remove(T element) { if(this.head==null) return null; LinearNode current = this.head; for(int i = 0; i < count; i++){ if(current.getElement().equals(element)){ break; } else{ current = current.getNext(); } } if(current != null){ T ret = current.getElement(); current.setElement(this.head.getElement()); this.head = this.head.getNext(); count--; return ret; } else{ return null; } } @Override public T removeRandom() { // TODO Auto-generated method stub return null; } @Override public int size() { return count; } @Override public SetADT union(SetADT set) { LinkedSet both = new LinkedSet(); // LinearNode current = this.head; // while(current !=null){ // both.add(current.getElement()); // current = current.getNext(); // } for(Iterator iter = this.iterator(); iter.hasNext(); ){ T element = iter.next(); both.add(element); }

for(Iterator iter = set.iterator(); iter.hasNext(); ){ T element = iter.next(); both.add(element); } return both; } @Override public SetADT intersection(SetADT set) { // TODO Auto-generated method stub return null; } } ------------------------------------------------------------------------