数据结构(PYTHON+JAVA)(微课版)

第 1章 数据结构与算法概论　1

1.1 问题求解　1

1.1.1 计算机解决问题的步骤　1

1.1.2 非数值数学模型　3

1.2 数据结构概述　5

1.2.1 数据结构的相关概念　5

1.2.2 抽象数据类型　7

1.3 算法概述　9

1.3.1 算法及其特性　9

1.3.2 算法设计的要求　10

1.3.3 算法描述方法　10

1.3.4 算法评价　10

本章小结　13

本章习题　13

第 2章 线性表　14

2.1 线性表的概念　14

2.2 线性表的顺序存储结构　15

2.2.1 顺序表的概念　15

2.2.2 顺序表的操作　15

2.3 线性表的链式存储结构　18

2.3.1 链表的概念　18

2.3.2 单向链表　19

2.3.3 双向链表　23

2.4 线性表特点与比较　27

2.4.1 线性表的特点　27

2.4.2 顺序表与链表的比较　27

2.4.3 单向链表与双向链表的比较　28

2.5 线性表的应用　28

2.5.1 多项式的合并　28

2.5.2 稀疏矩阵的表示　30

2.5.3 约瑟夫问题　32

本章小结　33

本章习题　34

第3章 栈和队列　35

3.1 栈　35

3.1.1 栈的定义与基本操作　35

3.1.2 栈的顺序存储结构与实现　36

3.1.3 栈的链式存储结构与实现　39

3.1.4 顺序栈和链栈的比较　41

3.1.5 栈的应用案例　41

3.2 队列　44

3.2.1 队列的定义与基本操作　44

3.2.2 队列的顺序存储结构与实现　45

3.2.3 队列的链式存储结构与实现　49

3.2.4 循环队列与链队列的比较　51

3.2.5 队列的应用案例　51

本章小结　55

本章习题　56

第4章 递归　57

4.1 递归定义　57

4.2 递归算法设计　57

4.3 消除递归　60

4.3.1 直接转换法　60

4.3.2 间接转换法　61

4.4 回溯法　62

4.5 递归的评价　65

本章小结　66

本章习题　66

第5章 树　68

5.1 树的概念　68

5.1.1 树的定义　68

5.1.2 树的相关概念　68

5.1.3 树的表示　69

5.2 二叉树　70

5.2.1 二叉树的概念　70

5.2.2 二叉树的性质　72

5.2.3 二叉树的存储　72

5.2.4 二叉树的遍历　74

5.3 树、森林与二叉树　76

5.3.1 树的存储　76

5.3.2 树与二叉树的转换　78

5.3.3 森林与二叉树的转换　79

5.3.4 树的遍历　80

5.4 哈夫曼树　81

5.4.1 哈夫曼树的相关概念　81

5.4.2 哈夫曼算法　84

5.4.3 哈夫曼编码　85

5.5 堆　86

5.5.1 堆的概念　86

5.5.2 堆的操作　87

5.5.3 堆的算法分析　92

本章小结　93

本章习题　93

第6章 图　95

6.1 图的概念　95

6.1.1 图的相关术语　95

6.1.2 图的存储结构　97

6.2 图的遍历　101

6.2.1 深度优先遍历　101

6.2.2 广度优先遍历　102

6.3 图的应用　104

6.3.1 *小生成树　104

6.3.2 拓扑排序问题　106

6.3.3 关键路径问题　109

6.3.4 *短路径问题　110

本章小结　118

本章习题　118

第7章 排序　120

7.1 排序的概念　120

7.2 插入排序　120

7.2.1 直接插入排序　120

7.2.2 希尔排序　122

7.3 交换排序　122

7.3.1 冒泡排序　122

7.3.2 快速排序　124

7.4 选择排序　125

7.4.1 简单选择排序　125

7.4.2 堆排序　127

7.5 归并排序　130

7.6 排序算法比较　131

本章小结　132

本章习题　132

第8章 查找　133

8.1 查找的概念　133

8.2 线性表查找　134

8.2.1 顺序查找　134

8.2.2 二分查找　135

8.2.3 分块查找　137

8.3 树表查找　138

8.3.1 二叉排序树的节点　139

8.3.2 二叉排序树的查找　139

8.3.3 二叉排序树的插入　140

8.3.4 二叉排序树的构造　141

8.3.5 二叉排序树的删除　143

8.4 散列表查找　144

8.4.1 散列查找　145

8.4.2 散列函数　145

8.4.3 冲突处理　147

8.4.4 查找性能分析　149

本章小结　150

本章习题　150