数据结构与算法

出版时间：2010-9  出版社：北京航空航天大学出版社  作者：于晓敏　等编著  页数：265  

前言

计算机在各个领域的应用过程中，都会涉及数据的组织与程序的编排等问题，都会用到各种各样的数据结构，特别是针对各种特殊数据的表示，就更需要学会分析和研究计算机加工对象的特性、选择最合适的数据组织结构及其存储表示方法，以及编制相应实现算法的方法，这是计算机工作者不可缺少的知识。因此“数据结构”这门课一直是高等院校计算机专业教学中的一门主要技术基础课程，在我国当前的计算机专业教学计划中，它是主干课程之一。本书分数据结构和算法设计两部分。在数据结构中，讨论了四大类型数据结构的逻辑特性、存储表示及其应用。在算法设计中着重阐述典型算法的设计与分析。每一章后都配有适量的习题，以供读者练习。全书分上、下两篇，共16章。前9章为上篇，主要阐述数据结构的相关内容；后7章主要阐述算法设计的相关内容。第1章至第4章主要介绍数据结构的基本知识和几种基本的数据结构，即线性表、栈和队列、串和数组，它们均属于线性数据结构。第5和第6章叙述非线性数据结构，它们是树、图和广义表；第7、8两章分别介绍数据处理中广泛使用的技术——排序和查找；第9章讨论外存储器上的数据结构——文件；第10章至第14章介绍了蛮力法、贪心法、分治法、动态规划法和回溯法等典型算法及应用；第15章介绍计算复杂性理论；第16章介绍分布式算法的设计与分析。本书是在计算机科学与技术专业规范和作者多年的教学经验的基础上编写而成的。本书的编写思路既注重基本原理的介绍又重视实践能力的培养。书中还配有大量的例题和习题，供学生练习，加深对知识点的理解。本书讲解详细，通俗易懂，详略得当。书中算法采用C语言进行描述，且所给的程序均已在计算机上运行调试，部分程序还做了较详细的注解，以便于读者了解算法的实质和基本思想。书中每一章均有习题，可以检验读者的学习效果和培养程序设计的能力。本书既可作为计算机专业学生的教材，亦可供从事计算机应用的工程技术人员参考，特别适合于那些使用C语言编程的计算机应用人员。使用本书作为本科生教材时，其内容可以讲授一个学期；若作为专科生教材时，可以酌情精简有关内容。本书初稿经过在我校的教学实践的检验，教学效果较好，学生反映本书好学易懂。本书的第1章的前两节、第4章、第5章、第6章和第9章由于晓敏编写，第2章和第3章由于晓坤编写，第7章和第8章由耿蕊编写，第1章的第3节、第10章至第16章由袁琪编写。由于作者水平有限，书中缺点或错误在所难免，殷切希望广大读者批评指正。

内容概要

计算机在各个领域的应用过程中，都会涉及数据的组织与程序的编排等问题，都会用到各种各样的数据结构，选择最合适的数据结构和存储表示方法，以及编制相应的实现算法的方法是计算机工作者不可缺少的知识。本书根据计算机科学与技术专业规范的要求，全面、系统地介绍各种类型的、最常用的数据结构及常用的算法。全书分上、下两篇，上篇数据结构，下篇算法设计与分析。在数据结构中，讨论了4大类型数据结构的逻辑特性、存储表示及其应用。在算法设计中着重阐述典型算法的设计与分析。每一章后都配有适量的习题，以供读者练习。概念清楚，内容丰富，详略得当，既可以作为高等院校计算机应用本科等层次的教材，也可以供从事计算机工程与应用的科技工作者参考或自学。

书籍目录

第1章　绪论上篇　数据结构　第2章　线性表　第3章　栈和队列　第4章　串和数组　第5章　二叉树和树　第6章　图和广义表　第7章  排  序　第8章  查  找　第9章  文  件下篇　算法分析　第10章　蛮力法　第11章　贪心法　第12章　分治法　第13章　动态规划法　第14章  回溯法　第15章　计算复杂性理论　第16章　分布式算法参考文献

章节摘录

插图：分治法求解较大规模的问题时，先简化问题规模，把该问题分解成几个子问题，最终通过子问题的解获得原问题的解。在分解问题的过程中采用的是自顶向下的方法，将大问题分割成独立的子问题，再对子问题递归分解，最终通过最小子问题的解层层合并，最终获得原问题的解。反之，如果在求解过程中采用自底向上的方法，先求出最小规模子问题的解，向上逐步扩大问题的规模，最终获得原问题的解，这样的处理过程就引出了动态规划法。动态规划法主要是针对最优化问题采用的一种算法。其基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任意子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。可以看出，动态规划法是对多阶段决策过程的求解，它的决策不是线性的，而是全面考虑各种不同的情况分阶段作出决策。每一阶段的决策都会使问题的规模和状态发生变化，而决策序列就是在这种变化的状态中产生出来的，因此称之为“动态”的。这种解决多阶段决策最优化的过程称为动态规划法。数据结构中用于计算有向图传递闭包的warshall算法、计算完全最短路径的Floyed算法、最优二叉查找树等，数学应用中的矩阵乘积问题、复杂工程问题的多种应用如资源分配问题、前面介绍过的0／1背包问题、货郎担问题、作业调度问题等都可以通过动态规划法获得最优解。那么到底哪些问题适用于动态规划法呢？如果原问题能分解为独立子问题，用分治法较为简单方便。当子问题不独立时，则采用动态规划法。通常，能用动态规划法解决的问题应该具有下面三个性质：1）最优化子结构如果问题的最优解所包含的子问题也是最优的，称该问题具有最优子结构，满足最优化原理。2）无后向性某阶段状态一旦确定，不受这个状态以后决策的影响，即某状态以后的过程不会影响以前的状态，只与当前状态有关。3）子问题重叠子问题之间不独立，一个子问题在下一阶段决策中可能被多次使用到。该性质不是动态规划适用的必要条件，但如果该性质无法满足，动态规划法解决相应问题的优势将不复存在。

编辑推荐

《数据结构与算法》：高等学校教材·计算机教学丛书。

用户评论 (总计8条)

•   信息学竞赛数据结构学习用书。
•   帮亲戚买的，她很喜欢这本书。
•   上学用的，还凑合，价格也还行。
•   东西还不错的除非对方的
•   讲得还可以，就是是c++的
•   破书！！！内容编排还好，给出的例程编写很不认真，错误超多！要知道，代码这些东西少一个字母都会出错！！！它几乎每个例程都有写错！
•   是看了该老师的视频才特意买这本书的，感觉的和一般的数据结构的书还是有区别的。
•   书本身没什么问题。学校用的是廖明宏那版，这两本书出版社和封皮都一模一样，哈工大的同学们注意。