集合 (计算机科学)

✍ dations ◷ 2025-11-20 20:10:28 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 维生素Bsub12/sub缺乏症维生素B12缺乏症指的是血液中维生素B12含量过低的情况。此病症状广泛,可致思考能力下降、人格改变(如抑郁、易怒、思觉失调)、感觉异常(英语:Paresthesia)、反射改变、肌肉功能减
  • 无政府主义与性和爱情大多数男性无政府主义思想家(除了普鲁东)支持女性平权。自由恋爱提倡者有时会把沃伦或其他试验性社群视为思想根源,并视性自由为自我所有权的体现。自由恋爱思潮特别注重妇女权
  • 教育部美国教育部(英语:United States Department of Education,缩写:ED),是美国联邦政府主管联邦教育行政事务的行政部门。1979年10月17日,吉米·卡特总统签署生效《教育部组织法》(Depa
  • 保罗·范迪克保罗·范迪克(Paul van Dyk,本名马蒂亚斯·保罗(Matthias Paul), 1971年12月16日-)是一位曾获葛来美奖的电子舞曲DJ、音乐家和唱片制作人。保罗·范迪克的《Reflections》专辑在200
  • 卜部卜部,就汉字索引来说,是为部首之一,康熙字典214个部首中的第二十五个(两划的则为第十九个)。就中文而言,卜部归于两划部首。卜部从上、下、右方都可为部字,且无其他部首可用者将部
  • 七阶正方形镶嵌在几何学中,七阶正方形镶嵌是由正方形组成的双曲面正镶嵌图,每七个正方形共用一个顶点。在施莱夫利符号用{4,7}表示。七阶正方形镶嵌即每个顶点皆为七个正方形的公共顶点,顶点
  • 王巍 (科学家)王巍(1966年10月9日-),导航、制导与控制专家,2013年当选中国科学院院士,国际宇航科学院通讯院士,研究员,博士生导师。2018年2月24日,当选中华人民共和国十三届全国人民代表大会代表。
  • 先锋号电力动车组DJF2型“先锋号”电力动车组是中国铁路的动力分散式电力动车组车型之一,由南京浦镇车辆厂、上海铁道大学、铁道部科学研究院、株洲电力机车研究所等单位于2001年研制成功,为中
  • 凤头鹮凤头鹮(),又名凤头朱鹭,是一种大型的朱鹭。它们长达76厘米,呈深褐色,有白色胡子,双翼呈紫色,有绿色光泽。喙呈黑色,上颌有红色斑纹,双脚也是黑色的。凤头鹮分布在苏丹、埃塞俄比亚、塞
  • 色姆布·贡其格苏姆拉色姆布·贡其格苏姆拉(蒙古语:Сэмбийн Гончигсумлаа,1915年2月18日-1991年2月25日),蒙古国最重要的古典音乐作曲家之一。出生于蒙古国巴彦洪戈尔省,早年曾前往