数据结构：“包”的学习与数组实现和链式实现，java语言描述。

以你之姓@ 2022-05-17 05:48 143阅读 0赞

# 前言 #

包是一个抽象数据类型，许多java数据结构书籍都拿其当做入门数据结构(如：《算法（第四版）》,《数据结构与抽象（JAVA语言描述）》等)。阅读此篇文章需要java基础知识（简单语法，泛型及基本类库的使用）

# 定义： #

包这一抽象概念与生活中的包极其类似，允许其中放入重复的事物，而且我们不关心其中的次序。

// 简单说，就是可重复，不关心顺序。

注：常用的 foreach 中就隐含着包的思想，遍历时：不关心遍历的顺序，也不在乎其中的内容，只需要遍历即可。

# 标准接口 #

先有接口后有实现，包自然有属于自己的接口

//一个包应该实现这个借口(没有使用块状注释，节省版面。）
    public interface BagInterface<T> {
        // 给包内新增一个元素
        public boolean add(T newEntry);
        // 得到当前包内的东西的个数
        public int getCurrentSize();
        // 包内是否为空
        public boolean isEmpty();
        // 随机移除一个东西
        public T remove();
        // 移除一个指定元素(只移除一个即可)
        public boolean remove(T anEntry);
        // 清楚包内事物
        public void clear();
        // 得到某个物品在包内的个数
        public int getFrequencyOf(T anEntry);
        // 包内是否拥有这个物品
        public boolean contains(T anEntry);
        // 将包内的物品们转化为数组并返回
        public T[] toArray();
    }

# 实现 #

## 静态数组实现 ##

静态数组实现的bag中，字段应该含有一个泛型数组存储事物，一个number记载物品个数方便操作。

而且，静态数组一定有容量上限，所以我们应该提供两种构造方法，一种是默认的无参构造方法，容量为默认规定的常量。所以这就需要我们定义一个int常量为默认。其次，提供一种可以由调用者决定容量的有参构造方法。

所以ArrayBag的字段和构造方法如下

public class ArrayBag<T> implements BagInterface<T> {
        // 当前包内物品的个数
        private int numberOfEntries;
        // 存储内容的数组
        private final T[] bag;
        // 在程序设计时，不可以出现魔法值，所以需要命名一个常量
        private static final int DEFAULT_CAPACITY = 25;
        /**
         * 写构造方法，一个默认的，一个手动输入容量
         */
        @SuppressWarnings("unchecked")   // 压制警告：泛型创建数组必然有警告
        public ArrayBagTest(int capacity) {
            super();
            this.numberOfEntries = 0;
            this.bag = (T[]) new Object[capacity];
        }
        public ArrayBagTest() {
            this(DEFAULT_SIZE);    // 使用this调用其他构造方法
        }
    }

接下来实现add()方法，因为其他方法都是建立在数据上实现的。

@Override
        public boolean add(T newEntry) {
            boolean result = true;
            if (isArrayFull()) { //使用一个方法增强自注释能力
                result = false;
            } else {
                bag[numberOfEntries] = newEntry;    // 添加结点
                numberOfEntries++;            // number增加
            }
            return result;
        }  
        private boolean isArrayFull() {// 判断是否已经不能再添加了
            return numberOfEntries >= bag.length;
        }

接下来实现getCurrentSize()和isEmpty()

@Override
        public int getCurrentSize() {
            return numberOfEntries;
        }
        @Override
        public boolean isEmpty() {
            return numberOfEntries == 0;
        }

然后实现清理clear()和各种remove方法

@Override
        public T remove() {
            return removeEntry(numberOfEntries);
        }
        @Override
        public boolean remove(T anEntry) {
            int index = getIndexof(anEntry);
            T result = removeEntry(index);
            return anEntry.equals(result);
        }
        private T removeEntry(int index) {
            T result = null;
            if (!isEmpty() && (index >= 0)) {
                result = bag[index];
                bag[index] = bag[numberOfEntries - 1];
    
                bag[numberOfEntries - 1] = null;
                numberOfEntries--;
            }
            return result;
        }
        private int getIndexof(T anEntry) {
            int where = -1;
            boolean found = false;
            int index = 0;
            while (!found && (index < numberOfEntries)) {
                if (anEntry.equals(bag[index])) {
                    found = true;
                }
                index++;
            }
            return where;
        }
        @Override
        public void clear() {
            while (!isEmpty()) {
                remove();
            }
        }

