数据结构

图书目录

第1章 绪论

1.1什么是数据结构

1.2抽象数据类型及面向对象概念

1.2.1数据类型

1.2.2数据抽象与抽象数据类型

1.2.3 面向对象的概念

1.2.4 用于描述数据结构的语言

1.3数据结构的抽象层次

*1.4 用C＋＋描述面向对象程序

1.4.1C＋＋的函数特征

1.4.2C＋＋的数据声明

1.4.3C＋＋的作用域

1.4.4 C＋＋的类

1.4.5C＋＋中的对象

1.4.6C＋＋的输入输出

1.4.7C＋＋中的函数

1.4.8C＋＋中的参数传递

1.4.9 C＋＋中的函数名重载和操作符重载

1.4.10 C＋＋中的动态存储分配

1.4.11友元（friend）函数

1.4.12内联（inline）函数

1.4.13 结构（struct）与类

1.4.14 联合（Union）与类

1.5算法定义

1.6模板（template）

1.7性能分析与度量

1.7.1算法的性能标准

1.7.2算法的后期测试

1.7.3算法的事前估计

1.7.4 空间复杂度度量

1.7.5时间复杂度度量

1.7.6时间复杂度的渐进表示法

1.7.7渐进的空间复杂度

习题

第2章 数组

2.1作为抽象数据类型的数组

2.1.1在C＋＋中数组的定义和初始化

2.1.2作为抽象数据类型的数组

2.1.3数组的顺序存储方式

2.2 顺序表

2.2.1顺序表的定义和特点

2.2.2顺序表的类定义

2.2.3顺序表的查找、插入和删除

2.2.4作为抽象数据类型，使用顺序表的事例

2.3多项式抽象数据类型

2.3.1多项式抽象数据类型

2.3.2 多项式的表示

2.3.3多项式的相加

2.4 稀疏矩阵

2.4.1稀疏矩阵的抽象数据类型

2.4.2稀疏矩阵的压缩表示

2.4.3稀疏矩阵的转置

2.4.4 稀疏矩阵相乘

2.5字符串

2.5.1字符串抽象数据类型和类定义

2.5.2字符串操作的实现

2.5.3字符串的模式匹配

2.5.4模式匹配的改进算法——KMP（D.E.Knuth—J.H.Morris—V.R.Pratt）算法

习题

第3章 链表

3.1单链表（SinglyLinkedList）

3.1.1单链表的结构

3.1.2单链表的类定义

3.1.3单链表中的插入与删除

3.1.4带表头结点的单链表

3.1.5用模板定义的单链表类

3.1.6单链表的游标（Iterator）类

3.1.7静态链表

3.2循环链表

3.2.1循环链表的类定义

3.2.2用循环链表求解约瑟夫问题

3.3多项式及其相加

3.3.1多项式的类定义

3.3.2多项式的加法

3.4双向链表

3.5稀疏矩阵

3.5.1稀疏矩阵的类定义

3.5.2稀疏矩阵的建立

3.5.3删除稀疏矩阵

3.6C＋＋中的虚函数和动态联编

3.6.1C＋＋中的继承（inheritance）

3.6.2基类与派生类对象指针的转换

3.6.3虚函数（virtualfunction）

3.6.4 纯虚函数和抽象基类

3.6.5多态性（polymorphism）和动态联编

习题

第4章 栈和队列

4.1栈

4.1.1栈的抽象数据类型

4.1.2栈抽象数据类型的顺序存储表示与实现——顺序栈

4.1.3栈抽象数据类型的链接存储表示——链式栈

4.2表达式的计算

4.2.1表达式

4.2.2应用后缀表示计算表达式的值

4.2.3中缀表达式转换为后缀表达式

4.3队列

4.3.1队列的抽象数据类型

4.3.2队列的顺序存储表示——循环队列

4.3.3队列的链接存储表示——链式队列

4.3.4 队列的应用举例——打印二项展开式（a＋b）j的系数

4.4优先级队列（PriorityQueue）

4.4.1优先级队列的定义

4.4.2优物级队列的存储表示和实现

4.5事件驱动模拟

习题

第5章 递归

5.1递归的概念

5.2迷宫问题

5.3递归过程与递归工作栈

5.4利用栈实现的迷宫问题非递归解法

5.5广义表

5.5.1广义表的概念

5.5.2广义表的表示及操作

5.5.3广义表存储结构的实现

5.5.4 广义表的访问算法

5.5.5广义表的递归算法

5.5.6三元多项式的表示

习题

第6章 树与森林

6.1树和森林的概念

6.1.1树的定义

6.1.2树的术语

6.1.3树的抽象数据类型

6.2二叉树

6.2.1二叉树的定义

6.2.2二叉树的性质

6.2.3二叉树的抽象数据类型

