1.包(Bag)的简介

1.1 什么是包

在现实生活中,我们常见的包有购物袋,塑料袋,布袋等。这些物品的共同特性是他们都是一种容器,可以用来装物品。
而抽象数据类型(ADT)包是没有特定次序的对象的有限集合。这些对象具有相同的或相关的数据类型。包可以含有重复项。
包的行为有:
1.得到当前包中的项数
2.查看包是否为空
3.将给定的对象加到包中
4.从包中删除一个未指定的对象
5.可能的话,从包中删除一个具体对象的一次出现
6.可能的话,从包中删除一个具体对象的全部出现
7.从包中删除所有的对象
8.统计包中的某个对象的个数
9.测试包中是否含有某个对象
10.查看包中的所有对象

1.2说明一个包

可以使用UML来描述一个包类:

包的规格说明(Specification)

抽象数据类型:Bag
数据
有限个对象,不需要唯一,无序,且有相同的数据类型
这个集合中的对象个数
操作
伪代码 UML 描述
getCurrentSize() +getCurrentSize(): integer 任务:报告包中当前的对象个数
输入:无
输出:包中当前对象的个数
isEmpty() +isEmpty(): boolean 任务:查看包是否为空
输入:无
输出:根据包是否为空返回真或假
add(newEntry) +add(newEntry: T): boolean 任务:将给定对象添加到包中
输入:newEntry是一个对象
输出:根据添加是否成功返回真或假
remove() +remove(): T 任务:从包中删除未指定的项,如果可能的话
输入:无
输出:如果删除成功则返回被删除的对象,否则返回null
remove(anEntry) +remove(anEntry: T): boolean 任务:从包中删除某个对象的一次出现,如果可能的话
输入:anEntry是一个对象
输出:根据删除是否成功返回真或假
removeAll(anEntry) +removeAll(anEntry: T): boolean 任务:从包中删除某个对象的所有出现
输入:anEntry是一个对象
输出: 根据删除是否成功返回真或假
clear() +clear(): void 任务:从包中删除所有对象
输入:无
输出:无
getFrequencyOf(anEntry) +getFrequencyOf(anEntry: T): integer 任务:计数一个包中对象出现的次数
输入:anEntry是一个对象
输出:包中anEntry出现的次数
contains(anEntry) +contains(anEntry: T): boolean 任务:测试包中是否含有某个对象
输入:anEntry是一个对象
输出:根据包中是否含有anEntry返回真或假
toArray() +toArray(): T[] 任务:查找包中所有对象
输入:无
输出:包中当前对象的新数组

包的接口类

package cn.young22.dsa.ch01;
/**
 * 
* @TypeName:BagInterface   
* @Description: 一个描述包操作的接口
 */
public interface BagInterface {
	/**
	 * 
	* @FunctionName: getCurrentSize
	* @Action: 显示当前包中的对象个数
	* @return 返回当前包中的对象个数
	 */
	public int getCurrentSize();
	
	/**
	 * 
	* @FunctionName: isEmpty
	* @Action: 判断包是否为空
	* @ReturnType: boolean    
	* @return:返回真或假
	 */
	public boolean isEmpty();
	
	/**
	 * 
	* @FunctionName: add
	* @Action: 向包中添加一个新元素
	* @param @param newEntry
	* @ReturnType: boolean    
	* @return: 当添加成功时返回真,当添加失败时返回假
	 */
	public boolean add(T newEntry);
	
	/**
	 * 
	* @FunctionName: remove
	* @Action: 删除任意一个包中的元素
	* @param @return    
	* @ReturnType: T    
	* @return: 成功则返回被删除的元素,失败返回null
	 */
	public T remove();
	
	/**
	 * 
	* @FunctionName: remove
	* @Action: 删除一个指定的元素
	* @param @param anEntry
	* @ReturnType: boolean    
	* @return:成功则返回真,失败返回假
	 */
	public boolean remove(T anEntry);
	
	/**
	 * 
	* @FunctionName: removeAll
	* @Action: 删除一个指定的元素在数组中的所有出现
	* @param @param anEntry
	* @ReturnType: boolean    
	* @return:成功则返回真,失败返回假
	 */
	public boolean removeAll(T anEntry);
	
	/**
	 * 
	* @FunctionName: clear
	* @Action: 清空整个包    
	* @ReturnType: void    
	 */
	public void clear();
	
	/**
	 * 
	* @FunctionName: getFrequencyOf
	* @Action: 显示特定元素在包中的个数
	* @param @param anEntry 要被计数的元素
	* @ReturnType: int    
	* @return 返回特定元素的个数
	 */
	public int getFrequencyOf(T anEntry);
	
	/**
	 * 
	* @FunctionName: contains
	* @Action: 判断包中是否含有特定的元素
	* @param @param anEntry
	* @param @return    
	* @ReturnType: boolean    
	* @return:若存在给定的元素,返回真,否则返回假
	 */
	public boolean contains(T anEntry);
	
	/**
	 * 
	* @FunctionName: toArray
	* @Action: 检索包中的所有元素,将其赋值到一个数组中  
	* @ReturnType: T[]    
	* @throws
	* @return: 一个根据包中元素新建的数组
	* 		  注意:若包为空,则返回的数组也为空
	 */
	public T[] toArray();	
	
}

1.3使用ADT包

1.3.1在线购物袋的程序维护

package cn.young22.dsa.ch01;

import jdk.nashorn.internal.objects.annotations.Getter;

/** 一个用来描述商品名称和价格的类*/
public class Item {
	private String description;	// 物品描述
	private int    price;		// 物品价格,以分为单位
	
	/** 构造器方法,
	 * 将客户端传来的productDescription赋值给description
	 * productPrice赋值给price
	 * */
	public Item(String productDescription, int productPrice){
		description = productDescription;
		price = productPrice;
	}// end constructor
	
	@Getter
	public String getDescription() {
		return description;
	}
	
	@Getter
	public int getPrice() {
		return price;
	}
	
	// 以下面的格式输出对象的信息
	@Override
	public String toString() {
		return description + "\t$" + price / 100 + "." + price % 100;
	}
	
	
}
package cn.young22.dsa.ch01;

import cn.young22.dsa.ch02.ArrayBag1;

/**
 * 
* @TypeName:OnlineShopper   
* @Description: 一个用来维持在线商城购物车的类
 */
public class OnlineShopper {

	public static void main(String[] args) {
		// 模拟商品
		Item[] items = {new Item("Bird feeder", 2050),
				new Item("Squirrel guard", 1547),
				new Item("Bird batch", 4499),
				new Item("Sunflower seeds", 1295)
		};
		
		// 创建
		BagInterface shoppingCart = new ArrayBag1<>();
		// 物品的总价格
		int totalCost = 0;
		
		// 将挑选的商品加到购物车中
		for(int index = 0; index < items.length; index++){
			Item nextItem = items[index];
			shoppingCart.add(nextItem);
			totalCost = totalCost + nextItem.getPrice();
		}
		
		// 每次删除一个购物车中的商品并显示商品信息
		while(!shoppingCart.isEmpty()){
			System.out.println(shoppingCart.remove());
		}
		
		// 显示商品总价格
		System.out.println("Total cost: " + "\t$" + totalCost / 100 + "." + totalCost % 100);
		
	}

}

1.3.2扑满(PiggyBank)

package cn.young22.dsa.ch01;

/** 一个硬币名的枚举类*/
public enum CoinName {PENNY, NICKEL, DIME, QUARTER, FIFTY_CENT, DOLLAR}
package cn.young22.dsa.ch01;

