本书主要讲解了C、C++常见算法的算法思想和使用。其中包括排序算法、查找算法、迭代算法、递推算法、递归算法、枚举算法、贪心算法、回溯算法、矩阵算法。本书内容全面、讲解详细、配合图表重难点突出、代码完整，有分明的层次架构。可以作为计算机专业学生、教师、工程技术人员的参考用书、案头必备书，方便查阅。

终于完成本书，稍微可以放松下了。
每次写书实际花费的时间远远超过计划的时间，虽然花费很多时间去修改、完善，但对于书中文字的表述、例子的选取、讲解及算法的实现总感觉还不够满意，也许这不是一次能达到的，只能期待下一次改版再做修订。
在编写本书的过程中，也是我重新学习的过程，特别是在调试程序上花费了不少时间，但是我感觉每一次都有很大收获，因为我在调试程序的过程中发现了一些错误，这些错误之前我并没有遇到过，并且对算法有了更深一步的理解。
在写完《最新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语句结合起来使用，即可接受一个字符串，这个字符串也可以包含空格，假设以回车符作为结束，代码如下：
while((ch=getchar())!=’\n’)
{
str[i++]=ch;
}
这样就巧妙地解决了上面的问题。
本书中，特别是在数据结构部分，我们把基本运算单独放在一个.h文件中，以便对代码进行重用，每一章的算法调用基本比较模式化，经常会使用一些比如输入或输出的功能，这时即可把这些比较常用的功能写成一个函数，避免重复编码，这就是软件工程的思想，今后大家开发程序也要养成这个习惯。
◎程序调试
在写作本书的过程中，不断有读者让我帮忙看程序中哪里出了错误，我在调试时也会遇到这样或那样的错误，我想有不少接触C语言不久的朋友们也有类似的困惑：如何能快速找出程序的错误位置和原因，以便让程序正确运行。针对程序调试问题，我觉得首先选择一个比较合适的开发工具，比如VC++就是一个很成熟的开发工具，对于语法错误，编译器会直接定位错误行，并给出相应的错误提示。对于逻辑错误和运行时错误，需要对可能出问题的代码段设置断点，跟踪查看变量在程序运行过程中的变化情况，针对输入的数据进行分析，这样就能很快找出问题的所在。
虽然本书为所有的案例提供了完整的代码，但是还是建议读者能亲自在计算机上敲代码，在敲代码的过程中去体会算法设计思想，也许会不小心输入错误、也许会为一个小小错误苦恼半天，经过多次检查和艰难调试，终于找到错误的原因并且解决，直到程序正常运行。这个过程也是每个成功者必经之路，只有经历了痛苦、挣扎、喜悦的反复过程，你才可能成为一名经验丰富的C/C++程序员或合格的计算机教师。计算机是一门科学，也是一门技术，算法思想虽然很重要，但再伟大的算法也需要去验证，只有验证了才知道是否可行，在验证的过程中才能发现问题，这就像一个伟大的数学家提出一个定理或猜想，也需要去证明这个定理的正确性或验证猜想的正确性。
如果大家看完本书，感觉你有所收获，那我这么长时间的辛苦也有了回报，也达到写作本书的目的。
◎应该感谢的人
首先，应该感谢我的导师华庆一教授和张蕾教授。在华教授的引领下，我迈入了人机交互的大门，华教授不仅在科研上给予我耐心的指导，还在生活上给予我无微不至的关怀。华教授对科研工作的严谨态度深深地感染了我，他深厚的计算机理论知识和娴熟的技术水平折服了我，他对科研事业孜孜不倦的精神影响和鼓舞了我，促使我不敢懈怠，对待任何事情不能马虎，也让我的学习能力和认识水平有了很大提高，为本书的编写奠定了良好的理论与技术基础。
其次，还应该感谢耿国华教授，耿教授虽是国家级教学名师，但是对待学生一向平易近人，没有任何架子，她对青年人的发展给予了许多无私的帮助和支持，她在数据结构和算法领域有很深的造诣，她对我在算法和数据结构方面的学习给予了很大的启发。
最后，特别要感谢我的家人，他们是我事业和学习上的坚强后盾，正是他们的默默付出与鼓励，我才能顺利完成本书。
在本书出版的过程中，许多热心的读者提出了改进意见，特别是puppypyb（网名）很认真地提供具体的修改意见，感谢中国科学院大学的胡英鹏、中国科学技术大学的王启、华中科技大学的杨梨花、西安电子科技大学的杜坚、西安交通大学的郝昊天、华东师范大学的牛颖楠、南京航空航天大学的韩琦文、南京理工大学的邓裕彬、北京工业大学的潘姝妤、电子科技大学的丁亮、上海海事大学的左伟康、福州大学的李川、湘潭大学的王乾、天津职业技术师范大学的董春妹、桂林电子科技大学的曹礼、郑州大学的张杨，张冬冬、成都理工大学的张良、西华师范大学的刘富腾、衡水学院的杨帅、重庆电子工程职业学院的冯博、湖南女子学院的李奇、湖北汽车工业学院的李兴海、黄淮学院的于景波、九江学院的樊美林、信阳师范学院的周亚林、衡水学院的杨帅、云南大学的袁宏磊、广东技术师范学院欧阳镇、江苏省扬州中学的张佑杰、浙江工业大学的陈文邦、电子科技大学的吕鑫垚、北京邮电大学世纪学院的昂超、兴义民族师范学院的鲜一峰、赶集网的康钦谋、济南趣维网络科技有限公司的刘晓倩、中国航空计算研究所的王泉、中兴通讯公司的杨柯、华为科技有限公司的卢春俊、云南昆船设计研究院的夏翔，还有很多网友也提出了宝贵建议，这里不再一一列举。

