数据结构

第1章 数据结构基础

1.1 什么是数据结构

1.2 数据结构的定义

1.3 数据结构的目的

1.4 数据结构的种类

1.5 数据结构与抽象数据类型

1.6 数据结构的特性

1.7 数据结构的表现方式

1.8 数据结构的基本操作

1.8.1 数据结构操作的成本

1.8.2 最好、最坏、平均

1.8.3 O、Ω、⊙表示

1.9 数据结构的哲学

1.1 0为什么学习数据结构

思考题

第2章 栈结构

2.1 后进先出即为栈

2.2 栈的定义

2.3 栈的实现

2.4 栈的应用

2.4.1 应用1：乘坐校园通勤车

2.4.2 应用2：反转波兰计算器

2.4.3 表达式的前、中、后缀表示及其转换

2.4.4 应用3：括号匹配

2.5 链接栈（栈的链接实现）

2.6 链接栈存在的问题

思考题

第3章 队列结构

3.1 先进先出即为队列

3.2 队列的实现

3.3 队列实现的别样问题

3.4 队列的环形实现

3.5 基于计数器的循环队列的实现

3.6 队列应用举例

3.6.1 应用1：先来先得礼品专送

3.6.2 应用2：机场模拟程摩

3.7 链接队列

3.8 链接队列应用举例：多项式算术

思考题

第4章 表结构

4.1 表的定义

4.2 表的实现

4.3 表结构应用举例：查找特定位置上的乘客编号

4.4 链表——链接实现的表结构

4.4.1 链表的插入操作

4.4.2 链表的删除操作

4.4.3 链表的其他操作

4.4.4 链表操作的时间成本

4.4.5 链表的优化：记住当前位置

4.5 双链表

4.6 基于数组和基于链表实现的表结构比较

4.7 链表的应用举例：字典

4.8 讨论：栈、队列、表、栈表、队表

思考题

第5章 查找操作

5.1 什么是查找

5.2 查找的实现

5.3 顺序查找

5.4 折半查找

5.5 查找的成本下限

5.6 常数查找

5.6.1 直接查找

5.6.2 间接查找

思考题

第6章 排序操作

6.1 什么是排序

6.2 排序的实现

6.3 插入排序

6.4 选择排序

6.5 冒泡／沉底排序

6.6 希尔排序

6.7 归并排序

6.7.1 归并排序的时间复杂性

6.7.2 归并排序的链表实现

6.8 快速排序

6.8.1 快速排序的过程

6.8.2 快速排序的时间成本分

思考题

第7章 高级表结构

7.1 穷则思变

7.2 跳转表

7.2.1 跳转表的定义

7.2.2 跳转表操作

7.3 索引表

7.4 哈希表（散列表）

7.4.1 哈希函数

7.4.2 哈希结构中的碰撞问题

7.4.3 开放寻址哈希

7.4.4 封闭寻址哈希

7.4.5 探寻序列的设计

7.4.6 哈希结构的查找效率

7.4.7 哈希表的实现

7.4.8 哈希表结构的测试

7.5 讨沦：跳转表、哈希表、索引表

思考题

第8章 树结构

8.1 树结构的定义

8.2 二叉树

8.2.1 二叉树的另一种表示

8.2.2 二叉树的遍历

8.2.3 编译器中用到的二叉树结构

8.2.4 二叉树的基本操作

8.3 二叉查找树

8.3.1 二叉查找树的查找操作

8.3.2 二叉查找树的插入操作

8.3.3 二叉查找树的删除操作

8.3.4 构建初始二叉查找树

8.3.5 二叉查找树结构的测试

8.3.6 二叉查找树的高度

8.4 平衡二叉树

8.5 AVL高度平衡树

8.5.1 AVL树的实现

8.5.2 AVL树的插入操作

8.5.3 AVL树的节点删除操作

8.5.4 AVL树结构的测试

8.6 满二叉树和完全二叉树

思考题

……

第9章 高级树结构

第10章 堆结构

第11章 图结构

第12章 集合结构

第13章 划分结构

附录

从软件设计师和系统架构师角度出发，以“问题”为驱动，以“使用”为轴线，对每一种数据结构出现的动机、发展逻辑、表示方式进行演绎，再现了数据结构的本质和内涵。　　逻辑性强，注重阐述如何从一种想法转换为一种设计，又如何从设计转化为具体程序，从而化复杂为简单、化抽象为具体，将学习的难度大幅度降低。　　内容丰富，将重心集中在数据结构本身的设计和构造上，抛开与数据结构无关的外在因素，摒弃繁杂的语言叙述，有利于初学者更好地理解数据结构相关知识。　　采取“上分下合”策略，将数据结构内容与算法进行适度剥离，与程序设计更加靠近，更好地满足了程序设计的现实需求；章节安排和知识阐述上富有创新，讨论问题独到有趣，代码实现简洁且符合软件工程规范，具有较好的可读性。《高等学校教材：数据结构：炫动的0、1之弦》从软件设计师和系统架构师的视角对数据结构进行阐述。通过两个角度的对望，以实际生活中的“问题”为驱动，以计算机软件设计师的“使用”为轴线，对每一种数据结构出现的动机、发展逻辑、表示方式、实现细节进行演绎，再现了数据结构的本质和内涵。《高等学校教材：数据结构：炫动的0、1之弦》讨论的结构包括栈、队列、表、栈表、索引表、跳转表、哈希表、二叉（查找）树、AVL树、伸展树、B/B+树、堆、幂堆、斐波那契堆、图、集合、划分和标准模板结构等。全书逻辑性强，注重阐述如何从一种想法转换为一种设计，又如何从设计转化为具体程序，从而化复杂为简单、化抽象为具体，大幅度降低学习和掌握数据结构的难度。为了方便准备考研的读者，《高等学校教材：数据结构：炫动的0、1之弦》还提供了2009-2010年两年的全国硕士研究生入学统一考试中数据结构部分真题的详细解析。　　《高等学校教材：数据结构：炫动的0、1之弦》可作为高等学校计算机科学与技术、软件工程等相关专业数据结构课程教材，也可供程序设计人员及参加全国硕士研究生入学统一考试的应试者参考使用。【作者简介】邹恒明，美国密歇根大学（University of Michigan-Ann Arbor）计算机科学与工程博士、中国科学院计算技术研究所计算机科学硕士、华中科技大学计算机科学与工程学士；曾先后在美国IBM、美国国家数据公司、美国朗讯和美国EMC公司任职8年多，现为上海交通大学教授。