/** 一个代表硬币的类*/

public class Coin {
	private enum CoinSide {HEADS, TAILS}
	private CoinName myName;
	private int value;	// 以分(cent)为单位
	private int year;  // 铸币年份(mint year)
	private CoinSide sideUp;
	
	/**
	 * 构造器方法, 创建一个给定面值和铸币年份的对象,正面朝上的面是随机设定的
	 * @param coinValue
	 * @param mintYear
	 */
	public Coin(int coinValue, int mintYear){
		switch(coinValue){
		case 1:
			myName = CoinName.PENNY;
			break;
		case 5:
			myName = CoinName.NICKEL;
			break;
		case 10:
			myName = CoinName.DIME;
		case 25:
			myName = CoinName.QUARTER;
			break;
		case 50:
			myName = CoinName.FIFTY_CENT;
			break;
		case 100:
			myName = CoinName.DOLLAR;
			break;
		default:
			myName = CoinName.PENNY;
			break;
		}
		
		value = coinValue;
		year = mintYear;
		sideUp = getToss();
	}
	/**
	 * 构造器方法,创建一个给定硬币名称和铸币年份的对象,正面朝上的面是随机设定的
	 * @param name
	 * @param mintYear
	 */
	public Coin(CoinName name, int mintYear){
		switch(name){
		case PENNY:
			value = 1;
			break;
		case NICKEL:
			value = 5;
			break;
		case DIME:
			value = 10;
			break;
		case QUARTER:
			value = 25;
			break;
		case FIFTY_CENT:
			value = 50;
			break;
		case DOLLAR:
			value = 100;
			break;
		default:
			value = 1;
			break;
		}
	}
	
	/** 返回硬币的名称*/
	public CoinName getMyName() {
		return myName;
	}
	/** 返回硬币的面值*/
	public int getValue() {
		return value;
	}
	/** 返回硬币的铸造年份*/
	public int getYear() {
		return year;
	}
	/** 如果头像朝上则返回 "HEADS",否则返回"TAILS"*/
	public String getSideUp() {
		return sideUp.toString();
	}
	
	/** 若头像朝上,则返回真,否则返回假*/
	public boolean isHeads(){
		return sideUp == CoinSide.HEADS;
	}
	
	/** 若背面(非头像面)朝上,则返回真,否则返回假*/
	public boolean isTails(){
		return sideUp == CoinSide.TAILS;
	}
	
	/** 抛掷硬币,朝上的面会随机的为"HEADS"或"TAILS"*/
	public void toss(){
		sideUp = getToss();
	}
	
	/** 以value/year/side-up的格式返回硬币的字符串信息*/
	public String toString(){
		return value + "/" + year + "/" + sideUp;
	}
	
	/** 返回一个投掷硬币后的随机面朝上的值"HEADS"或"TAILS"*/
	private CoinSide getToss(){
		CoinSide result;
		if(Math.random() < 0.5){
			result = CoinSide.HEADS;
		}else{
			result = CoinSide.TAILS;
		}
		return result;
	}
	
}
package cn.young22.dsa.ch01;

import cn.young22.dsa.ch02.ArrayBag;
/** 小猪存钱罐类*/
public class PiggyBank {
	// 私有的包类型的变量coins
	private BagInterface coins;
	/** 构造方法,新生产一个ArrayBag对象并赋值给coins*/
	public PiggyBank(){
		coins = new ArrayBag<>();
	}
	
	/** 向coins中添加硬币*/
	public boolean add(Coin aCoin){
		return coins.add(aCoin);
	}
	
	/** 移除coins中的硬币*/
	public Coin remove(){
		return coins.remove();
	}
	
	/** 判断coins是否为空*/
	public boolean isEmpty(){
		return coins.isEmpty();
	}
}
package cn.young22.dsa.ch01;

/** 一个用来测试小猪存钱罐的类*/
public class PiggyBankExample {

	public static void main(String[] args) {
		// 初始化一个小猪存钱罐
		PiggyBank myBank = new PiggyBank();
		// 向存钱罐中加入硬币
		addCoin(new Coin(1, 2010), myBank);
		addCoin(new Coin(5, 2011), myBank);
		addCoin(new Coin(10, 2000), myBank);
		addCoin(new Coin(25, 2012), myBank);
		
		// 开始从存钱罐中取出硬币
		System.out.println("Removing all the coins:");
		
		// 取出硬币的数目
		int amountRemoved = 0;
		
		// 从存钱罐中一个一个的取出硬币并输出硬币的信息
		while(!myBank.isEmpty()){
			Coin removedCoin = myBank.remove();
			System.out.println("Removed a " + removedCoin.getMyName() + ".");
			amountRemoved = amountRemoved + removedCoin.getValue();
		}
		// 硬币全部取完
		System.out.println("All done. Removed " + amountRemoved + " cents.");
	}
	
	/** 向存钱罐中加入硬币的方法*/
	public static void addCoin(Coin aCoin, PiggyBank aBank){
		if(aBank.add(aCoin)){
			System.out.println("Added a " + aCoin.getMyName() + ".");
		}else{
			System.out.println("Tried to add a " + aCoin.getMyName() +
					", but couldn't");
		}
	}// end addCoin
}// end PiggyBankExample

/*运行结果:
Added a PENNY.
Added a NICKEL.
Added a DIME.
Added a QUARTER.
Removing all the coins:
Removed a QUARTER.
Removed a DIME.
Removed a NICKEL.
Removed a PENNY.
All done. Removed 41 cents. 
*/

1.4ADT集合(Set)

package cn.young22.dsa.ch01;
/**
 * Set是不包括重复元素的包(Bag),其操作与ADT包的操作类似
 * 一个描述集合(Set)对象操作的接口
 */
public interface SetInterface {
	/**
	 * 获得当前集合中元素的数目
	 * @return 返回集合中的元素个数
	 * */
	public int getCurrentSize();
	
	/**
	 * 判断该集合是否为空
	 * @return 若结合空,返回True,否则返回False
	 * */
	public boolean isEmpty();
	
	/**
	 * 向集合中添加一个元素,且添加的元素不能与集合已有的元素重复
	 * @param newEntry 要加入集合的元素
	 * @return 若添加元素成功,返回True,否则,返回False
	 * */
	public boolean add(T newEntry);
	
	/**
	 * 从集合中删除一个指定的元素,如果可以删除的话
	 * @param anEntry 要被删除的元素
	 * @return 若删除成功返回True,否则返回False 
	 * */
	public boolean remove(T anEntry);
	
	/**
	 * 从集合中删除一个任意的元素,如果可以删除的话
	 * @return 若删除成功的,返回删除的元素,否则,返回null
	 */
	public T remove();
	
	/**
	 * 删除集合中的所有元素
	 * */
	public void clear();
	
	/**
	 * 测试该集合是否含有制定的元素
	 * @param anEntry 要锁定的元素
	 * @return 若含有该元素,返回True,否则,返回False
	 * */
	public boolean contains(T anEntry);
	
	/**
	 * 检索集合中的所有元素
	 * @return 一个由集合中所有元素新分配的数组
	 * */
	public T[] toArray();
}// end SetInterface

1.5Java类库:接口Set

2.包的顺序实现

package cn.young22.dsa.ch02;

import cn.young22.dsa.ch01.BagInterface;

