数据结构与算法分析新视角

第1章 绪论 1 1.1 从编程说起 1 1.2 程序要处理的数据 5 1.3 数据结构的引入 11 1.4 数据结构的基本概念 13 1.4.1 数据结构基本术语 13 1.4.2 数据结构的三个要素 13 1.5 如何设计算法 16 1.5.1 算法的定义及表示方法 16 1.5.2 算法设计与函数设计的关系 17 1.5.3 软件设计描述方法 18 1.5.4 算法设计的一般步骤 19 1.6 如何评价算法的优劣 21 1.6.1 算法的设计要求 21 1.6.2 算法效率的度量方法 22 1.7 算法性能的事前分析方法 23 1.7.1 问题的规模与算法的策略 23 1.7.2 算法效率的上限与下限 25 1.7.3 渐进的上限——算法的时间 复杂度 28 1.7.4 算法时间复杂度的综合讨论 29 1.7.5 算法的空间效率分析方法 33 1.8 算法性能综合考量 37 1.9 本章小结 38 习题 38 第2章 结点逻辑关系为线性的结构——线性表 41 2.1 从逻辑结构角度看线性表 41 2.1.1 实际问题中的线性关系 41 2.1.2 线性表的逻辑结构 42 2.2 线性表的存储结构方法之一——顺序表 43 2.2.1 顺序表的存储结构设计 43 2.2.2 顺序表的运算 46 2.2.3 顺序存储结构的讨论 53 2.3 线性表的存储结构方法之二——链表 53 2.3.1 单链表的存储 56 2.3.2 单链表的运算 60 2.3.3 单链表的讨论 78 2.3.4 循环链表 78 2.3.5 双向链表 81 2.3.6 链表小结 86 2.4 线性表的应用举例 87 2.4.1 逆序输出单链表结点值 87 2.4.2 一元多项式的相加 88 2.5 顺序表和链表的比较 95 2.6 本章小结 96 习题 97 第3章 运算受限的线性表——栈和队列 100 3.1 栈——按照先入后出的方式管理的线性表 100 3.1.1 栈处理模式的引入 100 3.1.2 栈的逻辑结构 104 3.1.3 栈的存储结构设计 106 3.1.4 栈的操作 107 3.1.5 各种栈结构的比较 123 3.1.6 栈的应用举例 123 3.2 队列——按照先入先出方式管理的线性表 132 3.2.1 队列处理模式的引入 133 3.2.2 队列的逻辑结构 136 3.2.3 队列的顺序存储结构 137 3.2.4 顺序队列的基本操作 148 3.2.5 队列的链式存储结构 152 3.2.6 链队列的基本操作 153 3.2.7 各种队列结构的比较 160 3.2.8 队列的应用举例 161 3.3 本章小结 171 习题 172 第4章 内容特殊的线性表——多维数组与字符串 175 4.1 多维数组 175 4.1.1 数组的概念 175 4.1.2 数组的存储结构 177 4.2 矩阵的压缩存储 181 4.2.1 对称矩阵的压缩存储 182 4.2.2 三角矩阵的压缩存储 183 4.2.3 对角矩阵的压缩存储 183 4.2.4 稀疏矩阵的压缩存储 185 4.3 字符串 189 4.3.1 字符串的定义 189 4.3.2 字符串的存储结构 190 4.3.3 字符串的查找——模式匹配 195 4.4 本章小结 211 习题 213 第5章 结点逻辑关系分层次的非线性结构——树 216 5.1 实际问题中的树 216 5.2 树的逻辑结构 219 5.2.1 树的定义和基本术语 219 5.2.2 树的操作定义 222 5.3 树的存储结构 222 5.3.1 树的连续存储方式 223 5.3.2 树的链式存储方式 224 5.4 二叉树的逻辑结构 226 5.4.1 二叉树的概念 229 5.4.2 二叉树的基本性质 230 5.4.3 二叉树的操作定义 231 5.5 二叉树的存储结构及实现 231 5.5.1 二叉树的顺序结构 232 5.5.2 二叉树的链式存储 结构——二叉链表 235 5.5.3 建立动态二叉链表 236 5.6 二叉树结点的查找 问题——树的遍历 240 5.6.1 树的广度优先遍历 242 5.6.2 树的深度优先遍历 244 5.6.3 树的遍历的应用 255 5.7 树的应用 259 5.7.1 表达式树 259 5.7.2 线索二叉树 260 5.7.3 哈夫曼树及哈夫曼编码 265 5.8 广义表 278 5.8.1 广义表的定义 279 5.8.2 广义表的存储 281 5.8.3 广义表的基本运算 287 5.9 本章小结 293 习题 295 第6章 结点逻辑关系任意的非线性结构——图 299 6.1 实际问题中的图及抽象 299 6.2 图的逻辑结构 304 6.2.1 图的定义和基本术语 304 6.2.2 图的操作定义 307 6.3 图的存储结构及实现 308 6.3.1 图的数组表示法1—— 邻接矩阵 308 6.3.2 图的数组表示法2—— 边集数组 310 6.3.3 图的链表表示法1——邻接表 311 6.3.4 图的链表表示法2—— 十字链表 316 6.3.5 图的链表表示法3——邻接多重表 317 6.3.6 图各种存储结构的归结比较 319 6.4 图的基本操作 320 6.4.1 邻接矩阵的操作 320 6.4.2 邻接表的操作 322 6.5 图的顶点查找问题——图的遍历 328 6.5.1 图的广度优先遍历BFS 329 6.5.2 图的深度优先遍历DFS 334 6.5.3 图的遍历小结 340 6.6 图的经典应用——图中的树问题 340 6.6.1 生成树 342 6.6.2 最小生成树MST 343 6.6.3 求最小生成树算法1——Prim 算法 344 6.6.4 求最小生成树算法2——Kruskal算法 349 6.6.5 生成树算法小结 356 6.7 图的经典应用——最短路径问题 357 6.7.1 最短路径问题的引入 357 6.7.2 单源最短路径算法——Dijkstra算法 359 6.7.3 各顶点对间最短路径算法——Floyd算法 364 6.7.4 最短路径问题小结 369 6.8 图的经典应用——活动顶点与活动边的问题 370 6.8.1 图的活动顶点排序问题的引入 370 6.8.2 AOV网与拓扑排序——活动顶点排序问题 373 6.8.3 AOE网与关键路径——活动边最长问题 378 6.8.4 活动顶点与活动边问题小结 390 6.9 本章小结 390 习题 391 第7章 数据的处理方法——排序技术 397 7.1 概述 397 7.1.1 排序的基本概念 397 7.1.2 排序算法的分类 399 7.2 插入排序 399 7.2.1 直接插入排序 399 7.2.2 希尔排序 402 7.3 交换排序 404 7.3.1 冒泡排序 404 7.3.2 快速排序 406 7.4 选择排序 409 7.4.1 简单选择排序 410 7.4.2 堆排序 411 7.5 归并排序 415 7.6 分配排序 418 7.6.1 桶排序 418 7.6.2 基数排序 421 7.7 各种排序算法的比较 424 7.8 本章小结 427 习题 428 第8章 数据的处理——索引与查找技术 431 8.1 索引的基本概念 433 8.1.1 索引的定义 433 8.1.2 索引的逻辑特征 434 8.1.3 索引的主要操作 435 8.2 线性索引技术 435 8.2.1 稠密索引 435 8.2.2 分块索引 436 8.2.3 多重表 437 8.2.4 倒排表 439 8.3 树形索引 441 8.3.1 二叉排序树 441 8.3.2 B树 448 8.4 查找概述 452 8.4.1 查找的基本概念 452 8.4.2 查找算法的性能 453 8.5 线性表的查找技术 453 8.5.1 顺序查找 453 8.5.2 有序表查找 454 8.5.3 索引查找 459 8.6 树表的查找技术 461 8.6.1 二叉排序树 461 8.6.2 B树 462 8.6.3 在非数值有序表上的查找——字典树 462 8.7 散列表的查找技术 464 8.7.1 散列概述 465 8.7.2 散列函数的设计 467 8.7.3 处理冲突的方法 469 8.7.4 散列查找的性能分析 473 8.8 本章小结 474 习题 476 第9章 经典算法 479 9.1 递归算法 479 9.1.1 递归的概念及要素 479 9.1.2 递归的应用场景 481 9.1.3 递归的计算机实现 482 9.1.4 递归方法特点分析 483 9.1.5 递归算法实例 485 9.1.6 递归小结 487 9.2 分治算法 487 9.2.1 分治是什么 487 9.2.2 分治法的适用条件 488 9.2.3 分治问题的类型 488 9.2.4 分治法小结 490 9.3 动态规划 491 9.3.1 什么是动态规划 491 9.3.2 动态规划的解题方法 493 9.3.3 动态规划解题实例 495 9.3.4 动态规划小结 500 9.4 贪心算法 501 9.4.1 贪心算法是什么 501 9.4.2 贪心算法经典问题 502 9.4.3 贪心算法小结 504 9.5 回溯法 504 9.5.1 回溯法是什么 504 9.5.2 回溯法经典问题 507 9.5.3 回溯法小结 509 9.6 分支限界法 509 9.6.1 什么是分支限界法 509 9.6.2 分支限界法的求解思想 511 9.6.3 分支限界法经典问题 512 9.6.4 分支限界法小结 514 9.7 本章小结 514 习题 516 附录A 数据的联系图 517 附录B 自定义头文件的加入方法 518 附录C 软件设计说明书格式 519 参考文献 521