目录
第1章绪论1
1.1数据结构研究的内容1
1.1.1为什么要学习数据结构2
1.1.2数据结构中的例子4
1.1.3数据结构研究的内容8
1.2数据结构中的基本概念8
1.2.1基本概念与术语8
1.2.2数据结构9
1.3数据类型的表示与实现12
1.3.1数据类型12
1.3.2抽象数据类型13
1.4算法与算法分析15
1.4.1算法的定义及特性15
1.4.2算法的时间复杂度16
1.4.3算法的空间复杂度20
1.5Python语言简介21
1.5.1Python的标准数据类型21
1.5.2输入/输出和文件操作21
1.5.3面向对象编程22
小结24
习题25第2章线性表27
2.1线性表的基本概念27
2.1.1线性表的定义27
2.1.2线性表的抽象数据类型描述29
2.2线性表的顺序存储结构30
2.2.1线性表的顺序表示30
2.2.2顺序表的基本操作32
2.2.3顺序表的应用案例37
2.3线性表的链式表示和实现39
2.3.1链表的存储结构39
2.3.2单链表的基本操作41
2.3.3双向链表57
2.3.4循环链表64
2.4顺序表和链表的比较69
2.5线性表的应用——机场乘客排队值机系统70
小结71
习题72第3章栈与队列75
3.1栈75
3.1.1栈的基本概念75
3.1.2使用Python列表实现栈79
3.1.3栈的应用场景81
3.2队列83
3.2.1队列的基本概念84
3.2.2使用collections.deque实现队列85
3.2.3优先队列87
3.2.4队列的应用场景89
小结91
习题92第4章串、数组与广义表94
4.1串94
4.1.1串的基本概念94
4.1.2串的顺序存储及运算95
4.1.3串的链式存储及运算97
4.1.4串的模式匹配99
4.1.5串的应用案例101
4.2数组102
4.2.1数组的基本概念102
4.2.2数组的顺序存储103
4.2.3特殊矩阵的压缩存储105
4.2.4数组的应用案例106
4.3广义表108
4.3.1广义表的基本概念108
4.3.2广义表的存储结构108
4.3.3广义表的操作109
小结111
习题112第5章树114
5.1树和二叉树114
5.1.1树的定义与基本术语115
5.1.2二叉树的定义与特点115
5.1.3树与二叉树的示例描述116
5.2二叉树案例引入116
5.3二叉树的性质和存储结构118
5.3.1二叉树的性质118
5.3.2二叉树的存储结构119
5.4遍历二叉树和线索二叉树121
5.4.1遍历二叉树121
5.4.2线索二叉树130
5.5树和森林132
5.5.1树的表示方法132
5.5.2森林和二叉树的转换134
5.5.3哈夫曼树136
5.6案例分析与实现138
小结141
习题141第6章图144
6.1图的基本概念144
6.1.1图的定义144
6.1.2图的基本术语144
6.2图的存储结构146
6.2.1邻接矩阵146
6.2.2邻接表147
6.3图的遍历149
6.3.1深度优先遍历149
6.3.2广度优先遍历150
6.4图的最小生成树152
6.4.1基本概念152
6.4.2Prim算法152
6.4.3Kruskal算法154
6.5最短路径156
6.5.1基本概念156
6.5.2应用实例157
6.6拓扑排序159
6.6.1基本概念159
6.6.2拓扑排序的实现160
6.7关键路径162
6.7.1基本概念162
6.7.2关键路径的算法164
小结165
习题165第7章查找168
7.1查找的基本概念168
7.2线性表的查找169
7.2.1顺序查找169
7.2.2折半查找170
7.2.3分块查找172
7.3二叉树的查找174
7.3.1二叉排序树174
7.3.2平衡二叉树183
7.4哈希表的查找185
7.4.1哈希表186
7.4.2哈希函数的构造方法187
7.4.3冲突处理的方法188
7.4.4哈希表查找的算法分析190
小结191
习题191第8章排序194
8.1认识排序194
8.1.1排序的基本概念194
8.1.2排序算法的评价指标195
8.2插入排序195
8.2.1直接插入排序196
8.2.2二分法插入排序197
8.2.3希尔排序199
8.3交换排序200
8.3.1冒泡排序200
8.3.2快速排序202
8.4选择排序203
8.4.1简单选择排序203
8.4.2堆排序204
8.5归并排序207
8.6基数排序208
小结210
习题212附录A实验215
实验1顺序表的基本操作215
实验2链表的基本操作217
实验3利用顺序栈实现数制转换220
实验4二叉树的建立及递归遍历221
实验5二叉树的应用224
实验6折半插入排序算法的实现226参考文献230
