算法第四版P98 算法1.4背包,基于链表结构来实现背包的功能

亦凉 2022-03-19 15:35 115阅读 0赞

# 概念 #

背包可以理解成为阉割版本的栈或者队列  
不在乎先进先出还是后进后出  
只在乎可以存放内容,并且可以迭代拿出来就可以了  
于是,我们可以通过栈的方法来实现背包,删掉pop取的功能就行了  
下面的代码是通过链表来实现背包的,迭代顺序是后进先出的

# java代码 #

package book1_3;
    
    import java.util.Iterator;
    
    /**
     * @description: ${description}
     * @create: 2019-02-17
     * 基于LinkedList数据结构的Bag,后进先出(可随意)
     * 成员变量first n
     * 方法:isEmpty size add iterator
     **/
    public class LinkedListBag<Item> implements Iterable {
        private class Node {
            Item item;
            Node next;
        }
    
        private Node first;
        private int n;
    
        public boolean isEmpty() {
            return n == 0;
        }
    
        public int size() {
            return n;
        }
    
        public void add(Item item) {
            //在集合的头部插入元素
            Node old = first;
            first = new Node();
            first.item = item;
            first.next = old;
        }
    
        @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;
            }
        }
    
        public static void main(String[] args) {
            LinkedListBag<String> bag = new LinkedListBag<String>();
            bag.add("a");
            bag.add("b");
            bag.add("c");
            bag.add("d");
            bag.add("e");
            bag.add("f");
            for (Object s : bag
            ) {
                System.out.print(s + " ");
            }
        }
    }

# 运行结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 心得 #

会写栈和队列之后.背包是相对比较简单的,没啥好说的  
只是打个基础吧

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220319/88c0e7993ddc4c73bffc400ec9c5dae5.png