集合 (计算机科学)

✍ dations ◷ 2025-11-21 19:43:12 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 心肌炎心肌炎(拉丁语:Myocarditis),也称为炎症性心肌病(Inflammatory Cardiomyopathy),是心肌的炎症。症状可表现为呼吸困难、胸口疼痛(英语:chest pain)、运动能力降低、心律不整等。发病时
  • 毛囊炎毛囊炎(folliculitis)是指葡萄球菌侵入毛囊部位所发生的化脓性炎症。其多发于头部、颈部、臀部、阴部、肛周或身体其他部位,较易复发,性质顽固。
  • 辐射电离辐射(英语:ionizing radiation)是指波长短、频率高、能量高的射线(粒子或波的双重形式)。辐射可分为电离辐射和非电离辐射,电离辐射可以从原子或分子里面电离过程(Ionization)中
  • 唐纳德·戴维森唐纳德·赫伯特·戴维森(英语:Donald Davidson,1917年3月6日-2003年8月30日)20世纪下半叶美国最为著名和活跃的哲学家之一。戴维森1917年3月6日生于美国麻省斯普林菲尔德。在早期
  • 麦克斯韦麦克斯韦(Maxwell),缩写Mx,厘米-克-秒制的磁通量单位。此名称用以纪念苏格兰物理学家詹姆斯·克拉克·麦克斯韦。1900年,麦克斯韦在巴黎举办的International Electrical Congress
  • 玩具总动员《玩具总动员》(英语:Toy Story)是一部于1995年上映的美国计算机动画冒险伙伴(英语:Buddy film)喜剧片,由皮克斯动画工作室制作,华特迪士尼影业发行。该片是约翰·拉塞特的导演处女
  • 浦市镇浦市镇,是中华人民共和国湖南省湘西土家族苗族自治州泸溪县下辖的一个乡镇级行政单位。浦市镇下辖以下地区:十字街社区、太平街社区、新建街社区、印家桥社区、城乡村、黄家桥
  • 阿里山国家风景区坐标:23°31′N 120°48′E / 23.517°N 120.800°E / 23.517; 120.800阿里山国家风景区位于台湾嘉义县东部,是由交通部观光局规划与管理的一座国家级风景特定区,设立于2001年
  • 阿留特语阿留特语(nəməlʔu、Alyutor、Alutor))为俄罗斯联邦远东地区堪察加边疆区阿留特人的语言,属古西伯利亚语言的一种,2010年俄罗斯普查使用的人口约25人。根据UNESCO的濒危语言红
  • 高翔 (清朝)高翔(1688年-1753年),字凤冈,号西唐、樨堂,一作西堂,江苏扬州甘泉人,清朝画家。终身布衣,性格高傲,与石涛、金农、汪士慎为友。世称“扬州八怪”。石涛曾有“谁将一石春前酒,漫洒孤山雪