数据结构与算法基础

本书共分为10章, 主要包括集合线性表栈和队列、树和二叉树、二叉树应用、图、图的应用、查找以及排序等内容。

第1章绪论 1 1.1数据结构的有关概念 2 1.2算法描述 10 1.3算法评价 11 思考与练习 17 第2章集合 22 2.1集合的定义和抽象数据类型 23 2.2集合的顺序存储结构和操作实现 24 2.2.1集合的顺序存储结构和存储类型定义 24 2.2.2集合运算在顺序存储结构下的操作实现 25 2.2.3对顺序集合进行各种运算的程序示例 29 2.3集合的链式存储结构和操作实现 30 2.3.1链式存储集合的有关概念 30 2.3.2集合运算在链式存储结构下的操作实现 32 2.3.3对链式存储集合进行各种运算的程序示例 36 思考与练习 38 第3章线性表 42 3.1线性表的定义和抽象数据类型 43 3.2线性表的顺序存储结构和操作实现 44 3.3链式存储数据的概念和方法 51 3.4线性表的每种运算在单链表上的操作实现 55 思考与练习 61 第4章栈和队列 65 4.1栈的定义和抽象数据类型 66 4.2栈的顺序存储结构和操作实现 67 4.3栈的链式存储结构和操作实现 70 4.4栈的简单应用举例 72 4.5队列 76 4.5.1队列的定义和抽象数据类型 76 4.5.2队列的顺序存储结构和操作实现 77 4.5.3队列的链式存储结构和操作实现 80 4.5.4队列的应用简介 83 4.6算术表达式的计算 84 4.6.1算术表达式的两种表示 84 4.6.2后缀表达式求值的算法 85 4.6.3把中缀表达式转换为后缀表达式的算法 87 4.7栈与递归 90 4.7.1阶乘求解的递归算法 91 4.7.2求解迷宫问题的递归算法 92 4.7.3求解汉诺塔问题的递归算法 96 思考与练习 98 第5章树和二叉树 103 5.1树的概念 104 5.1.1树的定义 104 5.1.2树的表示 105 5.1.3树的基本术语 106 5.1.4树的性质 107 5.2二叉树 108 5.2.1二叉树的定义 108 5.2.2二叉树的性质 108 5.2.3二叉树的抽象数据类型 110 5.2.4二叉树的存储结构 110 5.3二叉树遍历 113 5.4二叉树其他运算 115 5.5树的存储结构和运算 122 5.5.1树的抽象数据类型 122 5.5.2树的存储结构 122 5.5.3树的运算 123 思考与练习 129 第6章二叉树应用 134 6.1二叉搜索树 135 6.1.1二叉搜索树的定义 135 6.1.2二叉搜索树的抽象数据类型 135 6.1.3二叉搜索树的运算 136 6.1.4二叉搜索树运算的应用程序示例 140 6.2堆 142 6.2.1堆的定义 142 6.2.2堆的抽象数据类型 143 6.2.3堆的存储结构 143 6.2.4堆的运算 144 6.2.5堆运算的应用程序示例 147 6.3哈夫曼树 148 6.3.1基本术语 148 6.3.2构造哈夫曼树 149 6.3.3哈夫曼编码 151 思考与练习 154 第7章图 157 7.1图的概念 158 7.1.1图的定义 158 7.1.2图的基本术语 159 7.1.3图的抽象数据类型 161 7.2图的存储结构 161 7.2.1邻接矩阵 162 7.2.2邻接表 164 7.2.3边集数组 166 7.3图的遍历 168 7.3.1深度优先搜索遍历 168 7.3.2广度优先搜索遍历 171 7.3.3非连通图的遍历 174 7.3.4图的遍历算法的上机调试 174 7.4图的其他运算 177 思考与练习 189 第8章图的应用 192 8.1图的生成树和最小生成树 193 8.1.1生成树和最小生成树的概念 193 8.1.2普里姆算法 194 8.1.3克鲁斯卡尔算法 198 8.2最短路径 201 8.2.1最短路径的概念 201 8.2.2从图中一顶点到其余各顶点的最短路径 202 8.2.3图中每对顶点之间的最短路径 207 8.3拓扑排序 211 8.3.1拓扑排序的概念 211 8.3.2拓扑排序算法 212 8.4关键路径 216 思考与练习 222 第9章查找 226 9.1查找的概念 227 9.2顺序表查找 228 9.2.1顺序查找 228 9.2.2二分查找 229 9.3索引查找 233 9.3.1索引的概念 233 9.3.2索引查找算法 236 9.3.3分块查找 238 9.4散列查找 240 9.4.1散列的概念 240 9.4.2散列函数 241 9.4.3处理冲突的方法 243 9.4.4散列表的运算 246 9.5B树查找 252 9.5.1B树定义 252 9.5.2在B树上查找元素的过程 254 9.5.3在B树上插入元素的过程 255 9.5.4在B树上删除元素的过程 257 思考与练习 258 第10章排序 262 10.1排序的基本概念 263 10.2插入排序 264 10.2.1直接插入排序 264 10.2.2希尔排序 265 10.3选择排序 266 10.3.1直接选择排序 266 10.3.2堆排序 267 10.4交换排序 271 10.4.1气泡排序 271 10.4.2快速排序 272 10.5归并排序 276 10.6各种内排序方法的比较 281 10.7外排序 282 10.7.1外排序的有关概念 282 10.7.2外排序算法 284 10.7.3外排序应用程序运行示例 287 思考与练习 290