《数据结构与算法C语言描述中文.doc》由会员分享，可在线阅读，更多相关《数据结构与算法C语言描述中文.doc（438页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 .前言数据结构与算法的学习对于进行软件开发的专业程序员而言是非常关键的。虽然有许许多多关于数据结构与算法的书籍，但是这些书籍通常都是大学教材，而且是用在大学里经典讲授的Java语言或C+语言编写的。C#语言正在成为一种广受欢迎的编程语言。这本书为C#语言程序员提供了学习基础数据结构与算法的机会。C#语言根植在一个功能非常丰富的.NET框架开发环境中。在.NET框架库中包含有一套数据结构类（也称为集合类）。这套类的围从Array类、ArrayList类和Collection类到Stack类和Queue类，再到Hashtable类和SortedList类。学习数据结构与算法的学生在学习如何实现它
2、们之前可以先明白如何使用数据结构。以前老师在构建完整的堆栈数据结构之前只能抽象地讲解堆栈的概念。而现在老师可以立刻通过示数据结构工具来向学生们展示如何用堆栈执行一些计算，比如数制之间的转换。有了这些知识后，学生可以课后学习数据结构（或算法）的基本原理，甚至可以构造属于他们自己的实现。本书把所有认真的计算机程序员们需要知道和了解的数据结构与算法的实践概述作为主要的写作容。由于这种情况，本书没有涵盖数据结构与算法的正规的分析。因此，本书没有一个数学公式，也一次没有提与大O分析（如果你不知道大O分析的含义，查看参考文献中提到的任何一本书都可以）。取而代之的，本书把各种各样的数据结构与算法表示成求解问
3、题的工具。书中讨论的数据结构与算法用简单的时间测试来进行性能比较。前提条件阅读本书的唯一前提条件就是需要读者对C#语言有大概的了解 。如果会用C#进行面向对象编程更好。章节组织第1章向读者介绍数据结构作为数据集合的概念。介绍线性和非线性集合的概念。示说明了Collection类。本章还介绍泛型编程的概念。泛型编程允许程序员编写一个类或一种方法，并且把它用于众多数据类型。泛型编程是C#语言一种重要的新特性（在C#2.0以与更高版本中可用）。这种特性是如此重要以至于在System.Collections.Generic命名空间中存在一个专门的泛型数据结构库。当数据结构具有在此库中能找到的泛型实现时
4、，就会讨论它的用途。本章结尾处介绍了衡量书中讨论的数据结构与算法性能的方法。第2章提供了数组构造方法的回顾，并连同示例说明了Array类的特征。Array类把许多与数组相关的函数（UBound函数、LBound函数等等）封装到单独一个包中。ArrayLists是数组的一种特殊类型，它支持动态地调整容量。第3章是对基础排序算法的介绍，例如冒泡排序和插入排序。而第4章则研究了用于存查找的最基本算法，顺序查找和二叉查找。第5章探讨了两种经典的数据结构：堆栈和队列。本章节强调的重点是这些数据结构在解决日常数据处理问题中的实际应用。第6章讲述了BitArray类。这种类可以用于有效地表示大量整数值，比如
5、测试成绩。数据结构的书常不包含字符串，但是第7章介绍了字符串、String类和StringBuilder类。这是因为在C#语言中许多的数据处理是在字符串上执行的，读者应该接触基于这两种类的特殊方法。第8章分析了用于文本处理和模式匹配的正则表达式的使用。与较传统的字符串函数和方法相比，正则表达式常常会提供更强大更有效的处理。第9章向读者介绍作为数据结构的字典的使用。字典和基于字典的不同数据结构把数据作为键/值对来存储。本章向读者说明了如何创建基于DictionaryBase类的他或她自己的类。DictionaryBase类是一个抽象类。第10章包括散列表和HashTable类。HashTable
6、类是字典的一种特殊类型，它用散列算法对部数据进行存储。链表作为另外一种经典的数据结构是在第11章介绍。链表在C#语言中不像在C+这样基于指针的语言中那样重要，但是它始终在C#编程中发挥作用。第12章为读者介绍另一种经典数据结构二叉树。二叉查找树作为二叉树的特殊类型将是本章的主要容。其他二叉树类型在第15章进行介绍。第13章向读者说明在集合中存储数据的方法。这种方法在数据结构只存储唯一数据值的情况下是很实用的。第14章涵盖了高级排序算法，包括流行且高效的快速排序算法。此算法是大多数在.NET框架库中实现的排序程序的基础。第15章会看到三种数据结构。在无法使用二叉查找树的时候，这三种数据结构证明对
7、查找是很有用的。他们是：AVL树、红黑树和跳跃表。第16章讨论了图以与图的算法。图在表示许多不同的数据类型时非常有用，特别是网络的情况。最后，第17章向读者介绍真正的算法设计技巧是什么：动态算法和贪心算法。 致 在这里我要感来自各界帮助我完成此书的人们。首先，我要感首批聆听我讲授数据结构与算法开发课程的学生们。这些学生包括有（排名不分先后）：Matt Hoffman、Ken Chen、 Ken Cates、Jeff Richmond以与Gordon Caffey。此外，要感我在普拉斯基科技学院的同事Clayton Ruff。他多次旁听我的课程并且提出了建议和批评。我还要感系主管David Du
8、rr和系主席Bernica Tackett支持我的写作努力。而且，我要感我的家人在我全身心投入研究和写作时对我的容忍。最后，我要感剑桥的编辑Lauren Cowles和Heather Bergman，感他们容忍我的许多问题，更改容和经常的延迟。目 录前言 1前提条件 1章节组织 1第1章 Collections类、泛型类和Timing类概述 181.1群集的定义 181.2群集的描述 181.2.1直接存取群集 181.2.2顺序存取群集 201.2.3层次群集 211.2.4组群集 221.3 CollectionBase类 221.3.1用ArrayLists实现Collection类 2
9、21.3.2定义Collection类 231.3.3实现Collection类 231.4型编程 241.5时间测试 251.5.1一个简单化的时间测试 251.5.2用于.NET环境的时间测试 261.5.3Timing Test类 27小结 28练习 28第2章数组和ArrayLists 302.1数组基本概念 302.1.1数组的声明和初始化 302.1.2数组元素的设置和存取访问 302.1.3取回数组元数据的方法和属性 312.1.4多维数组 312.1.5参数数组 322.1.6锯齿状数组 322.2ArrayList类 332.2.1ArrayList类的成员 342.2.2应
10、用ArrayList类 34ArrayList grades = new ArrayList(); 34小结 36练习 36第3章基础排序算法 383.1 排序算法 383.1.1数组类测试环境 383.1.2 冒泡排序 393.1.3 检验排序过程 403.1.4 选择排序 403.1.5 插入排序 413.2 基础排序算法的时间比较 42小结 43练习 43第4章基础查找算法 444.1 顺序查找算法 444.1.1 查找最小值和最大值 454.1.2 自组织数据加快顺序查找速度 464.2 二叉查找算法 474.3 递归二叉查找算法 48小结 49练习 49第5章堆栈和队列 505.1堆
11、栈、堆栈的实现以与STACK类 505.1.1堆栈的操作 505.1.2Stack类的实现 505.2STACK类 525.2.1Stack构造器方法 525.2.2主要的堆栈操作 525.2.3Peek方法 545.2.4Clear方法 545.2.5Contains方法 545.2.6CopyTo方法和ToArray方法 545.2.7Stack类的实例：十进制向多种进制的转换 545.3队列、QUEUE类以与QUEUE类的实现 555.3.1队列的操作 555.3.2Queue的实现 565.3.3 Queue类：实例应用 565.3.4用队列存储数据 585.3.5源自Queue类的优
12、先队列 60小结 61练习 61第6章 BitArray类 636.1激发的问题 636.2位和位操作 636.2.1二进制数制系统 646.2.2处理二进制数：按位运算符和位移运算符 646.3按位运算符的应用 656.3.1位移运算符 666.4整数转换成二进制形式的应用程序 666.5位移的示例应用程序 686.6BITARRAY类 696.6.1使用BitArray类 696.6.2更多BitArray类的方法和属性 706.7用BITARRAY来编写埃拉托斯特尼筛法 716.8BITARRAY与数组在埃拉托斯特尼筛法上的比较 72小结 72练习 72第7章 字符串、String类和S
13、tringBuilder类 737.1STRING类的应用 737.1.1创建String对象 737.1.2常用String类的方法们 737.1.3Split方法和Join方法 757.1.4比较字符串的方法 767.1.5处理字符串的方法 787.2STRINGBUILDER类 817.2.1构造StringBuilder对象 817.2.2获取并且设置关于StringBuilder对象的信息 817.2.3修改StringBuilder对象 827.3STRING类与STRINGBUILDER的性能比较 83小结 84练习 85第8章 模式匹配和文本处理 868.1正则表达式概述 86
14、8.1.1概述：使用正则表达式 868.2数量词 878.3使用字符类 888.4用断言修改正则表达式 908.5使用分组构造 908.5.1匿名组 908.5.2命名组 918.5.3零宽度正向预搜索断言和零宽度反向预搜索断言 918.6CAPTURESCOLLECTION类 928.7正则表达式的选项 92小结 93练习 93第9章 构建字典：DictionaryBase类和SortedList类 949.1DICTIONARYBASE类 949.1.1DictionaryBase类的基础方法和属性 949.1.2其他的DictionaryBase方法 959.2通用的KEYVALUEPA
15、IR类 969.3SORTEDLIST类 979.3.1使用SortedList类 97小结 97练习 98第10章 散列和Hashtable类 9910.1 散列概述 9910.2 选择散列函数 9910.3 查找散列表中数据 10010.4 解决冲突 10110.4.1 桶式散列法 10110.4.2 开放定址法 10210.4.3 双重散列法 10210.5 HASHTABLE类 10210.5.1实例化Hashtable对象并且给其添加数据 10210.5.2从散列表中分别取回关键字和数值 10310.5.3取回基于关键字的数值 10310.5.4 Hashtable类的实用方法 10
16、410.6 HASHTABLE的应用程序：计算机术语表 104小结 106练习 106第11章 链表 10711.1数组存在的问题 10711.2链表的定义 10711.3面向对象链表的设计 10811.3.1 Node类 10811.3.2 LinkedList类 10811.4 链表设计的改进方案 10911.4.1 双向链表 11011.4.2 循环链表 11111.5 使用ITERATOR类 11311.5.1 新的LinkedList类 11411.5.2 实例化Iterator类 11411.6 通用的LINKED LIST类和通用的NODE类 11711.6.1 通用链表实例 1
17、17小结 118练习 118第12章 二叉树和二叉查找树 11912.1 树的定义 11912.2 二叉树 12012.2.1 构造二叉查找树 12012.2.2 遍历二叉查找树 12112.2.3 在二叉查找树中查找节点和最大/最小值 12312.2.4 从BST中移除叶子节点 12312.2.5 删除带有一个子节点的节点 12412.2.6 删除带有两个子节点的节点 124小结 126练习 127第13章 集合 12813.1集合的基础定义、操作与属性 12813.1.1集合的定义 12813.1.2集合的操作 12813.1.3集合的属性 12813.2第一个用散列表的SET类的实现 1
18、2913.2.1类数据成员和构造器方法 12913.2.2Add方法 12913.2.3Remove方法和Size方法 12913.2.4Union方法 12913.2.5Intersection方法 13013.2.6Subset方法 13013.2.7Difference方法 13013.2.8测试CSet实现的程序 13013.3CSET类的BITARRAY实现 13113.3.1使用BitArray实现的概述 13113.3.2BitArray集合的实现 132小结 133练习 133第14章 高级排序算法 13414.1希尔排序算法 13414.2归并排序算法 13514.3堆排序算
19、法 13614.3.1构造堆 13614.4快速排序算法 13814.4.1快速排序算法的描述 13914.4.2快速排序算法的代码 13914.4.3快速排序算法的改进 140小结 140练习 140第15章 查找的高级数据结构和算法 14115.1 AVL树 14115.1.1 AVL树的基本原理 14115.1.2 AVL树的实现 14115.2 红黑树 14315.2.1 红黑树规则 14315.2.2 红黑树的插入 14315.2.3 红黑树实现代码 14415.3 跳跃表 14615.3.1 跳跃表的基本原理 14615.3.2 跳跃表的实现 147小结 149练习 150第16章
20、 图和图的算法 15116.1 图的定义 15116.2 由图模拟真实世界系统 15116.3 图类 15116.3.1 顶点的表示 15216.3.2 边的表示 15216.3.3 图的构造 15216.3.4 图的第一个应用：拓扑排序 15316.3.5 拓扑排序算法 15416.3.6 拓扑排序算法的实现 15416.4 图的搜索 15616.4.1 深度优先搜索 15616.4.2 广度优先搜索 15716.5 最小生成树 15816.5.1 最小生成树算法 15816.6 查找最短路径 15916.6.1 加权图 15916.6.2 确定最短路径的Dijkstra算法 16016.6
21、.3 Dijkstra算法的代码 160小结 164练习 164第17章 高级算法 16517.1 动态规划 16517.1.1动态规划实例：计算斐波纳契数列 16517.1.2 寻找最长公共子串 16717.1.3 背包问题 16817.2 贪心算法 16917.2.1贪心算法实例：找零钱问题 16917.2.2 采用哈夫曼编码的数据压缩 17017.2.3用贪心算法解决背包问题 174小结 176练习 176索引 177第1章 Collections类、泛型类和Timing类概述这本书采用C#语言来讨论数据结构与算法的开发和实现。书中用到的数据结构都可以在.NET框架类库System.Co
22、llections中找到。本章会逐步展开群集的概念，首先是讨论自身特有的Collection类（采用数组作为我们实现的基础）的实现，接着会介绍.NET框架中Collection类的容。泛型是C#语言2.0版新增加的一个重要补充。泛型允许C#语言程序员可以独立地或者在一个类中编写函数的某一个版本，而且不需要为了不同的数据类型而多次负载此函数。C#语言2.0版还为个别几种System.Collections数据结构实现型提供了一个专门的库System.Collections.Generic。本章将向读者介绍泛型编程。本章最后会介绍一种用户定制的类Timing类。后续的几个章节将会用此类来衡量数据结
23、构与/或算法的性能。此类将代替大O分析法的位置。这不是因为大O分析法不重要，而是因为本书采取了一种更为实用的方法来学习数据结构与算法。1.1群集的定义群集是一种结构化的数据类型。它存储数据，并且提供数据的添加、删除、更新操作，以与对群集的不同属性值的设置与返回操作。群集可以分为两类：线性的和非线性的。线性群集是一元素列表，表中的元素顺次相连。线性群集中的元素通常由位置来决定次序（例如，第一个元素、第二个元素、第三个元素，依次类推）。在现实世界中，购物清单就是很好的线性群集实例。而在计算机世界中（当然这也是真实世界）则把数组设计成线性群集。非线性群集所包含的元素在群集没有位置次序之分。组织结构图
24、就像用架子垒好的台球一样是一个非线性群集的实例。而在计算机世界中树、堆、图和集都是非线性群集。无论是线性的还是非线性的群集都拥有一套定义好的属性和操作的集合。其中，属性用来描述群集，而操作就是群集能执行的容。群集Count就是群集属性的一个实例。它保存着群集中数据项的数量。这里把群集的操作称为方法，它包括Add（即向群集添加新元素），Insert（即在群集指定的索引位置添加新元素）、Remove（即从群集中移除指定元素）、Clear（即从群集中移除所有元素）、Contains（即确定指定元素是否是群集的成员）、以与IndexOf（即确定指定元素在群集中的索引位置）。1.2群集的描述在两种主要的
25、群集类中有几个子类别。线性的群集可能是直接存取群集，也可能是顺序存取群集。而非线性的群集既可以是层次群集，也可以是组群集。本小节就来讨论这些群集的类型。1.2.1直接存取群集直接存取群集最常见的实例就是数组。这里把数组定义为具有一样数据类型的元素的群集，而且所有数组元素如同图1-1说明的那样可以通过整数型索引直接进行存取访问。（原书P3页图）第0项、第1项、第2项、第3项、第j项、第n-1项图1-1数组数组可以是静态的，这样当声明数组的时候便于针对程序的长度来固定指定元素的数量。数组也可以是动态的，通过ReDim或者ReDim Preserve语句就可以增加数组元素的数量。在C#语言中，数组不
26、只是置的数据类型，它还是一种类。在本章的后续部分，当详细分析数组使用的时候将会讨论如何把数组作为类对象来使用。我们可以用数组来存储一个线性的群集。向数组添加新元素是很容易的，只要简单地把新元素放置在数组尾部第一个空位上就可以了。但是，在数组中插入一个元素就不是这么容易的（或高效）了。因为要给插入的元素空出位置，所以需要按顺序向后移动数组元素。从数组的尾部删除一个元素也是很有效率的操作，只要简单地移除掉最后一个元素的值就可以了。但是，删除数组中任何其他位置上的元素就没有这么有效率了，就像处理插入操作一样，为了保持数组中元素的连续性，可能需要先前调整许多数组元素的位置。这些情况将在本章后续容中进行
27、讨论。.NET框架为简化线性群集的编程提供了一种专门的数组类ArrayList。第3章将会对此类进行分析研究。字符串是直接存取群集的另外一种类型。字符串是字符的群集。和存取数组元素的方式一样，也可以基于字符的索引对其进行存取。在C#语言中，字符串也是作为类对象来实现的。这个类包含一个在字符串上执行标准操作的庞大的方法集合，其中操作有串连接、返回子串、插入字符、移除字符等等。第8章会讨论String类。C#字符串是不可变的。这意味着一旦对字符串进行了初始化，就不能再改变它了。当要修改字符串的时候，不是改变原始的字符串，而是创建一个字符串的副本。在某些情况下这种行为可能会导致性能下降，所以.NET
28、框架提供了StringBuilder类来让用户能处理可变的字符串。第8章也会对StringBuilder进行介绍。结构（在其他编程语言中也被称为记录）是最后一种直接存取的群集类型。结构是一种复合数据类型。它所包含的数据可能拥有许多不同的数据类型。例如，一名雇员记录就是由雇员的（字符串）、薪水（整数）、工号（字符串或整数），以与其他属性组成的。由于把这些数据的值分别存储在分散的变量是很容易变混淆的，所以编程语言采用结构来存储此类数据。C#语言的结构所增加的强大能力就是为执行存储在数据上的操作定义了方法。尽管不能从结构继承或推导出一种新的类型，但是这种做法使得结构在某些地方很像一个类。下面的代码举
29、例明了C#语言中结构的一个简单应用。using System;public struct Name private string fname, mname, lname; public Name(string first, string middle, string last) fname = first; mname = middle; lname = last; public string firstName get return fname; set fname = firstName; public string middleName get return mname; set mna
30、me = middleName; public string lastName get return lname; set lname = lastName; public override string ToString() return (String.Format(0 1 2, fname, mname,lname); public string Initials() return (String.Format(012, fname.Substring(0, 1),mname.Substring(0, 1), lname.Substring(0, 1); public class Nam
31、eTest static void Main() Name myName = new Name(Michael, Mason, McMillan); string fullName, inits; fullName = myName.ToString(); inits = myName.Initials(); Console.WriteLine(My name is 0., fullName); Console.WriteLine(My initials are 0., inits); 虽然.NET环境中许多元素都是作为类来实现的（比如数组和字符串），但是语言的几个主要元素还是作为结构来实现的
32、，比如数字数据类型。例如，整数类型就是作为Int32结构来实现的。采用Int32的方法之一就是把用字符串表示的数转换成为整数的Parse方法。实例如下所示：using System;public class IntStruct static void Main() int num; string snum; Console.Write(Enter a number: ); snum = Console.ReadLine(); num = Int32.Parse(snum); Console.WriteLine(num); 1.2.2顺序存取群集顺序存取群集是把群集元素按顺序存储的表。这里也把此
33、类群集称为线性表。线性表在创建时没有大小限制，这就意味着它们可以动态地扩展和收缩。不能对线性表中数据项进行直接存取访问，而要像图1-2表示的那样通过数据项的位置对其进行存取。线性表的第一个元素在表头的位置，而最后一个元素在表尾的位置。（原书P6页图）第1项、第2项、第3项、第4项、第n项表头 表尾图1-2线性表由于不能直接存取线性表的元素，为了访问某个元素就需要遍历线性表直到到达要找元素的位置为止。线性表的实现通常允许两种遍历表的方法：一种是单向从前往后遍历，而另一种则是双向遍历，即从前向后和从后先前遍历。线性表的一个简单实例就是购物清单。顺次写下要购买的全部商品就会形成一购物清单。在购物时一
34、旦找到某种商品就把它从清单中划掉。线性表既可以是有序的，也可以是无序的。有序线性表具有顺次对应的有序值。如下列人名所表示的情况：Beata、Bernica、David 、Frank、Jennifer、Mike、Raymond、Terrill。而无序线性表则是由无序元素组成的。在第2章对二叉查找算法与简单线性查找算法进行讨论时就会发现线性表的顺序会在查找表中数据时产生很大的差异。线性表的某些类型限制访问数据元素。这类线性表有堆栈和队列。堆栈是一种只允许在表头（或顶端）存取数据的表。在表的顶端放置数据项，而且也只能从表的顶端移出数据项。正是基于这种原因，堆栈也被称为后进先出结构。这里把向堆栈添加数
35、据项的操作称为入栈，而把从堆栈移出数据项的操作称为出栈。图1-3展示了堆栈的这两种操作。（原书P7页图）入栈、出栈图1-3堆栈操作堆栈是非常常见的一种数据结构，特别是在计算机系统编程中尤为普遍。在堆栈的众多应用中，它常用于算术表达式的计算和平衡符号。队列是一种只允许在表尾进行数据项添加和移出操作的表。它也被称为是先进先出结构。这里把向队列添加数据项称为EnQueue，而把从队列移出数据项称为DeQueue。图1-4展示了队列的这两种操作。（原书P7页图）图1-4队列操作队列既可用于调度操作系统任务的系统编程，也可用于模拟研究的编程。在每一种能想象到的少量情况下，队列都可以为模拟等待队列产生极好
36、的结构。优先队列是队列的一种特殊类型。它允许最先移出队列的数据项具有最高的优先级。例如，优先队列可以用来研究医院急诊室的操作，这里应该对心脏病突发患者先进行救护，然后再处理手臂骨折患者。最后要讨论的一类线性群集被称为通用的索引群集。这类群集的第一种就是散列表。它存储了一组与关键字相关联的数据值。在散列表中有一个被称为散列函数的特殊函数。此函数会取走一个数据值，并且把此数据值（称为关键字）转换成用来取回数据的整数索引。然后此索引会用来存取访问与关键字相关联的数据记录。例如，一条雇员记录可能由雇员、薪水、工作年限以与所工作的部门组成。此结构如图1-5所示。此数据记录的关键字就是雇员的。C#语言有一
37、个称为HashTable的类用来存储散列表的数据。第10章会讨论此结构。（原书P8页图）“信息系统”部门图1-5散列的记录另外一种通用的索引群集就是字典。字典也被称为联合，它是由一系列键值对构成的。此结构与词典类似，词典中的词是关键字，而词的定义则是与关键字相关联的值。关键字就是与其相关联的值的索引。虽然索引不需要就是整数，但是由于上述这种索引方案，所以还是常把字典称为联合数组。第11章会对.NET框架容的几种Dictionary类进行讨论。1.2.3层次群集非线性群集分为两大主要类型：层次群集和组群集。层次群集是一组划分了层次的数据项集合。位于某一层的数据项可能会有位于下一较低层上的后继数据
38、项。树是一种常见的层次群集。树群集看上去像是一棵倒立的树，其中一个数据项作为根，而其他数据值则作为叶子挂在根的下面。树的元素被称为节点，而且在特定节点下面的元素被称为是此节点的孩子。图1-6展示了一棵实例树。（原书P9页图）根图1-6树群集树在几种不同的领域都有应用。大多数现代操作系统的文件系统都是采用树群集设计而成的，其中一个目录作为根，而其他子目录则作为根的孩子们。二叉树是树群集的一种特殊类型，树中每个节点最多只有两个孩子。二叉树可以变成二叉查找树，这样做可以极提高查找大量数据的效率。实现的方法是依据从根到要存储数据的节点的路径为最短路径的方式来放置节点。还有一种树类型就是堆。堆这样组织就
39、是为了便于把最小数据值始终放置在根节点上。在删除时会移除根节点。此外，堆的插入和删除操作总是会导致堆的重组，因为只有这样才能把最小值放在根节点上。我们经常会用堆来排序，这被称为是堆排序。通过反复删除根节点以与重组堆的方式就可以对存储在堆的数据元素进行排序。第12章将对几种不同类型的树进行讨论。1.2.4组群集数据项为无序的非线性群集被称为组。集合、图和网络是组群集的三种主要类型。集合是一种无序数据值的群集，并且集合中每一个数据值都是唯一的。当然，就像整数一样，班级中学生的列表就是一个集合的实例。在集合上执行的操作包括联合和交叉。图1-7显示了集合操作的实例。（原书P10页图）A集合、B集合、A
40、集合交叉B集合、A集合联合B集和图1-7集合操作图是由节点集合以与与节点相连的边集合组成的。图用来对必须访问图中每个节点的情况进行建模，而且有些时候还要按照特定顺序进行访问。这样做的目的是为了找到“遍历”图的最有效的方法。图可用于，也可用于计算机科学和数学研究领域。大家可能听说过“旅行商”问题。这就是图问题的一种特殊类型。此问题要求在旅行预算允许的条件下为需要拜访路线中所有城市的商人确定最有效的完整旅行路线。此问题的实例图表示在图1-8中。（原书P10页图）Tokyo:东京、Seattle:西雅图、LA:洛杉矶、Boston:波士顿、New York:纽约、Washington:华盛顿、London:伦敦、Paris:巴黎、Rome:罗马、Moscow:莫斯科图1-8旅行商问题此问题是被称为NP