实用数据结构教程:Java语言描述

　　本书以面向对象语言java作为描述语言，系统介绍如何用面向对象的方法来设计和实现传统的数据结构，内容包括数组、链表、栈、队列、表、二叉树、优先队列、堆、集合、映射、散列表、树和图等基本数据结构，以及插入、删除、遍历、查找、归并和排序等基本算法。本书突出了抽象数据类型的概念，提供了大量精心设计的示例程序，不仅讲述了常用数据结构的具体实现，而且抽象出一般的设计原则。
　　本书选材精当、结构新颖、深入浅出、简明实用，可作为高等院校计算机专业和相近专业本科生"数据结构"课程的教材或参考书，也可供计算机应用领域的工程技术人员参考。

第1章　绪论　
　1.1　数据结构与数据类型　
　1.2　抽象数据类型　
　　1.2.1　adt的规格说明　
　　1.2.2　adt的实现　
　　1.2.3　java中adt的规格说明与实现　
　1.3　串抽象数据类型　
　　1.3.1　串adt的规格说明　
　　1.3.2　串adt的实现　
　习题　
第2章　算法　
　2.1　问题、算法和程序　
　2.2　算法的代价　
　2.3　算法分析　
　　2.3.1　规模与基本操作　
　　2.3.2　运行时间和增长率　
　　2.3.3　最佳、最差和平均情况　
　2.4　大o符号　
　　2.4.1　大o的定义　
　　2.4.2　大o的性质　

　　“数据结构”是计算机专业的基础与核心课程之一，同时面向对象方法已经成为目前系统开发和程序设计的主流方式，而Java语言是目前使用最为广泛的面向对象程序设计语言之一。本书以Java为描述语言，系统地介绍如何用面向对象的方法来设计和实现传统的数据结构，内容包括数组、链表、栈、队列、表、二叉树、优先队列、堆、集合、映射、散列表、树和图等基本数据结构，以及插入、删除、遍历、查找、归并和排序等基本算法。对每一种数据结构，除了详细阐述其基本概念和可能的实现方式以外，还对每一种操作都给出Java语言的算法描述。.
　　本书中解决问题的典型步骤是：首先对问题的需求进行分析，抽象出一个适当的数学模型，即抽象数据类型(ADT)；然后设计一个规格说明来描述ADT应支持的操作，并用Java接口来表示这个规格说明；最后选择合适的数据结构来实现ADT规格说明并分析和比较各种不同实现的代价。这种做法清楚地区分了ADT的接口与实现，体现了软件工程中分离关注点的重要原则。
　　全书分为12章和3个附录。第1章介绍抽象数据类型(ADT)的概念，以及怎样用Java接口表示ADT的规格说明，并且选择不同的数据结构来实现ADT规格说明。第2章介绍算法，阐述怎样分析算法的效率并介绍递归算法。
　　第3章和第4章讲解两个简单和普遍存在的数据结构——数组和链表，以及与它们有关的插入、删除、查找、归并和排序算法。第5章和第6章介绍栈、队列、表ADT和它们各自可供选择的实现。第7章主要介绍二叉树和二叉查找树及其相关算法的实现。第8章介绍优先队列ADT及其可供选择的实现，重点介绍了堆数据结构、用堆实现优先队列和堆排序。作为优先队列的应用，还介绍了赫夫曼编码树。第9章介绍集合与映射ADT及其各种可供选择的实现。第10章介绍散列表及其插入、删除和查找操作的实现。第11章介绍树的表示与应用。第12章介绍图ADT及其实现，以及与图有关的——些算法。
　　附录A给出了分析算法的效率所需要的——些数学知识。附录B总结了对本书很重要的一些Java特性，有些高级特性可能在初级程序设计课程中被省略了。附录C提供了——些课程实验项目。
　　本书覆盖了ACM／IEEE-CS计算学科教程CC2001(后来演变成CC2005)中关于数据结构和算法方面的大部分知识单元，主要包括：
　　PF2 算法与问题求解
　　PF3 基本数据结构
　　PF4 递归..
　　AL1 基本算法分析
　　AL3 基本计算算法
　　DS5 图与树
　　本书可作为本科生一个学期(64学时)的教学内容。如果精简一部分内容(如第9章集合与映射、第12章中的迷宫问题等)，则可以在48学时内讲完。
　　本书假定读者己预先修过Java初级程序设计课程，需要掌握的基本知识主要有表达式、语句、对象和类，以及接口、异常和内部类等。读者若不熟悉这些主题可以随时参考附录B。
　　某些数学主题(如指数、对数、级数求和与递归关系)是分析算法效率时需要的。这些数学主题大多数包含在高中数学课程中。读者遇到不熟悉的数学问题时，可以查阅附录A中的相关内容。
　　本书的主要特点如下：
　　·把面向对象程序设计方法与数据结构和算法有机地结合了起来。
　　·强调抽象数据类型的概念，说明如何用“规格说明”定义抽象数据类型的操作，并且清楚地区分抽象数据类型的规格说明和它的基于合适的数据结构与算法的实现。
　　·用精心设计的Java代码表示算法，说明如何分析它们的效率，并且尽量避免涉及高深的理论和数学知识。
　　·配有大量的插图，便于学生直观地理解数据结构与算法。