第1章 绪论 1
1.1 数据结构概述 1
1.1.1 学习数据结构课程的意义 1
1.1.2 数据结构课程的特点 3
1.2 研究对象 4
1.3 算法的描述和分析 7
1.3.1 算法的描述 7
1.3.2 算法的分析 10
本章小结 11
习题 12
2.1.2 线性表的运算 13
2.1.1 线性表 13
2.1 基本概念 13
第2章 线性结构之一 ——顺序表 13
2.1.3 线性表的存储 14
2.2 顺序表 14
2.2.1 顺序表的存储 14
2.2.2 顺序表的运算 15
2.2.3 顺序表的应用 18
2.3 栈和队 25
2.3.1 栈和队的概念 25
2.3.2 栈和队的特点 26
2.3.3 栈和队的存储 26
2.3.4 栈和队的运算 26
2.3.5 栈和队的应用 28
习题 32
本章小结 32
3.1 链表的存储及运算 33
3.1.1 链表的存储 33
第3章 线性结构之二 ——链表 33
3.1.2 链表的运算 34
3.2 链接的栈和队 38
3.2.1 链接栈和队的逻辑表示 38
3.2.2 链接栈和队的存储 38
3.2.3 链接栈和队的运算 39
3.3 链表的推广 40
3.3.1 带头结点的链表 40
3.3.2 循环链表 41
3.3.3 双向链表 42
3.4.1 一元多项式的表示及相加 43
3.3.4 多重链表 43
3.4 链表的应用 43
3.4.2 位组排序 44
3.5 用数组实现链表 46
3.5.1 链表的数组存储及运算 46
3.5.2 存储池 47
本章小结 49
习题 49
第4章 层次结构 ——树 50
4.1 树的概念 50
4.2 二叉树 52
4.2.1 二叉树的概念 52
4.2.2 二叉树的存储 53
4.2.4 一般树的二叉树表示 54
4.2.3 二叉树的性质 54
4.2.5 二叉树的运算 55
4.2.6 二叉树的其他存储及运算 60
4.3 树的应用 62
4.3.1 二叉排序树 62
4.3.2 堆排序 64
4.3.3 哈夫曼树及运算 68
4.3.4 决策树 72
4.3.5 博弈树 73
本章小结 76
习题 76
5.1 图的概念 78
第5章 网状结构 ——图 78
5.2 图的存储 80
5.2.1 邻接矩阵法 80
5.2.2 邻接表法 81
5.2.3 十字链表法 83
5.3 图的遍历 84
5.3.1 深度优先遍历 85
5.3.2 广度优先遍历 86
5.3.3 生成树 86
5.4 最短路径 88
5.4.1 某源点到其余各顶点的最短路径 88
5.4.2 每对顶点间的最短路径 90
5.5.1 拓扑排序的概念 92
5.5 拓扑排序 92
5.5.2 拓扑排序的算法 93
5.6 关键路径 94
5.6.1 关键路径的概念 94
5.6.2 关键路径的算法 96
本章小结 98
习题 98
第6章 文件组织 99
6.1 文件的结构 99
6.1.1 文件的逻辑结构 99
6.1.2 文件的物理结构 100
6.2 顺序文件和随机文件 101
6.2.1 顺序文件 101
6.1.3 文件的组织 101
6.2.2 随机文件 105
6.3 索引技术 107
6.3.1 索引的概念 107
6.3.2 顺序索引 107
6.3.3 散列索引 111
6.3.4 二叉树索引 118
6.3.5 B树索引 122
6.4 索引文件 128
6.4.1 索引文件 129
6.4.2 索引顺序文件 130
6.5 散列文件 135
本章小结 137
习题 137