数据结构与算法设计
2008-1
中国电力出版社
冯志全 著
240
一方面，从计算机软件理论角度看，程序设计=数据结构+算法；另一方面，从软件工程生命周期方法学的角度来看，算法设计是详细设计阶段的根本任务，程序设计是代码编写阶段的根本任务。无论从哪个角度分析，都突显出“数据结构”在计算机科学中的核心地位。“数据结构”不仅是计算机学科的核心课程，而且是高等院校很多专业必修的课程。也是许多高等院校计算机专业研究生入学考试的必考科目之一。 然而，由于“数据结构”既具有极强的理论性，又具有极强的实践性，给读者的学习带来极大的困难。大多数读者刚刚学习完“程序设计”课程，马上就要在“数据结构”中面临比较复杂的程序设计，无形中会在心理上对“数据结构”有种恐惧感。另一方面，数据结构把程序设计、算法设计等交织在一起，而后者本身又分别是两门比较独立的专业学科，这就更增添了问题的复杂性，使得很多读者摸不着头绪，不知所措。尤其是算法设计与分析本身比较抽象，还需要读者具有一定专业知识和实际经验的积累，使得不少读者感到难度很大。 针对上述问题，本教材应运而生，它主要有以下特色： （1）沿着“一个中心、两条主线”展开全书。“一个中心”就是以“数据结构”为中心，“两条主线”是指同一种数据结构分别沿着顺序和链式两种存储结构探讨算法。 （2）把算法与程序实现相分离。只要完成算法设计，至于用什么编程工具实现算法已经不是问题的关键了。 （3）竭力突破难点。算法设计是真正的难点所在，本教材列举大量实例，深入浅出，给出详细的操作过程，手把手帮助读者突破难点。 （4）把重点放到数据结构的应用上。唯有如此，才能突出算法、算法分析、程序设计等众多学科之间的联系，才能理解数据结构的地位和作用，才能引导读者学会根据问题需要设计恰当的数据结构。 （5）把计算机学科最新研究的成果引入到教材中，让读者从崭新的背景中了解相关知识点，感到技术发展的崭新气息和强烈挑战。 另外，本教材采用的总体编写思路和组织风格是：问题提出→问题抽象→算法思想→算法描述→算法实现→实例分析→算法分析，但考虑到篇幅所限，不同章节又有所差别。在适当的技术背景下有针对性地提出问题，有利于激发读者的学习动机和学习兴趣；从问题中抽象出一般性（数学）模型，并用规范的形式进行问题描述，是计算机科学中研究问题的一个重要环节；算法思想主要分析算法的核心思路，突出算法的创新点和关键点，有利于读者探究问题的突破口；算法描述要求用专业规范的形式完整地描述解决问题模型的步骤；算法实现为读者把算法转变为程序代码的基本过程进行示范，虽然教材中不少地方省略了这个环节，但对于计算机开发人员来说，这是一项基本功；实例分析主要示意算法对某具体输入的一个执行过程，检验算法的正确性和可行性，同时有利于读者加深对算法基本思想的理解；算法分析主要分析算法的时间开销。
《21世纪高等学校规划教材：数据结构与算法设计》是为适应各类大学本科生学习数据结构的需要而编写的教材。《21世纪高等学校规划教材：数据结构与算法设计》共分11章，第1章绪论主要介绍学习这门课程的意义以及这门课程的研究内容和关键问题；第2章线性表主要介绍线性表的特点以及算法设计；第3章栈和队列主要介绍这两种结构的实现方法及其应用；第4章串主要介绍了串的几种典型的算法；第5章数组和广义表主要介绍数组存储结构的特点和广义表的存储结构；第6章树和二叉树主要介绍树和二叉树的构造、遍历以及线索化方法；第7章图主要介绍图的实现方法以及典型算法；第8章介绍查找；第9章介绍排序，第10章介绍文件，最后一章是算法设计策略。第8、9、10章可以看成是数据结构的基本应用；最后一章可以看成是数据结构的高级应用或理论升华。
前言第1章 绪论1.1 数据结构的实践意义1.2 数据结构的理论意义1.3 数据结构研究的内容和关键问题习题第2章 线性表2.1 线性表的概念及抽象数据类型定义2.2 线性表的顺序存储2.3 线性表的链式存储2.4 线性表的应用——一元多项式的表示及相加2.5 顺序表与链表的综合比较习题第3章 栈和队列3.1 栈3.2 队列习题第4章 串4.1 串的定义与操作4.2 串的存储结构及操作4.3 串操作应用举例习题第5章 数组和广义表5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表习题第6章 树6.1 树的定义、操作及基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 哈夫曼树及其应用习题第7章 图7.1 图定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性7.5 有向无环图及其应用7.6 最短路径习题第8章 查找8.1 查找的基本概念8.2 静态查找表8.3 动态查找表8.4 哈希表习题第9章 排序9.1 概述9.2 插入排序9.3 交换排序9.4 选择排序9.5 归并排序9.6 外部排序简介习题第10章 文件10.1 基本概念10.2 顺序文件10.3 索引文件10.4 ISAM文件和VSAM文件10.5 直接存取文件（散列文件）习题第11章 算法设计策略11.1 分而治之（DivideandConqureAlgorithm）11.2 贪心算法（GreedyAlgorithm）11.3 动态规划算法（DynamicProgramming）11.4 状态搜索策略（StateSearch）11.5 回溯算法（BacktrakingAlgorithm）11.6 随机算法（RandomAlgorithm）11.7 算法设计中关键与技巧习题参考文献
《21世纪高等学校规划教材：数据结构与算法设计》不仅可作为大专院校的教材，而且适用于自学者学习本书的，还可以作为研究生入学考试的参考资料。