/** 使用数组实现包的类的代码结构
 *  定义该类的私有数据:存储元素的包bag, 包中的元素个数numberOfEntries
 *  及数组的默认容量DEFAULT_CAPACITY
 *  实现构造方法: 实现一个给定容量的ArrayBag构造方法,在该方法中初始化bag数组
 *  实现BagInterface中要求实现的方法
 * */
public class ArrayBag implements BagInterface {
	// 定义终态的泛型数组bag
	private final T[] bag;	
	// 定义包中元素的个数
	private int numberOfEntries;
	// 定义包中默认元素的个数
	private static final int DEFAULT_CAPACITY = 25;
	
	/** 默认构造器方法,创建一个默认容量的包*/
	public ArrayBag(){
		this(DEFAULT_CAPACITY);
	}
	/** 创建一个给定容量的ArrayBag对象*/
	public ArrayBag(int capacity) {
		@SuppressWarnings("unchecked")
		T[] tempBag = (T[])new Object[capacity];
		bag = tempBag;
		numberOfEntries = 0;
	}
	
	/**
	 * 
	* @FunctionName: add
	* @Action: 向包中添加一个新元素
	* @param @param newEntry
	* @ReturnType: boolean    
	* @return: 当添加成功时返回真,当添加失败时返回假
	 */
	public boolean add(T newEntry) {
		// to be defined
		return false;
	}

	/**
	 * 
	* @FunctionName: toArray
	* @Action: 检索包中的所有元素,将其赋值到一个数组中  
	* @ReturnType: T[]    
	* @throws
	* @return: 一个根据包中元素新建的数组
	* 		  注意:若包为空,则返回的数组也为空
	 */
	public T[] toArray() {
		// to be defined
		return null;
	}	
	
	/**
	 * 
	* @FunctionName: isArrayFull
	* @Action: 判断包是否满了
	* @ReturnType: boolean    
	* @return 若包满,返回真,否则返回假
	 */
	public boolean isArrayFull(){
		// to be defined
		return false;
	}
	
	/**
	 * 
	* @FunctionName: isEmpty
	* @Action: 判断包是否为空
	* @ReturnType: boolean    
	* @return:返回真或假
	 */
	public boolean isEmpty(){
		// to be defined
		return false;
		
	};
	/**
	 * 
	* @FunctionName: getCurrentSize
	* @Action: 显示当前包中的对象个数
	* @return 返回当前包中的对象个数
	 */
	public int getCurrentSize(){
		return numberOfEntries;
		
	};
	
	
	/**
	 * 
	* @FunctionName: remove
	* @Action: 删除任意一个包中的元素
	* @param @return    
	* @ReturnType: T    
	* @return: 成功则返回被删除的元素,失败返回null
	 */
	public T remove() {
		return null;
	}
	
	/**
	 * 
	* @FunctionName: remove
	* @Action: 删除一个指定的元素
	* @param @param anEntry 要被删除的元素
	* @ReturnType: boolean    
	* @return:成功则返回真,失败返回假
	 */
	public boolean remove(T anEntry) {
		return false;
	}
	
	/**
	 * 
	* @FunctionName: clear
	* @Action: 清空整个包    
	* @ReturnType: void    
	 */
	public void clear() {
	}
	
	/**
	 * 
	* @FunctionName: getFrequencyOf
	* @Action: 显示特定元素在包中的个数
	* @param @param anEntry 要被计数的元素
	* @ReturnType: int    
	* @return 返回特定元素的个数
	 */
	public int getFrequencyOf(T anEntry) {
		return 0;
	}
	
	/**
	 * 
	* @FunctionName: contains
	* @Action: 判断包中是否含有特定的元素
	* @param @param anEntry
	* @param @return    
	* @ReturnType: boolean    
	* @return:若存在给定的元素,返回真,否则返回假
	 */
	public boolean contains(T anEntry) {
		return false;
	}
	
	/**
	 * 
	* @FunctionName: removeAll
	* @Action: 删除一个指定的元素在数组中的所有出现
	* @param @param anEntry
	* @ReturnType: boolean    
	* @return:成功则返回真,失败返回假
	 */
	@Override
	public boolean removeAll(T anEntry) {
		// TODO Auto-generated method stub
		return false;
	}
}

2.1使用固定大小的数组实现ADT包

package cn.young22.dsa.ch02;

import cn.young22.dsa.ch01.BagInterface;

/** ArrayBag2类在ArrayBag1类的基础上添加了:
 * 	remove()的实现
 *  remove(T anEntry)的实现
 *  removeAll(T anEntry)的实现
 *  clear()的实现
 *  
 *  在实现上述4个方法时,用到了一下几个方法:
 *  getIndexOf(T anEntry)		通过给定值找到它在包中的第一次出现位置
 *  removeEntry(int givenIndex)	通过给定的在数组中的索引删除包中的元素
 * */

public class ArrayBag2 implements BagInterface{
	// 定义一个泛型的数组,并设置为final,不让它被修改
	private final T[] bag;	
	// 定义int类型的numberOfEntries变量,用来存放包中的元素个数
	private int numberOfEntries;
	// 布尔型的变量initialized用在构造方法中,用来判断对象是否正常被构造完全
	private boolean initialized = false;
	// 初试的包容量
	private static final int DEFAULT_CAPACITY = 25;
	// 包的最大容量
	private static final int MAX_CAPACITY = 10000;
	
	/** 默认构造器方法*/
	public ArrayBag2(){
		this(DEFAULT_CAPACITY);
	}
	
	/** 创建一个给定容量的ArrayBag对象*/
	public ArrayBag2(int desiredCapacity) {
		// 将客户指定的容量与最大的容量比较,若大于最大容量,则抛出异常
		if(desiredCapacity <= MAX_CAPACITY){
			// 在分配数组是不能使用泛型,但可以使用Object类型
			// 故先分配Object类型的数组,再进行强制类型转换,变成泛型数组
			// 但是转型完后还会在编译时出现警告
			// ArrayBag2.java uses unchecked or unsafe operations
			// Note:Recompile with -Xlint:unchecked for details
			// 由于数组刚刚分配,其中仅含有null项,故这种类型转换时安全的,使用
			// @SuppressWarnings("unchecked")来让编译程序忽略这个警告
			@SuppressWarnings("unchecked")
			T[] tempBag = (T[])new Object[desiredCapacity];
			bag = tempBag;
			numberOfEntries = 0;
			initialized = true;
		}else{
			throw new IllegalStateException("Attempt to create a bag" +
					"whose capacity exceeds allowed maximum");
		}
		
	}
	
	/**
	 * 
	* @FunctionName: add
	* @Action: 向包中添加一个新元素
	* @param @param newEntry
	* @ReturnType: boolean    
	* @return: 当添加成功时返回真,当添加失败时返回假
	 */
	public boolean add(T newEntry) {
		checkInitialization();
		boolean result = true;
		if(isArrayFull()){
			result = false;
		}else{
			// Assertion: result is true here
			bag[numberOfEntries] = newEntry;
			numberOfEntries++;
		}
		return result;
	}

	/**
	 * 
	* @FunctionName: toArray
	* @Action: 检索包中的所有元素,将其赋值到一个数组中  
	* @ReturnType: T[]    
	* @throws
	* @return: 一个根据包中元素新建的数组
	* 		  注意:若包为空,则返回的数组也为空
	 */
	public T[] toArray() {
		checkInitialization();
		
		@SuppressWarnings("Unchecked")
		T[] result = (T[])new Object[numberOfEntries];
		
		for(int index = 0; index < numberOfEntries; index++){
			result[index] = bag[index];
		}
		return result;
	}	
	
