理解Java中的Bag ADT：一种灵活的数据结构

本文介绍了 java 中的 bag 抽象数据类型 (adt)，重点介绍了它处理具有重复元素和动态调整大小的无序集合的能力。通过详细的实现示例，它演示了 bag adt 如何提供有效的解决方案来管理库存系统等实际应用程序中的集合。

在计算机科学中，抽象数据类型（adt）对于管理和组织数据至关重要。它们可以被定义为“描述数据集以及对该数据的操作的规范”（carrano & henry，2018）。在java中，adt广泛用于包、栈、队列、集合等集合的开发。本文重点介绍 bag adt，它允许重复元素、支持动态调整大小并提供处理无序集合的灵活性。 java 中的 bag 类型是属于 collection 类的基本数据类型，见图 1。

图1可更新集合注意：链接缓冲区是 updatablebag 的实现，由任意数量的保存元素的缓冲区组成，排列在列表中。每个缓冲区保存一个元素数组。 arbtree 是 updatablebag 的实现，elementsortedcollection 实现红黑树，一种平衡排序二叉搜索树的形式。摘自 lee (n. d.) 的收藏包概述。

bag 的属性可以定义如下：

• 重复 — 允许重复。
• 无序 — bag 元素未排序。
• 动态调整大小 — 大小可以动态更改。
• 可迭代——在 java 中，包是可以迭代的。
• 无索引 — 包元素未建立索引。
• 高效的添加操作 - 将元素添加到包中通常是 o(1) 操作。
• 支持集合操作。见图2。
• 通用类型——包可以容纳任何类型的元素。
• 没有键值对 — 包存储没有关联键的元素。
• 可变 — 包的内容在创建后可以更改，可以动态调整大小。
• 支持空元素 - 包可能允许空元素。

图2包类 uml注意：来自 carrano 和 henry 的《data structures and abstractions with java》（第五版）（2018 年）。

在 java 编程语言的上下文中，堆栈、队列、

• linkedlist、set 和 bag 可以描述如下：
• 堆栈是具有特定删除顺序的元素集合的adt = lifo（后进先出），允许重复。
• 队列是具有特定移除顺序的元素集合的adt = fifo（先进先出），允许重复。
• linkedlist 是列表的实现。
• set 是元素集合的 adt，不允许重复。
• bag是允许重复的元素集合的adt。

换句话说，任何包含元素的集合都是collection，任何允许重复的集合都是bag，否则就是set。 （马托尼，2017）

立即学习“Java免费学习笔记（深入）”；

bag 的主要好处是它允许重复和迭代，它也是可变的，允许动态调整其元素的大小和修改。换句话说，“如果不需要重复项，您可以使用 set 而不是 bag。此外，如果您关心删除顺序，您会选择堆栈或队列，它们基本上是具有特定删除顺序的包。您可以将 bag 视为 stack 和 queue 的超类型，它通过特定操作扩展其 api”（matoni，2017）。下面的程序是 bag adt 方法对杂货库存的简单实现的示例。

bag 类实现 bag adt

import java.util.iterator;
import java.util.nosuchelementexception;

/**
 * a simple implementation of a bag adt (abstract data type). it implements a
 * linked structure systems, a chain data structure. [item | next] -> [item |
 * next] -> [item | next] -> null.
 * 
 * @param  the type of elements held in this bag
 *
 * @author alejandro ricciardi
 * @date 08/12/2024
 */
public class bag implements iterable {
 private node headnode; // the first node in the bag list
 private int size; // number of node in the bag

 /**
  * private inner class that creates a node in the linked structure. each node
  * contains an item and a reference to the next node. [item | next] -> [item |
  * next] -> [item | next] -> null
  * 
  */
 private class node {
  t item; // the item stored in the node
  node next; // reference to the next node
 }

 /**
  * constructs an empty bag.
  */
 public bag() {
  headnode = null; // initialize the first (head) node in the bag to null   
                              (empty bag)
  size = 0; // initialize size of the bag to 0
 }

 /**
  * adds the specified item to this bag. this operation runs in constant time
  * o(1).
  *
  * @param item the item to add to the bag
  */
 public void add(t item) {
  node nextnode = headnode; // save the current head node becoming the next 
                                    // node in the added node
  headnode = new node(); // create a new node and make it the head node
  headnode.item = item; // set the item of the new node
  headnode.next = nextnode; // link the new node to the old head node
  size++; // increment the size of the bag
 }

 /**
  * removes one item from the bag if it exists. this operation runs in linear
  * time o(n) in the worst case.
  *
  * @param item the item to remove
  * @return true if the item was found and removed, false otherwise
  */
 public boolean remove(t item) {
  if (headnode == null)
   return false; // if the bag is empty, return false

  if (headnode.item.equals(item)) { // if the item is in the first node
   headnode = headnode.next; // make the next node the new head node
   size--; // decrement the size
   return true;
  }

  node current = headnode;
  while (current.next != null) { // iterates the linked structure
   if (current.next.item.equals(item)) { // if the next node contains  
                                                      // the item
    current.next = current.next.next; // remove the next node from 
                                                       // the chain
    size--; // decrement the size
    return true;
   }
   current = current.next; // move to the next node
  }
  return false; // item not found in the bag
 }