陈锐
2016年5月

Chapter 1 线性表 1
1-1 顺序表示的线性表——
顺序表 1
001 合并两个线性表中的元素 6
002 fgetc函数和getc函数 9
003 求两个线性表的差集 12
004 分拆顺序表：左边的元素小于等于0，右边的大于0 14
005 计算两个任何长度的
整数之和 17
1-2 链式表示的线性表之一——
单链表 19
006 求单链表的差集 27
007 合并两个单链表 32
1-3 链式表示的线性表之二——
循环单链表 36
008 分拆循环单链表 36
009 构造三个单循环链表 40
1-4 链式表示的线性表之三——
双向链表 44
010 双向链表的建立与插入
操作 47
011 约瑟夫问题（双向链表） 51
Chapter 2 栈 55
2-1 顺序表示的栈——
顺序栈 55
001 入栈和出栈 58
002 共享栈的入栈和出栈操作 60
003 求C(n,m)的值 65
2-2 链式表示的栈——
链式栈 69
004 进制转换 73
005 括号匹配 75
006 求算术表达式的值 79
007 判断字符串是否中心对称 87
Chapter 3 队列 91
3-1 顺序表示的队列——
顺序队列 91
001 入队和出队 96
002 舞伴配对 100
003 轮渡管理 103
3-2 链式表示的队列——
链式队列 107
004 队列在杨辉三角中的应用 111
005 判断是否为回文 114
Chapter 4 串 119
4-1 顺序表示的串——
顺序串 119
001 串的基本操作 125
002 将浮点型数转换为对应
的字符串 130
003 求最长公共子串 132
004 求等值子串 135
4-2 串的模式匹配 137
005 模式匹配 143
Chapter 5 数组 149
5-1 数组的定义及表示 149
001 查找第k小元素 151
002 将奇数移动到偶数的左边 153
5-2 二维数组（矩阵） 155
003 将矩阵旋转90度 155
004 打印魔方阵 157
005 打印螺旋矩阵 160
006 打印拉丁方阵 162
007 打印蛇形方阵 164
5-3 数组的压缩存储 166
008 上三角阵的压缩存储 169
5-4 稀疏矩阵的压缩存储 172
009 稀疏矩阵的相加 176
Chapter 6 广义表 181
6-1 广义表的定义及头尾
链表表示 181
001 创建广义表 183
6-2 广义表的扩展线性
链表表示 190
002 创建广义表并求其深度
和广度 191
Chapter 7 树 197
7-1 树与二叉树 197
001 根据广义表形式创建
二叉树 207
002 建立二叉树 211
7-2 二叉树的遍历 214
003 先序非递归遍历二叉树 215
004 层次遍历二叉树 219
005 输出树的各条边 221
006 由中序和后序序列构造
二叉树 225
7-3 二叉树的应用 229
007 交换二叉树的左右子树 229
008 判断是否为完全二叉树 233
009 求结点的个数 239
010 求二叉树的高度和宽度 242
011 求根结点到任一结点之间
的路径 246
7-4 哈夫曼树 251
012 构造哈夫曼树 253
Chapter 8 图 259
8-1 图的基本概念 259
001 用邻接矩阵表示法创建
有向图 264
002 利用邻接表创建有向图 267
003 把邻接矩阵转换为邻接表 271
8-2 图的遍历 276
004 判断有向图中是否
存在回路 278
005 深度遍历有向图 281
006 图的广度优先遍历 286
007 判断有向图中是否有根 291
008 求距离顶点v0的最短
长度为k的所有顶点 296
009 判断顶点u和顶点v是否
存在简单路径 301
010 判断图中是否为一棵树 307
Chapter 9 排序算法 313
9-1 插入排序 313
001 直接插入排序 313
002 折半插入排序 316
003 希尔排序 321
9-2 交换排序 324
004 冒泡排序 324
005 快速排序 328
9-3 选择排序 333
006 简单选择排序 333
007 堆排序 338
9-4 归并排序 345
008 归并排序 345
9-5 基数排序 348
009 基数排序 348
Chapter 10 查找算法 357
10-1 基于线性表的查找 357
001 顺序查找 357
002 折半查找 359
003 分块查找 363
10-2 基于树的查找 367
004 二叉排序树的创建和
插入操作 367
10-3 哈希表的查找 372
005 哈希表的构造与查找 372
Chapter 11 递推算法 379
11-1 顺推法 379
001 斐波那契数列（递推法） 379
002 将十进制数转换为
二进制数 382
003 母牛生小牛问题 384
004 杨辉三角 386
11-2 逆推法 388
005 猴子摘桃 388
006 该存多少钱 389
Chapter 12 迭代算法 391
12-1 精确迭代法 391
001 最大公约数与最小
公倍数 391
002 十进制整数转换为
二进制整数 393
003 质因数的分解 394
004 角谷猜想 395
12-2 近似迭代法 397
005 求一个数的平方根 397
006 二分法 398
007 牛顿迭代法 401
008 求定积分 404
Chapter 13 递归算法 409
13-1 简单递归 409
001 求n的阶乘 409
002 斐波那契数列（递归法） 413
003 求n个数中的最大者 415
004 数制转换 416
005 求最大公约数 417
13-2 复杂递归 419
006 颠倒字符串 419
007 和式分解 420
008 台阶问题 423
009 汉诺塔问题 426
010 大牛生小牛问题 429
Chapter 14 枚举算法 431
001 判断n是否能被3、5、7
整除 431
002 百钱买百鸡 434



