数据结构篇—包(Bag)

  数据结构中的包,其实是对现实中的包的一种抽象。 想像一下现实中的包,比如书包,它能做什么?有哪些功能?首先它用来装东西,里面的东西可以随便放,没有规律,没有顺序,当然,可以放多个相同的东西。其次,东西可以拿出来,拿出来也有几种情况,随便拿出一个,拿出特定的一个,比如书本,把所有的东西都拿出来。附带的功能就是,包有没有满,包是不是空的,里面有多少东西了,都是什么,里面是不是有书,放了几本书之类的。想好之后,就可以定义数据结构中的包的方法了。

  装东西,定义add()方法,要接受一个参数,要装的东西,返回值呢?没有返回值。

  随便拿出一个东西,定义remove()方法, 没有参数,返回拿出的东西。

  拿出一个特定的东西,定义remove(anEntry), 接收一个参数,要拿出的东西,返回值是布尔值,表示有没有成功,因为要拿出的东西,包里可能没有

  拿出所有东西,定义clear()方法,没有参数,也没有返回值。

  包里有多少东西,定义getCurrentSize()方法,返回包中元素的个数,它没有参数,返回值是整数。

  包是不是空的,定义isEmpty()方法,当然,它也没有参数,返回布尔值。

  包里有没有书,定义contains()方法,它接受一个参数,要找的东西,返回布尔值。

  包里有几本书,定义getFrequencyOf()方法,也是接受一个参数,返回的是整数。

  包里都是什么,可以定义toArray()方法,返回一个数组,包含包里所有的东西,也是定义迭代方法。

/**
 * 一个用来描述包的操作的接口
 */
public interface BagInterface<T> {
    /**
     * 获取包中元素的数量
     *
     * @return 元素数量
     */
    int getCurrentSize();

    /**
     * 包是否为空
     *
     * @return 包为空,返回true, 否则返回false
     */
    boolean isEmpty();

    /**
     * 向包里添加一个元素
     *
     * @param newEntry 要添加到包里的元素
     */
    void add(T newEntry);

    /**
     * 从包里删除任意一个元素
     * @return 删除的元素
     */
    T remove();

    /**
     * 从包里删除一个给定的元素
     * @param anEntry 要删除的元素
     * @return 是否删除成功
     */
    boolean remove(T anEntry);

    /**
     * 删除包中所有元素
     */
    public void clear();

    /**
     * 计算一个给定元素的数量
     * @param anEntry 给定的元素
     * @return 给定元素的数量
     */
    public int getFrequencyOf(T anEntry);

    /**
     * 是否包含给定的元素
     * @param anEntry 要查找的元素
     * @return 如查包含返回true, 否则返回false
     */
    public boolean contains(T anEntry);

    /**
     * 获取包中所有的元素,
     * @return 包含包中所有元素新数组。
     * 注意,如果包为空,返回空数组
     */

    T[] toArray();
}

  使用数组实现Bag --- 创建ArrayBag类来实现BagInterface

  在实现方法之前,先考虑一下类的属性。由于包(bag)是用来存储东西的,所以一个属性是数组,用来存储元素。包有容量,数组有长度,还要决定数组的长度。既也可以让使用者来决定,也可以提供一个默认容量。除此之外,还要记录包中元素的个数

private T[] bag;
private int numberOfEntries;
private static final int DEFAULT_CAPACITY = 25;

  构造方法,初始化包。首先是创建数组对象,赋值给bag属性,因为属性中的bag只是一个数组的引用,并没有真正地创建数组。其次,由于创建的是空数组,numberOfEntries初始化为0. 但怎么创建数组呢?假设构造函数接收一个参数capacity,  bag = new T[capacity]; 不行。bag = new Object[capacity]; 还是不行。bag = (T[])new Object[capacity]; 倒是没有报错,但有warning(unchecked cast). 编译器想让你确保数组中的每一个元素从Object类强制转化成泛型T是安全的,由于数组刚刚创建,每一个元素都是null,因此转化是安全的,我们可以使用@SuppressWarnings("unchecked")告诉编译器忽略这个warning。@SuppressWarnings("unchecked")只能出现在方法定义或变量声明之前,由于bag = (T[])new Object[capacity]; 是赋值操作,不是变量声明,因为bag已经声明了,还要转化成

