数据结构导论 1
第1章 概论 1
1.1引言 1
目 录 1
1.2数据、逻辑结构和运算 3
1.2.1 数据元素和数据项 3
1.2.2数据的逻辑结构 4
1.2.3 运算和基本运算 5
1.3.1 存储实现 7
1.3存储实现和运算实现 7
1.3.2运算实现 8
1.4算法分析 9
1.5数据结构及其评价和选择 11
1.5.1数据结构 11
1.5.2数据结构的评价和选择 12
小结 13
习题 14
2.1线性表的基本概念 15
2.1.1 线性结构 15
第2章线性表 15
2.1.2 线性表 16
2.2线性表的顺序实现 16
2.2.1 顺序表 16
2.2.2 基本运算在顺序表上的实现 17
2.2.3 顺序实现的算法分析 20
2.3线性表的链接实现 21
2 3.1 单链表 21
2.3.2 单链表的简单操作 23
2.3.3 基本运算在单链表上的实现 26
2.4.1 建表 28
2.4其它运算在单链表上的实现 28
2.4.2 清除重复结点 30
2.5其它链表 32
2.5.1 循环链表 32
2.5.2双链表 33
2.6顺序实现与链接实现的比较 35
2.6.1 空间性能的比较 35
2.6.2 时间性能的比较 35
2.7串 35
2.7.2 串的基本运算 36
2.7.1 串的基本概念 36
2.7.3 串的存储 37
小结 39
习题 40
第3章栈、队列和数组 42
3.1栈 42
3.1.1栈的基本概念 42
3.1.2栈的顺序实现 43
3.1.3 栈的链接实现 45
3.1.4举例 47
3.1.5 栈的简单应用和递归 48
3.2队列 51
3.2.1 队列的基本概念 51
3.2.2 队列的顺序实现 51
3.2.3 队列的链接实现 56
3.2.4 举例 58
3.3数组 59
3.3.1 数组的逻辑结构和运算 59
3.3.2数组的存储结构 60
3.3.3 矩阵的压缩存储 61
3.4综合应用示例 66
小结 71
习题 71
第4章树 74
4.1树的基本概念 74
4.2二叉树 76
4.2.1 二叉树的基本概念 76
4.2.2 二叉树的性质 77
4.3.1 二叉树的链式存储结构 79
4.3二叉树的存储结构 79
4.3.2 二叉树的顺序存储结构 81
4.4二叉树的遍历 82
4.5递归消除 86
4.5.1 简单递归消除 86
4.5.2基于栈的递归消除 89
4.6树和林 92
4.6.1 树的存储结构 92
4.6.2树的遍历 96
4.6.3 树、林与二叉树的关系 96
4.7.1 分类与判定树 98
4.7判定树和哈夫曼树 98
4.7.2 哈夫曼树与哈夫曼算法 100
小结 103
习题 104
第5章 图 106
5.1图的基本概念 106
5.1.1 图的实际背景 106
5.1.2 图的定义和术语 107
5.2.1 邻接矩阵 109
5.2图的存储结构 109
5.2.2 邻接表 111
5.3图的遍历 113
5.3.1 连通图的深度优先搜索 113
5.3.2 连通图的广度优先搜索 115
5.3.3 图的连通分量计算 116
5.4最小生成树 117
5.5拓扑排序 121
小结 124
习题 124
6.1.1 集合的基本概念 128
第6章查找表 128
6.1基本概念 128
6.1.2查找表的基本概念 129
6.2静态查找表的实现 130
6.2.1 顺序表上的查找 130
6.2.2 有序表上的查找 132
6.2.3 索引顺序表上的查找 133
6.3树表 134
6.3.1 二叉排序树 135
6.3.2平衡二叉排序树 139
6.4散列表 143
6.4.1 散列函数的构造法 144
6.4.2 动态查找表在开散列表上的实现 145
6.4.3 动态查找表在闭散列表上的实现 147
6.4.4 开散列表与闭散列表的比较 149
小结 150
习题 151
第7章 文件 152
7.1基本概念 152
7.1.1 文件结构 152
7.1.2外存储器简介 154
7.2顺序文件 156
7.3索引文件 156
7.4 IsAM文件 157
7.5 VsAM文件 159
7.6散列文件 160
7.7多关键字文件 161
7.7.1 多重表文件 162
7.7.2倒排文件 162
习题 163
小结 163
第8章排序 164
8.1概述 164
8.2插入排序 165
8.3交换排序 166
8.3.1 冒泡排序 167
8.3.2 快速排序 168
8.4选择排序 170
8.4.1 直接选择排序 170
8.4.2 堆排序 171
8.5.1 有序序列的合并 177
8.5归并排序 177
8.5.2二路归并排序 178
8.6外排简介 179
小结 180
习题 181
参考文献 182
数据结构导论自学考试大纲 185
出版前言 185
一、课程的性质与设置目的 187
第1章概论 188
二、课程内容与考核目标 188
第2章线性表 189
第3章栈、队列和数组 190
第4章树 191
第5章图 192
第6章查找表 193
第7章 文件 195
第8章 排序 196
三、有关说明与实施要求 197
附录题型举例 199
后记 200