包邮数据结构与算法:C语言描述

第1章　Collections类、泛型类和Timing类概述　1 1.1　群集的定义　1 1.2　群集的描述　1 1.2.1　直接存取群集　2 1.2.2　顺序存取群集　4 1.2.3　层次群集　6 1.2.4　组群集　7 1.3　CollectionBase类　8 1.3.1　用ArrayList实现Collection类　8 1.3.2　定义Collection类　8 1.3.3　实现Collection类　8 1.4　泛型编程　10 1.5　时间测试　12 1.5.1　一个简单化的时间测试　12 1.5.2　用于.NET环境的时间测试　13 1.5.3　Timing Test类　14 小结　16 练习　17 第2章　数组和ArrayList　18 2.1　数组基本概念　18 2.1.1　数组的声明和初始化　18 2.1.2　数组元素的设置和存取访问　19 2.1.3　检索数组元数据的方法和属性　19 2.1.4　多维数组　20 2.1.5　参数数组　21 2.1.6　锯齿状数组　22 2.2　ArrayList类　23 2.2.1　ArrayList类的成员　23 2.2.2　应用ArrayList类　24 小结　27 练习　27 第3章　基础排序算法　29 3.1　排序算法　29 3.1.1　数组类测试环境　29 3.1.2　冒泡排序　31 3.1.3　检验排序过程　32 3.1.4　选择排序　33 3.1.5　插入排序　35 3.2　基础排序算法的时间比较　36 小结　37 练习　38 第4章　基础查找算法　39 4.1　顺序查找　39 4.1.1　查找*小值和*大值　41 4.1.2　自组织数据加快顺序查找速度　42 4.2　二叉查找算法　43 4.3　递归二叉查找算法　45 小结　47 练习　47 第5章　栈和队列　48 5.1　栈、栈的实现以及Stack类　48 5.1.1　栈的操作　48 5.1.2　Stack类的实现　49 5.2　Stack类　51 5.2.1　Stack构造器方法　51 5.2.2　主要的栈操作　52 5.2.3　Peek方法　54 5.2.4　Clear方法　54 5.2.5　Contains方法　54 5.2.6　CopyTo方法和ToArray方法　54 5.2.7　Stack类的实例：十进制向多种进制的转换　55 5.3　队列、Queue类以及Queue类的实现　56 5.3.1　队列的操作　56 5.3.2　Queue的实现　57 5.3.3　Queue类：实例应用　58 5.3.4　用队列排序数据　61 5.3.5　源自Queue类的优先队列　64 小结　65 练习　66 第6章　BitArray类　67 6.1　激发的问题　67 6.2　位和位操作　68 6.2.1　二进制数制系统　68 6.2.2　处理二进制数：按位运算符和移位运算符　69 6.3　按位运算符的应用　70 6.4　整数转换成二进制形式的应用程序　74 6.5　移位的示例应用程序　76 6.6　BitArray类　78 6.6.1　使用BitArray类　78 6.6.2　更多BitArray类的方法和属性　81 6.7　用BitArray来编写埃拉托斯特尼筛法　81 6.8　BitArray与数组在埃拉托斯特尼筛法上的比较　83 小结　83 练习　84 第7章　字符串、String类和StringBuilder类　85 7.1　String类的应用　85 7.1.1　创建String对象　85 7.1.2　常用的String类方法　86 7.1.3　Split方法和Join方法　88 7.1.4　比较字符串的方法　90 7.1.5　处理字符串的方法　92 7.2　StringBuilder类　98 7.2.1　构造StringBuilder对象　98 7.2.2　获取并且设置关于StringBuilder对象的信息　98 7.2.3　修改StringBuilder对象　99 7.3　String类与StringBuilder的性能比较　101 小结　103 练习　103 第8章　模式匹配和文本处理　105 8.1　正则表达式概述　105 8.2　数量词　107 8.3　使用字符类　109 8.4　用断言修改正则表达式　111 8.5　使用分组构造　112 8.5.1　匿名组　112 8.5.2　命名组　112 8.5.3　零宽度正向预搜索断言和零宽度反向预搜索断言　113 8.6　CapturesCollection类　114 8.7　正则表达式的选项　115 小结　116 练习　116 第9章　构建字典：DictionaryBase类和SortedList类　117 9.1　DictionaryBase类　117 9.1.1　DictionaryBase类的基础方法和属性　117 9.1.2　其他的DictionaryBase方法　119 9.2　泛型KeyValuePair类　121 9.3　SortedList类　122 小结　123 练习　123 第10章　散列和Hashtable类　125 10.1　散列概述　125 10.2　选择散列函数　125 10.3　查找散列表中数据　127 10.4　解决冲突　128 10.4.1　桶式散列法　128 10.4.2　开放定址法　129 10.4.3　双重散列法　130 10.5　Hashtable类　130 10.5.1　实例化Hashtable对象并且给其添加数据　130 10.5.2　从散列表中分别检索键和数值　131 10.5.3　检索基于键的数值　132 10.5.4　Hashtable类的实用方法　133 10.6　Hashtable的应用：计算机术语表　133 小结　136 练习　136 第11章　链表　137 11.1　数组存在的问题　137 11.2　链表的定义　137 11.3　面向对象链表的设计　138 11.3.1　Node类　138 11.3.2　LinkedList类　139 11.4　链表设计的改进方案　141 11.4.1　双向链表　141 11.4.2　循环链表　143 11.5　使用Iterator类　146 11.5.1　新的LinkedList类　148 11.5.2　实例化Iterator类　148 11.6　泛型Linked List类和泛型Node类　152 小结　154 练习　154 第12章　二叉树和二叉查找树　155 12.1　树的定义　155 12.2　二叉树　156 12.2.1　构造二叉查找树　157 12.2.2　遍历二叉查找树　159 12.2.3　在二叉查找树中查找节点和*大/*小值　161 12.2.4　从二叉查找树中移除叶子节点　162 12.2.5　删除带有一个子节点的节点　163 12.2.6　删除带有两个子节点的节点　164 小结　167 练习　167 第13章　集合　169 13.1　集合的基础定义、操作及属性　169 13.1.1　集合的定义　169 13.1.2　集合的操作　169 13.1.3　集合的属性　169 13.2　**个用散列表的Set类的实现　170 13.2.1　类数据成员和构造器方法　170 13.2.2　Add方法　170 13.2.3　Remove方法和Size方法　171 13.2.4　Union方法　171 13.2.5　Intersection方法　172 13.2.6　Subset方法　172 13.2.7　Difference方法　172 13.2.8　测试CSet实现的程序　173 13.3　CSet类的BitArray实现　174 13.3.1　使用BitArray实现的概述　174 13.3.2　BitArray集合的实现　175 小结　177 练习　177 第14章　高级排序算法　178 14.1　希尔排序算法　178 14.2　归并排序算法　179 14.3　堆排序算法　182 14.4　快速排序算法　185 14.4.1　快速排序算法的描述　186 14.4.2　快速排序算法的代码　187 14.4.3　快速排序算法的改进　188 小结　188 练习　188 第15章　用于查找的高级数据结构和算法　189 15.1　AVL树　189 15.1.1　AVL树的基本原理　189 15.1.2　AVL树的实现　190 15.2　红黑树　192 15.2.1　红黑树规则　192 15.2.2　红黑树