前言

Foreword

终于完成本书，稍微可以放松下了。

每次写书实际花费的时间远远超过计划的时间，虽然花费很多时间去修改、完善，但对于书中文字的表述、例子的选取、讲解及算法的实现总感觉还不够满意，也许这不是一次能达到的，只能期待下一次改版再做修订。

在编写本书的过程中，也是我重新学习的过程，特别是在调试程序上花费了不少时间，但是我感觉每一次都有很大收获，因为我在调试程序的过程中发现了一些错误，这些错误之前我并没有遇到过，并且对算法有了更深一步的理解。

在写完《最新C/C++函数与算法速查速用大辞典》（书号为978-7-113-20740-3）之后，觉得似乎还不够一个体系，应该有一个数据结构与算法方面的类似辞典或手册类的书，于是我就与出版社编辑商量这个想法，决定完成本书。

最初《C/C++函数与算法速查手册》自2012年1月首次出版以来，得到众多读者的喜欢和好评，有来自各个院校的教师和学生，还有从事软件开发的程序员，更有一些热心的读者通过电子邮件或QQ等方式给其提出了宝贵意见，指出了书中的不足之处，期待以后进行改进。有这么多热心读者的关注，我感到非常开心，在此向所有关注的朋友们说声谢谢！

为满足读者朋友的需求，本书不仅讲解了数据结构和算法的基础知识，还融合了大量的数据结构和算法方面的典型例子，这些算法都经过精心调试运行，保证算法的正确性。调试程序是一件花费时间的事情，但是只有自己亲自动手调试，才能深刻理解算法思想，发现错误和不足，在调试程序的过程中，自身水平也得到了提高。因此，希望大家能多动手，亲自上机调试程序，哪怕是把程序敲一遍，也会比不动手效果好。

本书由西北大学的陈锐、华庆一、耿国华、姬翔和西安科技大学的李洪安编著，南阳理工学院的赵娟、辽源职业技术学院的王慧博，西北大学的吴昊参与编著。

由于时间仓促，加上本人水平有限，书中一定会存在一些不足和错误，希望读者朋友通过邮箱nwuchenrui@126.com、huaqy@nwu.edu.cn与我们联系，也可以通过QQ群（515119018）沟通交流。祝愿各位在阅读本书的过程中有一个愉快的旅程。

◎本书内容

本书涵盖数据结构和算法等内容，是一本计算机专业人士的案头必备工具书，适合从事C/C++的程序员和科研人员作为词典进行查阅，也可以作为数据结构和算法初学者的参考用书。

本书分数据结构和算法两部分，其中数据结构涵盖数据线性表、栈、队列、串、数组和广义表、树、图等内容，算法部分涵盖排序、查找、迭代、递推、枚举、递归、贪心、分治、实用算法等内容。

本书选取的案例具有代表性、趣味性和实用性。数据结构除了注重基础知识的讲解，给出了基本运算的实现，案例大部分来自著名高校的考研题目，代表性强，内容和案例结合性强，注重理论与实践相结合。算法部分不少案例极具趣味性，例如，“求n个数中的最大者”、“和式分解”、“大牛生小牛问题”巧妙利用递归来实现。在算法案例的选取上，还注重实用性，尽量将案例与实际工作生活结合，例如，加油站问题、找零钱问题，大小写金额转换。本书案例丰富，以上特点不仅涵盖了数据结构和算法的各个知识点，还能增加学习的积极性和趣味性。

本书最后提供了一个关于如何用VC++6.0调试程序的案例剖析，希望对读者有所帮助。

◎本书特点

（1）结构安排合理。概念讲解通俗易懂，内容安排和案例选取都是先易后难，循序渐进，注重学习知识的连贯性。

（2）注重基础知识的讲解。在数据结构部分首先是对基础知识和概念的介绍，然后给出相应的基本运算算法实现，最后是提供典型案例和考研试题的讲解及算法实现。

（3）涵盖个人学习经验总结。在讲解知识点、分析案例及调试程序时，加入了作者自己学习过程中的经验总结，指出了初学者常犯的错误，避免读者少走弯路。

