本书以较通俗的语言，按照由易到难的原则，详细介绍了各种数据结构的基本概念、逻辑特性和物理特性，对各种结构定义了相应的抽象数据类型（ADT）以及相关的操作和算法。本书采用类C语言描述算法，并给出了各种算法的效率分析，以及这些结构在计算机科学及其他领域的应用。在各章末尾，还给出了几个算法设计的例子。
　　本书可作为高等院校计算机专业的教材，同时也可供计算机工程技术人员参考。

无

“数据结构”是20世纪70年代开始设立的计算机科学与技术专业的基础课，现在是其重要的核心课程。随着计算机软、硬件技术的发展，计算机在各个学科和领域得到广泛应用，其当今应用的一个主要方面就是数据处理，如情报检索、数据采集、企业管理、决策分析和人工智能等。而应用到这些领域时所面临的首要问题就是对于信息量大、种类繁多、结构复杂的数据和数据关系的处理，由此必须设计高级的数据结构和数据组织，以便有效地实现数据采集、数据组织、数据存储、数据传输和数据处理。数据结构主要研究数据的逻辑结构、数据在计算机中的物理结构，以及处理不同结构数据的算法。我们研究数据结构的目的是为了学会编写更高效的程序，而高效、简洁的程序取决于数据结构和算法的设计。
　　现在，有关算法与数据结构的教材，一部分侧重于算法的基本思想和步骤，用伪代码描述；一部分用程序语言描述，侧重于算法的程序实现。前者侧重于对数据结构原理的阐述，不利于学生掌握算法的程序实现以及对算法的分析、比较。后者增加了对数据元素的描述，从而使得程序更难理解。
　　本教材对数据结构和算法用类C语言描述，数据结构和算法在设计本质上是属于底层的，在本书中并不提供可直接上机运行的源代码，而是提供一种类C语言伪代码来描述算法的基本思想和基本步骤。此外，用类C语言描述的算法容易转换为C语言程序。
　　本书系统全面地介绍了各种传统的数据结构，对每种数据结构及相关算法都进行了时间和空间效率的分析，强调算法与数据结构的密不可分性，引进抽象数据类型概念，将数据类型与其上的操作封装为一体，为面向对象的程序设计方法奠定了坚实的基础。此外，针对不同的抽象数据类型讨论不同的存储方法，并且研究不同存储方法的可能算法，从而体现了计算机学科方法论的理论、抽象和设计三个过程。
　　全书分为11章：第1章是概论，解释了从问题到程序的求解过程，以及在这一过程中抽象数据类型的表述和作用，介绍了程序的运行步骤及复杂度；第2章介绍了有关线性表的概念及其基本操作，该章是后续章节的基础；第3章在第2章的基础上讨论了操作受限的线性表——栈与队列的特点，并列举了几个应用示例；第4章简要给出了非数值处理——串的处理方法；第5章主要是关于程序设计中的一种常用数据类型——数组在计算机内部的表示和实现，同时介绍了广义表的概念；第6章描述了非线性复杂数据结构——树，它是解决决策和博弈等问题的基本结构；第7章是关于图的内容，包括有向图和无向图。图是一种比树更复杂的数据结构；第8章涉及存储管理中应用的基本方法；第9章以集合作为数据模型，讨论了查找的方法和技术；第10章介绍了一些常用的排序算法，包括内部排序和外部排序；第11章简要介绍了文件。
　　本书由教学一线的教授亲自主笔，根据作者多年的教学实践经验，针对算法与数据结构这门课程的特点撰写而成，目的是培养学生合理组织数据和进行优秀的算法设计的能力。本书尽量合理地安排内容顺序，教师可以根据需要自由地重新组织内容。
　　本教材可作为高等院校计算机科学与技术专业的教材、参考书和考研辅导，同时也可供计算机工程技术人员参考。对于计算机科学与技术专业，可讲授64学时，对于其他专业，去掉带星号的章节，可讲授48学时。
　　本书的第1、2、3章由周世平同志编写，第4、10章由胡潇琨同志编写，第5、9章由孟佳娜同志编写，第6、8、11章由谭征同志编写，第7章由范策同志编写。全书由范策同志统稿，陈守孔同志编写了各章最后一节的算法设计并审阅了全书，孟佳娜同志编写了本书的电子教案。
　　由于作者水平所限，加上计算机科学技术的发展十分迅速，书中难免有不妥和挂一漏万之处，恳请广大读者赐教。

编　 者
2004年4月于烟台大学

范策 周世平 胡潇琨 等编著：暂无简介

