数据结构及应用算法教程

　　本书从数据类型的角度，分别讨论了4大类型的数据结构的逻辑特性、存储表示及其应用。为了便于读者理解，书中对数据结构众多知识点的来龙去脉都做了详细的解释和说明，并配有大量的算法实例穿插其间；书的最后还专门辟出一章，用来讲解数据结构在解决实际问题中的应用示例，便于举一反三。本书的第1章综述数据、数据结构和抽象数据类型等基本概念和算法；第2章、第4至7章从数据类型的角度，分别讨论线性表、栈和队列、串和数组、二叉树和树以及图和广义表等数据结构的逻辑特性、存储表示及其应用；第3章和第8章分别讨论排序和查找表的各种实现方法，其中除介绍各种实现方法外，并着重对算法的时间效率做了定性的分析，对算法的应用场合及适用范围进行了比较和介绍；第9章讨论常用的文件结构；第10章以8个数据结构的综合应用为例，阐述以抽象数据类型为中心的程序设计方法，这一章的内容相当于“数据结构学习指导”，本意是为学生提供一个“综合利用数据结构知识编制小型软件”的规范示例。书的每一章都配有适量的习题，供读者复习提高之用。教授学时可为40至60，另外应留有一定的时间供学生完成适量的上机作业。本书在编排方面注意了数据结构本身的内在联系和从易到难的学习规律。例如，将排序安排在第3章，因为对读者来说，排序的内容比较容易理解，而且所涉及的数据结构主要是线性结构；又如对栈和队列的学习重点应是它们的应用，因此在第4章里更多地列举了栈和队列的应用例子；在第5章中，结合C语言的串类型讲解串结构的知识内容，以使实际和理论在应用中和谐统一起来，等等。又如为了降低理解难度，尽管广义表属线性结构，但由于它的“递归”特性，使得涉及广义表操作的算法和树更相似，因此将它放在图之后进行讨论。全书采用了类C语言作为数据结构和操作算法的描述工具，它是C语言的一个精选子集，同时又采用了C++对C的非面向对象的增强功能。例如动态分配和释放顺序存储结构的空间；利用引用参数传递运算的结果；使用缺省参数以简化函数参数表的描述，等等。这些措施使数据类型的定义和数据结构相关操作算法的描述更加简明清晰、可读性更好，转变成C程序也极方便。另一方面又可把类型定义和操作算法稍加技术处理，就很容易将其封装成类，并进一步转化成面向对象的程序模型。从课程性质上讲，“数据结构”是一门专业技术基础课。它的教学要求应当是：学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，要求学生会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。数据结构比高级程序设计语言课有着更高的要求，它重在培养学生的数据抽象能力。在学习本书时应至少掌握一门高级程序设计的知识，如掌握的是C语言则最为理想；若能具有初步的离散数学和概率论的知识，对书中某些内容的理解会更容易。学习本书的同时还可把《数据结构》（C语言版）作为配套参考用书。与本书配套的还有一张软盘。本书内容丰富，概念阐述细致清楚，除可作为普通高等院校计算机类专业的教材之外，还可作为信息类相关专业“数据结构”或“软件基础”课程的本科教材。对于计算机类专业的学生或从事计算机工程与应用工作的科技工作者，本书也是一本实用的参考手册。

暂缺《数据结构及应用算法教程》作者简介

