第1章 绪 论（1） 1.1 为什么要学习数据结构（1） 1.2 基本概念和术语（4） 1.3 抽象数据类型及面向对象的概念（5） 1.4 算法和算法评价（10） 1.4.1 算法（10） 1.4.2 算法设计的要求（11） 1.4.3 算法效率的度量（11） 本章小结（15） 习 题（15） 第2章 线性表（17） 2.1 线性表的定义和抽象数据类型（17） 2.2 线性表的顺序表示及操作实现（20） 2.3 线性表的链式表示和实现（25） 2.3.1 线性链表（26） 2.3.2 循环链表（34） 2.3.3 双向链表（35） 2.4 线性表的应用（37） 本章小结（40） 习 题（41） 第3章 栈和队列（43） 3.1 栈（43） 3.1.1 抽象数据类型栈的定义（43） 3.1.2 栈的表示和实现（45） 3.1.3 栈的链式存储（47） 3.2 栈的应用举例（48） 3.2.1 数制转换（48） 3.2.2 数学表达式计算（49） 3.2.3 迷宫求解（50） 3.3 栈与递归（52） 3.4 队列（56） 3.4.1 队列的定义（56） 1目 录 3.4.2 队列的实现（57） 3.4.3 循环队列（61） 3.4.4 队列的应用举例（63） 本章小结（64） 习 题（65） 第4章 串（66） 4.1 串类型的定义（66） 4.1.1 串的基本概念（66） 4.1.2 串的抽象数据类型（67） 4.2 串的表示和实现（69） 4.2.1 定长顺序存储表示（69） 4.2.2 堆分配存储表示（71） 4.2.3 串的链式存储表示（72） 4.3 串的模式匹配算法（73） 4.3.1 串模式匹配的古典算法（74） 4.3.2 串模式匹配的KMP算法（75） 本章小结（81） 习 题（81） 第5章 数组与广义表（83） 5.1 数组的定义（83） 5.2 数组的顺序表示及操作的实现（85） 5.2.1 数组的顺序表示（85） 5.2.2 数组基本操作的实现（86） 5.3 矩阵的压缩存储（88） 5.3.1 特殊矩阵（88） 5.3.2 压缩存储（89） 5.4 稀疏矩阵（91） 5.4.1 稀疏矩阵的压缩存储（91） 5.4.2 稀疏矩阵的运算（95） 5.5 广义表（100） 5.5.1 基本概念（100） 5.5.2 存储结构（102） 5.5.3 基本运算（103） 本章小结（104） 习 题（104） 第6章 树（106） 6.1 树的概念（106） 2数据结构与算法 6.1.1 树的定义（106） 6.1.2 树的抽象数据类型（106） 6.1.3 树的表示（107） 6.1.4 树的基本术语（108） 6.2 二叉树（109） 6.2.1 二叉树的定义（109） 6.2.2 二叉树的性质（110） 6.2.3 二叉树的存储结构（113） 6.3 遍历二叉树（114） 6.3.1 遍历二叉树的递归算法（114） 6.3.2 遍历二叉树的非递归算法（116） 6.4 线索二叉树（118） 6.4.1 线索（118） 6.4.2 中序线索化二叉树（118） 6.5 树与森林（121） 6.5.1 树的存储表示（121） 6.5.2 森林、树与二叉树的转换（123） 6.5.3 树和森林的遍历（124） 6.6 哈夫曼树及应用（125） 6.6.1 基本术语（125） 6.6.2 哈夫曼树的构造算法（126） 6.6.3 哈夫曼编码（127） 本章小结（128） 习 题（128） 第7章 图（130） 7.1 图的概念（130） 7.1.1 图的定义（130） 7.1.2 图的基本术语（131） 7.2 图的存储结构（133） 7.2.1 邻接矩阵表示法（133） 7.2.2 邻接表（134） 7.2.3 十字链表（136） 7.2.4 邻接多重表（137） 7.3 图的遍历（138） 7.3.1 深度优先搜索（139） 7.3.2 广度优先搜索（140） 7.4 图的连通性问题（141） 7.4.1 无向图的连通分量和生成树（141） 7.4.2 最小生成树（141） 3目 录7.5 活动网络（146） 7.5.1 用顶点表示活动的网络（146） 7.5.2 用边表示活动的网络（148） 7.6 最短路径（152） 7.6.1 从某个源点到其余各顶点的最短路径（152） 7.6.2 每一对顶点之间的最短路径（154） 本章小结（156） 习 题（157） 第8章 查 找（159） 8.1 基本概念（159） 8.2 静态查找表（161） 8.2.1 静态查找表结构（161） 8.2.2 顺序查找（161） 8.2.3 二分查找（162） 8.2.4 分块查找（164） 8.3 树表的查找（165） 8.3.1 二叉排序树（165） 8.3.2 平衡二叉树（AVL树）（170） 8.3.3 B-树和B+树（173） 8.4 哈希表（179） 8.4.1 哈希表与哈希法（179） 8.4.2 常用哈希函数的构造方法（180） 8.4.3 处理冲突的方法（182） 8.4.4 哈希表的查找分析（184） 本章小结（186） 习 题（186） 第9章 排 序（188） 9.1 概述（188） 9.2 插入排序（189） 9.2.1 直接插入排序（189） 9.2.2 二分插入排序（190） 9.2.3 表插入排序（191） 9.2.4 希尔排序（193） 9.3 交换排序（194） 9.3.1 冒泡排序（194） 9.3.2 快速排序（196） 9.4 选择排序（197） 9.4.1 直接选择排序（198） 4数据结构与算法 9.4.2 树型选择排序（198） 9.4.3 堆排序（200） 9.5 归并排序（202） 9.6 基数排序（204） 9.6.1 多关键字排序（204） 9.6.2 链式基数排序（205） 9.7 各种内排序方法的比较和选择（208） 9.7.1 各种内排序方法的比较（208） 9.7.2 各种内排序方法的选择（208） 9.8 外部排序（209） 9.8.1 外部排序的基本过程（209） 9.8.2 多路平衡归并排序（211） 9.8.3 置换-选择排序（213） 9.8.4 最佳归并排序（216） 本章小结（217） 习 题（217） 第10章 文 件（219） 10.1 文件及其逻辑特性（219） 10.1.1 有关文件的基本概念（219） 10.1.2 文件操作的类型（220） 10.1.3 文件的存储结构（220） 10.2 顺序文件（221） 10.2.1 顺序文件的特点（221） 10.2.2 顺序文件操作（221） 10.3 索引文件（222） 10.3.1 概 述（222） 10.3.2 静态索引———ISAM 文件（223） 10.3.3 动态索引———VSAM 文件（225） 10.3.4 两种索引结构的比较（227） 10.4 散列文件（227） 10.5 多重链接表文件（229） 10.6 倒排文件（230） 本章小结（230） 习 题（231） 参考文献（232）