	/**
	 * 
	* @FunctionName: isArrayFull
	* @Action: 判断包是否满了
	* @ReturnType: boolean    
	* @return 若包满,返回真,否则返回假
	 */
	public boolean isArrayFull(){
		// 当数组中的元素个数大于或等于数组的大小时,返回True
		return numberOfEntries >= bag.length;
	}
	
	/**
	 * 
	* @FunctionName: isEmpty
	* @Action: 判断包是否为空
	* @ReturnType: boolean    
	* @return:返回真或假
	 */
	public boolean isEmpty(){
		return numberOfEntries == 0;
		
	};
	/**
	 * 
	* @FunctionName: getCurrentSize
	* @Action: 显示当前包中的对象个数
	* @return 返回当前包中的对象个数
	 */
	public int getCurrentSize(){
		return numberOfEntries;
	};
	
	
	/**
	 * 
	* @FunctionName: remove
	* @Action: 删除包中的最后一个元素
	* @param @return    
	* @ReturnType: T    
	* @return: 成功则返回被删除的元素,失败返回null
	 */
	public T remove() {
		checkInitialization();
		// 删除包中的最后一个元素
		T result = removeEntry(numberOfEntries - 1);
		return result;
	}
	
	/**
	 * 
	* @FunctionName: remove
	* @Action: 删除一个指定的元素,删除的元素的为数组中第一次出现该值的位置
	* @param @param anEntry 要被删除的元素
	* @ReturnType: boolean    
	* @return:成功则返回真,失败返回假
	 */
	public boolean remove(T anEntry) {
		// 检查对象是否正常初始化
		checkInitialization();
		// 获取给定元素的下标位置
		int index = getIndexOf(anEntry);
		// 删除给定下标的元素
		T result = removeEntry(index);
		// 返回删除的结果
		return anEntry.equals(result);
	}
	
	/**
	 * 
	* @FunctionName: removeAll
	* @Action: 删除一个指定的元素在数组中的所有出现
	* @param @param anEntry
	* @ReturnType: boolean    
	* @return:成功则返回真,失败返回假
	 */
	public boolean removeAll(T anEntry){
		// 检查对象是否正常初始化
		checkInitialization();
		// 查找bag中第一个给定值的位置
		int index = getIndexOf(anEntry);
		// 初始化result为null
		T result = null;
		
		// 通过循环删除包中所有的给定的值
		while(index > -1){
			result = removeEntry(index);
			index = getIndexOf(anEntry);		
		}
		
		return anEntry.equals(result);
	}
	
	/**
	 * 
	* @FunctionName: clear
	* @Action: 清空整个包    
	* @ReturnType: void    
	 */
	public void clear() {
		// 若包不为空,则一直删除该包的最后一个元素
		while(!isEmpty()){
			remove();
		}
	}
	
	/**
	 * 
	* @FunctionName: getFrequencyOf
	* @Action: 显示特定元素在包中的个数
	* @param @param anEntry 要被计数的元素
	* @ReturnType: int    
	* @return 返回特定元素的个数
	 */
	public int getFrequencyOf(T anEntry) {
		checkInitialization();
		int counter = 0;
		for(int index = 0; index < numberOfEntries; index++){
			// 这里不可以使用bag[index].equals(anEntry),因为bag[index]可能没有值,程序会抛出NullPointerException
			if(anEntry.equals(bag[index])){
				counter++;
			}
		}
		return counter;
	}
	
	/**
	 * 
	* @FunctionName: contains
	* @Action: 判断包中是否含有特定的元素
	* @param @param anEntry
	* @param @return    
	* @ReturnType: boolean    
	* @return:若存在给定的元素,返回真,否则返回假
	 */
	public boolean contains(T anEntry) {
		checkInitialization();
		// 调用getIndexOf方法在bag数组中找anEntry,
		// 若找到,返回的值不为负值
		return getIndexOf(anEntry) > -1;
	}
	
	/**
	 * 
	* @FunctionName: getIndexOf
	* @Action: 根据给定的元素,在bag中找到其下标值
	* @param @param anEntry 
	* @ReturnType: int    
	* @return: 给定值的下标
	 */
	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;
				where = index;
			}
			index++;
		}
		// Assertion: If where > -1, anEntry is in the array bag and
		// it equals bag[where]; 
		// otherwise, anEntry is not in the arry.
		return where;
	}// end getIndexOf
	
	/**
	 * 
	* @FunctionName: removeEntry
	* @Action: 通过给定索引删除包中的元素 
	* @param @param givenIndex
	* @ReturnType: T    
	* @return 若删除成功,返回True,否则,返回False
	 */
	private T removeEntry(int givenIndex){
		T result = null;
		
		if(!isEmpty() && (givenIndex > -1)){
			result = bag[givenIndex]; // 要删除的元素
			int lastIndex = numberOfEntries - 1;// 找到最后一个元素的下标
			bag[givenIndex] = bag[lastIndex];// 将最后一个元素移到要删除元素的位置
			bag[lastIndex] = null;// 将最后一个元素的值赋值为null
			numberOfEntries--;// 将bag中的元素数目-1
		}// end if
		
		return result;
	}// end removeEntry
	
	/**
	 * 
	* @FunctionName: checkInitilization
	* @Action: 检测对象是否被正常初始化,若对象未正常初始化,则抛出异常
	* @ReturnType: void    
	 */
	public void checkInitialization(){
		if(!initialized){
			throw new SecurityException("ArrayBag object is not initialized properly");
		}
	}
}
package cn.young22.dsa.ch02;

import cn.young22.dsa.ch01.BagInterface;

/**
 * 这个类使用来测试ArrayBag2中新添加的方法的
 * 主要测试了remove系列的方法
 * */

public class ArrayBagDemo2 {

	public static void main(String[] args) {
		String[] contentsOfBag = {"A", "A", "B", "A", "C", "fadsd"};
		BagInterface aBag = new ArrayBag2<>(contentsOfBag.length);
		
		// Adding Strings
		testAdd(aBag, contentsOfBag);
		
		// Removing Strings
		String[] testString = {"", "B", "A", "C", "D", "A"};
		testRemove(aBag, testString);
		
		// test method removeAll(T anEntry)
		aBag.removeAll("A");
		displayBag(aBag);
	}

	// Tests the method add.
	private static void testAdd(BagInterface aBag, String[] content)
	{
		System.out.print("Adding ");
		for (int index = 0; index < content.length; index++)
		{
			aBag.add(content[index]);
         System.out.print(content[index] + " ");
		} // end for
      System.out.println();    
		displayBag(aBag);
	} // end testAdd	
	
	// test remove() and remove(T anEntry) method
	private static void testRemove(BagInterface aBag, String[] contents){
		for(int index = 0; index < contents.length; index++){
			String aString = contents[index];
			if(aString.equals("") || (aString == null)){
				// test remove()
				System.out.println("\nRemoving a string from the bag");
				String removedString = aBag.remove();
				System.out.println("remove returns " + removedString);
			}else{
				// test remove(T anEntry)
				System.out.println("\nRemoving \"" + aString + "\" from the bag:");
				boolean result = aBag.remove(aString);
				System.out.println("remove(\"" + aString + "\") returns " + result);
			}
			displayBag(aBag);
		}
	}

	// Tests the method toArray while displaying the bag.
	private static void displayBag(BagInterface aBag)
	{
		System.out.println("The bag contains " + aBag.getCurrentSize() +
		                   " string(s), as follows:");		
		Object[] bagArray = aBag.toArray();
		for (int index = 0; index < bagArray.length; index++)
		{
			System.out.print(bagArray[index] + " ");
		} // end for
		
		System.out.println();
	} // end displayBag
}

