数据结构

第1章 绪论 1
1.1 什么是数据结构 1
1.2 数据的逻辑结构和物理结构 2
1.3 算法描述 4
1.3.1 数据结构上的基本操作 4
1.3.2 算法的描述方法 5
1.4 算法分析 7
1.4.1 算法设计的要求 8
1.4.2 算法设计的时间因素 8
1.5 小结 9
习题1 10
第2章 线性表 11
2.1 线性表的逻辑结构 11
2.1.1 线性表的定义 11
2.1.2 线性表的逻辑结构表示 12
2.1.3 线性表的基本操作 13
2.2 线性表的顺序存储结构表示 13
2.3 线性表元素的操作 15
2.3.1 线性表元素插入操作 15
2.3.2 线性表元素删除操作 17
2.3.3 线性表元素定位操作 17
2.4 线性表应用举例 20
2.5 小结 28
习题2 28
第3章 链表 30
3.1 线性表的链式存储结构表示 30
3.2 单链表的基本操作 33
3.2.1 单链表的建立 33
3.2.2 单链表元素定位操作 34
3.2.3 单链表元素插入操作 37
3.2.4 单链表元素删除操作 42
3.3 单链表应用举例 44
3.4 循环链表 48
3.5 双向链表 51
3.6 各种链式存储结构的比较 52
3.7 顺序表与链表的结构和应用比较 52
3.8 链表应用举例 53
3.9 小结 58
习题3 59
第4章 栈和队列 60
4.1 栈的结构及其运算 60
4.2 队列的结构及其运算 63
4.3 链栈和链队 69
4.3.1 链栈的存储结构及其运算 70
4.3.2 链队的存储结构及其运算 71
4.4 栈的应用举例 73
4.5 小结 75
习题4 75
第5章 数组 77
5.1 二维数组的顺序存储表示 77
5.2 稀疏矩阵的压缩 80
5.3 特殊矩阵的压缩 83
5.4 小结 85
习题5 85
第6章 串 87
6.1 串的定义和特性 87
6.2 串的存储结构 88
6.2.1 串的静态存储结构 88
6.2.2 串的动态存储结构 90
6.3 串的运算 91
6.3.1 串的基本运算 91
6.3.2 串运算的应用 93
6.4 串在文本编辑中的应用 97
6.5 小结 99
习题6 100
第7章 树 101
7.1 树的基本概念 101
7.2 树的存储结构 103
7.3 二叉树 105
7.3.1 二叉树的表示 105
7.3.2 二叉树的特性 106
7.3.3 二叉树的存储结构 108
7.4 遍历二叉树 109
7.4.1 遍历二叉树的递归算法 109
7.4.2 中根遍历的非递归算法 113
7.5 树和森林 116
7.5.1 森林与二叉树的转换 116
7.5.2 树的遍历 118
7.6 哈夫曼树及其应用 119
7.6.1 哈夫曼树的表示 119
7.6.2 哈夫曼树的构造 121
7.6.3 哈夫曼树的应用 121
7.7 二叉树的应用举例 123
7.8 小结 126
习题7 126
第8章 图 128
8.1 图的基本概念 128
8.2 图的存储结构 132
8.2.1 图的邻接矩阵表示 132
8.2.2 图的链接表表示 134
8.3 图的遍历 137
8.3.1 深度优先搜索法 138
8.3.2 广度优先搜索法 139
8.4 最短路径 141
8.5 生成树 143
8.6 拓扑排序 146
8.7 小结 151
习题8 151
第9章 查找 153
9.1 查找的基本概念 153
9.2 静态查找 154
9.2.1 顺序查找 154
9.2.2 折半查找 156
9.2.3 分块查找 158
9.3 动态查找 160
9.3.1 二叉查找树查找 160
9.3.2 二叉查找树插入结点的算法 161
9.4 哈希查找 164
9.4.1 哈希表和哈希函数 164
9.4.2 冲突和解决冲突的方法 169
9.5 各种查找方法的比较 175
9.6 查找应用举例 176
9.7 小结 178
习题9 178
第10章 排序 180
10.1 排序的基本概念 180
10.2 排序方法 181
10.2.1 直接插入排序 181
10.2.2 简单选择排序 183
10.2.3 快速排序 185
10.2.4 堆排序 191
10.2.5 归并排序 197
10.3 各种排序方法的比较 200
10.4 排序应用举例 204
10.5 小结 206
习题10 206
附录1 上机实验 208
实验一 顺序表中元素的插入和删除 208
实验二 单链表中元素的查找. 插入和删除 208
实验三 栈和队列中元素的交换 208
实验四 二叉树的建立和中根遍历的应用 208
实验五 图遍历的应用 209
实验六 折半查找的应用 209
实验七 哈希查找中的链地址法 209
实验八 直接插入排序和快速排序在实际中的应用 209
实验九 查找和排序技术的综合应用 209
附录2 课程设计 210
参考文献 211