集合 (计算机科学)

✍ dations ◷ 2024-12-23 08:34:41 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 内细胞团内细胞团(英语:Inner cell mass,缩写:ICM、内细胞群)是大多数真兽类哺乳动物在胚胎发生中的一个早期阶段,又称胚细胞(embryoblast)。是一团位于初期胚胎中的一个细胞团块,也是最后将
  • 环加氧酶环氧合酶(拉丁语:Cyclooxygenase,简称COX)是一种酶(又名酵素),负责合成重要的生物激素——前列腺素家族的导介物质。当身体组织受到某种刺激如外伤、感染等会激活环氧合酶,使花生四
  • 沉香木沉香木(Agarwood)指的是沉香属里的树木,但是沉香木这个俗称也普遍形容一些产生了“结香”效果之后而有了“沉香”味的特定树木。俗称沉香指的是沉香属植物流出的树脂与木质结合
  • 亚硫酸根亚硫酸盐是亚硫酸所成的盐,含有亚硫酸根离子SO32−。亚硫酸根离子是强还原剂,因此可以利用强还原剂(如溴、酸化过锰酸盐、酸化重铬酸盐)来检验。会使溴水褪色。绝大多数葡萄酒中
  • 胡经甫胡经甫(1896年11月21日-1972年2月1日),原名宗权、笔名胡烈,祖籍广东三水,出生于上海,昆虫学家,中国昆虫学的奠基人之一。由他编著的《中国昆虫名录》是中国昆虫学研究史上的重要著作
  • 犬部犬部,为汉字索引中的部首之一,康熙字典214个部首中的第九十四个(四划的则为第三十四个)。就繁体和简体中文中,犬部归于四划部首。犬部通常是从下、左、右方均可为部字。当左为部
  • 联璧金融上海联璧金融有限公司,原名上海联币有限公司,是成立于2012年的一家网络货款平台公司,以高额返利模式吸引投资者。2018年6月暴发财务问题而停业。联璧金融CEO为云南人侬锦。该公
  • 冲绳海槽以下是与本页面相关的转换组:冲绳海槽(日语:沖縄トラフ/おきなわとらふ ,英语:Okinawa Trough),狭义说法是位于日本九州琉球群岛西方和台湾本岛东北方之间;广义说法是位于台湾宜兰县
  • 艾米·汉莫亚曼德·道格拉斯·“艾米”·汉默(英语:Armand Douglas "Armie" Hammer,1986年8月28日-)是一名美国男演员,知名作品如电影《社交网络》(2010年)、《胡佛传》(2011年)和《秘密特工》(20
  • 利格牛肝菌 C. Martín 1894 sensu auct. mult.利格牛肝菌(学名:),是一种担子菌门真菌,隶属于牛肝菌属。这种真菌分布于欧洲,并且是有毒的。其有毒成分主要引发人体胃肠道症状,并且与魔牛肝