第1章 绪论 1
1．1数据结构的基本概念 1
1．1．1数据结构实例 1
1．1．2数据结构的概念 4
1．1．3学习数据结构的理由 5
1．2算法分析的基本概念 6
1．2．1算法 6
1．2．2算法效率的分析 7
1．2．3算法效率的评价 7
1．3程序设计基础 9
1．3．1软件工程的基本概念 9
1．3．2软件设计基础 11
1．3．3编码基础 11
1．3．4计算机体系结构基础 12
习题 14
第2章 线性表 17
2．1线性表的概念及运算 17
2．1．1线性表的概念 17
2．1．2线性表的基本运算 17
2．1．3一个有趣的问题 18
2．2线性表的顺序存储结构 19
2．2．1顺序表 19
2．2．2顺序表的基本运算 20
2．3线性表的链式存储结构 23
2．3．1线性链表 23
2．3．2线性链表的基本运算 24
2．3．3循环链表 27
2．4顺序存储结构和链式存储结构的比较 28
2．5数组 28
2．5．1数组的定义和存储 28
2．5．2特殊矩阵的压缩存储 29
2．6线性表的应用 32
习题 34
第3章 栈 37
3．1栈的概念及运算 37
3．1．1栈的概念 37
3．1．2栈的基本运算 37
3．1．3一个有趣的问题 38
3．2栈的存储和实现 39
3．2．1顺序栈 39
3．2．2链栈 41
3．3栈的应用 43
3．3．1数制转换 43
3．3．2表达式求值 44
3．3．3栈与递归 48
3．3．4回溯法 51
习题 52
第4章 队列 55
4．1队列的概念及基本运算 55
4．1．1队列的概念 55
4．1．2队列的基本运算 56
4．1．3一个有趣的问题 56
4．2队列的顺序存储结构及运算 57
4．3循环队列 58
4．4链队列 60
4．5队列的应用 62
习题 65
第5章 串和广义表 68
5．1串的定义和基本运算 68
5．1．1串的定义 68
5．1．2串的基本运算 69
5．1．3一个有趣的问题 70
5．1．4串的定长顺序存储 71
5．1．5模式匹配 73
5．1．6串的链式存储结构 77
5．1．7串的应用 78
5．2广义表 80
5．2．1广义表的定义 80
5．2．2广义表的存储 81
习题 83
第6章 树 86
6．1树的概念及基本运算 86
6．1．1树的概念 86
6．1．2树的基本术语 87
6．1．3树的基本运算 88
6．1．4一个有趣的问题 88
6．1．5树的存储 89
6．2二叉树的概念与性质 91
6．2．1二叉树的概念及基本运算 92
6．2．2二叉树的性质 92
6．2．3二叉树的存储 94
6．3二叉树的遍历 96
6．4二叉树遍历算法的应用 99
6．5线索二叉树 101
6．6树和二叉树 106
6．6．1树与二叉树的转换 106
6．6．2二叉树与森林的转换 108
6．7哈夫曼树及其应用 110
6．8二叉树的应用 113
习题 115
第7章 图 117
7．1图的概念及基本运算 117
7．1．1图的概念 117
7．1．2图的基本运算 121
7．1．3一个有趣的问题 121
7．2图的存储 122
7．2．1数组表示 122
7．2．2邻接表表示 124
7．3图的遍历 127
7．3．1深度优先搜索遍历 127
7．3．2广度优先搜索遍历 129
7．4图的连通性问题 131
7．4．1无向图的连通性 131
7．4．2最小生成树 132
7．4．3 Prim算法 133
7．4．4 Kruskal算法 135
7．5最短路径 138
7．5．1单源点最短路径 138
7．5．2任意一对顶点之间的最短路径 141
7．6有向无环图的应用 142
7．6．1 AOV网 142
7．6．2拓扑排序 143
7．6．3 AOE网 144
7．6．4关键路径 145
7．7图的应用 149
习题 150
第8章 排序 154
8．1排序的基本概念 154
8．2一个有趣的问题 155
8．3插入排序 156
8．3．1直接插入排序 156
8．3．2折半插入排序 158
8．3．3希尔排序 160
8．4交换排序 162
8．4．1冒泡排序 162
8．4．2快速排序 164
8．5选择排序 167
8．5．1直接选择排序 167
8．5．2树形选择排序 168
8．5．3堆排序 170
8．6归并排序 175
8．7排序的应用 177
8．8各种排序方法的综合比较 177
习题 178
第9章 查找 181
9．1查找的基本概念 181
9．2一个有趣的问题 182
9．3静态查找表 184
9．3．1顺序查找法 185
9．3．2折半查找法 187
9．3．3分块查找法 190
9．4动态查找表 191
9．5哈希表 200
9．5．1哈希法与哈希表 200
9．5．2冲突处理的方法 202
9．5．3哈希函数的构造方法 204
9．5．4哈希表的查找 207
9．6查找的应用 210
习题 211
参考文献 214