// 强制类型转化是安全的,因为新数组中所有元素都是null
@SuppressWarnings("unchecked")
T[] tempBag = (T[])new Object[capacity]; // Unchecked cast
bag = tempBag;

  整个构造函数如下

    /**
     * 创建一个空bag,初始空量为用户指定容量
     * @param capacity 指定容量
     */
    public ArrayBag(int capacity) {
        // 强制类型转化是安全的,因为新数组中所有元素都是null
        @SuppressWarnings("unchecked")
        T[] tempBag = (T[]) new Object[capacity]; // Unchecked cast
        bag = tempBag;
        numberOfEntries = 0;
    }

    /**
     * 创建一个空bag,初始空量为默认容量25
     */
    public ArrayBag() {
        this(DEFAULT_CAPACITY);
    }

  添加方法add,如果数组满了,就不能添加了,需要扩容,如果数组没有满,就可以继续添加。扩容后面再说,先看添加。添加元素,就是把要添加的元素直接放到数组中最后一个元素的后面,元素个数加1。刚开始时,数组为空,numberOfEntries为0,数组中没有元素,直接在0位置放置新元素,然后numberOfEntries + 1。再添加一个元素,那就要放到1的位置,numberOfEntries+1。再添加一个元素,那就要放到2的位置,numberOfEntries+1。

数据结构篇—包(Bag)

  你会发现,新元素的放置位置就是bag[numberOfEntries]的位置,add()方法就是

public void add(T newEntry) {
    if(isArrayFull()){

    } else {
      bag[numberOfEntries] = newEntry;
      numberOfEntries++;
    }
}

  实现isArrayFull很简单,元素的个数等于数组的长度就满了。

private boolean isArrayFull() {
    return numberOfEntries == bag.length;
}

  ToArray() 方法,也比较好实现,创建一个新数组,把bag中的元素复制过去

public T[] toArray() {
    @SuppressWarnings("unchecked")
    T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
    for (int index = 0; index < numberOfEntries; index++)
    {
        result[index] = bag[index];
    } // end for
    return result;
}

   现在可以向bag中添加元素,也可以查看bag中的元素,是时候实现其它方法了。先从简单的开始,isEmpty(),  getCurrentSize(), 

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

   getFrequencyOf(),计算一个元素在bag中出现的次数,就是计算一个元素在数组中出现的次数。使用for循环,遍历数组中的每一个元素,只要有元素和要查找的元素相等,计数器加1。遍历完成后,返回计数器,就可以了。

public int getFrequencyOf(T anEntry) {
    int count = 0;

    for (int i = 0; i < numberOfEntries; i++) {
        if(anEntry.equals(bag[i])){
            count++;
        }
    }
    return count;
}

  contains()方法,bag中是否包含某一个元素,还是循环遍历数组,只不过返回的true或false,在遍历中,只要有一个元素和要查找的元素相等,那就返回true。可以先设一个表示找到找不到的变量found,默认是false,只有当fasle的时候,才遍历数组,在遍历过程中,如果找到了,设为true。

public boolean contains(T anEntry) {
    boolean found = false;
    int index = 0;
    
    while (!found && index < numberOfEntries){
        if (anEntry.equals(bag[index])){
            found = true;
        }
        
        index++;
    }
    return found;
}

  clear()方法,清空bag,简单一点的实现,就是numberOfEntries = 0;,复杂一点就是bag不为空的时候,循环调用remove()方法

public void clear() {
    // numberOfEntries = 0;
    while (!isEmpty()){
        remove();
    }
}

  remove() 方法,删除任意一个元素,由于bag中的元素是没有顺序和规律的,可以随便删除,简单起见,我们就删除最后一个元素,当然,如果bag为空的话,删除是要报错的。

public T remove() {
    if (isEmpty()) {
        throw new RuntimeException("空");
    }
    
    T result = bag[numberOfEntries - 1];
    bag[numberOfEntries - 1] = null;
    numberOfEntries--;
    
    return result;
}

  remove(anEntry),删除一个给定的元素,首先要先查找这个元素,如果bag中没有这个元素,也就没有办法删除,直接return false就好了。如果找到了,再想办法删除。查找,用的是循环遍历,找到了,也就是找到了这个元素所在的位置。

数据结构篇—包(Bag)

  怎么删除呢?最先想到的是把后面的元素向前移,因为数组是连续的。

数据结构篇—包(Bag)

 

  有点复杂了。因为bag中的元素,并没有规定顺序,也就没有必要前移。我们可以让要删除的元素和最后一个元素,进行交换,直接删除最后一个元素就好了。

 数据结构篇—包(Bag)

public boolean remove(T anEntry) {
    if(isEmpty()){
        throw new RuntimeException("空");
    }

    boolean found = false;
    int index = 0;
    while (!found && index < numberOfEntries){
        if (anEntry.equals(bag[index])){
            found = true;
        } else {
            index++;
        }
    }

    if(found){
        bag[index] = bag[numberOfEntries - 1];
        bag[numberOfEntries - 1] = null;
        numberOfEntries--;
        return true;
    } else {
        return false;
    }
}

 

上一篇:gmapping建图功能应用


下一篇:LeetCode 数据结构—杨辉三角