集合 (计算机科学)

✍ dations ◷ 2025-11-22 11:34:02 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 德热纳皮埃尔-吉勒·德热纳(法语:Pierre-Gilles de Gennes,1932年10月24日-2007年5月18日),法国物理学家,1991年获诺贝尔物理学奖。2007年5月18日于奥赛逝世。德热纳1932年生于巴黎,1961年
  • 地星目Geasteroides 地星属 Geastrum 多口地星属 Myriostoma Nidulariopsis Phialastrum Radiigera Schenella 弹球菌属 Sphaerobolus地星是指伞菌纲地星目(学名:Geastrales)下的真菌
  • 金衢片金衢片,是吴语的一个方言片,主要分布在金衢盆地,人口620万,占吴语人口总数的12.4%。 在旧分区法中,金衢片的大部分地区属于婺州片,其余地区属于处衢片。金衢片内部差异较大,有些县
  • 中残联中国残疾人联合会(英语:China Disabled Persons Federation),简称中国残联,是由中国各类残疾人代表和残疾人工作者组成的全国性残疾人事业团体。中国残联是在1953年成立的中国盲
  • 卡罗尔·格雷德卡罗琳·维德尼·卡罗尔·格雷德(英语:Carolyn Widney "Carol" Greider,1961年4月15日-),美国分子生物学家,现任约翰·霍普金斯大学分子生物学与遗传学系教授。她因为“发现端粒和
  • 开前圆唇元音开前圆唇元音是元音的一种,用于一些语言当中,国际音标以⟨ɶ⟩代表此音,而X-SAMPA音标则以⟨&⟩代表此音。⟨ɶ⟩是⟨Œ⟩的一个小体大写字母。表内成对的元音分别为不圆唇/圆唇
  • 伊朗共产党 (1983年)伊朗共产党(波斯语:حزب کمونیست ایران)是伊朗的一个非法的共产主义政党。1983年,该党成立于伊朗库尔德斯坦,由共产主义战斗者联盟和伊朗库尔德斯坦革命劳动者协会
  • 鲁思·本尼迪克特瓦萨学院英国文学学士(1909年)Frederick Fulton 鲁思·本尼迪克特(Ruth Benedict,原姓Fulton,1887年6月5日-1948年9月17日),美国人类学家。20世纪初少数的女性学者,受到法兰兹·鲍亚
  • 弗兰季舍克·克里格尔弗兰季舍克·克里格尔(捷克语:František Kriegel,1908年4月10日-1979年12月3日),是一名医生,捷克斯洛伐克共产党领导人之一,亚历山大·杜布切克的改革伙伴。。
  • 选情告急《选情告急》(英语:)是一部HBO自制的剧情片,由导演杰洛奇执导、编剧丹尼史壮改编。故事主要描写2008年美国总统大选期间,共和党候选人参议员约翰·麦肯(艾德·哈里斯饰)与搭挡阿拉