本文介绍了 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 方法实现了一个简单的杂货店库存管理系统：
即构数智人
即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。
36 查看详情
/** * 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: 50Apples 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：一种灵活的数据结构的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/614409.html
微信扫一扫 
支付宝扫一扫 
