集合 (计算机科学)

✍ dations ◷ 2025-12-07 18:18:29 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 楚科奇自治区楚科奇自治区(俄语:Чуко́тский автоно́мный о́круг,罗马化:Chukotsky avtonomny okrug;楚科奇语:Чукоткакэн автономныкэн о
  • 负鼠目 Didelphimorphia负鼠目(学名:Didelphimorphia)是脊索动物门哺乳纲的一目,属于美洲有袋总目,目前仅包含负鼠科一科,大部分生活在南美洲,只有北美负鼠生活在北美洲。
  • 双性性格双性性格(英语:androgyny)指的是一个人同时拥有男性化和女性化两性性格的现象, 他们或者是没有性别特性的价值观,或者是倾向于与自身性别相反的性格。双性格结合了行为上的雌雄通
  • IntuitIntuit Inc.是一家总部位于美国加利福尼亚州山景城的跨国计算机软件公司,主要制作金融和退税相关的软件。 其较著名的产品包括Quicken、TurboTax和QuickBooks。该公司由斯科
  • 英国皇室女王陛下爱丁堡公爵殿下政治主题英国王室由英国君主及其家族所组成。英国君主与其近亲的关系由其名号可知。王室成员虽然没有严格的法律或者正式的定义,并且不同的名单会有不
  • 芷江芷江侗族自治县(芷江县)位于湖南省西部,云贵高原东缘。地图坐标为东经109°17'3″-109°54'49″、北纬27°04'12″-27°38'24″。面积2096平方千米,总人口为354,562人(2004年),国内
  • 巴西红木巴西红木(学名:),又称巴西苏木,豆目豆科苏木属的一种物种,盛产于巴西。生长速度缓慢,木纹直而且木质非常致密坚韧,树干富含水溶性的红色染料成分,古时候主要被当作染料,也是高级的家具
  • 北海郡北海郡,中国古代的郡。汉景帝二年(前155年),削胶西国营陵、淳于、平寿、都昌、斟、桑犊六县置北海郡,治所在营陵县(今山东昌乐县东南五十里),后属青州刺史部。汉武帝时,削胶西国安丘
  • 贾铭贾铭(约1269年-1374年),字文鼎,自号“华山老人”,海宁(今属浙江)人。生于南宋度宗年间,元朝时曾任万户,卒于明朝太祖年间。好饮食养生,甚有心得,朱元璋其问其平日颐养之法,贾铭对曰︰“要
  • 托津托津(满语:ᡨᠣᠵᡳᠨ,穆麟德:,太清:,大词典:;1755年-1835年),字知亭,富察氏,满洲镶黄旗人,清朝大臣。出身不详,初任都察院笔帖式,历官军机章京、工部主事、工部员外郎、户部银库员外郎、掌福