数据结构与算法

第1章Collections类、泛型类和Timing类概述

1.1群集的定义

1.2群集的描述

1.2.1直接存取群集

1.2.2顺序存取群集

1.2.3层次群集

1.2.4组群集

1.3CollectionBase类

1.3.1用ArrayList实现Collection类

1.3.2定义Collection类

1.3.3实现Collection类

1.4泛型编程

1.5时间测试

1.5.1一个简单化的时间测试

1.5.2用于.NET环境的时间测试

1.5.3TimingTest类

小结

练习

第2章数组和ArrayList

2.1数组基本概念

2.1.1数组的声明和初始化

2.1.2数组元素的设置和存取访问

2.1.3检索数组元数据的方法和属性

2.1.4多维数组

2.1.5参数数组

2.1.6锯齿状数组

2.2ArrayList类

2.2.1ArrayList类的成员

2.2.2应用ArrayList类

小结

练习

第3章基础排序算法

3.1排序算法

3.1.1数组类测试环境

3.1.2冒泡排序

3.1.3检验排序过程

3.1.4选择排序

3.1.5插入排序

3.2基础排序算法的时间比较

小结

练习

第4章基础查找算法

4.1顺序查找

4.1.1查找最小值和最大值

4.1.2自组织数据加快顺序查找速度

4.2二叉查找算法

4.3递归二叉查找算法

小结

练习

第5章栈和队列

5.1栈、栈的实现以及Stack类

5.1.1栈的操作

5.1.2Stack类的实现

5.2Stack类

5.2.1Stack构造器方法

5.2.2主要的栈操作

5.2.3Peek方法

5.2.4Clear方法

5.2.5Contains方法

5.2.6CopyTo方法和ToArray方法

5.2.7Stack类的实例：十进制向多种进制的转换

5.3队列、Queue类以及Queue类的实现

5.3.1队列的操作

5.3.2Queue的实现

5.3.3Queue类：实例应用

5.3.4用队列排序数据

5.3.5源自Queue类的优先队列

小结

练习

第6章BitArray类

6.1激发的问题

6.2位和位操作

6.2.1二进制数制系统

6.2.2处理二进制数：按位运算符和移位运算符

6.3按位运算符的应用

6.4整数转换成二进制形式的应用程序

6.5移位的示例应用程序

6.6BitArray类

6.6.1使用BitArray类

6.6.2更多BitArray类的方法和属性

6.7用BitArray来编写埃拉托斯特尼筛法

6.8BitArray与数组在埃拉托斯特尼筛法上的比较

小结

练习

第7章字符串、String类和StringBullder类

7.1String类的应用

7.1.1创建String对象

7.1.2常用的String类方法

7.1.3Split方法和Join方法

7.1.4比较字符串的方法

7.1.5处理字符串的方法

7.2StringBuilder类

7.2.1构造StringBuilder对象

7.2.2获取并且设置关于StringBuilder对象的信息

7.2.3修改StringBuilder对象

7.3String类与StringBuilder的性能比较

小结

练习

第8章模式匹配和文本处理

8.1正则表达式概述

8.2数量词

8.3使用字符类

8.4用断言修改正则表达式

8.5使用分组构造

8.5.1匿名组

8.5.2命名组

8.5.3零宽度正向预搜索断言和零宽度反向预搜索断言

8.6CapturesCollection类

8.7正则表达式的选项

小结

练习

第9章构建字典：DictionaryBase类和SortedList类

9.1DictionaryBase类

9.1.1DictionaryBase类的基础方法和属性

9.1.2其他的DictionaryBase方法

9.2泛型KeyValuePair类

9.3SortedList类

小结

练习

第10章散列和HashtabIe类

10.1散列概述

10.2选择散列函数

10.3查找散列表中数据

10.4解决冲突

10.4.1桶式散列法

10.4.2开放定址法

10.4.3双重散列法

10.5Hashtable类

10.5.1实例化Hashtable对象并且给其添加数据

10.5.2从散列表中分别检索键和数值

10.5.3检索基于键的数值

10.5.4Hashtable类的实用方法

10.6Hashtable的应用：计算机术语表

小结

练习

第11章链表

11.1数组存在的问题

11.2链表的定义

11.3面向对象链表的设计

11.3.1Node类

11.3.2IJnkedList类

11.4链表设计的改进方案

11.4.1双向链表

11.4.2循环链表