（4）案例很多都来自全国著名高校（清华大学、哈尔滨工业大学、西北大学、华中科技大学、西安电子科技大学、北京航空航天大学、上海大学）的考研题目，并给出了完整的算法实现。

（5）提供完整代码实现，所有代码均在VC++6.0以上调试通过。

◎如何使用本书

本书中涵盖大量关于数据结构和算法中的线性表、栈、队列、串、数组和广义表、树、图等基本运算和典型算法实现代码，读者朋友们在使用本书的过程中，若需要用到哪些功能，可以直接调用，不需要另外重新编写代码。但是这些已经实现的代码资源意在帮助大家学习和理解，要想真正学好数据结构与算法，需要大家尽量自己去实现，或者至少要阅读理解每段代码的功能。

本书有基本概念和相关知识点的讲解，读者朋友们可以将这本书作为一本教材从头到尾阅读；本书涵盖案例丰富、典型，有代表性，也可以作为一本工具书，需要时查阅。

本书中的算法都是使用C/C++实现，但是并不涉及面向对象知识，仅仅是考虑到输入和输出书写方便，有的代码只是用cin代替了scanf函数，cout代替了printf函数。

◎如何学好数据结构与算法

经常有读者问我在看关于数据结构部分时，为什么在线性表或栈的初始化部分会用二级指针，而在其他基本运算用一级指针，我想也有不少朋友会有这个疑惑，这说明有的读者还是比较细心的，但是也表明大家对指针的用法还是不十分清楚，这里用二级指针的目的是为了返回指针的值，所以要用二级指针。

另外，需要读者注意：在学习数据结构和算法之前，读者最好熟练掌握C语言，起码应该熟悉C语言的语法，在学习数据结构和算法的过程中也可以提高C语言水平。

发现问题是好事情，我们在学习的过程中，要不断地尝试，去实践，书上也有错误，有疑惑就要去验证，俗话说“尽信书则不如无书”，到底是书上的对还是你的判断正确，只有自己去上机调试，才知道到底哪个正确。

在看书的过程中，不要做空头理论家，只看不动手。对难以理解的算法，特别是递归、树和图的算法，可以跟着程序在纸上画一遍，不要怕麻烦，觉得这是浪费时间。在学习数据结构与算法的过程中，不能偷懒，除了理解算法思想外，还要抽时间尽量在计算机上运行，因为每个算法最终是要实现的，需要在计算机上运行起来的。学数据结构与算法的目的有两个：一是学会算法设计，这属于理论思想层次；二是要用C/C++/Java等语言实现，正确运行出算法结果。你设计的算法正确与否，不是靠想象，是需要经过编译器运行检验的。任何一个人，即使非常善于设计算法，他也不能保证写出的程序不需要修改直接在计算机上运行。因此，编写出算法然后在计算机上运行是非常重要的，只有这样才能真正学好数据结构和算法。

◎关于开发

在写作本书和之前学习数据结构与算法的过程中，我也与大家一样，会经常遇到这样或那样的困惑，只是现在越来越少了，这是因为接触多了，每遇到一个问题，就想办法试图去解决它，现在想来，其实就C语言、数据结构和算法来说，没有那么复杂。记得当时写本书第四章时，需要通过键盘接受输入两个字符串，但是直接使用C提供的gets函数或C++的cin输入流，都会遇到很莫名其妙的问题，就是当输入一个字符串完毕后回车，就会出现跳过第二个输入提示，有时是因为一个字符串中包含了空格，有时是因为连续用几个gets函数的原因，导致直接使用gets函数或cin都不行，可以尝试使用最原始的getchar函数，把它与while语句结合起来使用，即可接受一个字符串，这个字符串也可以包含空格，假设以回车符作为结束，代码如下：

这样就巧妙地解决了上面的问题。

本书中，特别是在数据结构部分，我们把基本运算单独放在一个.h文件中，以便对代码进行重用，每一章的算法调用基本比较模式化，经常会使用一些比如输入或输出的功能，这时即可把这些比较常用的功能写成一个函数，避免重复编码，这就是软件工程的思想，今后大家开发程序也要养成这个习惯。

◎程序调试

