数据结构：算法实现与解析.高一凡(第二版C语言版).扫描版
目 录第1章 绪论........................................................................................................................................11.1 什么是数据结构.................................................................................................................................11.2 基本概念和术语.................................................................................................................................11.3 抽象数据类型的表示与实现...............................................................................................................11.4 算法和算法分析.................................................................................................................................71.4.1 算法.............................................................................................................................................71.4.2 算法设计的要求..........................................................................................................................71.4.3 算法效率的度量..........................................................................................................................7第2章 线性表....................................................................................................................................92.1 线性表的类型定义..............................................................................................................................92.2 线性表的顺序表示和实现..................................................................................................................92.3 线性表的链式表示和实现................................................................................................................ 212.3.1 线性链表 ................................................................................................................................... 212.3.2 循环链表 ................................................................................................................................... 602.3.3 双向链表 ................................................................................................................................... 652.4 一元多项式的表示及相加................................................................................................................ 80第3章 栈和队列............................................................................................................................. 863.1 栈...................................................................................................................................................... 863.1.1 抽象数据类型栈的定义............................................................................................................. 863.1.2 栈的表示和实现........................................................................................................................ 863.2 栈的应用举例................................................................................................................................... 903.2.1 数制转换 ................................................................................................................................... 903.2.2 括号匹配的检验........................................................................................................................ 923.2.3 行编辑程序................................................................................................................................ 933.2.4 迷宫求解 ................................................................................................................................... 953.2.5 表达式求值.............................................................................................................................. 1003.3 栈与递归的实现............................................................................................................................. 1043.4 队列................................................................................................................................................ 1083.4.1 抽象数据类型的定义............................................................................................................... 1083.4.2 链队列队列的链式表示和实现........................................................................................ 1083.4.3 循环队列队列的顺序表示和实现 .................................................................................... 1143.5 离散事件模拟.................................................................................................................................. 130第4章 串........................................................................................................................................ 1404.1 串类型的定义................................................................................................................................. 140 - 2 -4.2 串的表示和实现............................................................................................................................. 1404.2.1 定长顺序存储表示 .................................................................................................................. 1404.2.2 堆分配存储表示...................................................................................................................... 1464.2.3 串的块链存储表示 .................................................................................................................. 1514.3 串的模式匹配算法.......................................................................................................................... 1584.3.1 求子串位置的定位函数Index(S,T,pos)..................................................................................... 1584.3.2 模式匹配的一种改进算法....................................................................................................... 1594.4 串操作应用举例............................................................................................................................. 1614.4.1 文本编辑 ................................................................................................................................. 1614.4.2 建立词索引表.......................................................................................................................... 167第5章 数组和广义表 .................................................................................................................. 1775.1 数组的定义..................................................................................................................................... 1775.2 数组的顺序表示和实现.................................................................................................................. 1775.3 矩阵的压缩存储............................................................................................................................. 1815.3.1 特殊矩阵 ................................................................................................................................. 1815.3.2 稀疏矩阵 ................................................................................................................................. 1815.4 广义表的定义................................................................................................................................. 2065.5 广义表的存储结构.......................................................................................................................... 2065.6 m元多项式的表示 .......................................................................................................................... 2075.7 广义表的递归算法.......................................................................................................................... 2075.7.1 求广义表的深度...................................................................................................................... 2075.7.2 复制广义表.............................................................................................................................. 2085.7.3 建立广义表的存储结构........................................................................................................... 208第6章 树和二叉树....................................................................................................................... 2186.1 树的定义和基本术语...................................................................................................................... 2186.2 二叉树............................................................................................................................................ 2186.2.1 二叉树的定义.......................................................................................................................... 2186.2.2 二叉树的性质.......................................................................................................................... 2186.2.3 二叉树的存储结构 .................................................................................................................. 2186.3 遍历二叉树和线索二叉树.............................................................................................................. 2456.3.1 遍历二叉树.............................................................................................................................. 2456.3.2 线索二叉树.............................................................................................................................. 2456.4 树和森林......................................................................................................................................... 2546.4.1 树的存储结构.......................................................................................................................... 2546.4.2 森林与二叉树的转换............................................................................................................... 2706.4.3 树和森林的遍历...................................................................................................................... 2706.5 树与等价问题................................................................................................................................. 2716.6 赫夫曼树及其应用.......................................................................................................................... 2716.6.1 最优二叉树(赫夫曼树)........................................................................................................... 2716.6.2 赫夫曼编码.............................................................................................................................. 271- 3 -第7章 图........................................................................................................................................ 2777.1 图的定义和术语............................................................................................................................. 2777.2 图的存储结构................................................................................................................................. 2777.2.1 数组表示法.............................................................................................................................. 2777.2.2 邻接表..................................................................................................................................... 2927.2.3 十字链表 ................................................................................................................................. 3067.2.4 邻接多重表.............................................................................................................................. 3177.3 图的遍历......................................................................................................................................... 3287.3.1 深度优先搜索.......................................................................................................................... 3287.3.2 广度优先搜索.......................................................................................................................... 3297.4 图的连通性问题............................................................................................................................. 3357.4.1 无向图的连通分量和生成树 ................................................................................................... 3357.4.2 有向图的强连通分量............................................................................................................... 3387.4.3 最小生成树.............................................................................................................................. 3387.4.4 关节点和重连通分量............................................................................................................... 3437.5 有向无环图及其应用...................................................................................................................... 3477.5.1 拓扑排序 ................................................................................................................................. 3477.5.2 关键路径 ................................................................................................................................. 3507.6 最短路径......................................................................................................................................... 3537.6.1 从某个源点到其余各顶点的最短路径 .................................................................................... 3537.6.2 每一对顶点之间的最短路径 ................................................................................................... 356第8章 动态存储管理 .................................................................................................................. 3668.1 概述................................................................................................................................................ 3668.2 可利用空间表................................................................................................................................. 3668.3 边界标识法..................................................................................................................................... 3668.3.1 可利用空间表的结构............................................................................................................... 3668.3.2 分配算法 ................................................................................................................................. 3678.3.3 回收算法 ................................................................................................................................. 3748.4 伙伴系统......................................................................................................................................... 3748.4.1 可利用空间表的结构............................................................................................................... 3748.4.2 分配算法 ................................................................................................................................. 3758.4.3 回收算法 ................................................................................................................................. 3808.5 无用单元收集................................................................................................................................. 381第9章 查找.................................................................................................................................... 3849.1 静态查找表..................................................................................................................................... 3849.1.1 顺序表的查找.......................................................................................................................... 3849.1.2 有序表的查找.......................................................................................................................... 3879.1.3 静态树表的查找...................................................................................................................... 3889.1.4 索引顺序表的查找 .................................................................................................................. 390 - 4 -9.2 动态查找表..................................................................................................................................... 3919.2.1 二叉排序树和平衡二叉树....................................................................................................... 3919.2.2 B树和B 树.............................................................................................................................. 3999.2.3 键树......................................................................................................................................... 4049.3 哈希表............................................................................................................................................ 4139.3.1 什么是哈希表.......................................................................................................................... 4139.3.2 哈希函数的构造方法............................................................................................................... 4139.3.3 处理冲突的方法...................................................................................................................... 4139.3.4 哈希表的查找及其分析........................................................................................................... 414第10章 内部排序......................................................................................................................... 41910.1 概述.............................................................................................................................................. 41910.2 插入排序....................................................................................................................................... 41910.2.1 直接插入排序........................................................................................................................ 41910.2.2 其它插入排序........................................................................................................................ 42210.2.3 希尔排序 ............................................................................................................................... 42510.3 快速排序....................................................................................................................................... 42610.4 选择排序....................................................................................................................................... 42910.4.1 简单选择排序........................................................................................................................ 42910.4.2 树形选择排序........................................................................................................................ 43110.4.3 堆排序................................................................................................................................... 43210.5 归并排序....................................................................................................................................... 43410.6 基数排序....................................................................................................................................... 43510.6.1 多关键字的排序.................................................................................................................... 43510.6.2 链式基数排序........................................................................................................................ 43510.7 各种内部排序方法的比较讨论..................................................................................................... 440第11章 外部排序......................................................................................................................... 44111.1 外存信息的存取............................................................................................................................ 44111.2 外部排序的方法............................................................................................................................ 44111.3 多路平衡归并的实现.................................................................................................................... 44111.4 置换—选择排序............................................................................................................................ 446第12章 文件.................................................................................................................................. 45212.1 有关文件的基本概念.................................................................................................................... 45212.2 顺序文件....................................................................................................................................... 452附录A 关于标准C程序................................................................................................................ 456附录B 光盘文件目录 .................................................................................................................. 461
评论