11.5使用Iterator类

11.5.1新的LinkedList类

11.5.2实例化Iterator类

11.6泛型LinkedList类和泛型Node类

小结

练习

第12章二叉树和二叉查找树

12.1树的定义

12.2二叉树

12.2.1构造二叉查找树

12.2.2遍历二叉查找树

12.2.3在二叉查找树中查找节点和最大，最小值

12.2.4从二叉查找树中移除叶子节点

12.2.5删除带有一个子节点的节点

12.2.6删除带有两个子节点的节点

小结

练习

第13章集合

13.1集合的基础定义、操作及属性

13.1.1集合的定义

13.1.2集合的操作

13.1.3集合的属性

13.2第一个用散列表的Set类的实现

13.2.1类数据成员和构造器方法

13.2.2Add方法

13.2.3Remove方法和Size方法

13.2.4IJnion方法

13.2.5Intersection方法

13.2.6Subset方法

13.2.7Difference方法

13.2.8测试CSet实现的程序

13.3CSet类的BitArray实现

13.3.1使用BitArray实现的概述

13.3.2BitArray集合的实现

小结

练习

第14章高级排序算法

14.1希尔排序算法

14.2归并排序算法

14.3堆排序算法

14.4快速排序算法

14.4.1快速排序算法的描述

14.4.2快速排序算法的代码

14.4.3快速排序算法的改进

小结

练习

第15章用于查找的高级数据结构和算法

15.1AVL树

15.1.1AVL树的基本原理

15.1.2AVL树的实现

15.2红黑树

15.2.1红黑树规则

15.2.2红黑树的插入

15.2.3红黑树实现代码

15.3跳跃表

15.3.1跳跃表的基本原理

15.3.2跳跃表的实现

小结

练习

第16章图和图的算法

16.1图的定义

16.2由图模拟真实世界系统

16.3图类

16.3.1顶点的表示

16.3.2边的表示

16.3.3图的构造

16.3.4图的第一个应用：拓扑排序

16.3.5拓扑排序算法

16.3.6拓扑排序算法的实现

16.4图的搜索

16.4.1深度优先搜索

16.4.2广度优先搜索

16.5最小生成树

16.6查找最短路径

16.6.1加权图

16.6.2确定最短路径的Dijkstra算法

16.6.3Dijkstra算法的代码

小结

练习

第17章高级算法

17.1动态规划

17.1.1动态规划实例：计算斐波纳契数列

17.1.2寻找最长公共子串

17.1.3背包问题

17.2贪心算法

17.2.1贪心算法实例：找零钱问题

17.2.2采用哈夫曼编码的数据压缩

17.2.3贪心算法解决背包问题

小结

练习

参考文献

索引

　　随着.NET框架的广泛应用，C#已经成为最受欢迎的程序设计语言之一。但是，市面上尚无用C#语言讲述数据结构和算法的图书，广大C#程序员不得不将自己转换C++或Java描述的数据结构，费时费力，而且容易出错。本书填补了这一空白。而且更加难能可贵的是，作者基于自己多年的教学和实践经验，从开发实战出发，采用了一种与一般数据结构图书不同的讲解方式：充分利用.NET框架中现成的数据结构类，先讲述各种数据结构怎么在开发中选用，怎样用来解决实际问题，在有了感性认识之后，再深入研究如何实现；同时，用更加实用的时间测试方法代替常规的大O表示法来分析算法性能，避免了复杂的数学推导。书中除涵盖了数组、广义表、链表等常规数据结构和算法外，还讨论了概率和动态规划等方面的高级算法。　　本书是在.NET框架下用C#语言实现数据结构和算法的第一本全面的参考书。本书介绍的方法非常实用，采用了时间测试而非大O表示法来分析算法性能。内容涵盖了数据结构和算法的基本原理，涉及数组、广义表、链表、散列表、树、图、排序搜索算法以及更多概率算法和动态规则等高级算法。此外，书中还提供了.NET框架类库中的C#语言实现的数据结构和算法。　　本书适合作为C#数据结构课程的教材，同时也适合C#专业人士阅读。【作者简介】　　MichaelMcMillan：资深的软件开发技术专家，拥有二十多年的编程实践和教学经验。目前任教于美国阿肯色大学、Pulaski技术学院等校。他在业界技术杂志上发表过大量技术文章，还著有Object-OrientedProgrammingwithVisualBasic.NET等著作。