第1章　 概论1
11　 引言1
111　 解决问题的步骤1
112　　一个例子2
12　 数据结构4
121　 为什么要学习数据结构4
122　 有关概念和术语5
13　 抽象数据类型9
14　 类C语言描述11
15　 算法和算法分析14
151　 算法的定义及算法设计的要求14
152　 算法与数据结构和程序16
153　 算法性能分析与度量16
154　 复杂度函数的增长率19
155　 复杂度分析的例子20
第2章　 线性表23
21　 线性表的类型定义23
211　 线性表的概念23
212　 线性表的抽象数据类型 24
213　 线性表的例子25
22　 线性表的顺序表示和实现27
221　 线性表的顺序表示27
222　 顺序表操作的实现28
23　 线性表的链式表示和实现31
231　 单链表的表示32
232　 线性链表操作的实现33
24　 线性表实现方法的比较38
25　 循环链表39
26　 双链表40
27　 静态链表41
*28　 算法设计举例43
第3章　 栈和队列47
31　 栈47
311　 栈的类型定义47
312　 栈的表示和实现48
313　 顺序栈和链栈的比较51
32　 队列52
321　 队列的类型定义52
322　 循环队列53
323　 链队——队列的链式表示和实现56
*33　 递归57
331　 递归的定义57
332　 递归的实现59
333　 递归和迭代64
334　 递归的消除65
*34　 算法设计举例68
第4章　 串73
41　 串的类型定义73
42　 串的表示和实现74
421　 串的顺序存储结构75
422　 串的链式存储结构76
*43　 串的模式匹配77
431　 朴素的模式匹配算法77
432　 首尾模式匹配算法78
433　 KMP算法79
44　 串的应用举例82
*45　 算法设计举例83
第5章　 数组和广义表85
51　 数组的概念及其基本操作85
52　 数组的顺序存储86
53　 矩阵的压缩存储88
531　 特殊矩阵88
532　 稀疏矩阵 90
*54　 广义表98
541　 广义表的定义98
542　 广义表的存储结构99
*55　 算法设计举例101
第6章　 树105
61　 树的概念及操作105
62　 二叉树107
621　 二叉树的概念及操作108
622　 二叉树的性质109
623　 二叉树的存储结构111
63　 二叉树的遍历112
*64　 线索二叉树116
65　 树和森林121
651　 树的存储结构121
652　 森林、树、二叉树的相互转换124
653　 树和森林的遍历126
66　 哈夫曼树及其应用127
661　 最优二叉树(哈夫曼树)127
662　 哈夫曼编码129
*67　 算法设计举例132
第7章　 图137
71　 图的定义和术语137
72　 图的存储结构140
721　 数组表示法140
722　 邻接表141
*723　 十字链表143
*724　 邻接多重表144
73　 图的遍历145
731　 深度优先搜索145
732　 广度优先搜索146
74　 图的连通性问题147
741　 图的连通分量和生成树147
742　 最小生成树149
75　 有向无环图及其应用151
751　 拓扑排序151
*752　 关键路径154
76　 最短路径158
761　从某个源点到其他各顶点的最短路径158
762　 每一对顶点之间的最短路径161
*77　 网络流问题163
*78　 算法设计举例167
*第8章　 动态存储管理171
81　 概述171
82　 可利用空间表及分配方法172
83　 边界标识法176
84　 伙伴系统181
第9章　 集合187
91　 概述187
92　 线性表上的查找188
921　 顺序表的查找189
922　 有序表的查找190
93　 索引表上的查找196
94　 树表上的查找197
941　 二叉排序树197
942　 平衡二叉树203
*943　 B树210
*944　 键树216
95　 哈希表217
951　 哈希表查找的基本概念217
952　 构造哈希函数的方法218
953　 哈希冲突的解决方法220
954　 哈希表的查找及分析223
*96　 算法设计举例225
第10章　 排序229
101　 概述229
102　 插入排序230
1021　 直接插入排序230
1022　 折半插入排序232
*1023　 二路插入排序232
*1024　 表插入排序234
1025　 希尔排序236
103　 交换排序237
1031　 起泡排序237
1032　 快速排序238
104　 选择排序241
1041　 直接选择排序241
1042　 树形选择排序242
1043　 堆排序243
105　 归并排序246
106　 分配排序247
107　 各种内部排序方法的比较250
108　 外部排序252
1081　 文件管理252
1082　 外部排序的方法253
1083　 多路平衡归并排序255
1084　 置换选择排序257
*1085　 最佳归并树261
*1086　 磁带排序262
*109　 算法设计举例263
第11章　 文件267
111　 文件的基本概念267
112　 顺序文件269
113　 索引文件272
114　 索引顺序文件273
1141　 ISAM文件274
*1142　 VSAM文件276
115　 散列文件278
*116　 多关键字文件279
1161　 多重表文件279
1162　 倒排文件280
参考书目282