 /**
  * returns the number of items in this bag.
  *
  * @return the number of items in this bag
  */
 public int size() {
  return size;
 }

 /**
  * checks if this bag is empty.
  *
  * @return true if this bag contains no items, false otherwise
  */
 public boolean isempty() {
  return size == 0;
 }

 /**
  * returns an iterator that iterates over the items in this bag.
  *
  * @return an iterator that iterates over the items in this bag
  */
 public iterator iterator() {
  return new bagiterator();
 }

 /**
  * private inner class that implements the iterator interface.
  */
 private class bagiterator implements iterator {
  private node current = headnode; // start from the first (head) node

  /**
   * checks if there are more elements to iterate over.
   *
   * @return true if there are more elements, false otherwise
   */
  public boolean hasnext() {
   return current != null;
  }

  /**
   * returns the next element in the iteration.
   *
   * @return the next element in the iteration
   * @throws nosuchelementexception if there are no more elements
   */
  public t next() {
   if (!hasnext())
    throw new nosuchelementexception();
   t item = current.item; // get the item from the current node
   current = current.next; // move to the next node
   return item;
  }
 }
}

groceryinventory 使用 bag adt 方法实现了一个简单的杂货店库存管理系统：

/**
 * a simple grocery store inventory management system using a bag adt.
 * 
 * @author alejandro ricciardi
 * @date 08/12/2024 
 */
public class groceryinventory {
    // the bag adt used to store items
    private bag inventory;

    /**
     * constructs a new grocoryinventory 
     */
    public groceryinventory() {
        inventory = new bag<>();
    }

    /**
     * adds items to the inventory.
     * 
     * @param item the name of the item to add.
     * @param quantity the number of items to add.
     */
    public void addshipment(string item, int quantity) {
        // add the item to the bag 'quantity' times
        for (int i = 0; i < quantity; i++) {
            inventory.add(item);
        }
    }

    /**
     * removes item from the inventory.
     * 
     * @param item the name of the item to remove.
     * @return true if the item was successfully removed, false otherwise.
     */
    public boolean sellitem(string item) {
        return inventory.remove(item);
    }

    /**
     * counts the number of a specific item in the inventory (duplicates).
     * 
     * @param item the name of the item to be counted.
     * @return the number of this item in the inventory.
     */
    public int getitemcount(string item) {
        int count = 0;
        // iterate through the bag and count the number of the given item in it
        for (string s : inventory) {
            if (s.equals(item)) {
                count++;
            }
        }
        return count;
    }

    /**
     * main method.
     */
    public static void main(string[] args) {
        groceryinventory store = new groceryinventory();

        // add inventory
        store.addshipment("apple", 50);
        store.addshipment("banana", 30);
        store.addshipment("orange", 40);

        // initial apple count
        system.out.println("apples in stock: " + store.getitemcount("apple"));

        // selling apples
        store.sellitem("apple");
        store.sellitem("apple");

        // apple count after selling
        system.out.println("apples after selling 2: " + 
                            store.getitemcount("apple"));
    }
}

输出

Apples in stock: 50
Apples after selling 2: 48

bag adt 在这个例子中很有用，因为它是可迭代的，它可以存储同一对象的多个实例（例如，像苹果这样的重复项），并创建一个抽象来简化对项目数据的操作，并且不需要项目待订购。与数组不同，bag 不需要固定大小，可以根据需要动态调整大小。此外，它们（对于本示例）比列表更好，因为它们不需要订购物品（例如，苹果可以存储在香蕉之后或之前）。此外，它们比 sets 更好（对于本例），因为它们允许重复（例如，您可以在商店里拥有多个苹果）。

换句话说，在这个例子中很有用并且更好，因为：

• 您可以轻松添加多个苹果或香蕉 (addshipment)。
• 您可以在单个商品售出后将其移除 (sellitem)。
• 您可以计算您拥有的每件物品的数量 (getitemcount)

总之，java 中的 bag adt 是一种灵活且高效的管理元素集合的方法，特别是在需要重复和动态调整大小时。它是一个简单但功能强大的结构，允许轻松添加、删除和迭代元素，使其成为库存系统等应用程序的理想选择，如杂货店示例所示。

参考文献：

carrano, f.m. 和 henry, t.m.（2018 年，1 月 31 日）。 java 的数据结构和抽象（第五版）。皮尔逊。

lee, d. (n. d.)。收藏包概述 [doug lea 的主页]。纽约州立大学计算机科学系。 https://gee.cs.oswego.edu/dl/classes/collections/

马托尼（2017 年，4 月 15 日）。在 java 中使用 bag 的原因 [post]。堆栈溢出。 https://stackoverflow.com/questions/43428114/reasons-for-using-a-bag-in-java

最初于 2024 年 10 月 3 日发表于 alex.omegapy - medium。

以上就是理解Java中的Bag ADT：一种灵活的数据结构的详细内容，更多请关注图灵教育其它相关文章！