数据结构基础 第4版PDF电子书下载

第一章 绪论 1

1.1基本概念和术语 1

1.2算法的描述 3

1.3算法分析基础知识 4

1.3.1概述 4

1.3.2算法时间复杂度的计算 5

1.3.3算法空间复杂度的计算 9

习题 9

第二章 线性表 10

2.1线性表的定义和运算 10

2.1.1线性表的定义 10

2.1.2线性表的运算 10

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

2.2.1顺序表 11

2.2.2插入 12

2.2.3删除 12

2.2.4查找 12

2.2.5插入、删除运算的时间分析 13

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

2.3.1线性链表 13

2.3.2单链表的基本运算 16

2.3.3链表的其他运算示例 20

2.4栈 24

2.4.1栈的定义和运算 24

2.4.2顺序栈和主要运算的实现 24

2.4.3链栈 26

2.5栈与递归 27

2.6队列 30

2.6.1队列的定义 30

2.6.2队列的顺序存储结构 31

2.6.3链队 32

2.7循环链表和双向链表 34

2.7.1循环链表 34

2.7.2双向链表 36

2.8一元多项式相加 38

习题 40

第三章 数组和广义表 41

3.1数组 41

3.1.1数组的定义和运算 41

3.1.2数组的顺序存储结构 41

3.1.3特殊矩阵 43

3.2稀疏矩阵 44

3.2.1三元组表示 44

3.2.2十字链表 47

3.3广义表 50

3.3.1广义表定义 50

3.3.2广义表的存储结构 50

3.3.3 m元多项式的表示 52

习题 53

第四章 树和二叉树 54

4.1树的定义和术语 54

4.2二叉树 55

4.2.1二叉树的定义和性质 55

4.2.2几种特殊形态的二叉树 56

4.2.3二叉树的存储结构 57

4.2.4树与二叉树的转换 58

4.2.5森林与二叉树转换 59

4.3遍历二叉树 60

4.3.1遍历二叉树的定义及递归算法 61

4.3.2遍历二叉树的非递归算法 63

4.3.3由结点先序序列和中序序列构造对应的二叉树 65

4.4线索二叉树 65

4.5树的存储结构和遍历 69

4.5.1树的存储结构 69

4.5.2树的遍历 71

4.6哈夫曼树 74

习题 78

第五章 图 80

5.1图的概念及术语 80

5.2图的存储结构 81

5.2.1邻接矩阵 82

5.2.2邻接表 83

5.2.3邻接多重表 85

5.3图的遍历 86

5.3.1深度优先搜索遍历 86

5.3.2广度优先搜索遍历 87

5.4最小生成树 89

5.5最短路径 91

5.5.1求从一个顶点到其他各顶点的最短路径 91

5.5.2求每一对顶点之间的最短路径 93

5.6拓扑排序 94

5.7关键路径 97

习题 99

第六章 串 101

6.1串的基本概念和存储结构 101

6.1.1串的顺序存储结构 101

6.1.2串的链式存储结构 102

6.2串的基本运算 102

6.3模式匹配 104

习题 108

第七章 集合 109

7.1集合的概念及主要运算 109

7.2集合的存储表示 110

7.2.1字位串存储表示 110

7.2.2链式存储表示 111

7.2.3顺序存储表示 114

7.2.4散列存储表示 114

7.3典型的集合结构 114

7.3.1字典 114

7.3.2优先队列 115

习题 115

第八章 查找 116

8.1线性表查找 116

8.1.1顺序查找 116

8.1.2二分法查找 117

8.1.3分块查找 119

8.2散列表和查找 120

8.2.1散列函数 120

8.2.2冲突的处理 121

8.2.3负载因子和平均检索长度 127

8.3二叉排序树 127

8.3.1二叉排序树的定义和运算 127

8.3.2最佳二叉排序树 131

8.3.3平衡二叉排序树 132

习题 135

第九章 排序 137

9.1插入排序 137

9.1.1直接插入排序 137

9.1.2二分法插入排序 139

9.1.3希尔排序 140

9.2选择排序 141

9.2.1直接选择排序 141

9.2.2堆排序 142

9.3交换排序 146

9.3.1起泡排序 146

9.3.2快速排序 147

9.4基数排序 148

9.5归并排序 151

9.6内部排序方法的选择和使用 152

习题 153

第十章 文件 155

10.1顺序文件 155

10.2索引文件 156

10.2.1索引顺序文件 156

10.2.2索引无序文件 157

10.2.3 B-树 157

10.2.4 B+树 158

10.3散列文件 161

10.4倒排文件 162

习题 163

第十一章 常用算法设计方法 165

11.1递推法 165

11.2分治法 165

11.3回溯法 168

11.4贪心法 171

附录一 上机实习题 173

附录二 上机实习例题 175

附录二 综合练习题 180

综合练习题参考答案 195

参考文献 202