数据结构与算法

出版时间：2009-2  出版社：清华大学出版社  作者：唐宁九　等主编  页数：473  

前言

数据结构与算法内容丰富，包含了计算机科学与技术的许多重要方面。分析和解决问题的思路和方法新颖，技巧性强，对学生的计算机软件素质的培养作用明显。培养和训练学生选用合适的数据结构与算法设计方法编写质量高、风格好的应用程序，并具备评价算法优劣的能力至关重要。本书采用C++面向对象的观点介绍数据结构与算法，并使用模板程序设计技术，与采用面向过程的传统观点相比优势较大，使所设计的程序更容易实现代码重用，在提供通用性和灵活性的同时，又保证了效率。本书已将面向对象程序设计的思想融合到数据结构与算法中，读者通过学习可进一步提高面向对象程序设计的能力。全书共分为11章。第1章是基础知识，介绍了基本概念及其术语，抽象数据类型的实现，还讨论算法的概念和算法分析的简单方法。作为预备知识，读者应具有一定的C++程序设计的基础。但是为了降低读者的门槛，本章还介绍了要用的C++的主要知识点，并介绍了实用程序软件包。第2章引入线性表，详细讨论线性表的顺序存储结构与链式存储结构。在讨论链式存储结构时，首先仿照传统方法实现线性表，然后在此基础之上，在链表结构中保存当前位置和元素个数。这样，在难度增加不大的情况下提高算法效率，使学生逐步体会改进算法的途径与方法。第3章介绍了栈和队列，讨论了栈和队列的顺序存储结构与链式存储结构，用栈实现了表达式求值。通过学习能掌握各种栈和队列的实现与使用方法，对后继课程（如操作系统原理和编译原理）的学习打下良好的基础。本章还讨论了优先队列，使队列应用更加广泛。第4章介绍串，详细讨论了串的存储结构与模式匹配算法，为开发串应用（如实现文本编辑软件）软件打下坚实的基础。第5章介绍数组和广义表，详细讨论了数组，特殊矩阵，稀疏矩阵和广义表的存储结构及实现方法，首次提出了广义表的使用空间表存储结构，并使用广义表实现了m元多项式的表示。第6章介绍了树结构，讨论了二叉树、线索二叉树、树、森林及其哈夫曼树的结构及其实现，还应用哈夫曼编码实现了压缩软件。第7章介绍图结构，实现了图的常用存储结构，并讨论了图的相关应用，实现了相应算法（如求最小生成树的Prim算法与Kruskal算法，求最短路径的Dijkstra算法与Floyd算法）。第8章介绍查找，讨论了静态查找表、动态查找表与散列表，还讨论了二叉排序树、二叉平衡树与B树，并实现了所有算法。第9章介绍排序，以简洁方式实现各种排序算法，还测试了各种排序算法的实际运行时间。第10章介绍了文件，讨论了主存储器和辅助存储器，以及各种常用文件结构，还特别介绍了在数据库中经常采用的VSAM文件，对读者研究与学习数据库有一定的帮助。第11章介绍了算法设计技术、分析技术与可计算问题，详细讨论了各种算法设计技术（如贪心算法、分治算法、回溯算法）的使用方法并实现了各种算法，对算法分析技术和可计算问题也进行了深入浅出的讨论。对读者的算法设计和分析的理论和实践都有极大的帮助。对于初学者，要完全独立编写数据结构与算法的代码是相当困难的。因此，本书讨论的数据结构与算法都加以实现并进行了严格测试，提供了完整的测试程序，读者可参考这些测试程序编写相关算法。但是，如果只会使用已有的数据结构编写简单的程序也不利于读者对数据结构与算法的深入理解，以及研究新数据结构与算法的能力。因此，本书的习题不但包括了基本练习题，还包括了仿照书中数据结构构造新数据结构的题目，或改造已有算法的题目，这样使读者具有构造新结构及改造或改进算法的能力。本书各章还提供了实例研究，主要提供给那些精力充沛的学生深入学习与研究，这些实例包括对正文内容的补充（例如第9.9.3小节中的用堆实现优先队列），读者可能感兴趣但感到无从下手的算法（例如第1.6.2小节中的计算任意位数的π) 、离散数学中学习的著名算法的实现（例如第7.7.1小节中的周游世界问题——哈密尔顿圈与第7.7.2小节中的一笔画问题——欧拉问题）以及应用所学知识解决实际问题（例如第6.8.2小节中的Huffman压缩算法）。通过读者对实例研究的学习，可提高实际应用数据结构与算法的能力。当然，这可能有一定的难度，但应比读者想象的更易学习与掌握。现在，各校在开设“数据结构与算法”课时都安排有上机实验课时，因此本书每章都安排有上机实验题，这些实验题不但包括读者感兴趣的实验（例如纸牌游戏—— “21点”) ，数据结构与算法基本应用的实验（例如编写一个程序读入一个字符串，统计字符串中出现的字符及次数，然后输出结果，要求用一个二叉排序树来保存处理结果，结点的数据元素由字符与出现次数组成，关键字为字符），对课本数据结构与算法改进的实验（例如改进本书实现的求最小生成树的Kruskal算法，用最大优先队列来实现按照边的权值顺序处理，用等价关系判断两个结点是否属于同一棵自由树以及合并自由树），还包括了解决实际问题的实验（例如采用散列文件实现电话号码查找系统），通过实验能极大地提高读者对数据结构与算法的应用能力。为了进一步提高读者运用数据结构与算法的水平，现在很多学校还开设了“数据结构与算法课程设计”。为此，本书的附录提供了11个课程设计项目，这些项目包括了接近实际课题的题目（例如开发排课软件与公园导游系统）、容易引起读者兴趣的项目（例如理论计算机科学家族谱的文档／视图模式）与需要通过查找资料进一步提高的题目（例如采用自适应形式的哈夫曼编码方案开发压缩软件）。课程设计项目一般都提供功能的扩展方法，基础较差的读者可只实现基础功能，对数据结构与算法有兴趣的读者可实现更强的功能，这样使不同层次的读者都会有所收获，通过做这些项目能快速提高读者解决实际问题的能力。为了尽快提高读者的学习能力，本书各章还提供了深入学习导读，包含了本书作者实现相关数据结构与算法的最原始思想的资料来源，也包括了进一步学习的参考资料，极大地方便读者与教师查阅资料。本教材在内容组织上特别考虑了读者的可接受性；在算法实现时，重点考虑了程序的可读性，为实现更强的功能，一般采用启发的方式在习题、上机实验或课程设计中实现，这样容易培养起读者的学习兴趣，使读者感到自己具有发展或改进已有算法的能力，也会使读者感到自己已达到计算机高手的自信心。本书作者都活跃在教学研究第一线上，同时有的作者还具有深厚的数学功底。因此，本书不但完成了所有算法的测试程序，对算法分析的相关公式进行了严格的数学推理，还独立地从数学上严格推出了一种产生泊松随机数的算法（见附录B) 。事实上，用同样的方法可产生任何离散随机分布（例如二项分布），本书作者还首次对本书中关于计算任意位数π的算法作了严格的理论推导。本书采用了模板程序设计技术，现在模板技术已成为现代C++语言的风格基础，C++98(1998年标准化的C++)提供的标准程序库中有80%的成分是使用模板机制实现的STL(Standard Template Library，标准模板库)。而国内现阶段教学并未重视C++的模板程序设计，书籍资料也不是很多。作者认为在C++中，只要模仿本书算法，读者会在不知不觉中掌握模板程序设计技巧。现在来讨论一下在国外“数据结构与算法”课程上机教学时喜欢采用的STL。实际上，STL是AT&T贝尔实验室和HP研究实验室的研究人员将模板程序设计和面向对象程序设计的原理结合起来，创造的一套研究数据结构与算法的一种统一的方法，现在已成为C++标准库的一部分。STL提供了实现数据结构的新途径，它将(数据)结构(即组织数据的存储结构)抽象为容器，将之分为3类：序列容器、关联容器和适配器容器。通过使用模板和迭代器，STL使得程序员能够将广泛的通用算法应用到各种容器类上。通过本书作者的研究与了解，STL只覆盖了数据结构中的线性结构和树结构，并没有覆盖图部分。因此，对数据结构来讲，STL并不完备。同时，如果读者上机编程都只使用STL解决数据结构的相关算法，可能使读者在数据结构编程方面，只会使用STL，而不能独自设计新数据结构。本书采用模板方法实现了书中所有的数据结构算法，应比STL更完备。同时，STL中包含的源代码可读性差，不适合作为教学使用，本书的算法源程序首要强调可读性，使读者容易接受与模仿，并且读者可进行改进或修改算法实现。因此，在某种意义上讲，本书提供的关于数据结构与算法实现的类模板与函数模板是一种GTL (General Template Library）或OSGTL (Open Source General Template Library) 。读者也可由作者个人主页提供的软件包（具体内容请参看附录C）来进行实际数据结构与算法方面的软件开发。当然，通过本书的学习，再返回来学习STL的应用，将会达到事半功倍的效果。读者只要找一本介绍STL的书籍或上网找一些介绍使用STL的文档，并用STL试着编程即可完全掌握STL的使用。现在谈谈有关C++编译器的问题，在C++之外的任何编程语言中，编译器都没有受到过如此重视。这是因为C++是一门非常复杂的语言，以至于编译器也难于构造。我们常用的编译器都不能完全符合C++标准，以至于本书的部分测试不得不使用条件编译技术来适应不同C++编译器，下面介绍一些常用的优秀C++编译器。(1)  Visual C++编译器：由微软开发，现在主要流行Visual C++ 6.0、Visual C++ 2005以及Visual C++ 2005 Express，特点是集成开发环境用户界面友好，信息提示准确，调试方便，对模板支持最完善。Visual C++ 6.0对硬件环境要求低，现在安装的计算机最多，但对标准C++兼容只有83.43%. Visual C++ 2005与Visual C++ 2005 Express在软件提示信息上做了进一步的优化与改进，并且对标准C++兼容达到了98%以上的程度，但对硬件的要求较高。同时，Visual C++ 2005 Express是一种轻量级的Visual C++软件，易于使用。对于编程爱好者、学生和初学者来说，Visual C++ 2005 Express是很好的编程工具，微软在2006年4月22日正式宣布 Visual Studio 2005 Express版永久免费。(2)  GCC编译器：著名的开源C++编译器。是类UNIX操作系统（例如Linux）下编写C++程序的首选，有非常好的可移植性，可以在非常广泛的平台上使用，也是编写跨平台、嵌入式程序很好的选择。GCC 3.3与标准C++兼容大概能够达到96.15%。现已有一些移植在Windows环境下使用GCC编译器的IDE（集成开发环境），例如Dev-C++与MinGW Developer Studio。其中，Dev-C++是能够让GCC在Windows下运行的集成开发环境，提供了与专业IDE相媲美的语法高亮、代码提示、调试等功能；MinGW Developer Studio是跨平台下的GCC集成开发环境，目前支持 Windows、Linux和 FreeBSD。根据作者的实际使用，感觉使用GCC编译器的IDE错误信息提示的智能较低，错误提示信息不太准确，还有就是对模板支持较差，对语法检查较严格，在Visual C++编译器中编译通过的程序可能在GCC编译器的IDE还会显示有错误信息。本书所有算法都同时在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio中通过测试。读者可根据实际情况选择适当的编译器，建议选择Visual C++ 2005.教师可采取多种方式来使用本书讲授数据结构，数据结构与算法分析，数据结构与算法设计，数据结构与算法等课程，应该根据学生的背景知识以及课程的学时数来进行内容的取舍。为满足不同层次的教学需求，本教材使用了分层的思想，分层方法如下：没有加星号（）及双星号（）的部分是基本内容，适合所有读者学习；加星号的部分适合计算机专业的读者深入学习；加有双星号的部分适合于感兴趣的同学研究，尤其适合于那些有志于ACM竞赛的读者加以深入研究。下面给出了几种可能的课程安排，建议习题及实验的主要形式是让学生编写并调试一些程序。开始时程序可以比较短，随着课程的深入，程序将逐渐变大。学生应根据课堂上所讲授的主题同步阅读课本相关内容。学 分大约课时数内  容232选讲第1章~~第9章中没有打星号（）及双星号（）的内容348第1章~~第10章中没有打星号（）及双星号（）的内容464第1章~~第11章中没有打星号（）及双星号（）的内容580第1章~~第11章中没有打星号（）及双星号（）的内容，选讲部分打有星号（）的内容696第1章~~第11章中没有打双星号（）的内容，选讲部分打有双星号（）的内容  作者为本书提供了全面的教学支持，如果在教学或学习过程中发现与本书有关的任何问题都可以与作者联系作者将尽力满足读者的要求，并可能将解答公布在作者的教学网站上。另外，在作者的教学网站上还将提供如下内容。(1)  提供书中所有算法在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio开发环境中的测试程序，今后还会提供当时流行的C++开发环境的测试程序，每种开发环境还将提供基本开发过程的文档；还提供本书作者开发的软件包（包含所有本书所讲的数据结构与算法的类模板与函数模板）。2)  提供教学用PowerPoint幻灯片PPT课件。(3)  向教师提供所有习题、上机实验题与课程设计项目的解答或参考程序，对学生来讲，将在每学期期末（第15周~~第20周）公布解压密码。(4)  数据结构与算法问答专栏。(5)  提供至少8套数据结构与算法模拟试题及其解答，以供学生期末及其考研复习，也可供教师出考题时参考。(6)  提供数据结构与算法相关的其他资料（例如作者收集的计算任何位数π的资料，Dev-C++与MinGW Developer Studio软件，流行免费C++编译器的下载网址）。希望各位读者能够抽出宝贵的时间将建议或意见（当然也可以发表对国内外“数据结构与算法”课程教学的任何意见）寄给作者，为我们修订教材提供重要参考。孙界平、张卫华、邹昌文、王文昌、周焯华、胡开文、沈洁、周德华与欧阳等人对本书做了大量的工作，包括提供资料，调试算法，以及参与部分章节的编写；作者还要感谢为本书提供直接或间接帮助的每一位朋友，由于他们热情的帮助与鼓励，激发了写好本书的信心以及热情。在此还要感谢清华大学出版社的编辑及评审专家，他们为本书的出版倾注了大量热情。正是由于他们具有前瞻性的眼光才让读者有机会看到本书。尽管作者秉着负责任的态度编写这本书，并尽了最大努力，但由于水平有限，书中难免有不妥之处，因此，敬请各位读者不吝赐教，以便作者不断提高，提高写作水平。