之后再将其他不太重要的方法补全即可。

import java.util.Arrays;
    
    /**
     * Description: 使用数组实现bag
     * @ClassName: ArrayBag
     * @author 过道
     * @date 2018年8月7日 上午9:17:41
     * @version V1.0
     * 
     */
    public class ArrayBag<T> implements BagInterface<T> {
    
        // 当前包内物品的个数
        private int numberOfEntries;
    
        private final T[] bag;
        // 在程序设计时，不可以出现魔法值：即未定义的常量如：{“这是一个魔法值”，234，87981.2123}，以上常量都是魔法值
        private static final int DEFAULT_CAPACITY = 25;
    
        public ArrayBag(int capacity) {
            this.numberOfEntries = capacity;
            @SuppressWarnings("unchecked")
            T[] tempBag = (T[]) new Object[capacity];
            bag = tempBag;
            numberOfEntries = 0;
        }
    
        public ArrayBag() {
            this(DEFAULT_CAPACITY);
        }
    
        @Override
        public boolean add(T newEntry) {
            boolean result = true;
            if (isArrayFull()) {
                result = false;
            } else {
                bag[numberOfEntries] = newEntry;
                numberOfEntries++;
            }
            return result;
        }
        private boolean isArrayFull() {
            return numberOfEntries >= bag.length;
        }
    
        @Override
        public int getCurrentSize() {
            return numberOfEntries;
        }
    
        @Override
        public boolean isEmpty() {
            return numberOfEntries == 0;
        }
        @Override
        public T remove() {
            return removeEntry(numberOfEntries);
        }
        @Override
        public boolean remove(T anEntry) {
            int index = getIndexof(anEntry);
            T result = removeEntry(index);
            return anEntry.equals(result);
        }
        private T removeEntry(int index) {
            T result = null;
            if (!isEmpty() && (index >= 0)) {
                result = bag[index];
                bag[index] = bag[numberOfEntries - 1];
    
                bag[numberOfEntries - 1] = null;
                numberOfEntries--;
            }
            return result;
        }
    
        private int getIndexof(T anEntry) {
            int where = -1;
            boolean found = false;
            int index = 0;
            while (!found && (index < numberOfEntries)) {
                if (anEntry.equals(bag[index])) {
                    found = true;
                }
                index++;
            }
            return where;
        }
    
        @Override
        public void clear() {
            while (!isEmpty()) {
                remove();
            }
        }
    
        @Override
        public int getFrequencyOf(T anEntry) {
            int counter = 0;
            for (int i = 0; i < numberOfEntries; i++) {
                if (anEntry.equals(bag[i])) {
                    counter++;
                }
            }
            return counter;
        }
    
        @Override
        public boolean contains(T anEntry) {
            return getIndexof(anEntry) > -1;
        }
    
        @Override
        public T[] toArray() {
            return Arrays.copyOf(bag, numberOfEntries);
        }
    }

## 动态数组实现 ##

所谓动态，即没有容量限制，但是数组一定有容量限制，所以我们使用扩容数组。

当新添加时，发现现在正在使用的数组已经满了，那么就先进行扩容操作，之后再进行添加，以防万一，我们添加一个最大容量，一旦扩容超过我们规定的最大容量，就抛出异常。

