集合 (计算机科学)

✍ dations ◷ 2025-11-13 17:35:04 #数据结构,抽象数据类型

在计算机科学中,集合是一组可变量量的数据项(也可能是0个)的组合,这些数据项可能共享某些特征,需要以某种操作方式一起进行操作。一般来讲,这些数据项的类型是相同的,或基类相同(若使用的语言支持继承)。列表(或数组)通常不被认为是集合,因为其大小固定,但事实上它常常在实现中作为某些形式的集合使用。

集合的种类包括列表,集,多重集,树和图。枚举类型可以是列表或集。

在列表中,数据项的顺序是确定的,也可以存在多个相同的数据项。列表支持的操作包括查找项目并找到其位置(若存在),将项目从列表中删除,在特定位置插入项目等。通常的队列,或称FIFO即是一个列表,该列表只能在一端添加项目,而在另一端删除项目。而栈,或LIFO则只能在同一端添加或删除项目。不管是队列还是栈,集合中项目的顺序都应当是一定的,因此这两种情况只是列表的特例。其它列表支持的操作包括排序,再一次说明了其中顺序的重要性。

列表的具体形式包括数组,链表等。

与列表不同,在集中,数据项是无序的,也不允许存在相同数据项。集支持添加、删除和查找项目。一些语言内建对集的支持,而在其它语言中,可以利用散列表实现集。

多重集的行为类似于集,其中数据项是无序的。但在多重集中,可以存在相同的数据项。多重集支持的操作包括添加、删除项,查询相同项在多重集中出现的次数。多重集可以通过排序转换成列表。

关联数组(或称查找表,字典等)的行为和字典相似,为键(例如字典中的单词)输入提供一个值(如字典中的定义)输出。值可以是对复杂数据结构的引用。通常使用散列表实现高效率的关联数组。

在树中,“根”节点与一定数量的数据项以亲-子关系联系起来,而其子数据项也与另外的数据项以同样的方式联系。除了根节点的每个项都有且只有一个父节点,并可能有一些子节点。树支持的操作包括遍历,插入等。用于排序操作的树通常称为堆。通常使用树来保存存在包含亲-子关系的数据,例如菜单,目录及其中文件等。

在图中,每个数据项都可以与一个或多个其它数据项联系起来,其中每个节点都是平等的,类似于无根节点、无亲-子关系的树。图支持的操作包括遍历,查找等。图常常用于对实际问题进行建模,并解决这些问题。在生成树协议中,创建一张代表网络结构的图(或称网格),从而了解应当断开哪些链路以避免数据回圈。

如上所述,集合,以及集合的各种分类都只是抽象概念。由于名字相同或相似,集合及其在各种语言中的实现常常会造成文字上的混淆。集合,列表,集,树等名字究竟是数据结构,抽象数据类型抑或类只能通过具体分析来确定。其中,集合则是计算问题的解决方案中抽象程度最高的概念。从这个方面来看,若过于关注其实现,则可能会对理解集合的数学概念产生反作用。

相关

  • 定量定量属性是指以数量形式存在着的属性,并因此可以对其进行测量。测量的结果用一个具体的量(称为单位)和一个数的乘积来表示。以物理量为例,距离、质量、时间等都是定量属性。很多
  • 林奈卡尔·冯·林奈(英语:Carl Linnaeus,瑞典语:Carl von Linné,1707年5月23日-1778年1月10日),也译为林内,受封贵族前名为卡尔·林奈乌斯(Carl Linnaeus),由于瑞典学者阶层的姓常拉丁化,又
  • 各家学说中医各家学说是指中国历史上发展出的基于中国医学传统的,以研究、讨论中医学思想理论及临床经验为主的各类中医学学术流派及其学说。而事实上人们所说的各家学说,多指以《黄帝
  • 螺旋压力机螺旋压力机(螺旋压榨机、螺杆挤压机)是一类使用螺杆驱动的机械压力机,通过螺旋将手柄或驱动轮的旋转力矩放大转换为轴向运动。螺旋压力机在公元一世纪由罗马人发明,主要用于葡萄
  • 提婆 (人名)龙树、圣天、无著、 世亲、陈那、法称、 释迦光、功德光 【其他】─ 《入中论》 《释量论》 《俱舍论》 《现观庄严论》 《戒律本论》【其他】─ 提婆(梵语:आर्यदेव,Ar
  • 1欧分硬币1欧分硬币(€0.01)是价值为欧元百分之一的硬币,材料由镀铜钢组成。欧元区内每个国家的硬币都有一个共同的背面和各国(各民族)特定的正面。它是自2002年欧元(以现金形式)面世以来开
  • 区徽区徽可以指:
  • 伊罗姆·沙米拉伊罗姆·查努·沙米拉(英语:Irom Chanu Sharmila)(1972年3月14日-),被尊称为曼尼普尔铁娘子(英语:Iron Lady of Manipur)是一名印度的维权运动人士,她为了反对印度现行的《武装部队特别
  • 埃德温·鲁琴斯埃德温·兰西尔·鲁琴斯爵士 OM, KCIE, PRA, FRIBA(Sir Edwin Landseer Lutyens /ˈlʌtjənz/ ,1869年3月29日-1944年1月1日),或译埃德温·勒琴斯,是一名20世纪英国建筑师,曾任皇家艺
  • 佟图赖佟图赖((满语:ᡨᡠᠩ ᡨᡠᠯᠠᡳ ,穆麟德:;1606年-1658年),初名盛年。初隶汉军正蓝旗下,任汉军正蓝旗都统。佟养真(佟养正)之子。卒于顺治十五年,赐祭葬,赠少保,仍兼太子太保,谥勤襄。先世