内容概要

本书结合C++面向对象程序设计的特点，构建了数据结构与算法，对所有算法都在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio开发环境中进行了严格的测试，作者教学网站（http://cs.scu.edu.cn/~youhongyue）提供了大量的教学支持内容。同时本书配有《数据结构与算法（C++版）实验和课程设计教程》 (ISBN 978-7-302-17503-2）供读者学习参考。　　本书共分11章，第1章是基础知识，介绍了基本概念及其术语，并讨论了实用程序软件包；第2章引入线性表；第3章介绍了栈和队列，用栈实现了表达式求值；第4章介绍串，详细讨论了串的存储结构与模式匹配算法；第5章介绍数组和广义表，首次提出了广义表的使用空间表存储结构；第6章介绍了树结构，应用哈夫曼编码实现了压缩软件；第7章介绍图结构，实现了图的常用存结构，讨论了图的相关应用，并实现了相应算法；第8章介绍查找，讨论了静态查找表、动态查找表与散列表，实现了所有算法；第9章介绍排序，以简洁方式实现各种排序算法；第10章介绍了文件，讨论了各种常用文件结构；第11章介绍了算法设计技术、分析技术与可计算问题。　　通过本书的学习，不但能迅速提高数据结构与算法的水平，同时还能提高C++程序设计的能力，经过适当的选择，本书能作为高等院校计算机及相关专业“数据结构”、“数据结构与算法”、“数据结构与算法分析”和“数据结构与算法设计”等课程的教材，也可供其他从事软件开发工作的读者参考。

