集合 (计算机科学)

✍ dations ◷ 2025-11-23 13:06:43 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 迈克尔·沃特曼迈克尔·斯宾塞·沃特曼(英语:Michael Spencer Waterman,1942年6月28日-),美国生物信息学家,南加州大学数学与计算机科学学院联合主任。此前,他曾在洛斯阿拉莫斯国家实验室和爱达荷
  • 活性度化学中,活性(Activity)即某物质的“有效浓度”,或称为物质的“有效莫尔分率”。此概念由吉尔伯特·牛顿·路易斯首先提出。将理想混合物中组分i的化学势表示式中的莫尔分率(xi)替
  • 猪形亚目猪形亚目(学名:Suina)是偶蹄目的一个演化支,包含了所有亲缘上与猪科相近、离反刍动物较远的物种。本亚目是全撰类的演化支,鲸反刍类则成为本亚目的姐妹群,本亚目与其它偶蹄目的关
  • 金融情报办公室金融情报办公室(葡文;Gabinete de Informação Financeira, GIF)是澳门特别行政区政府保安司辖下的部门,于2006年8月8日成立,最初隶属经济财政司。于2018年10月16日改隶属保安司
  • 高加索高加索(格鲁吉亚语:კავკასია;车臣语、俄语:Кавказ; 旧名太和岭)是位于西亚及东欧交界处,黑海、里海之间高加索山脉的地区,总面积约44万平方公里。该地名根据古罗马学
  • 前列腺素E1前列腺素E1(Prostaglandin E1;PGE1),亦称前列地尔(Alprostadil) 是一种前列腺素,常用于治愈勃起障碍、 进行血管舒张等。前列地尔在美国主要被当做尿道栓剂和血管注射剂。栓剂的商
  • 伊美黛·史道顿伊美黛·玛丽·菲洛梅娜·贝尔纳黛特·史道顿,CBE(英语:Imelda Mary Philomena Bernadette Staunton,1956年1月9日-),英格兰女演员。2004年,她因演出《维拉·德雷克》而获得威尼斯电
  • 约翰·哈钦松约翰·哈钦松,OBE,FRS(英语:John Hutchinson)(1884年4月7日-1972年9月2日)是英国植物学家,对植物分类学有很大贡献。 哈钦松出生于诺森伯兰郡的伯里本,他在达勒姆接受了园艺训练,1904年
  • 新垣世璋新垣世璋(琉球语:新垣 世璋/アラカチ シーショー ;日语:新垣 世璋/あらかき せいしょう ;1840年-1920年)是活跃于琉球王国第二尚氏王朝末期和日本冲绳县时期的唐手武术家。为唐手中
  • 海因里希·冯·赫尔佐根伯格海因里希·彼得·弗雷赫尔·冯·赫尔佐根伯格(德语:Heinrich Peter Freiherr von Herzogenberg,1843年6月10日-1900年10月9日),法国血统的奥地利作曲家。他是法国贵族的后裔,早年先