背包抽象数据类型

清疚 2021-07-24 18:27 395阅读 0赞

**一 代码**

package common;
    
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    
    public class Bag<Item> implements Iterable<Item> {
        private Node<Item> first;    // beginning of bag
        private int n;               // number of elements in bag
    
        // helper linked list class
        private static class Node<Item> {
            private Item item;
            private Node<Item> next;
        }
    
        public Bag() {
            first = null;
            n = 0;
        }
    
        public boolean isEmpty() {
            return first == null;
        }
    
        public int size() {
            return n;
        }
    
        public void add(Item item) {
            Node<Item> oldfirst = first;
            first = new Node<Item>();
            first.item = item;
            first.next = oldfirst;
            n++;
        }
    
        public Iterator<Item> iterator()  {
            return new ListIterator(first);  
        }
    
        // an iterator, doesn't implement remove() since it's optional
        private class ListIterator implements Iterator<Item> {
            private Node<Item> current;
    
    
            public ListIterator(Node<Item> first) {
                current = first;
            }
    
            public boolean hasNext()  { return current != null;                     }
            public void remove()      { throw new UnsupportedOperationException();  }
            public Item next() {
                if (!hasNext()) throw new NoSuchElementException();
                Item item = current.item;
                current = current.next;
                return item;
            }
        }
    
        public static void main(String[] args) {
            Bag<String> bag = new Bag<String>();
            while (!StdIn.isEmpty()) {
                String item = StdIn.readString();
                bag.add(item);
            }
    
            StdOut.println("size of bag = " + bag.size());
            for (String s : bag) {
                StdOut.println(s);
            }
        }
    }

**二 测试**

F:\Algorithm\target\classes>more tobebag.txt
    to be or not to be that is
    
    
    F:\Algorithm\target\classes>java common.Bag < tobebag.txt
    size of bag = 8
    is
    that
    be
    to
    not
    or
    be
    to