在写作本书的过程中，不断有读者让我帮忙看程序中哪里出了错误，我在调试时也会遇到这样或那样的错误，我想有不少接触C语言不久的朋友们也有类似的困惑：如何能快速找出程序的错误位置和原因，以便让程序正确运行。针对程序调试问题，我觉得首先选择一个比较合适的开发工具，比如VC++就是一个很成熟的开发工具，对于语法错误，编译器会直接定位错误行，并给出相应的错误提示。对于逻辑错误和运行时错误，需要对可能出问题的代码段设置断点，跟踪查看变量在程序运行过程中的变化情况，针对输入的数据进行分析，这样就能很快找出问题的所在。

虽然本书为所有的案例提供了完整的代码，但是还是建议读者能亲自在计算机上敲代码，在敲代码的过程中去体会算法设计思想，也许会不小心输入错误、也许会为一个小小错误苦恼半天，经过多次检查和艰难调试，终于找到错误的原因并且解决，直到程序正常运行。这个过程也是每个成功者必经之路，只有经历了痛苦、挣扎、喜悦的反复过程，你才可能成为一名经验丰富的C/C++程序员或合格的计算机教师。计算机是一门科学，也是一门技术，算法思想虽然很重要，但再伟大的算法也需要去验证，只有验证了才知道是否可行，在验证的过程中才能发现问题，这就像一个伟大的数学家提出一个定理或猜想，也需要去证明这个定理的正确性或验证猜想的正确性。

如果大家看完本书，感觉你有所收获，那我这么长时间的辛苦也有了回报，也达到写作本书的目的。

◎应该感谢的人

首先，应该感谢我的导师华庆一教授和张蕾教授。在华教授的引领下，我迈入了人机交互的大门，华教授不仅在科研上给予我耐心的指导，还在生活上给予我无微不至的关怀。华教授对科研工作的严谨态度深深地感染了我，他深厚的计算机理论知识和娴熟的技术水平折服了我，他对科研事业孜孜不倦的精神影响和鼓舞了我，促使我不敢懈怠，对待任何事情不能马虎，也让我的学习能力和认识水平有了很大提高，为本书的编写奠定了良好的理论与技术基础。

其次，还应该感谢耿国华教授，耿教授虽是国家级教学名师，但是对待学生一向平易近人，没有任何架子，她对青年人的发展给予了许多无私的帮助和支持，她在数据结构和算法领域有很深的造诣，她对我在算法和数据结构方面的学习给予了很大的启发。

最后，特别要感谢我的家人，他们是我事业和学习上的坚强后盾，正是他们的默默付出与鼓励，我才能顺利完成本书。

在本书出版的过程中，许多热心的读者提出了改进意见，特别是puppypyb（网名）很认真地提供具体的修改意见，感谢中国科学院大学的胡英鹏、中国科学技术大学的王启、华中科技大学的杨梨花、西安电子科技大学的杜坚、西安交通大学的郝昊天、华东师范大学的牛颖楠、南京航空航天大学的韩琦文、南京理工大学的邓裕彬、北京工业大学的潘姝妤、电子科技大学的丁亮、上海海事大学的左伟康、福州大学的李川、湘潭大学的王乾、天津职业技术师范大学的董春妹、桂林电子科技大学的曹礼、郑州大学的张杨，张冬冬、成都理工大学的张良、西华师范大学的刘富腾、衡水学院的杨帅、重庆电子工程职业学院的冯博、湖南女子学院的李奇、湖北汽车工业学院的李兴海、黄淮学院的于景波、九江学院的樊美林、信阳师范学院的周亚林、衡水学院的杨帅、云南大学的袁宏磊、广东技术师范学院欧阳镇、江苏省扬州中学的张佑杰、浙江工业大学的陈文邦、电子科技大学的吕鑫垚、北京邮电大学世纪学院的昂超、兴义民族师范学院的鲜一峰、赶集网的康钦谋、济南趣维网络科技有限公司的刘晓倩、中国航空计算研究所的王泉、中兴通讯公司的杨柯、华为科技有限公司的卢春俊、云南昆船设计研究院的夏翔，还有很多网友也提出了宝贵建议，这里不再一一列举。

陈锐

2016年5月