本书作者力图突破此类教材多年来形成的定式，在很多方面都做了大胆尝试。在体例方面，作者结合多年教学实践，对知识点进行了重新整理编排，许多处理方法在同类教材中独树一帜，旨在将读者引向更高层次，使读者形成对数据结构的宏观认识。在内容方面，本书并未对各种数据结构面面俱到，而是按照CC2001标准对必要知识点和技能要求精心加以裁剪，通过系统分类和启发式讲解，在基本数据结构与高级数据结构之间架起一座桥梁。在算法方面，本书不仅强调对复杂度等基本概念的把握，同时结合具体问题介绍算法复杂度的各种分析方法，尤其是分摊分析等高级技巧。而且所有数据结构仍然构成一个完整的体系，帮助读者养成面向实际应用的意识，并掌握构建实际应用的基本能力。

本书充分展示了面向对象技术在现代数据结构理论中的应用，普遍采用了抽象、封装及继承等技术。本书既介绍了基本的数据结构，包括栈、队列、向量、列表结构；也介绍了若干高级数据结构，包括优先队列结构、映射和词典结构、查找树结构等。并结合具体问题介绍了算法的应用、实现及其分析方法，涉及的算法包括堆结构的生成及调整算法、Huffman编码树算法、平衡查找树的生成、插入和删除算法，并着重介绍了串匹配的KMP和BM算法。本书还通过遍历算法框架将各种图算法统一起来，并基于遍历算法模板加以实现，在同类教材中独树一帜。

本书图文并茂，循序渐进。书中代码都配有详尽而简洁的注释。书中还结合各部分的具体内容穿插了大量问题，以激发读者的求知欲，培养良好的自学习惯和自学能力。本书适合用作计算机专业本科生教材或参考书。

前言

第1章 算法及其复杂度

 1．1 计算机与算法

1．1．1 过指定垂足的直角边

1．1．2 三等分线段

1．1．3 排序

1．1．4 算法的定义

 1．2 算法性能的分析与评价

1．2．1 三个层次

1．2．2 时间复杂度及其度量

1．2．3 空间复杂度

 1．3 算法复杂度及其分析

1．3．1 O(1)——取非极端元素

1．3．2 O(logn)——进制转换

1．3．3 O(n)——数组求和

1．3．4 O(n2)——起泡排序

1．3．5 O(2r)——幂函数

 1．4 计算模型

1．4．1 可解性

1．4．2 有效可解

1．4．3 下界

 1．5 递归

1．5．1 线性递归

1．5．2 递归算法的复杂度分析

1．5．3 二分递归

1．5．4 多分支递归

第2章 栈与队列

 2．1 栈

2．1．1 栈ADT 

2．1．2 基于数组的简单实现

2．1．3 Java虚拟机中的栈

2．1．4 栈应用实例

 2．2 队列

2．2．1 队列ADT

2．2．2 基于数组的实现

2．2．3 队列应用实例

 2．3 链表

2．3．1 单链表

2．3．2 基于单链表实现栈

2．3．3 基于单链表实现队列

 2．4 位置

2．4．1 位置ADT 

2．4．2 位置接口

 2．5 双端队列

2．5．1 双端队列ADT

2．5．2 双端队列接口

2．5．3 双向链表

2．5．4 基于双向链表实现的双端队列

第3章 向量、列表与序列

 3．1 向量与数组

3．1．1 向量ADT 

3．1．2 基于数组的简单实现

3．1．3 基于可扩充数组的实现

3．1．4 java．util．ArrayList类和java．util．

Vector类

 3．2 列表

3．2．1 基于节点的操作

3．2．2 由秩到位置

3．2．3 列表ADT 

3．2．4 基于双向链表实现的列表

 3．3 序列

3．3．1 序列ADT

3．3．2 基于双向链表实现序列

3．3．3 基于数组实现序列

 3．4 迭代器

3．4．1 迭代器ADT

3．4．2 迭代器接口

3．4．3 迭代器的实现

3．4．4 Java qp的列表及迭代器

第4章 树

 4．1 术语及性质

4．1．1 节点的深度、树的深度与高度

4．1．2 节点的度与内部节点、外部

节点

4．1．3 路径

4．1．4 祖先、后代、子树和节点的

高度

…………………………………………………………