9

这是与问题相关的示例代码。此 API 试图将具有邻接列表表示的图实现为由图中每个顶点索引的 Bags 数组。

public class Graph{

private final int V;          //no. of vertices
private Bag<Integer>[] adj;  // A bag for each vertex to store all adjacent vertices
.
.
.
}

在这里使用 Bag 比链表或 Set 有什么优势吗？我知道袋子是无序的，但是当它们不能节省我们的时间或空间时，为什么还要使用无序列表呢？

4

4 回答 4

6

每种数据结构都可以在不同的情况下使用：

Set（特别是HashSet）可以是无序的唯一元素列表。另一方面，Bags是多重集（可能包含重复元素的无序集合）。

至于LinkedList它们提供更简单的链接操作，即在不同的地方添加元素，更容易（恒定时间）。

于 2014-12-25T18:07:51.977 回答
4

Bag 可能使用二叉搜索树或哈希表实现，给我们 O(log n) 或 O(1) 搜索。链表将提供 O(n) 次搜索。

Set 只允许唯一元素，因此如果您需要存储重复项，则需要一个 Bag。Java Collections 库中的 TreeSet 或 HashSet 将分别为我们提供 O(log n) 或 O(1) 搜索。

一般来说，当您经常需要进行搜索或删除操作时，Set 或 Bag 接口会更合适。如果您只需要添加到集合的末尾并对其进行迭代，则不会有太大区别。

于 2014-12-25T18:07:32.723 回答
2

bag、queue 和 stack 等数据类型在接下来要删除或检查的对象的规范上有所不同。

包是不支持删除项目的集合。Bags 的目的是为客户提供收集物品然后迭代它们的能力。

API 包 (Java)

public class Bag<Item> implements Iterable<Item>
    Bag() // creates an empty bag
    void add(Item item)
    boolean isEmpty()
    int size()

包.java

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

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;
    private int n;

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    public Bag() {
        first = null;
        n = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return n;
    }

    public void add(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            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;
        }
    }
}
于 2020-03-19T07:28:32.600 回答
1

除了其他答案之外， Bag 和其他无序数据结构（即 Set）之间的主要区别在于 Bags在添加项目后不支持删除项目。

一个示例用例是一个特殊的日志系统，我们从不打算删除过去的插入。或者确保高度并发系统中的不变性。

请参阅https://algs4.cs.princeton.edu/13stacks/以获取袋子与其他数据结构的准确描述和比较。

于 2020-03-12T15:24:46.027 回答