/**
Expected output:

Adding A A B A C fadsd 
The bag contains 6 string(s), as follows:
A A B A C fadsd 

Removing a string from the bag
remove returns fadsd
The bag contains 5 string(s), as follows:
A A B A C 

Removing "B" from the bag:
remove("B") returns true
The bag contains 4 string(s), as follows:
A A C A 

Removing "A" from the bag:
remove("A") returns true
The bag contains 3 string(s), as follows:
A A C 

Removing "C" from the bag:
remove("C") returns true
The bag contains 2 string(s), as follows:
A A 

Removing "D" from the bag:
remove("D") returns false
The bag contains 2 string(s), as follows:
A A 

Removing "A" from the bag:
remove("A") returns true
The bag contains 1 string(s), as follows:
A 
The bag contains 0 string(s), as follows:

 */

2.2使用可变大小的数组实现ADT包

package cn.young22.dsa.ch02;

import java.util.Arrays;

import cn.young22.dsa.ch01.BagInterface;
/** 数组容量可增大的ArrayBag
 *  这个类与ArrayBag2类的主要不同在于添加元素时,
 *  当判断ifArrayFull为True时,不再是拒绝添加,而是倍增数组容量再继续添加新元素
 * */
public class ResizeableArrayBag implements BagInterface{

	private T[] bag;	// cannot be final due to doubling
	private int numberOfEntries;
	private boolean initialized = false;
	private static final int DEFAULT_CAPACITY = 25;
	private static final int MAX_CAPACITY = 10000;
	
	/** 默认构造函数,调用给定容量的构造函数进行初始化*/
	public ResizeableArrayBag() {
		this(DEFAULT_CAPACITY);
	}
	
	/** 以给定容量的的方式初始化一个ResizeableArrayBag对象*/
	public ResizeableArrayBag(int initialCapacity) {
		// 检查用户指定的容量是否超过最大容量
		checkCapacity(initialCapacity);
		
		@SuppressWarnings("unchekced")
		T[] tempBag = (T[])new Object[initialCapacity];
		bag = tempBag;
		numberOfEntries = 0;
		initialized = true;
	}
	
	/** 以给定包内容的方式初始化一个ResizeableArrayBag对象*/
	public ResizeableArrayBag(T[] contents) {
		checkCapacity(contents.length);
		// 使用Arrays工具数组将contents的内容复制给bag
		bag = Arrays.copyOf(contents, contents.length);
		// 将contents的length赋值给numberOfEntries
		numberOfEntries = contents.length;
		// 初始化完毕
		initialized = true;
	}
	
	/** 获取包中当前的元素个数*/
	@Override
	public int getCurrentSize() {
		return numberOfEntries;
	}

	/** 判断包是否为空*/
	@Override
	public boolean isEmpty() {		
		return numberOfEntries == 0;
	}
	
	/**添加新的元素,当数组容量满时,则倍增数组容量,之后再将新元素加到数组最后*/
	@Override
	public boolean add(T newEntry) {
		checkInitialization();
		if(isArrayFull()){
			doubleCapacity();
		}		
		bag[numberOfEntries] = newEntry;
		numberOfEntries++;		
		return true;
	}
	
	/** 删除包中的最后一个元素*/
	@Override
	public T remove() {
		checkInitialization();
		// 删除最包的最后一个元素并将返回值赋值给result
		T result = removeEntry(numberOfEntries - 1);
		// 返回删除元素的值
		return result;
	}

	/** 删除给定元素在包中的第一次出现*/
	@Override
	public boolean remove(T anEntry) {
		checkInitialization();
		// 找到数组中第一次出现给定值的下标并赋值给index
		int index = getIndexOf(anEntry);
		// 删除给定下标index的元素并将返回值赋值给result
		T result = removeEntry(index);
		// 使用equals方法判断是否返回成功,
		// 若anEntry的值与result的值相等,返回True,否则返回False
		return anEntry.equals(result);
	}

	/** 删除包中所有的给定的元素*/
	@Override
	public boolean removeAll(T anEntry) {
		checkInitialization();
		// 得到给定元素在数组中第一次出现的下标并赋值给index
		int index = getIndexOf(anEntry);
		// 初始化 result
		T result = null;
		
		// 通过循环删除包中所有给定的值
		while(index > -1){					// 若index不为负值即包中仍有给定的元素,则继续循环
			result = removeEntry(index);	// 删除给定数组下标的元素,并将返回值赋给result
			index = getIndexOf(anEntry);	// 继续再包中寻找给定值的下标
		}
		return anEntry.equals(result);		// 返回查找删除结果,若删除成功,返回True,否则,返回False
	}
	
	/** 清空包中的所有元素*/
	@Override
	public void clear() {
		// 通过isEmpty来控制while循环,
		// 若isEmpty=False,则每次删除包的最后一个元素
		// 若isEmpty=True,则结束循环
		while(!isEmpty()){
			remove();
		}
	}
	
	/** 根据指定的下标去删除包中的元素*/
	private T removeEntry(int givenIndex){
		
		T result = null;
		// 若包非空,且给定的下标非负,则将包的最后一个元素赋值到要删除的元素的位置
		// 再将最后一个元素赋值为null,最后将numberOfEntries-1
		if(!isEmpty() && (givenIndex >= 0)){
			result = bag[givenIndex];
			int lastIndex = numberOfEntries - 1;
			bag[givenIndex] = bag[lastIndex];
			bag[lastIndex] = null;
			numberOfEntries--;
		}
		
		return result;		
	}

	/** 查找给定元素出现在包中的次数*/
	@Override
	public int getFrequencyOf(T anEntry) {
		checkInitialization();
		int counter = 0;
		for(int index = 0; index < numberOfEntries; index++){
			if(anEntry.equals(bag[index])){
				counter++;
			}
		}
		return counter;
	}
	
	/** 使用getIndexOf方法来查看包中是否包含指定元素*/
	@Override
	public boolean contains(T anEntry) {
		checkInitialization();
		return getIndexOf(anEntry) > -1;
	}

	/** 将包中的元素赋值给新的数组数组并返该数组*/
	@Override
	public T[] toArray() {
		checkInitialization();
		
		@SuppressWarnings("unchekced")
		T[] result = (T[])new Object[numberOfEntries];
		for(int index = 0; index < numberOfEntries; index++){
			result[index] = bag[index];
		}
		
		return result;
	}
	
	/** 判断数组是否满了*/
	private boolean isArrayFull(){
		return numberOfEntries >= bag.length;
	}
	
	/** 判断客户端所要求的包的容量是否过大,若过大则抛出异常*/
	private void checkCapacity(int capacity){
		if(capacity > MAX_CAPACITY){
			throw new IllegalStateException("Attempt to create a bag"+
					"whose capacity exceeds allowed maximum of" + 
					MAX_CAPACITY);
		}
	}
	
	/** 判断对象是否正常初始化,若未正常初始化,则抛出异常*/
	private void checkInitialization(){
		if(!initialized){
			throw new SecurityException("Uninitialized object used " + 
					"to call an ArrayBag method");
		}
	}// end checkinitialization
	
