集合 (计算机科学)

✍ dations ◷ 2025-05-10 19:09:45 #数据结构,抽象数据类型

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

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

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

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

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

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

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

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

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

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

相关

  • 个体个体(英语:individual),一般指一个人或是一个群体中的特定主体,指人时也称个人。个体性(英语:individuality,或selfhood),又称个性,则是指能够成为一个个体的特性或是状态。在生物学中,
  • Wiki引擎Wiki引擎,或称为Wiki软件,是指用来架设Wiki的软件。广义来说,即是一种软件能作为网络共笔,供网民自行编辑,并最终集合成完整的数据库。狭义来说,即是能达成维基百科样式的软件。由
  • 台湾电视博览馆本段时间均以二十四小时制东八区时间(UTC+8)为准。台湾电视博览馆(英语:Taiwan Television Exposition)是台湾电视公司(台视)创办的台湾第二个电视博物馆,2004年4月28日开馆,2008年1
  • 德累斯顿德累斯顿轰炸(1945年2月13日-2月15日)是二战期间由英国皇家空军和美国陆军航空军对德国东部城市德累斯顿联合发动的大规模空袭行动。由于盟军的轰炸造成了2万人以上的平民死亡
  • 文莱暴乱英联邦决定性胜利1963年1964年1965年文莱暴乱(马来语:Pemberontakan Brunei)是1962年12月在英国的保护国文莱发生的一场反对君主制以及加入马来西亚联邦提议的暴乱。这场叛乱由
  • 磁振脉冲序列磁振脉冲序列(MR pulse sequence)出现在核磁共振相关的领域,包括了传统的核磁共振频谱(1952年)、磁振造影以及核磁共振量子电脑(简称磁振量脑)。历史上,一开始脉冲序列是只有
  • 第五云雀军团第五云雀军团(英语:Legio V Alaudae)古罗马军队建制名称。由尤利乌斯·凯撒于公元前52年在高卢建立。该军团主要由高卢人组成,绝大部分士兵在加入军团时不具备罗马公民权,不符合
  • 蒙古入侵波兰蒙古在成吉思汗的带领下,自十三世纪起进行了大规模的征战行动,其入侵欧洲的最终目标为占领匈牙利及保加利亚,并借此创造有利的政战形势以攻击拜占庭帝国。1240年至1241年蒙古入
  • 佐藤江梨花佐藤江梨花(1986年6月8日-),日本前模特儿及AV女优。佐藤江梨花最初为模特儿,于2005年12月发表首支成人影片作品《BODY TO BODY》,移籍到桃太郎映像出版后大受欢迎,作品包括《超极级
  • 玩偶玩偶一词泛指模仿人或动物造型的赏玩物品,其中形若人类的称为人偶。人偶、玩偶的外型面貌,从抽象到拟真,涵盖不同种族、年龄、性别的外型,因各国、各民族的需求与文化背景而发展