书在选材与编排上,以“可读”“可学”“可用”“可研”“可练”为目标。全书共8章,内容涵盖绪论、线性表、栈和队列、数组和矩阵、树和二叉树、图、查找以及排序。全书共有118个算法、61个示例、21个应用案例、212道练习题。练习题题型包括填空题、简答题、应用题、算法设计题和上机练习题五类,满足原理理解、知识应用、模仿、创新、算法训练及实践训练多方面需求。每章小结给出全章知识结构图以及相关算法与应用汇总。 本书内容丰富、编排新颖、图文并茂。原理叙述直达要义,算法步骤与伪码一一对应。可作为高等学校计算机及相关专业“数据结构”课程教材,也可供从事计算机软件开发与应用的工程技术人员参考。

第1章绪论1 1.1课程属性与术语1 1.1.1数据结构是程序的重要组成部分1 1.1.2数据结构是提升编程能力的2 1.1.3数据结构与术语2 1.1.4数据结构决定算法4 1.2数据结构的研究内容4 1.2.1逻辑结构5 1.2.2存储结构/物理结构6 1.2.3逻辑结构与物理结构的关系7 1.2.4非数值计算问题8 1.2.5数据结构与程序设计的关系10 1.3抽象数据类型11 1.3.1抽象数据类型的定义11 1.3.2抽象数据类型的实现12 1.4算法与算法分析13 1.4.1算法的概念13 1.4.2算法描述13 1.4.3算法性能分析15 1.5小结20 习题121 第2章线性表25 2.1线性表的定义25 2.1.1线性表的逻辑特性25 2.1.2线性表的抽象数据类型26 2.2顺序表28 2.2.1顺序表的定义28 2.2.2顺序表的存储设计29 2.2.3顺序表的操作及实现30 2.2.4顺序表应用举例36 2.3链表39 2.3.1单链表的定义及特性39 2.3.2单链表的存储设计40 2.3.3单链表的操作及实现41 2.3.4其他形式的链表50 2.3.5链表应用举例53 2.4顺序表与链表的比较57 2.4.1空间性能比较58 2.4.2时间性能比较58 2.4.3环境性能比较58 2.5小结58 习题259 第3章栈和队列63 3.1栈63 3.1.1栈的定义和特点63 3.1.2顺序栈65 3.1.3链栈69 3.1.4顺序栈和链栈的比较73 3.1.5栈的应用73 3.2队列80 3.2.1队列的定义和特点80 3.2.2循环队列81 3.2.3链队85 3.2.4循环队列与链队列的比较89 3.2.5队列的应用89 3.3小结91 习题392 第4章数组和矩阵95 4.1多维数组95 4.1.1数组的定义95 4.1.2数组的顺序存储97 4.2特殊矩阵99 4.2.1对称矩阵100 4.2.2三角矩阵100 4.2.3对角矩阵101 4.3稀疏矩阵102 4.3.1三元组表顺序存储102 4.3.2带行指针向量的链式存储105 4.3.3十字链表108 4.4小结109 习题4110 第5章树和二叉树113 5.1树114 5.1.1树的定义与表示114 5.1.2树的术语115 5.1.3树的抽象数据类型116 5.1.4树的存储设计118 5.1.5树和森林的遍历120 5.2二叉树的定义与特性121 5.2.1二叉树的定义121 5.2.2特殊二叉树122 5.2.3二叉树的性质123 5.2.4二叉树的抽象数据类型125 5.3二叉树的存储结构127 5.4二叉树操作129 5.4.1二叉树遍历129 5.4.2根据遍历序列确定二叉树137 5.4.3先、中、后序遍历的非递归算法139 5.4.4二叉树的其他操作145 5.5线索二叉树148 5.5.1线索二叉树的定义148 5.5.2线索二叉树的建立149 5.5.3线索二叉树的遍历151 5.6树和森林与二叉树的相互转换154 5.6.1树与二叉树相互转换154 5.6.2森林与二叉树相互转换156 5.7二叉树及其应用157 5.7.1基本概念157 5.7.2构造二叉树158 5.7.3哈夫曼编码164 5.8小结167 习题5168 第6章图171 6.1图的定义及相关术语171 6.1.1图的定义171 6.1.2图的术语172 6.1.3图的抽象数据类型176 6.2图的存储及操作177 6.2.1邻接矩阵表示法及操作举例177 6.2.2邻接表表示法及操作举例181 6.2.3十字链表表示法及操作举例184 6.2.4邻接多重表表示法及操作举例186 6.3图的遍历及应用189 6.3.1深度优先遍历189 6.3.2广度优先遍历192 6.3.3遍历应用举例195 6.4图的应用199 6.4.1小生成树199 6.4.2短路径205 6.4.3AOV网与拓扑排序211 6.4.4AOE网与关键路径216 6.5小结220 习题6221 第7章查找225 7.1查找的基本概念225 7.1.1术语225 7.1.2查找性能226 7.2线性表查找技术227 7.2.1顺序查找227 7.2.2折半查找228 7.2.3串的模式匹配231 7.3树表查找236 7.3.1二叉排序树236 7.3.2平衡二叉树243 7.4散列查找247 7.4.1散列函数的构造方法248 7.4.2处理冲突的方法250 7.4.3散列表的查找253 7.5小结255 习题 7256 第8章排序259 8.1排序的基本概念259 8.1.1排序的定义260 8.1.2内排序与外排序261 8.1.3排序性能261 8.1.4内部排序方法的分类262 8.1.5待排序记录的存储方式262 8.2插入排序262 8.2.1直接插入排序263 8.2.2折半插入排序265 8.2.3希尔排序267 8.3交换排序268 8.3.1冒泡排序269 8.3.2快速排序271 8.4选择排序275 8.4.1简单选择排序275 8.4.2树形选择排序277 8.4.3堆排序279 8.5归并排序284 8.6基数排序287 8.6.1分配排序287 8.6.2多关键码排序288 8.6.3基数排序详解289 8.7各种排序方法的比较291 8.7.1性能比较292 8.7.2方法选用293 8.8小结294 习题8294 附录术语表297 参考文献301