集合 (计算机科学)

✍ dations ◷ 2025-02-24 07:38:15 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 球囊菌门球囊菌门(学名:Glomeromycota,AM fungi),又称聚合菌门、锈球菌门,是真菌界的一个门,目前约已发现400种物种。本门真菌可与陆生植物形成丛枝菌根(英语:arbuscular mycorrhizas),这种共生
  • 二项式系数在数学上,二项式系数是二项式定理中各项的系数。一般而言,二项式系数由两个非负整数 n 和 k 为参数决定,写作
  • 丙醛C2, C3: sp3丙醛是三个碳的醛,分子式为CH3CH2CHO。它是丙酮的同分异构体,室温下为无色液体,略微带有刺激性的水果气味。丙醛主要通过金属催化剂存在下,混合合成气和乙烯,发生加氢
  • 虱毛目见内文虱毛目(学名:Phthiraptera)是原虱目和食毛目的合称,通称虱或虱子(英语:louse)。全世界约有3,000种。虱寄生于人体、其他哺乳动物(除了单孔目和蝙蝠外)和鸟类的身上。以人类为宿
  • 圣迭戈州立大学圣迭戈州立大学(英语:San Diego State University)是位于美国加利福尼亚州圣迭戈的一所公立大学,始建于1897年,属于加利福尼亚州立大学(CSU)系统中的一员。在美国新闻(U.S.NEWS)202
  • 空心菜蕹菜(学名:Ipomoea aquatica;“蕹”,拼音:wèng),又称空心菜、通菜、通心菜、壅菜、瓮菜、应菜、藤菜及葛菜,为一年生草本植物,茎蔓性,中空,节上能生不定根。应菜,蕹菜(南方草木状、嘉祐
  • 南迈阿密 (佛罗里达州)南迈阿密(英语:South Miami),是美国佛罗里达州下属的一座城市。建立于1926年。面积约 为6平方公里(约合2.3平方英里)。根据2010年美国人口普查,该市有人口11,657人。论人口在本州排
  • 马国翰马国翰(1794年-1857年),字词溪,号竹吾,山东济南历城人,清代目录学家。先世是山东章丘人,曾祖父时迁居历城。父马锦,历任山西汾州府经历、甯乡、武乡、天镇等知县。自幼随父于山西任上
  • 德尔茨巴赫德尔茨巴赫(德语:Dörzbach)是德国巴登-符腾堡州的一个市镇。总面积32.36平方公里,总人口2434人,其中男性1213人,女性1221人(2011年12月31日),人口密度75人/平方公里。
  • 霍赫斯陶芬山坐标:47°45′0″N 12°51′0″E / 47.75000°N 12.85000°E / 47.75000; 12.85000霍赫斯陶芬山(德语:Hochstaufen),是德国的山峰,位于该国南部,由巴伐利亚负责管辖,属于基姆高山脉