书籍目录

第1章 绪论　1.1 数据结构的概念和学习数据结构的必要性　1.2 数据结构的基本概念　1.3 抽象数据类型及其实现　1.4 算法和算法分析?1.5 实用程序软件包　1.6 实例研究　1.7 深入学习导读　习题1　上机实验题1第2章 线性表　2.1 线性表的逻辑结构　2.2 线性表的顺序存储结构　2.3 线性表的链式存储结构　2.4 实例研究　2.5 深入学习导读　习题2　上机实验题2第3章 栈和队列　3.1 栈　3.2 队列?3.3 优先队列　3.4 实例研究　3.5 深入学习导读　习题3　上机实验题3第4章 串　4.1 串类型的定义　4.2 字符串的实现　4.3 字符串模式匹配算法?4.4 实例研究　4.5 深入学习导读　习题4　上机实验题4第5章 数组和广义表第6章 树和二叉树第7章 图第8章 查找第9章 排序第10章 文件第11章 算法设计与分析附录A 调和级数附录B 泊松分布附录C 配套的软件包附录D 课程设计项目附录E 实验报告格式附录F 课程设计报告格式参考文献

章节摘录

可能有人认为，随着计算机的功能越来越强大和运行速度越来越快，程序运行效率已变得越来越不重要了。然而，计算机功能越强大，人们就越要尝试解决更加复杂的问题，而更复杂的问题需要更大的计算量，这使得对程序的运行效率有更高的要求，工作越复杂越偏离人们的日常经验，使得从事软件开发的人必须学习和具备彻底理解隐藏在程序设计后面的一般原理——数据结构和算法。从本质上讲，数据结构与算法的原理和方法独立于具体描述语言，然而只能使用具体的某种计算机语言才能在计算机上实现。本书采用目前普遍使用的C++程序设计语言来描述各种数据结构与算法，假设读者具有程序设计基础，了解C++的基本结构和语法。为了、使读者更好理解，本章将对C++的基本结构和语法进行介绍。1.1 数据结构的概念和学习数据结构的必要性对于数值计算问题的解决方法，主要是用数学方程建立数学模型，例如天气预报的数学模型为二阶椭圆偏微分方程；预测人口增长的数学模型为常微分方程。求解这些数学模型的方法是计算数学研究的范畴，例如采用差分算法、有限元算法和无限元算法等。对于非数值计算问题，主要采用数据结构的方法建立数学模型，下面通过实例加以说明。

