目录
第1章绪论1
问题导入1
1.1数据结构的研究内容1
1.2数据结构的基本概念和术语1
1.2.1数据的逻辑结构2
1.2.2数据的存储结构3
1.2.3数据的操作实现4
1.2.4抽象数据类型的定义4
1.3算法分析5
1.3.1算法的定义及特性5
1.3.2时间复杂度的度量6
1.3.3空间复杂度7
1.4应用案例: 人工智能大模型的参数量7
1.5本章小结8
1.6本章习题8
第2章线性表10
问题导入10
2.1线性表的定义10
2.2线性表的顺序存储结构11
2.2.1顺序表的结构定义11
2.2.2顺序表的基本操作12
2.3线性表的链式存储实现16
2.3.1单链表16
2.3.2单链表的基本操作17
2.3.3循环链表20
2.3.4双向链表21
2.3.5引入案例的实现22
2.3.6静态链表23
2.4线性表实现方法的比较24
2.5应用案例: 深度学习模型中的张量存储25
2.6本章小结25
2.7本章习题26
第3章栈与队列28
问题导入28
3.1栈的定义与结构28
3.1.1栈的抽象数据类型定义28
3.1.2栈的顺序存储实现29
3.1.3栈的链式存储实现30
3.2栈的应用举例31
3.2.1数制转换31
3.2.2括号匹配检测32
3.2.3行编辑程序33
3.2.4栈的迷宫求解34
3.2.5表达式求值35
3.3栈与递归的实现36
3.4队列38
3.4.1队列的抽象数据类型定义38
3.4.2队列的链式存储实现39
3.4.3队列的顺序存储实现41
3.4.4队列的迷宫求解43
3.5应用案例: 区块链技术45
3.6本章小结46
3.7本章习题46
第4章串49
问题导入49
4.1串类型的表示49
4.2串的表示和实现51
4.2.1定长顺序存储表示51
4.2.2堆分配存储表示54
4.2.3串的块链存储表示58
4.3串的模式匹配算法59
4.3.1求子串位置的定位函数59
4.3.2模式匹配的改进算法59
4.4串操作应用举例63
4.4.1文本编辑63
4.4.2建立词索引表64
4.5本章小结65
4.6本章习题66第5章数组和广义表68
问题导入68
5.1数组的定义68
5.1.1数组的基本概念68
5.1.2数组的实现69
5.2数组的顺序表示和实现69
5.2.1存储映像69
5.2.2数据元素存储位置的映像关系70
5.2.3数组的顺序存储实现70
5.3矩阵的压缩存储72
5.3.1特殊矩阵72
5.3.2稀疏矩阵73
5.3.3三元组顺序表存储稀疏矩阵74
5.3.4行逻辑链接的顺序表存储稀疏矩阵77
5.3.5十字链表存储稀疏矩阵79
5.4广义表的定义和存储结构82
5.4.1广义表的定义82
5.4.2表头表尾存储结构84
5.4.3子表存储结构85
5.5广义表操作的递归算法86
5.5.1求广义表的深度87
5.5.2复制广义表88
5.5.3建立广义表的存储结构89
5.6应用案例: 深度学习模型中的张量91
5.7本章小结92
5.8本章习题92
第6章树和二叉树94
问题导入94
6.1树的定义和基本术语94
6.1.1树的定义和基本操作94
6.1.2树的基本术语96
6.2二叉树96
6.2.1二叉树的定义96
6.2.2二叉树的性质97
6.2.3二叉树的存储结构99
6.3遍历二叉树100
6.3.1问题提出100
6.3.2二叉树遍历算法101
6.3.3遍历算法应用104
6.4线索二叉树106
6.4.1问题提出106
6.4.2线索二叉树算法107
6.4.3建立线索链表107
6.5树和森林108
6.5.1树的存储结构108
6.5.2森林与二叉树的转换110
6.5.3树和森林的遍历112
6.5.4树的计数112
6.6应用案例115
6.6.1哈夫曼树及其应用115
6.6.2人工智能中的决策树118
6.7本章小结120
6.8本章习题120
第7章图122
问题导入122
7.1图的定义和术语122
7.1.1图相关基本概念122
7.1.2图基本操作125
7.2图的存储126
7.2.1邻接矩阵126
7.2.2邻接表129
7.2.3十字链表130
7.2.4邻接多重表133
7.3图的遍历134
7.3.1深度优先搜索134
7.3.2广度优先搜索137
7.4图的连通性问题139
7.4.1无向图的连通分量和生成树139
7.4.2有向图的强连通分量141
7.4.3最小生成树141
7.5有向无环图及其应用146
7.5.1拓扑排序147
7.5.2关键路径149
7.6最短路径153
7.6.1从某个源点到其余各顶点的最短路径153
7.6.2每一对顶点之间的最短路径156
7.7应用案例158
7.7.1社交网络分析158
7.7.2路径规划158
7.8本章小结159
7.9本章习题160
第8章查找164
问题导入164
8.1静态查找表166
8.1.1顺序表的查找166
8.1.2有序表的查找167
8.1.3静态树表的查找169
8.1.4索引顺序表的查找170
8.2动态查找表171
8.2.1二叉排序树和平衡二叉树172
8.2.2B树和B+树180
8.2.3键树185
8.3哈希表186
8.3.1哈希表定义186
8.3.2构造哈希函数的方法186
8.3.3处理冲突的方法189
8.3.4哈希表的查找及其分析192
8.4应用案例193
8.4.1电商平台商品查找193
8.4.2数据库中的数据查找193
8.5本章小结194
8.6本章习题194
第9章内部排序198
问题导入198
9.1概述198
9.1.1排序的定义与基本概念199
9.1.2排序算法的性能分析指标199
9.2插入排序199
9.2.1直接插入排序200
9.2.2折半插入排序200
9.2.3希尔排序201
9.3交换排序202
9.3.1冒泡排序202
9.3.2快速排序203
9.4选择排序205
9.4.1简单选择排序205
9.4.2堆排序206
9.5归并排序207
9.5.1二路归并排序207
9.5.2多路归并排序208
9.6基数排序210
9.6.1多关键字排序210
9.6.2链式基数排序211
9.7各种内部排序方法的比较213
9.7.1时间性能对比213
9.7.2空间性能对比214
9.7.3稳定性214
9.8排序算法在深度学习中的应用215
9.8.1注意力机制中的权重筛选215
9.8.2推荐系统和搜索中的得分排序216
9.8.3Beam Search中的候选序列排序216
9.8.4其他场景216
9.9排序算法总结216
9.10本章小结218
9.11本章习题218
第10章算法思想221
10.1枚举法221
10.2回溯法222
10.3分治法224
10.4动态规划225
10.5贪心法226
10.6本章小结228
10.7本章习题228
参考文献230
