数据结构基础与应用

第1章 绪论 1
1.1认识数据结构 1
1.1.1举例认识数据结构 1
1.1.2数据结构定义 2
1.1.3数据结构的基本结构类型和表示 2
1.2数据结构类型 3
1.2.1线性结构 4
1.2.2非线性结构 4
1.3数据结构在程序设计中的地位 4
1.3.1算法的描述 4
1.3.2算法与程序设计 5
1.3.3算法的特性 6
1.4评价 6
1.4.1评价标准 6
1.4.2评价方法 6
1.5本章小结 7
1.6本章习题 7
第2章 数据结构分类 8
2.1几种数据结构案例 8
2.2数据结构分类 10
2.2.1数据类型 10
2.2.2抽象数据类型 10
2.3数据的逻辑结构与存储结构 11
2.3.1数据的逻辑结构 1l
2.3.2数据的存储结构 11
2.4本章小结 11
2.5本章习题 11
第3章 线性表 12
3.1线性表基本概念和逻辑结构 12
3.1.1线性表实例 12
3.1.2线性表定义 13
3.1.3线性表逻辑结构 13
3.2线性表存储方式及操作 13
3.2.1线性表的顺序存储 13
3.2.2线性表顺序存储的操作 14
3.2.3线性表顺序存储操作的评价 17
3.2.4线性表的链式存储 18
3.2.5单链表的操作 20
3.3线性表操作在单链表上实现的程序设计 26
3.4循环链表介绍 33
3.5静态链表介绍 35
3.6顺序表和链表的比较 39
3.7本章小结 39
3.8本章习题 39
第4章 栈 41
4.1栈的基本概念 41
4.1.1栈的实例 41
4.1.2栈的定义 42
4.1.3栈的基本操作 43
4.2栈的实现 43
4.2.1栈实现分类 43
4.2.2栈的数组实现 43
4.2.3栈的链接存储实现 46
4.3栈的应用实例 49
4.3.1数制转换实例 49
4.3.2堆栈实例 50
4.4栈与递归 51
4.5本章小结 52
4.6本章习题 52
第5章 队列 53
5.1队列的基本概念 53
5.1.1队列的实例 53
5.1.2队列的定义 54
5.2队列的分类 54
5.2.1队列存储结构分类 54
5.2.2链队列 55
5.2.3循环队列 55
5.3队列的实现 56
5.3.1队列的运算 56
5.3.2队列的顺序存储操作与实现 57
5.3.3队列的链接存储操作与实现 61
5.4本章小结 65
5.5本章习题 65
第6章 串 66
6.1串的应用实例 66
6.1.1串的应用举例 66
6.1.2串的定义 67
6.2串在非数值数据运算中的重要地位 70
6.3 串的运算 70
6.3.1串的存储表示 71
6.3.2串的存储结构与实现 73
6.4本章小结 77
6.5本章习题 78
第7章 数组与矩阵 79
7.1数组概述 79
7.1.1数组实例 79
7.1.2数组定义 79
7.2数组的存储 80
7.3矩阵 81
7.3.1矩阵简介 8l
7.3.2稀疏矩阵 8l
7.3.3用三元数组表示的稀疏矩阵 82
7.3.4用十字链表示的稀疏矩阵 85
7.4特殊矩阵的压缩存储 89
7.4.1对称矩阵的压缩存储 89
7.4.2三角矩阵的压缩存储 90
7.4.3带状矩阵的压缩存储 91
7.5本章小结 92
7.6本章习题 92
第8章 树 93
8.1树型结构 93
8.1.1树型结构实例 93
8.1.2树型结构定义 94
8.1.3树型结构相关术语 95
8.1.4树的表示方法 96
8.2二叉树 97
8.2.1二叉树实例 97
8.2.2二又树定义 97
8.2.3二叉树的基本性质 98
8.2.4二叉树的存储结构 100
8.2.5二叉树的操作 102
8.2.6二又树遍历 104
8.3二又树和森林的关系 106
8.3.1二叉树与树的转换 106
8.3.2树和森林的遍历 110
8.4树的应用 112
8.4.1最佳查找树 112
8.4.2平衡树 118
8.4.3huffman算法 123
8.5本章小结 126
8.6本章习题 126
第9章 图 128
9.1 图的定义和基本术语 128
9.1.1图的定义 128
9.1.2图的基本术语 129
9.2图的存储结构 130
9.2.1邻接矩阵 130
9.2.2邻接表 131
9.3图的遍历 133
9.3.1深度优先搜索(dfs)遍历 133
9.3.2深度优先搜索(bfs)遍历 135
9.4最小生成树 136
9.4.1普里姆(prim)算法 137
9.4.2克鲁斯卡尔(kruskal)算法 138
9.5最短路径 140
9.6拓扑排序 143
9.7关键路径法 145
9.8本章小结 149
9.9本章习题 149
第10章 查找 151
10.1线性表的查找 151
10.1.1顺序查找 151
10.1.2折半查找 153
10.1.3分块查找 156
10.2哈希法 157
10.2.1哈希表的概念 157
10.2.2哈希函数的构造 158
10.2.3处理冲突的方法 160
10.2.4.哈希表的查找分析 162
10.3本章小结 163
10.4本章习题 163
第11章 排序 164
11.1基本概念 164
11.2插入排序 165
11.2.1直接插入排序 165
11.2.2希尔排序 167
ll.3交换排序 169
11.3.1冒泡排序 169
11.3.2快速排序 171
11.4选择排序 174
11.4.1简单选择排序 174
1 1.4.2堆排序 176
11.5归并排序 178
11.5.1归并排序的基本思想 178
11.5.2归并排序算法 178
11.6基数排序 180
11.6.1基数排序的基本思想 180
11.6.2链式基数排序算法 182
11.7本章小结 183
11.8本章习题 184
部分习题答案 185