	/** 倍增数组容量方法,使用Arrays工具,
	 *  将原数组拷贝到一个新的容量为原数组两倍的数组中
	 *  把新数组的引用赋值给原变量
	 *  即完成了数组的扩容操作
	 * */
	private void doubleCapacity(){
		int newLength = 2 * bag.length;
		checkCapacity(newLength);
		bag = Arrays.copyOf(bag, newLength);
	}// end doubleCapacity
	
	/** 根据给定值查找元素在数组中的下标位置*/
	private int getIndexOf(T anEntry){
		// 初试化元素下标位置
		int where = -1;
		// 初始化查找结果
		boolean found = false;
		// 初始化数组下标
		int index = 0;

		// 若找到该元素在数组中的位置,则结束循环,found=true
		// 若知道循环结束仍未找到元素,则结束循环,found=false
		while(!found && (index < numberOfEntries)){
			if(anEntry.equals(bag[index])){
				found = true;
				where = index;
			}
			// 每经过一个元素,数组下标+1
			index++;
		}
		// 返回给定元素下标位置
		return where;
	}
}
package cn.young22.dsa.ch02;

import cn.young22.dsa.ch01.BagInterface;
/**
 *  测试ResizeableArrayBag类
 * */
public class ResizeableArrayBagDemo {

	public static void main(String[] args) {
		// A bag whose initial capacity is small
		// 初始化一个容量只有3的包
		BagInterface aBag = new ResizeableArrayBag<>(3);
		// 测试此时包空是否为真
		testIsEmpty(aBag, true);
		
		// 测试add方法,将contentsOfBag的值赋值到aBag中
		// 注意,这时contentsOfBag中有7个元素,而初始化的aBag的容量仅为3,故在运行时aBag会自动的增加容量
		System.out.println("Adding to the bag more strings that its initial capacity");
		String[] contentsOfBag = {"A", "D", "B", "A", "C", "A", "D"};
		testAdd(aBag, contentsOfBag);
		
		// 添加了元素后再测试isEmpty方法
		testIsEmpty(aBag, false);
		String[] testStrings2 = {"A", "B", "C", "D", "Z"};
		// 使用testStrings2去测试每个给定字符出现在aBag中的频率或判断包中是否包含给定字符
		testFrequency(aBag, testStrings2);
		testContains(aBag, testStrings2);
		
		// 测试remove()和remove(anEntry)方法,
		// 若传入的字符串为""或null则调用remove()方法,删除包中的最后一个元素的值
		// 否则,则调用remove(anEntry)方法,删除包中给定值的第一次出现
		String[] testStrings3 = {"", "B", "A", "C", "Z"};
		testRemove(aBag, testStrings3);
		
		// 测试removeAll()方法,删除给定元素在包中的所有值
		System.out.println("\nRemove the specific string in the bag");
		aBag.removeAll("A");
		displayBag(aBag);
		
		// 测试clear()方法,情况整个包中的元素
		System.out.println("\nClearing the bag:");
		aBag.clear();
		testIsEmpty(aBag, true);
		displayBag(aBag);
	}
	
	/** Tests the method add*/
	private static void testAdd(BagInterface aBag, String[] contents){
		System.out.print("Adding to the bag: ");
		for(int index = 0; index < contents.length; index++){
			aBag.add(contents[index]);
			System.out.print(contents[index] + " ");
		}// end for
		System.out.println();
		
		displayBag(aBag);
	}// end testAdd
	
	/** Tests the two remove methods*/
	private static void testRemove(BagInterface aBag, String[] tests){
		for(int index = 0; index < tests.length; index++){
			String aString = tests[index];
			if(aString.equals("") || (aString == null)){
				// test remove
				System.out.println("\nRemoving a string from the bag:");
				String removedString = aBag.remove();
				System.out.println("remove() returns" + removedString);
			}else{
				// testremove(aString)
				System.out.println("\nRemoving \"" + aString + "\" from the bag:");
				boolean result = aBag.remove(aString);
				System.out.println("remove(\"" + aString + "\") returns " + result);
			}		
			displayBag(aBag);
		}
	}
	
	/** Tests the method isEmpty*/
	// correctResult indicates what isEmpty should return
	private static void testIsEmpty(BagInterface aBag, boolean coorrectResult){
		System.out.print("Testing isEmpty with ");
		if(coorrectResult){
			System.out.println("an empty bag:");
		}else{
			System.out.println("a bag that is not empty");
		}
		
		System.out.println("isEmpty finds the bag ");
		if(coorrectResult && aBag.isEmpty()){
			System.out.println("empty: OK");
		}else if(coorrectResult){
			System.out.println("not empty, but it is empty: ERROR");
		}else if(!coorrectResult && aBag.isEmpty()){
			System.out.println("empty, but it is not empty: ERROR");
		}else{
			System.out.println("not empty: OK.");
		}
		System.out.println();
	}
	
	/** Tests the method getFrequency*/
	private static void testFrequency(BagInterface aBag, String[] tests){
		System.out.println("\nTesting the method getFrequencyOf:");
		for(int index = 0; index < tests.length; index++){
			System.out.println("In this bag, the count of " + tests[index] + 
					" is " + aBag.getFrequencyOf(tests[index]));
		}
	}
	
	/** Tests the method contains*/
	private static void testContains(BagInterface aBag, String[] tests){
		System.out.println("\nTesting the method contains");
		for(int index = 0; index < tests.length; index++){
			System.out.println("Does this bag contain " + tests[index] + 
					"? " + aBag.contains(tests[index]));
		}
	}
	
	/** Tests the method toArray while displaying the bag*/
	private static void displayBag(BagInterface aBag){
		System.out.println("The bag contains " + aBag.getCurrentSize() + 
				" string(s), as follows:");
		Object[] bagArray = aBag.toArray();
		for(int index = 0; index < bagArray.length; index++){
			System.out.print(bagArray[index] + " ");
		}
		System.out.println();
	}// end displayBag
}

/*
Expected output:

Testing isEmpty with an empty bag:
isEmpty finds the bag 
empty: OK

Adding to the bag more strings that its initial capacity
Adding to the bag: A D B A C A D 
The bag contains 7 string(s), as follows:
A D B A C A D 
Testing isEmpty with a bag that is not empty
isEmpty finds the bag 
not empty: OK.


Testing the method getFrequencyOf:
In this bag, the count of A is 3
In this bag, the count of B is 1
In this bag, the count of C is 1
In this bag, the count of D is 2
In this bag, the count of Z is 0

Testing the method contains
Does this bag contain A? true
Does this bag contain B? true
Does this bag contain C? true
Does this bag contain D? true
Does this bag contain Z? false

Removing a string from the bag:
remove() returnsD
The bag contains 6 string(s), as follows:
A D B A C A 

Removing "B" from the bag:
remove("B") returns true
The bag contains 5 string(s), as follows:
A D A A C 

Removing "A" from the bag:
remove("A") returns true
The bag contains 4 string(s), as follows:
C D A A 

Removing "C" from the bag:
remove("C") returns true
The bag contains 3 string(s), as follows:
A D A 

Removing "Z" from the bag:
remove("Z") returns false
The bag contains 3 string(s), as follows:
A D A 

Remove the specific string in the bag
The bag contains 1 string(s), as follows:
D 

Clearing the bag:
Testing isEmpty with an empty bag:
isEmpty finds the bag 
empty: OK

The bag contains 0 string(s), as follows:
 
 
 */

2.3包的顺序实现小结

3.包的链式实现

package cn.young22.dsa.ch03;

import cn.young22.dsa.ch01.BagInterface;

/** 包的链式实现的代码框架
 * 	仅实现了add()和toArray()方法
 * */