以下建立在静态数组实现的基础上进行改动的部分
     // 在程序设计时，不可以出现魔法值：即未定义的常量如：{“这是一个魔法值”，234，87981.2123}，以上常量都是魔法值
        private static final int DEFAULT_CAPACITY = 25;
    
        private static final int MAX_CAPACITY = 1600;
    
        @Override
        public boolean add(T newEntry) {
            boolean result = true;
            if (isArrayFull()) {
                doubleCapacity();
            }
            bag[numberOfEntries] = newEntry;
            numberOfEntries++;
            return result;
        }
        private void doubleCapacity() {
            int newLength = 2 * bag.length;
            checkCapacity(newLength);
            bag = Arrays.copyOf(bag, newLength);
        }
    
        private void checkCapacity(int capacity) {
               if(capacity > MAX_CAPACITY) {
                   throw new IllegalStateException();
               }
        }
        private boolean isArrayFull() {
            return numberOfEntries >= bag.length;
        }

## 链表实现 ##

链表实现，主要是注意以下链表如何定义。

/**
         * 
         * Description: 两个域，一个指向数据，另一个指向下一个结点的位置。
         * 
         * @ClassName: Node
         * @author 过道
         * @date 2018年8月10日 下午8:53:48
         * @version V1.0
         *
         */
        private class Node<T> {
            private T data;
            private Node next;
            // 空链表时，向链表中加入数据。
            public Node(T dataPortion) {
                this(dataPortion, null);
            }
            // 链表中有值，加入数据
            public Node(T data, Node next) {
                super();
                this.data = data;
                this.next = next;
            }
        }

package unit02_bag;
    
    public final class LinkedBag<T> implements BagInterface<T> {
        private Node firstNode;
        private int numberOfEntries;
    
        public LinkedBag() {
            this.firstNode = null;
            this.numberOfEntries = 0;
        }
    
        @SuppressWarnings("unchecked")
        @Override
        public boolean add(T newEntry) {
            Node newNode = new Node(newEntry);
            newNode.next = firstNode;
    
            firstNode = newNode;
            numberOfEntries++;
            // 对于链式存储，包不会满。
            return true;
        }
    
        @Override
        public int getCurrentSize() {
            return numberOfEntries;
        }
    
        @Override
        public boolean isEmpty() {
            return numberOfEntries == 0;
        }
    
        @Override
        public T remove() {
            T result = null;
            if (firstNode != null) {
                result = (T) firstNode.data;
                firstNode = firstNode.next;
                numberOfEntries--;
            }
            return result;
        }
    
        @Override
        public boolean remove(T anEntry) {
            boolean result = false;
            Node currentNode = firstNode;
            while (!result && currentNode != null) {
                if (currentNode.data.equals(anEntry)) {
                    // 此处利用包的不关心顺序的性质，将第一位的数据放到待删除结点的位置，然后删掉第一位结点即可。
                    currentNode.data = firstNode.data;
                    remove();
                    result = true;
                }
            }
            return result;
        }
    
        @Override
        public void clear() {
            while (!isEmpty()) {
                remove();
            }
        }
    
        @Override
        public int getFrequencyOf(T anEntry) {
            int frequency = 0; // 记录次数
            int loopCounter = 0; // 哨兵，进行记录,此处淡出为了保留逻辑完整性
            Node currentNode = firstNode;
            while ((loopCounter < numberOfEntries) && (currentNode != null)) {
                if (anEntry.equals(currentNode.data)) {
                    frequency++;
                }
                loopCounter++;
                currentNode = currentNode.next;
            }
            return 0;
        }
    
        @Override
        public boolean contains(T anEntry) {
            boolean found = false;
            Node currentNode = firstNode;
            while (!found && currentNode != null) {
                if (currentNode.data.equals(anEntry)) {
                    found = true;
                } else {
                    currentNode = currentNode.next;
                }
            }
            return found;
        }
    
        @SuppressWarnings("unchecked")
        @Override
        public T[] toArray() {
            T[] result = (T[]) new Object[numberOfEntries];
    
            int index = 0;
            Node currentNode = firstNode;
            while ((index < numberOfEntries) && (currentNode != null)) {
                result[index] = (T) currentNode.data;
                index++;
                currentNode = currentNode.next;
            }
            return result;
        }
    
        private class Node<T> {
            private T data;
            private Node next;
    
            public Node(T dataPortion) {
                this(dataPortion, null);
            }
    
            public Node(T data, Node next) {
                super();
                this.data = data;
                this.next = next;
            }
        }
    }