编辑推荐

通过《数据结构与算法(C++版)》的学习，不但能迅速提高数据结构与算法的水平，同时还能提高C++程序设计的能力，经过适当的选择，《数据结构与算法(C++版)》能作为高等院校计算机及相关专业“数据结构”、“数据结构与算法”、“数据结构与算法分析”和“数据结构与算法设计”等课程的教材，也可供其他从事软件开发工作的读者参考。

用户评论 (总计14条)

•   C++版的数据结构正合适
•   是一本很好的数据结构图书
•   包装很好，对打算从事软件游戏开发的有些基础的同学我觉得不错，尤其是那本C++编程思想，就是我想要的
•   同学推荐的，确实很好，特别喜欢。
•   C++版本的数据结构教材，内容很不错。
•   配上这本书的原版教材，然后和实验一起，超棒。
•   书有点脏，看起来比较旧
•   讲解的东西比我见过的其他任一本国内的数据结构教材都详细
•   买一年了还没看 哈哈哈
•   内容非常丰富，附带的代码非常齐全，在国内很少见这么认真的作者，难得啊，极力推荐
•   我们班就用的这本教材，此书内容丰富，算法新颖，在书中不少地方都有作者的独特见解，所有算法都用5种C++编写了测试程序进行了测试，在当前社会中作者能没有浮躁的心态而安心写作真的难能可贵。
•   内容错误太多，对应的网站上有相应的勘误表；如果自信Ｃ++学得好，值得看一看，对错误的认识会提高。
•   讲解的很详细，内容很充实
•   感觉还可以，但是整体太细了，有些地方和其他书写的不一样