003 五猴分桃 436
004 打印水仙花数 439
005 填数游戏 440
006 谁在说谎 442
Chapter 15 贪心算法 445
001 找零钱问题 445
002 哈夫曼编码 448
003 加油站问题 454
Chapter 16 回溯算法 457
001 组合问题 457
002 填字游戏 460
003 装箱问题 466
Chapter 17 实用算法 471
001 大小写金额转换 471
002 计算7的34次方 476
003 一年中的第几天 478
004 求算术表达式的值 481
005 一元多项式的乘法 489
006 大整数乘法 496
附录 程序调试 499
参考文献 514

陈锐，高级程序员，西北大学计算机应用技术硕士，中国计算机学会CCF会员。从事数据结构与算法和自然语言处理研究工作。著作有：《零基础学数据结构》、《C语言入门教程》、《C语言从入门到精通》等书。

◎本书特点
（1）结构安排合理。概念讲解通俗易懂，内容安排和案例选取都是先易后难，循序渐进，注重学习知识的连贯性。
（2）注重基础知识的讲解。在数据结构部分首先是对基础知识和概念的介绍，然后给出相应的基本运算算法实现，最后是提供典型案例和考研试题的讲解及算法实现。
（3）涵盖个人学习经验总结。在讲解知识点、分析案例及调试程序时，加入了作者自己学习过程中的经验总结，指出了初学者常犯的错误，避免读者少走弯路。
（4）案例很多都来自全国著名高校（清华大学、哈尔滨工业大学、西北大学、华中科技大学、西安电子科技大学、北京航空航天大学、上海大学）的考研题目，并给出了完整的算法实现。
（5）提供完整代码实现，所有代码均在VC++6.0以上调试通过。