public class LinkedBag implements BagInterface{
	/** 包中的节点类*/
	private class Node {
		private T 	data;	// Entry in bag
		private Node next; 	// Link to the next node
		
		/** 节点的构造方法,将客户传入的dataPortion赋值给节点,next赋值为null*/
		private Node(T dataPortion){
			this(dataPortion, null);
		}
		
		/** 节点的构造方法,将客户端传入的dataPortion和nextNode分别赋值给data和next*/
		private Node(T dataPortion, Node nextNode){
			data = dataPortion;
			next = nextNode;
		}
	}
	// 头结点
	private Node firstNode;
	// 包中的节点个数
	private int numberOfEntries;
	
	
	@Override
	public int getCurrentSize() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean add(T newEntry) {
		// Add to beginning of chain:
		Node newNode = new Node(newEntry);
		newNode.next = firstNode;	// make new node reference rest of chain
									// (firstNode is null if chain is empty)
									// New node is at beginning of chain
		firstNode = newNode;
		numberOfEntries++;
		
		return true;
	}// end add

	@Override
	public T remove() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean remove(T anEntry) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean removeAll(T anEntry) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		
	}

	@Override
	public int getFrequencyOf(T anEntry) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public boolean contains(T anEntry) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public T[] toArray() {
		// The cast is safe because the new array contains null entries
		@SuppressWarnings("unchecked")
		T[] result = (T[])new Object[numberOfEntries]; // unchecked cast
		
		int index = 0;
		Node currentNode = firstNode;
		while((index < numberOfEntries) && (currentNode != null)){
			result[index] = currentNode.data;
			index++;
			currentNode = currentNode.next;
		}
		return result;
	}

}

3.1包的链式实现

package cn.young22.dsa.ch03;

import cn.young22.dsa.ch01.BagInterface;

/**
 *  LinkedBag2类实现了所有的规格说明所需要的方法
 *  
 * */
public class LinkedBag2 implements BagInterface{
	/** 包的节点*/
	private class Node {
		private T 	data;	// Entry in bag
		private Node next; 	// Link to the next node
		
		/** 仅使用data初始化的Node*/
		private Node(T dataPortion){
			this(dataPortion, null);
		}
		
		/** 使用data和nextNode初始化的节点*/
		private Node(T dataPortion, Node nextNode){
			data = dataPortion;
			next = nextNode;
		}
	}
	
	// 包的第一个节点
	private Node firstNode;
	// 包中节点的个数
	private int numberOfEntries;
	
	/** LinkedBag2类的默认构造方法,将第一个节点初始化为null,包中的元素个数初始化为0*/
	public LinkedBag2(){
		firstNode = null;
		numberOfEntries = 0;
	}
	
	/** 返回包中当前的节点个数*/
	@Override
	public int getCurrentSize() {
		return numberOfEntries;
	}
	
	/** 判断包是否为空,若节点个数为0,返回True,否则,返回False*/
	@Override
	public boolean isEmpty() {
		return numberOfEntries == 0;
	}

	/** 使用头插法往包中新添节点*/
	@Override
	public boolean add(T newEntry) {
		// Add to beginning of chain:
		// 新建一个以newEntry为data值的Node对象
		Node newNode = new Node(newEntry);
		// 将 newNode的下一个节点引用指向头节点
		newNode.next = firstNode;	// make new node reference rest of chain
									// (firstNode is null if chain is empty)
									// New node is at beginning of chain
		// 将头结点的引用指向newNode
		firstNode = newNode;
		// 将包中的元素个数加1
		numberOfEntries++;
		
		return true;
	}// end add

	/** 删除链包中的第一个节点*/
	@Override
	public T remove() {
		// 新建泛型类型的result变量并赋初值为null
		T result = null;
		// 若头结点不为空,则删除包中的头结点
		if(firstNode != null){
			result = firstNode.data;
			firstNode = firstNode.next;
			// 这里不需要写像C或C++中的释放firstNode的方法
			// 因为在Java中没有被引用的对象会被JVM自动回收
			numberOfEntries--;	// 将包中元素的个数减1
		}
		return result;
	}
	
	/** 锁定给定元素在包中的位置
	 * 如果查找成功,返回一个指向这个节点的索引
	 * 否则,返回null
	 * */
	private Node getReferenceTo(T anEntry){
		// 初始化标志变量 found为假
		boolean found = false;
		// 将第一个节点的索引赋给currentNode,从此开始查找给定的值
		Node currentNode = firstNode;
		
		// 当找到data域为anEntry的节点后终止循环, found = true
		// 当遍历完整改链表仍未找到data域为anEntry的节点,结束循环, found 为初始值不变
		while(!found && (currentNode != null)){
			if(anEntry.equals(currentNode.data)){
				found = true;
			}else{
				currentNode = currentNode.next;
			}
		}		
		// 返回找到的节点的引用,
		// 若成功在链表中找到给定的anEntry值的节点,则返回该节点的引用
		// 否则,返回null
		return currentNode;		
	}

	/** 如果可行的话,删除指定元素的第一次在链表中的出现*/
	@Override
	public boolean remove(T anEntry) {
		// 初始化删除的结果为false
		boolean result = false;
		// 查找给定值anEntry在链表的第一次出现,并将该节点的引用赋值给nodeN
		Node nodeN = getReferenceTo(anEntry);
		
		// 若该节点的引用不为null,则在链表中删除该节点,并将result赋值为true
		if(nodeN != null){
			nodeN.data = firstNode.data;
			firstNode = firstNode.next;
			numberOfEntries--;
			result = true;
		}
		// 返回删除结果
		return result;
	}
	
	/** 如果可行的话,删除指定元素在链表中的所有出现*/
	@Override
	public boolean removeAll(T anEntry) {
		// 初始化删除结果为false
		boolean result = false;
		// 查找给定值anEntry在链表的第一次出现,并将该节点的引用赋值给nodeN
		Node nodeN = getReferenceTo(anEntry);
		
		// 当该节点的引用不为null时,进行删除节点的循环, 
		// 每删除一个节点,将包中的节点个数减1,将删除结果赋值为true,
		// 再继续查找包中是否还有改给定值的节点, 继续循环
		// nodeN为null时,结束循环
		while(nodeN != null){
			nodeN.data = firstNode.data;
			firstNode = firstNode.next;
			numberOfEntries--;
			result = true;
			nodeN = getReferenceTo(anEntry);
		}
		// 返回删除结果
		return result;
	}
	
	/** 清除包中的所有节点*/
	@Override
	public void clear() {
		// 当包不空时,调用remove()方法删除包中的第一个节点,直到包空为止
		while(!isEmpty()){
			remove();
		}
	}
	
	/** 查找给定值在包中出现的次数*/
	@Override
	public int getFrequencyOf(T anEntry) {
		// 初始化给定值出现的次数为0
		int frequency = 0;
		// 初始化循环计数器为0
		int loopCounter = 0;
		// 将第一个节点的引用赋值给currentNode
		Node currentNode = firstNode;
		
		// 当循环计数器小于节点个数且当前节点不为空时,进入循环
		while((loopCounter < numberOfEntries) && (currentNode != null)){
			// 比较给定值和当前节点的data域,若相同,则将frequency + 1
			if(anEntry.equals(currentNode.data)){
				frequency++;
			}		
			loopCounter++;						// 循环计数器 + 1
			currentNode = currentNode.next;		// 遍历下一个节点
		}
		// 返回给定值在包中出现的频次
		return frequency;
	}
	
