第1章 数据结构概述 1
1.1 数据结构的概念 1
1.2 数据结构的作用 3
1.3 数据结构包含的内容 3
1.4 算法 4
1.5 算法的描述 5
1.6 算法分析 7
1.7 数据结构解决的问题 9
习题1 10
第2章 顺序表 12
2.1 线性表的定义 12
2.2 顺序表 12
2.3 顺序表的操作 13
2.3.1 顺序表的插入操作 14
2.3.2 顺序表的删除操作 15
习题2 17
第3章 线性链表 19
3.1 链表的定义及存储特点 19
3.2 内存的动态分配和释放 19
3.3 链表的操作 20
3.3.1 单链表的建立 20
3.3.2 链表的查找 21
3.3.3 链表的插入 22
3.3.4 链表的删除 23
3.3.5 单链表的逆向链接 24
3.4 循环链表 25
3.4.1 循环链表的建立 26
3.4.2 循环链表的插入运算 26
3.4.3 循环链表的删除运算 27
3.5 双向链表 29
3.5.1 双向链表的建立 30
3.5.2 双向链表的插入运算 30
3.5.3 双向链表的删除运算 32
3.6 循环双向链表 33
习题3 34
实训题 36
第4章 数组 39
4.1 数组的定义 39
4.2 数组的顺序存储 40
4.3 特殊矩阵 40
4.4 稀疏矩阵 42
4.4.1 三元组表示法 42
4.4.2 稀疏矩阵的链接存储 44
4.5 数组的应用 46
习题4 47
实训题 48
第5章 栈 51
5.1 栈的概念 51
5.2 栈的表示及基本操作 52
5.2.1 栈的表示 52
5.2.2 栈的基本操作 52
5.3 栈的应用 54
5.3.1 中断处理 54
5.3.2 子程序调用 54
5.3.3 前缀算术表达式转换为后缀算术表达式(逆波兰式) 55
5.4 递归 56
5.4.1 递归的概念 56
5.4.2 递归的种类 56
5.4.3 递归的执行过程 56
5.4.4 递归的应用 57
习题5 59
实训题 60
第6章 队列 63
6.1 队列的定义 63
6.2 线性队列的表示及操作方法 63
6.2.1 线性队列的数组表示及实现 63
6.2.2 线性队列的链表表示及实现 65
6.3 循环队列 66
6.4 队列的应用 68
习题6 68
实训题 68
第7章 树 71
7.1 概念及术语 71
7.1.1 树的概念 71
7.1.2 树的术语 71
7.2 树的表示 72
7.3 二叉树 73
7.3.1 二叉树的定义及性质 73
7.3.2 二叉树的表示 74
7.3.3 二叉树的遍历 75
7.3.4 线索二叉树 76
7.3.5 二叉排序树 78
7.3.6 树与二叉树的相互转换 80
7.3.7 huffman树 82
习题7 84
实训题 85
第8章 图 89
8.1 图的基本概念 89
8.1.1 图的定义 89
8.1.2 图的基本术语 89
8.2 图的存储结构 91
8.2.1 邻接矩阵 92
8.2.2 邻接表 93
8.2.3 邻接多重表 95
8.3 图的遍历 95
8.3.1 深度优先搜索遍历(DFS) 96
8.3.2 广度优先搜索遍历(BFS) 97
8.4 生成树和最小生成树 99
8.4.1 基本概念 99
8.4.2 普里姆(Prim)算法 100
8.4.3 克鲁斯卡尔(kruskal)算法 101
8.5 最短路径 102
8.5.1 从某个源点到其余各顶点的最短路径 102
8.5.2 每对顶点之间的最短路径 103
8.6 拓扑排序 104
8.6.1 拓扑排序的概念 104
8.6.2 拓扑排序算法及实现 105
8.7 图的应用 109
习题8 112
实训题 114
第9章 查找 119
9.1 概述 119
9.2 顺序查找 121
9.3 折半查找 123
9.4 哈希查找(Hashing) 124
9.4.1 哈希表与哈希函数 124
9.4.2 构造哈希函数的常用方法 125
9.4.3 解决哈希冲突的方法 127
9.5 查找应用例题 129
9.6 折半查找树 131
9.7 B-树查找法 131
习题9 133
实训题 134
第10章 排序 136
10.1 基本概念 136
10.2 交换排序法 137
10.2.1 冒泡排序 137
10.2.2 快速排序 138
10.3 插入排序法 141
10.3.1 直接插入排序 141
10.3.2 希尔排序 142
10.4 选择排序法 143
10.4.1 直接选择排序 143
10.4.2 堆排序 145
10.5 归并排序法 148
10.5.1 二路归并 149
10.5.2 算法实现 150
10.5.3 算法分析 150
10.6 基数排序法 151
10.6.1 链式基数排序 151
10.6.2 算法实现 152
10.6.3 算法分析 154
10.7 内部排序法的比较和选择 154
10.7.1 内排序方法的比较 155
10.7.2 内排序一般性选择规则 155
10.8 外部排序简介 156
10.8.1 问题的提出 156
10.8.2 外部排序的基本过程 156
习题10 157
实训题 158