数据结构 本科PDF电子书下载

1绪论 1

1.1数据结构的基本术语和概念 1

1.2算法和算法分析简介 3

1.2.1算法 3

1.2.2时间复杂度 3

1.2.3空间复杂度 4

本章小结 4

习题 5

2线性表 6

2.1线性表的定义 6

2.2线性表的逻辑结构和基本操作 7

2.2.1线性表的逻辑结构 7

2.2.2线性表的基本操作 7

2.3线性表的顺序存储结构（顺序表）及相关操作 8

2.3.1顺序存储结构的概念 8

2.3.2利用数组处理线性表 8

2.3.3利用指针（变量）处理线性表 8

2.3.4顺序存储结构的线性表（顺序表）的操作 9

2.3.5插入、删除操作的时间复杂度分析 12

2.4线性表的链式存储结构（链表）及相关操作 12

2.4.1线性表的链式存储的基本概念 12

2.4.2单向链表 13

2.4.3单向循环链表 21

2.4.4双向循环链表 22

2.5一元多项式的存储和加法运算 24

2.5.1一元多项式和线性表 24

2.5.2使用数组方式 24

2.5.3使用链表方式 25

本章小结 28

习题 29

3栈和队列 31

3.1栈 31

3.1.1栈的定义 31

3.1.2栈的基本运算 32

3.1.3栈的顺序存储结构及基本操作 33

3.1.4栈的链式存储结构及基本操作 36

3.1.5栈的应用 39

3.1.6栈与递归 45

3.2队列 48

3.2.1队列的定义 48

3.2.2队列的基本运算 48

3.2.3队列的顺序存储结构及基本操作 49

3.2.4队列的链式存储结构及基本操作 54

3.2.5队列的简单应用举例 57

本章小结 58

习题 59

4串 62

4.1串的概念 62

4.1.1串的定义 62

4.1.2串的存储结构 63

4.1.3利用串初始化字符数组 64

4.1.4利用二维字符数组保存存储串 64

4.1.5字符串的输入和输出 65

4.2串的运算 66

4.3串应用举例 70

本章小结 72

习题 72

5数组和广义表 74

5.1数组的定义 74

5.2数组的顺序存储结构 75

5.3矩阵的压缩存储 76

5.3.1特殊矩阵 76

5.3.2稀疏矩阵 78

5.4广义表 81

5.4.1广义表的定义和性质 81

5.4.2广义表的存储结构 82

5.5数组应用举例 83

本章小结 84

习题 85

6树和二叉树 86

6.1树的概念 86

6.1.1树的定义 86

6.1.2树的日常应用举例 87

6.1.3树的表示 88

6.1.4树的基本术语 88

6.1.5树的性质 90

6.2二叉树的概念 91

6.2.1二叉树的定义 91

6.2.2二叉树的性质 92

6.3二叉树的存储结构 94

6.3.1顺序存储结构 94

6.3.2链接存储结构 95

6.4二叉树遍历 96

6.4.1二叉树遍历的概念 96

6.4.2二叉树的递归遍历算法 97

6.4.3二叉树的非递归遍历算法 99

6.4.4二叉树的按层遍历算法 100

6.5二叉树的其他运算 102

6.6二叉树运算的程序调试 107

6.7哈夫曼树 109

6.7.1基本术语 109

6.7.2构造哈夫曼树 110

6.7.3哈夫曼编码 113

6.7.4哈夫曼树运算的程序调试 116

本章小结 118

习题 119

7图 122

7.1图的概念 122

7.1.1图的定义 122

7.1.2图的基本术语 123

7.2图的存储结构 126

7.2.1邻接矩阵 127

7.2.2邻接表 129

7.2.3边集数组 132

7.3图的遍历 134

7.3.1深度优先搜索遍历 134

7.3.2广度优先搜索遍历 137

7.3.3非连通图的遍历 141

7.3.4图的遍历算法的上机调试 141

7.4图的生成树和最小生成树 144

7.4.1图的生成树和最小生成树的概念 144

7.4.2克鲁斯卡尔算法 145

7.5最短路径 150

7.5.1最短路径的概念 150

7.3.2从一顶点到其余各顶点的最短路径 151

7.6拓扑排序 154

本章小结 157

习题 157

8查找 161

8.1查找的基本概念 161

8.2线性表的查找 162

8.2.1顺序查找 163

8.2.2折半查找 164

8.2.3分块查找 167

8.3树表的查找 168

8.3.1二叉排序树的定义 168

8.3.2二叉排序树的查找 168

8.3.3二叉排序树的插入和删除 169

8.4哈希表及其查找 173

8.4.1哈希表的基本概念 174

8.4.2哈希函数的构造方法 174

8.4.3处理冲突的方法 176

本章小结 178

习题 178

9排序 180

9.1排序的基本概念 180

9.2插入排序 182

9.2.1直接插入排序 182

9.2.2折半插入排序 183

9.3交换排序 185

9.3.1冒泡排序 185

9.3.2快速排序 186

9.4选择排序 188

9.4.1直接选择排序 189

9.4.2堆排序 189

9.5归并排序 194

9.5.1归并两个有序的序列 194

9.5.2归并排序 196

本章小结 198

习题 199

附录实验 201

参考文献 210