集合 (计算机科学)

✍ dations ◷ 2025-09-09 23:56:39 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 可萨人可萨人,也译作卡扎人、哈扎尔人,常指一西突厥的属部落,他们的汗国是中世纪初期最大的汗国。最早见于《隋书·北狄传》,《旧唐书·西戎传》和《新唐书·西域传下》称其为“突厥可
  • Ksup+/sup通道在细胞生物学的范畴,钾离子通道是最广泛分布的离子通道,且几乎存在大多数的生物中。 它们具有钾离子选择性的孔洞在细胞膜上,并且存在于大多数的细胞,控制了广泛的生物功能。钾
  • 约翰·菲尔德约翰·菲尔德(英语:John Field,1782年7月26日-1837年1月23日),爱尔兰钢琴家,作曲家。菲尔德出生在一个新教家庭,自幼学习钢琴,10岁时公开演出,11岁随家人移居伦敦,师从穆齐奥·克莱门蒂
  • 朱里亚·克劳狄王朝儒略-克劳狄王朝(Julio-Claudian Dynasty,前27年-68年),罗马帝国建立者屋大维与其家族形成的王朝,是罗马帝国第一个王朝。儒略-克劳狄王朝建立者屋大维,其在结束罗马共和末期的混
  • 睾丸静脉精索静脉(英语:spermatic vein)或称睾丸静脉(testicular vein),是男性的生殖腺静脉(gonadal vein),其功能为从其相应的睾丸运载缺氧血至下腔静脉或其支流。对于男性而言精索静脉相
  • 延津县延津县是中华人民共和国河南省新乡市下辖的一个县。延津县位于河南省北部,开封市西北部。西距新乡37公里,南望郑州93公里,东南至开封50公里,北距安阳130公里。区域南北宽45.5公
  • 朱利乌斯·本尼迪克特朱利乌斯·本尼迪克特爵士(Sir Julius Benedict 1804年11月27日-1885年6月5日)是一名德裔英格兰作曲家、指挥家。他出生于斯图加特,师从约翰·尼波默克·胡梅尔和卡尔·马利亚
  • 瓦西里·弗拉基米洛维奇·巴托尔德瓦西里·弗拉基米洛维奇·巴托尔德(俄语:Василий Владимирович Бартольд)俄罗斯东方学学者,在突厥语民族以及中古伊斯兰史等领域研究卓著,一生撰写了
  • 江户四大饥荒江户四大饥荒,为日本江户时代因为长期的寒害、干旱、水灾等天气异常与虫害、火山爆发等原因而长期欠收造成的饥荒中最严重的四次。通常被称为四大饥荒的为以下四者。另外也常
  • 道义经济道义经济(英语:Moral economy),经济人类学概念,指传统社会中农村的经济模式,当中农民不单追求个人利益最大化,也受道德准则和价值观所驱使,在避免风险和安全第一的原则下,遵从“互惠