第1章  绪论                  
     1. 1  数据结构讨论的范畴                  
     1. 2  与数据结构相关的概念                  
     1. 2. 1  基本概念和术语                  
     1. 2. 2  数据结构(data structures)                  
     1. 2. 3  数据类型和抽象数据类型                  
     1. 3  算法及其描述和分析                  
     1. 3. 1  算法                  
     1. 3. 2算法的描述                  
     1. 3. 3  算法效率的衡量方法和准则                  
     1. 3. 4  算法的存储空间需求                  
     习题                  
   第2章  线性表                  
     2. 1  线性表的类型定义                  
     2. 1. 1  线性表的定义                  
     2. 1. 2  线性表的基本操作                  
     2. 2  线性表的顺序表示和实现                  
     2. 2. 1  顺序表——线性表的顺序存储表示                  
     2. 2. 2  顺序表中基本操作的实现                  
     2. 2. 3  顺序表其他算法举例                  
     2. 3  线性表的链式表示和实现                  
     2. 3. 1  单链表和指针                  
     2. 3. 2  单链表的基本操作                  
     2. 3. 3  单链表的其他操作举例                  
     2. 3. 4  循环链表                  
     2. 3. 5  双向链表                  
     2. 4  有序表                  
     2. 5  顺序表和链表的综合比较                  
     习题                  
   第3章  排序                  
     3. 1  排序的基本概念                  
     3. 2  简单排序方法                  
     3. 2. 1  插入排序                  
     3. 2. 2  起泡排序                  
     3. 3  先进排序方法                  
     3. 3. 1  快速排序                  
     3. 3. 2  归并排序                  
     3. 3. 3  堆排序                  
     3. 4  基数排序                  
     3. 5  各种排序方法的综合比较                  
     习题                  
   第4章  栈和队列                  
     4. 1  栈                  
     4. 1. 1  栈的结构特点和操作                  
     4. 1. 2  栈的表示和操作的实现                  
     4. 2  栈的应用举例                  
     4. 3  队列                  
     4. 3. 1  队列的结构特点和操作                  
     4. 3. 2  队列的表示和操作的实现                  
     4. 4  队列应用举例                  
     习题                  
   第5章  串和数组                  
     5. 1  串的定义和操作                  
     5. 2  串的表示和实现                  
     5. 2. 1  定长顺序存储表示                  
     5. 2. 2  堆分配存储表示                  
     5. 2. 3  块链存储表示                  
     5. 3  正文模式匹配                  
     5. 4  正文编辑——串操作应用举例                  
     5. 5  数组                  
     5. 5. 1  数组的定义和操作                  
     5. 5. 2  数组的顺序表示和实现                  
     5. 5. 3  数组的应用                  
     5. 6  矩阵的压缩存储                  
     5. 6. 1  特殊形状矩阵的存储表示                  
     5. 6. 2  随机稀疏矩阵的存储压缩                  
     习题                  
   第6章  二叉树和树                  
     6. 1  二叉树                  
     6. 1. 1  二叉树的定义和基本术语                  
     6. 1. 2  二叉树的几个基本性质                  
     6. 1. 3  二叉树的存储结构                  
     6. 2  二叉树遍历                  
     6. 2. 1  问题的提出                  
     6. 2. 2  遍历算法描述                  
     6. 2. 3  二叉树遍历应用举例                  
     6. 2. 4  线索二叉树                  
     6. 3  树和森林                  
     6. 3. 1  树和森林的定义                  
     6. 3. 2  树和森林的存储结构                  
     6. 3. 3  树和森林的遍历                  
     6. 4  树的应用                  
     6. 4. 1  堆排序的实现                  
     6. 4. 2  二叉排序树                  
     6. 4. 3  赫夫曼树及其应用                  
     习题                  
   第7章  图和广义表                  
     7. 1  图的定义和术语                  
     7. 2  图的存储结构                  
     7. 2. 1  图的数组(邻接矩阵)存储表示                  
     7. 2. 2  图的邻接表存储表示                  
     7. 3  图的遍历                  
     7. 3. 1  深度优先搜索遍历图                  
     7. 3. 2  广度优先搜索遍历图                  
     7. 4  连通网的最小生成树                  
     7. 5  单源最短路径                  
     7. 6  拓扑排序                  
     7. 7  关键路径                  
     7. 8  广义表                  
     7. 8. 1  广义表的定义                  
     7. 8. 2  广义表的存储结构                  
     7. 8. 3  广义表的遍历                  
     习题                  
   第8章  查找表                  
     8. 1 静态查找表                  
     8. 1. 1  顺序查找                  
     8. 1. 2  折半查找                  
     8. 1. 3 分块查找                  
     8. 2 动态查找表                  
     8. 2. 1  二叉查找树                  
     8. 2. 2  键树                  
     8. 3  哈希表及其查找                  
     8. 3. 1  什么是哈希表                  
     8. 3. 2  构造哈希函数的几种方法                  
     8. 3. 3  处理冲突的方法和建表示例                  
     8. 3. 4  哈希表的查找及其性能分析                  
     8. 3. 5  哈希表的应用举例                  
     习题                  
   第9章  文件                  
     9. 1  基本概念                  
     9. 1. 1  外存储器简介                  
     9. 1. 2  有关文件的基本概念                  
     9. 2  顺序文件                  
     9. 2. 1  存储在顺序存储器上的文件                  
     9. 2. 2  存储在直接存储器上的文件                  
     9. 3  索引文件                  
     9. 3. 1  B树                  
     9. 3. 2  B+树和索引顺序文件                  
     9. 4  哈希文件                  
     9. 4. 1  文件组织方式                  
     9. 4. 2  文件的操作                  
     9. 5  多关键码文件                  
     9. 5. 1  倒排文件                  
     9. 5. 2  索引链接文件                  
     习题                  
   第10章  数据结构程序设计示例                  
     10. 1  抽象数据类型                  
     10. 2  从问题到程序的求解过程                  
     10. 2. 1  建立数据结构模型设计抽象数据类型                  
     l0. 2. 2  算法设计                  
     10. 2. 3  实现抽象数据类型                  
     10. 2. 4  编制程序代码并进行静态测试和动态调试                  
     10. 3  程序的规范说明                  
     10. 4  应用示例分析                  
     10. 4. 1  含并. 交和差运算的集合类型                  
     l0. 4. 2  最佳任务分配方案求解                  
     10. 4. 3  排队问题的系统仿真                  
     l0. 4. 4  十进制四则运算计算器                  
     lo. 4. 5  自行车零部件库的库存模型                  
     l0. 4. 6  教务课程计划的辅助制定                  
     lo. 4. 7  一个小型全文检索模型                  
     10. 4. 8  汽车牌照的快速查找                  
   实习题                  
     实习一  链表的维护与文件形式的保存                  
     实习二  用回溯法求解“稳定婚配”问题                  
     实习三  以队列实现的仿真技术预测理发馆的经营状况                  
     实习四  利用树型结构的搜索算法模拟因特网域名的查询                  
     实习五  管道铺设施工的最佳方案选择                  
     实习六  使用哈希表技术判别两个源程序的相似性                  
   附录  算法一览表参考文献