背包是一种不支持从中删除元素的集合数据类型。
就像是一只貔貅，只进不出。也可以说是像张伟。
背包上的操作
背包的API:
/*public class Bag<Item> implements Iterable<Item>
Bag() 创建一个空背包
void add(Item item) 添加一个元素
boolean isEmpty() 背包是否为空
int size() 背包中的元素数量
*/
通过API我们知道，我们能够迭代背包中的元素，向背包中添加元素，检查背包是否为空，检查背包中元素的数量，但是，我们不能删除背包中的元素。背包中元素的迭代顺序是不确定的。
背包的链表实现:
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item>{
//定义节点内部类,一个Node表示链表的一个节点
private class Node{
Item item;
Node next;
}
//链表的首节点
private Node first;
private int count;
//创建一个空背包
public Bag(){
count = 0;
}
//添加一个元素
public void add(Item item){
if (first == null){
first = new Node();
first.item = item;
}else {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
}
count++;
}
//判断背包是否为空
public boolean isEmpty(){
return count==0;
}
//获得背包中的元素数量
public int size(){
return count;
}
//实现Iterator接口
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
以上就是背包的一个基本的链表实现
挑战－－随机背包
具体思路：
用数组来存储背包中的元素，在返回迭代器之前打乱数组
import java.util.Iterator;
public class RandomBag<Item> implements Iterable {
//用来存储吃进来的元素的数组
private Item[] items;
//用来统计吃进来的元素的个数的实例变量
private int count;
//构造方法
public RandomBag(){
items = (Item[]) new Object[1];
count = 0;
}
//添加一个元素
public void add(Item item){
if (count == items.length){
resize(2*items.length);
items[count] = item;
}else{
items[count] = item;
}
count++;
}
//当数组容量不足的时候将数组的容量加倍
void resize(int newSize){
Item[] newItems = (Item[]) new Object[newSize];
for (int i = 0; i < items.length; i++) newItems[i] = items[i];
items = newItems;
}
//检查背包是否为空
public boolean isEmpty(){
return items.length == 0;
}
//检查背包中的元素个数
public int size(){
return count;
}
//实现迭代协议
@Override
public Iterator iterator() {
/*
* 在返回迭代器之前打乱数组顺序(洗牌算法)
* */
for (int i = 0; i < count; i++){
Item temp = items[i];
int selected = i + (int) (Math.random()*(count - i));
items[i] = items[selected];
items[selected] = temp;
}
/*
* */
return new RandomBagIterator();
}
private class RandomBagIterator implements Iterator<Item>{
private int current;
public RandomBagIterator(){
current = 0;
}
@Override
public boolean hasNext() {
return current < count;
}
@Override
public Item next() {
Item item = items[current];
current++;
return item;
}
}
}
打乱数组的方式：
从左往右，依次从右边剩余元素中随机选择一个元素与左边的元素对换。
资源及参考
本笔记是学习普林斯顿大学算法课程以及阅读其教材《算法》第四版所作
