Hello! 欢迎来到小浪资源网!

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


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


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

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

bag 的属性可以定义如下:

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

图2
包类 uml
理解Java中的Bag ADT:一种灵活的数据结构
注意:来自 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。

相关阅读