目录Contents

第1章绪论1

1.1数据结构的基本概念1

1.1.1数据结构的定义1

1.1.2数据的逻辑结构及存储结构2

1.1.3数据结构有关概念及术语4

1.2算法和算法描述4

1.2.1什么是算法4

1.2.2算法描述5

1.3算法分析6

1.3.1空间复杂度6

1.3.2时间复杂度6

小结7

习题17

第2章线性表10

2.1线性表的逻辑结构10

2.1.1线性表的定义10

2.1.2线性表的基本操作11

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

2.2.1线性表的顺序存储——顺序表11

2.2.2顺序表基本操作的实现12

2.2.3顺序表的应用举例15

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

2.3.1线性表的链式存储——链表17

2.3.2单链表19

2.3.3循环链表26

2.3.4双向链表26

2.3.5单链表应用举例28小结31

习题232

实训135

第3章栈与队列37

3.1栈37

3.1.1栈的定义37

3.1.2栈的顺序存储及其基本操作的实现38

3.1.3栈的链式存储及其基本操作的实现42

3.1.4栈的应用举例45

3.2队列47

3.2.1队列的定义47

3.2.2队列的顺序存储及其基本操作的实现48

3.2.3队列的链式存储及其基本操作的实现52

3.2.4队列的应用举例54

小结55

习题355

实训258

第4章串、数组和广义表65

4.1串65

4.1.1串的定义和特性65

4.1.2串的顺序存储及其基本操作实现66

4.1.3串的链式存储及其基本操作实现73

4.1.4串的应用举例73

4.2数组74

4.2.1数组的定义和运算74

4.2.2数组的顺序存储结构74

4.2.3矩阵的压缩存储75

4.2.4稀疏矩阵76

4.3广义表81

4.3.1广义表的定义和特性81

4.3.2广义表的存储结构及其基本操作实现82

小结83

习题483

实训385

第5章树88

5.1树的定义与表示88

5.1.1树的定义及基本术语88

5.1.2树的表示89

5.2二叉树及其遍历89

5.2.1二叉树的定义89

5.2.2二叉树的重要性质90

5.2.3二叉树的存储结构91

5.2.4二叉树的遍历92

5.3线索二叉树98

5.3.1线索二叉树的定义98

5.3.2线索二叉树的基本操作100

5.4树和森林101

5.4.1树的存储结构101

5.4.2二叉树与树之间的转换102

5.4.3森林与二叉树的转换103

5.4.4树与森林的遍历103

5.5二叉树应用实例104

5.5.1二叉排序树104

5.5.2平衡二叉树110

5.5.3B树112

5.5.4哈夫曼树114

小结116

习题5117

实训4121

实训4.1二叉树的操作121

实训4.2树的应用121

第6章图126

6.1图的基本概念126

6.1.1图的定义126

6.1.2图的基本术语127

6.2图的存储结构129

6.2.1邻接矩阵129

6.2.2邻接表130

6.3图的遍历132

6.3.1深度优先搜索132

6.3.2广度优先搜索134

6.4最小生成树136

6.4.1普里姆算法137

6.4.2克鲁斯卡尔算法139

6.5最短路径142

6.5.1单源最短路径142

6.5.2每对顶点之间的最短路径146

6.6拓扑排序149

6.6.1AOV网149

6.6.2拓扑排序的实现150

小结152

习题6153

实训5155

第7章查找158

7.1查找的基本概念158

7.2顺序查找159

7.3二分查找160

7.4分块查找162

7.5哈希表查找165

7.5.1哈希表查找的基本概念165

7.5.2构造哈希函数的方法165

7.5.3哈希冲突的解决方法167

7.5.4哈希查找效率的分析171

小结172

习题7172

实训6175

第8章排序177

8.1排序的基本概念177

8.2插入排序178

8.2.1直接插入排序178

8.2.2二分法插入排序180

8.2.3希尔排序181

8.3选择排序182

8.3.1简单选择排序182

8.3.2堆排序183

8.4交换排序186

8.4.1冒泡排序186

8.4.2快速排序188

8.5归并排序190

8.6基数排序192

小结195

习题8195

实训7198

第9章课程设计指导202

9.1课程设计大纲202

9.2课程设计题目及设计要求202

9.3飞机售票系统实例205

小结210