	/** 查找包中是否含有给定值,若有则返回true,否则返回false*/
	@Override
	public boolean contains(T anEntry) {
		// 初始化查找标识为false
		boolean found = false;
		// 将第一个节点的引用赋值给currentNode
		Node currentNode = firstNode;
		
		// 当还没有找到给定值且当前的节点不为空时,进入循环
		while(!found && (currentNode != null)){
			// 若当前节点与给定值相等,则将found赋值为true
			if(anEntry.equals(currentNode.data)){
				found = true;
			}
			// 否则,继续遍历下一个节点
			else{
				currentNode = currentNode.next;
			}
		}
		// 返回查找结果
		return found;
	}
	
	/** 将链包中的值赋给数组并返回该数组*/
	@Override
	public T[] toArray() {
		// The cast is safe because the new array contains null entries
		@SuppressWarnings("unchecked")
		T[] result = (T[])new Object[numberOfEntries]; // unchecked cast
		
		// 循环控制索引
		int index = 0;
		Node currentNode = firstNode;
		while((index < numberOfEntries) && (currentNode != null)){
			result[index] = currentNode.data;
			index++;
			currentNode = currentNode.next;
		}
		// 返回链包的数组形式
		return result;
	}
}
package cn.young22.dsa.ch03;

import cn.young22.dsa.ch01.BagInterface;

/**
 * 这个类使用来测试LinkedBag2中新添加的方法的
 * 主要测试了remove系列的方法
 * 这个类的内容与ArrayBagDemo2类的内容类似,
 * 不同点在于:
 * 		由于它们的构造方法不同,在初始化时LinkedBag2类不需要填节点个数
 * 		在ArrayBagDemo2类的基础上抽象了testRemoveAll方法
 * */

public class LinkedBagDemo2 {

	public static void main(String[] args) {
		String[] contentsOfBag = {"A", "A", "B", "A", "C", "fadsd", "A", "A", "F", "G"};
		BagInterface aBag = new LinkedBag2<>();
		
		// Testing method isEmpty()
		testIsEmpty(aBag, true);
		
		// Adding Strings
		testAdd(aBag, contentsOfBag);
		
		// Removing Strings
		String[] testString = {"", "B", "A", "C", "D", "A"};
		testRemove(aBag, testString);
		
		// Testing method contains()
		String[] testContains = {"A", "B", "C", "D", "E"};
		testContains(aBag, testContains);
		
		// Testing method getFrequencyOf
		testFrequency(aBag, testString);
		
		// Tests method removeAll(T anEntry)
		String[] testString1 = {"A"};
		testRemoveAll(aBag, testString1);
		
		
	}

	/** Tests the method add.*/
	private static void testAdd(BagInterface aBag, String[] content)
	{
		System.out.print("Adding ");
		for (int index = 0; index < content.length; index++)
		{
			aBag.add(content[index]);
         System.out.print(content[index] + " ");
		} // end for
      System.out.println();    
		displayBag(aBag);
	} // end testAdd	
	
	/** Tests remove() and remove(T anEntry) methods */
	private static void testRemove(BagInterface aBag, String[] contents){
		for(int index = 0; index < contents.length; index++){
			String aString = contents[index];
			if(aString.equals("") || (aString == null)){
				// test remove()
				System.out.println("\nRemoving a string from the bag");
				String removedString = aBag.remove();
				System.out.println("remove returns " + removedString);
			}else{
				// test remove(T anEntry)
				System.out.println("\nRemoving \"" + aString + "\" from the bag:");
				boolean result = aBag.remove(aString);
				System.out.println("remove(\"" + aString + "\") returns " + result);
			}
			displayBag(aBag);
		}
	}
	
	/** Tests the method removeAll()*/
	private static void testRemoveAll(BagInterface aBag, String[] contents){
		for(int index = 0; index < contents.length; index++){
			String aString = contents[index];
			System.out.println("\nTests method removeAll()");
			boolean success = aBag.removeAll(aString);
			System.out.println("removeAll(\"" + aString + "\") returns " + success);
			displayBag(aBag);
		}
	}

	/** Tests the method toArray while displaying the bag. */
	private static void displayBag(BagInterface aBag)
	{
		System.out.println("The bag contains " + aBag.getCurrentSize() +
		                   " string(s), as follows:");		
		Object[] bagArray = aBag.toArray();
		for (int index = 0; index < bagArray.length; index++)
		{
			System.out.print(bagArray[index] + " ");
		} // end for
		
		System.out.println();
	} // end displayBag
	
	// Tests the method isEmpty
	// correctResult indicates what isEmpty should return
	private static void testIsEmpty(BagInterface aBag, boolean correctResult){
		System.out.print("Testing the method isEmpty with ");
		if(correctResult){
			System.out.println("an empty bag");
		}else{
			System.out.println("a bag that is not empty");
		}
		
		System.out.println("isEmpty finds the bag ");
		if(correctResult && aBag.isEmpty()){
			System.out.println("empty: OK.");
		}else if(correctResult){
			System.out.println("not empty, but it is empty: ERROR");			
		}else if(!correctResult && aBag.isEmpty()){
			System.out.println("empty, but it is not empty: ERROR");
		}else{
			System.out.println("not empty: OK");
		}
		System.out.println();
	}
	
	// Tests the method getFrequency
	private static void testFrequency(BagInterface aBag, String[] tests){
		System.out.println("\nTesting the method of getFrequency of:");
		for(int index = 0; index < tests.length; index++){
			System.out.println("In this bag, the count of " + tests[index] + 
					" is " + aBag.getFrequencyOf(tests[index]));
		}
		System.out.println();
	}
	
	// Tests the method contains
	private static void testContains(BagInterface aBag, String[] tests){
		System.out.println("Testing the method contains:");
		for (int index = 0; index < tests.length; index++){
			System.out.println("Does this bag cotain " + tests[index] +
					"? " + aBag.contains(tests[index]));
		}
	}
}

/*
Output:

Testing the method isEmpty with an empty bag
isEmpty finds the bag 
empty: OK.

Adding A A B A C fadsd A A F G 
The bag contains 10 string(s), as follows:
G F A A fadsd C A B A A 

Removing a string from the bag
remove returns G
The bag contains 9 string(s), as follows:
F A A fadsd C A B A A 

Removing "B" from the bag:
remove("B") returns true
The bag contains 8 string(s), as follows:
A A fadsd C A F A A 

Removing "A" from the bag:
remove("A") returns true
The bag contains 7 string(s), as follows:
A fadsd C A F A A 

Removing "C" from the bag:
remove("C") returns true
The bag contains 6 string(s), as follows:
fadsd A A F A A 

Removing "D" from the bag:
remove("D") returns false
The bag contains 6 string(s), as follows:
fadsd A A F A A 

Removing "A" from the bag:
remove("A") returns true
The bag contains 5 string(s), as follows:
fadsd A F A A 
Testing the method contains:
Does this bag cotain A? true
Does this bag cotain B? false
Does this bag cotain C? false
Does this bag cotain D? false
Does this bag cotain E? false

Testing the method of getFrequency of:
In this bag, the count of  is 0
In this bag, the count of B is 0
In this bag, the count of A is 3
In this bag, the count of C is 0
In this bag, the count of D is 0
In this bag, the count of A is 3


Tests method removeAll()
removeAll("A") returns true
The bag contains 2 string(s), as follows:
fadsd F 

*/

3.2包的链式实现小结

Leave a Reply

Your email address will not be published. Required fields are marked *