数据结构与程序设计

第1章绪论1

1.1数据结构的基本概念1

1.1.1数据结构实例1

1.1.2数据结构的概念4

1.1.3学习数据结构的理由5

1.2算法分析的基本概念6

1.2.1算法6

1.2.2算法效率的分析7

1.2.3算法效率的评价7

1.3程序设计基础9

1.3.1软件工程的基本概念9

1.3.2软件设计基础11

1.3.3编码基础11

1.3.4计算机体系结构基础12

习题14

第2章线性表17

2.1线性表的概念及运算17

2.1.1线性表的概念17

2.1.2线性表的基本运算17

2.1.3一个有趣的问题18

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

2.2.1顺序表19

2.2.2顺序表的基本运算20

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

2.3.1线性链表23

2.3.2线性链表的基本运算24

2.3.3循环链表27

2.4顺序存储结构和链式存储结构的比较28

2.5数组28

2.5.1数组的定义和存储28

2.5.2特殊矩阵的压缩存储29

2.6线性表的应用32

习题34

第3章栈37

3.1栈的概念及运算37

3.1.1栈的概念37

3.1.2栈的基本运算37

3.1.3一个有趣的问题38

3.2栈的存储和实现39

3.2.1顺序栈39

3.2.2链栈41

3.3栈的应用43

3.3.1数制转换43

3.3.2表达式求值44

3.3.3栈与递归48

3.3.4回溯法51

习题52

第4章队列55

4.1队列的概念及基本运算55

4.1.1队列的概念55

4.1.2队列的基本运算56

4.1.3一个有趣的问题56

4.2队列的顺序存储结构及运算57

4.3循环队列58

4.4链队列60

4.5队列的应用62

习题65

第5章串和广义表68

5.1串的定义和基本运算68

5.1.1串的定义68

5.1.2串的基本运算69

5.1.3一个有趣的问题70

5.1.4串的定长顺序存储71

5.1.5模式匹配73

5.1.6串的链式存储结构77

5.1.7串的应用78

5.2广义表80

5.2.1广义表的定义80

5.2.2广义表的存储81

习题83

第6章树86

6.1树的概念及基本运算86

6.1.1树的概念86

6.1.2树的基本术语87

6.1.3树的基本运算88

6.1.4一个有趣的问题88

6.1.5树的存储89

6.2二叉树的概念与性质91

6.2.1二叉树的概念及基本运算92

6.2.2二叉树的性质92

6.2.3二叉树的存储94

6.3二叉树的遍历96

6.4二叉树遍历算法的应用99

6.5线索二叉树101

6.6树和二叉树106

6.6.1树与二叉树的转换106

6.6.2二叉树与森林的转换108

6.7哈夫曼树及其应用110

.8二叉树的应用113

习题115

第7章图117

7.1图的概念及基本运算117

7.1.1图的概念117

7.1.2图的基本运算121

7.1.3一个有趣的问题121

7.2图的存储122

7.2.1数组表示122

7.2.2邻接表表示124

7.3图的遍历127

7.3.1深度优先搜索遍历127

7.3.2广度优先搜索遍历129

7.4图的连通性问题131

7.4.1无向图的连通性131

7.4.2最小生成树132

7.4.3Prim算法133

7.4.4Kruskal算法135

7.5最短路径138

7.5.1单源点最短路径138

7.5.2任意一对顶点之间的最短路径141

7.6有向无环图的应用142

7.6.1AOV网142

7.6.2拓扑排序143

7.6.3AOE网144

7.6.4关键路径145

7.7图的应用149

习题150

第8章排序154

8.1排序的基本概念154

8.2一个有趣的问题155

8.3插入排序156

8.3.1直接插入排序156

8.3.2折半插入排序158

8.3.3希尔排序160

8.4交换排序162

8.4.1冒泡排序162

8.4.2快速排序164

8.5选择排序167

8.5.1直接选择排序167

8.5.2树形选择排序168

8.5.3堆排序170

8.6归并排序175

8.7排序的应用177

8.8各种排序方法的综合比较177

习题178

第9章查找181

9.1查找的基本概念181

9.2一个有趣的问题182

9.3静态查找表184

9.3.1顺序查找法185

9.3.2折半查找法187

9.3.3分块查找法190

9.4动态查找表191

9.5哈希表200

9.5.1哈希法与哈希表200

9.5.2冲突处理的方法202

9.5.3哈希函数的构造方法204

9.5.4哈希表的查找207

9.6查找的应用210

习题211

参考文献214

　　本书以提高学生的程序设计能力为宗旨，全面介绍了程序设计的基础知识、各种常用的数据结构以及排序、查找的各种算法及其应用。全书既注重原理，又强调实践，配有大量的图表和习题，概念讲解清楚，逻辑性强，可读性好。本书可作为高职高专院校计算机专业教材，也可作为成人教育(面授或函授)教材，还可供广大从事计算机应用的科技人员参考。　　本书以提高学生的程序设计能力为宗旨，全面介绍了程序设计的基础知识、各种常用的数据结构以及排序、查找的各种算法及其应用。为了方便教学，书中各数据结构类型和基本运算首先用类C代码加以描述，并作了详细的注解。全书既注重原理，又强调实践，配有大量的图表和习题，概念讲解清楚，逻辑性强，可读性好。本书的主要特点在于：首次尝试采用“任务驱动”方式来设计教学内容，以帮助学生更好地理解所学知识；书中有大量以“课堂思考”形式出现的问题，能在恰当的时机激发思考，启发思维；使用脚注介绍计算科学发展史知识和其他相关知识，以拓展学生的知识范围。　　本书可作为高职高专院校计算机专业教材，也可作为成人教育(面授或函授)教材，还可供广大从事计算机应用的科技人员参考。