6.3二叉树的表示

6.3.1数组表示

6.3.2链表存储表示

6.4二叉树遍历

6.4.1中序遍历

6.4.2前序遍历

6.4.3后序遍历

6.4.4 应用二叉树遍历的事例

6.4.5二叉树遍历的游标类

6.4.6 不用栈的二叉树中序遍历算法

6.5线索化二叉树

6.5.1线索

6.5.2中序线索化二叉树

6.5.3前序与后序的线索化二叉树

6.6 堆（Heap ）

6.6.1堆的定义

6.6.2堆的建立

6.6.3堆的插入与删除

6.7树与森林

6.7.1树的存储表示

6.7.2森林与二叉树的转换

6.7.3树的遍历

6.7.4 森林的遍历

6.8二叉树的计数

6.9 霍夫曼树

6.9.1路径长度

6.9.2霍夫曼树

6.9.3霍夫曼编码

习题

第7章 集合与搜索

7.1集合及其表示

7.1.1集合基本概念

7.1.2以集合为基础的抽象数据类型

7.1.3用位向量实现集合抽象数据类型

7.1.4 用有序链表实现集合的抽象数据类型

7.2 等价类和并查集

7.2.1等价关系与等价类

7.2.2确定等价类的链表方法

7.2.3并查集

7.3静态搜索结构

7.3.1搜索的概念

7.3.2静态搜索结构

7.3.3顺序搜索

7.3.4 基于有序顺序表的折半搜索

7.3.5基于有序顺序表的斐波那契搜索和插值搜索

7.4 二叉搜索树

7.4.1定义

7.4.2二叉搜索树上的搜索

7.4.3二叉搜索树的插入

7.4.4 二叉搜索树的删除

7.4.5与二叉搜索树相关的中序游标类

7.5最优二叉搜索树

7.5.1扩充二叉搜索树

7.5.2最优二叉搜索树

7.6AVL树

7.6.1AVL树的定义

7.6.2平衡化旋转

7.6.3AVL树的插入和删除

7.6.4AVL树的高度

习题

第8章 图

8.1图的基本概念

8.1.1图的基本概念

8.1.2图的抽象数据类型

8.2图的存储表示

8.2.1邻接矩阵

8.2.2 邻接表

8.2.3邻接多重表

8.3图的遍历与连通性

8.3.1深度优先搜索

8.3.2广度优先搜索

8.3.3连通分量

8.3.4 重连通分量

8.4 最小生成树

8.4.1克鲁斯卡尔（Kruskal）算法

8.4.2普里姆（Prim）算法

8.5最短路径

8.5.1边上权值非负情形的单源最短路径问题

8.5.2边上权值为任意值的单源最短路径问题

8.5.3所有顶点之间的最短路径

8.6 活动网络

8.6.1用顶点表示活动的网络

8.6.2用边表示活动的网络

习题

第9章 排序

9.1概述

9.2插入排序

9.2.1直接插入排序

9.2.2折半插入排序

9.2.3链表插入排序

9.2.4 希尔排序

9.3交换排序

9.3.1起泡排序

9.3.2快速排序

9.4 选择排序

9.4.1直接选择排序

9.4.2锦标赛排序

9.4.3堆排序

9.5归并排序

9.5.1归并

9.5.2迭代的归并排序算法

9.5.3递归的表归并排序

9.6基数排序

9.6.1多关键码排序

9.6.2链式基数排序

9.7外排序

9.7.1外排序的基本过程

9.7.2k路平衡归并

9.7.3初始归并段的生成

9.7.4 并行操作的缓冲区处理

9.7.5最佳归并树

习题

第10章 索引结构与散列

10.1静态索引结构

10.1.1线性索引

10.1.2倒排表

10.1.3m路静态搜索树

10.2动态索引结构

10.2.1动态的m路搜索树

10.2.2B_树

10.2.3B_树的插入

10.2.4 B_树的删除

10.2.5B＋树

10.3Trie 树

10.3.1Trie树的定义

10.3.2Trie树的搜索

10.3.3在Trie树上的插入和删除

10.4散列

10.4.1词典（Dictionary）的抽象数据类型

10.4.2散列表与散列方法

10.4.3散列函数

10.4.4 处理溢出的闭散列方法

10.4.5处理溢出的开散列方法——链地址法

10.4.6散列表分析

10.5可扩充散列

10.5.1二叉Trie 树

10.5.2将二叉Trie树转换为目录

10.5.3插入与目录扩充

10.5.4 删除与目录收缩

10.5.5性能分析

习题

附录 实习要求与实习报告

实习1栈和队列

实习2串（内容：全屏幕文本编辑器）

实习3树（内容：作业调度）

实习4图（内容：某公园导游图）

实习5查找、排序（内容：简单的职工管理系统）

参考文献