数据结构

图书标准信息

• 作者 晋良颖 编
• 出版社 人民邮电出版社
• 出版时间 2002-03
• 版次 1
• ISBN 9787115093714
• 定价 26.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 304页
• 字数 477千字

【内容简介】

数据结构是高等学校计算机专业的核心课程，是学习计算机软件应用和开发必备的专业基础。随着计算机的日益普及，它还是"软件资格水平考试"和"考研"的必考科目，而且逐渐成为理工专业的热门选修课程。本书共分9章。前6章系统地介绍了数据结构的基本概念、逻辑结构、存储结构及在相应存储结构上的各种运算的实现算法，并对各种算法的性能进行了分析和比较；后3章介绍了检索、排序的算法及文件组织的方法。本书的算法采用C语言的函数描述，绝大多数算法都可上机实现，有的还给出了完整的C程序。
  本书内容丰富，结构严谨，阐述准确，实例众多。本书对算法的描述深入浅出、有详尽注释，有的还有图示说明和数据的动态变化过程，可读性强。本书每章都配有各种类型的习题，既便于教学也便于自学。
  本书是高等学校计算机专业或信息类相关专业的本科或专科教材，也是一本较好的"考研"和自学的参考书。

【目录】

第1章  绪论1

1.1  数据结构研究什么1

1.2  数据结构的发展概况和在计算机科学中的地位3

1.3  基本概念和术语4

1.4  数据类型和抽象数据类型6

1.5  算法和算法分析7

1.6  小结11

习题11

第2章  线性表12

2.1  线性表的基本概念12

2.2  顺序存储的线性表13

2.3  链式存储的线性表17

2.3.1  单链表17

2.3.2  循环链表32

2.3.3  双向链表33

2.4  广义表35

2.5  小结37

习题38

第3章  栈和队列40

3.1  栈40

3.1.1  栈的定义和操作40

3.1.2  栈的表示和操作的实现41

3.1.3  栈的应用举例43

3.2  队列61

3.2.1  队列定义和操作61

3.2.2  队列的表示和操作的实现62

3.2.3  队列的应用举例65

3.3  两个栈和队列的C语言程序举例68

3.4  小结76

习题76

第4章  串和数组78

4.1  字符串78

4.1.1  串的定义和操作78

4.1.2  串的存储结构和相应的操作80

4.1.3  正文模式匹配86

4.1.4  文本编辑87

4.2  数组89

4.2.1  数组的定义和操作89

4.2.2  数组的顺序表示89

4.2.3  矩阵的压缩存储90

4.2.4  一个数组应用的C语言程序98

4.3  小结101

习题101

第5章  树与二叉树102

5.1  树的定义及基本术语102

5.1.1  树的定义102

5.1.2  基本术语103

5.2  二叉树104

5.2.1  二叉树的性质104

5.2.2  二叉树的存储结构106

5.2.3  二叉树的建立109

5.3  遍历二叉树114

5.3.1  二叉树的遍历算法114

5.3.2  二叉树遍历算法的应用120

5.4  线索二叉树127

5.4.1  二叉树的线索化算法129

5.4.2  线索二叉树的有关操作131

5.5  二叉排序树（二叉查找树）135

5.5.1  二叉排序树的建立和插入135

5.5.2  二叉排序树的查找137

5.5.3  二叉排序树的删除139

5.5.4  平衡二叉树的概念142

5.6  树和森林143

5.6.1  树的存储结构143

5.6.2  树和森林与二叉树的转化146

5.6.3  树和森林的遍历148

5.7  哈夫曼树及其应用151

5.8  小结157

习题158

第6章  图160

6.1  基本概念和术语160

6.2  图的存储结构163

6.2.1  邻接矩阵163

6.2.2  邻接表165

6.3  图的遍历168

6.3.1  深度优先搜索遍历168

6.3.2  广度优先搜索遍历171

6.4  连通网的最小生成树172

6.4.1  普里姆（Prim）算法173

6.4.2  克鲁斯卡尔(Kruskal)算法177

6.5  最短路径180

6.5.1  从某个源点到其余各顶点的最短路径181

6.5.2  每一对顶点间的最短路径186

6.6  拓扑排序189

6.7  关键路径194

6.8  小结200

习题200

第7章  排序203

7.1  内排序204

7.1.1  内排序的分类204

7.1.2  插入排序205

7.1.3  交换排序211

7.1.4  选择排序216

7.1.5  合并排序222

7.1.6  计数排序229

7.1.7  基数排序231

7.1.8  各种内排序方法的比较讨论235

7.2  外排序237

7.2.1  K路平衡归并237

7.2.2  置换-选择排序242

7.2.3  哈夫曼归并树243

7.2.4  一个利用败者树进行外排序的C语言程序示例245

7.3  小结249

习题250

第8章 查找251

8.1  查找的基本概念251

8.2  静态查找表252

8.3  动态查找表256

8.3.1  B树256

8.3.2  B+树261

8.3.3  一个B+树的C语言实例265

8.3.4  B树与B+树各种操作的比较276

8.4  哈希表277

8.4.1  概述277

8.4.2  哈希函数279

8.4.3  处理冲突的方法及相应的造表和有关操作280

8.4.4  哈希表的查找分析285

8.5  小结286

习题287

第9章  文件288

9.1  文件的基本概念和文件的存储结构288

9.2  顺序文件290

9.2.1  存储在顺序存储器上的顺序文件290

9.2.2  存储在直接存取存储器上的顺序文件291

9.2.3  堆文件292

9.3  索引文件和索引顺序文件292

9.3.1  索引文件293

9.3.2  索引顺序文件293

9.3.3  对于B树、B+树需要注意的问题294

9.4  哈希文件296

9.4.1  文件的组织方式296

9.4.2  文件的操作298

9.4.3  文件的扩充298

9.5  多关键字文件299

9.5.1  索引链接文件（多重表文件）299

9.5.2  倒排文件301

9.6  小结302

习题303

参考书目304