算法

基础数据结构04：背包

介绍

  背包是一种不支持从中删除元素的集合数据类型。它存在的目的就是帮助收集元素并迭代遍历收集到的元素。迭代的顺序不确定且与用例无关。

API

Java实现

  背包可以使用数组，也可以使用链表来实现。如果使用数组，需要考虑数组的动态扩容。这里使用链表来实现，避免数组扩容的问题。另外沿用上一篇stack的实现，只需要把push方法修改为add方法即可。虽然使用链表后，元素遍历是有一定顺序的，不过没用影响，因为当使用Bag数据结构时，默认会认为遍历的数据是无序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package com.algs.base;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkBag<Item> implements Iterable<Item> {
	private Node first;
	private int N;			// 背包中的元素数量

	// 背包中每个元素的类型为Node
	private class Node{
		Item item;
		Node next;
	}

	public boolean isEmpty(){return N==0;}
	public int size(){return N;}

	// 添加元素(跟栈的push一样)
	public void add(Item item){
		Node oldFirst = first;
		first = new Node();
		first.item = item;
		first.next = oldFirst;
		N++;
	}

	@Override
	public Iterator<Item> iterator()  {
        return new ListIterator();  
    }
	//链表遍历实现
    private class ListIterator implements Iterator<Item> {
        private Node 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) {
    	LinkBag<String> bag = new LinkBag<String>();
    	bag.add("one");
    	bag.add("two");
    	bag.add("three");
		for(String node:bag){
			//打印结果为：three->two->one->
			System.out.print(node+"->");
		}
	}
}

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：基础数据结构03：栈

留言

欢迎交流想法。留言会通过 GitHub Issues 保存，首次使用需要登录 GitHub。