丁展，博士，毕业于浙江大学计算机科学与技术，现任职于金陵科技学院软件工程学院，中国计算机学会会员，著作方向为程序设计、软件开发，曾在人民邮电出版社出版《Visual C++网络通信编程实用案例精选》 《Visual C++游戏开发技术与实例》。从事C/C++教学工作多年，目前是金陵科技学院ACM竞赛指导老师。曾承担两项国家自然科学基金，海量空间数据的连续模型建模技术，点云曲面的数字拓扑与几何的若干基础问题研究。

随着信息技术的迅猛发展，程序设计在各个领域都起到举足轻重的作用。目前大部分高校的计算机、软件及相关专业都开设了各种程序设计语言数据结构课程。然而掌握一门程序设计语言或者了解数据结构知识并不等同于“会编程”。在实际教学中存在大量的只会考试但不会写代码解决问题的学生，这是令人焦虑的现象。

虽然已出版的关于算法设计的书籍比较多，但大都是介绍算法的理论基础。对于实际生活中的各种问题，需要将算法灵活地应用。本书精选了大量综合编程案例，基本上涵盖了当前基础算法领域的热点问题。

本书的特色如下。

一、本书提供大量的综合编程实例，涉及各种基础算法的应用领域。

二、所有的综合编程实例都按照设计思路、相关概念、原理、具体实现进行介绍，读者能够很容易地掌握实例的算法设计思路。

三、本书介绍了图形用户界面(GUI)编程基础，将4个综合编程实例的算法进行可视化，从而让读者理解并掌握算法可视化方法，进一步帮助对算法的理解与调试。

要运行本书中的绝大部分实例，读者只需要安装任何C/C++开发工具，如CodeBlocks、Visual Studio 2015 社区版、Dev C++等。如果要运行4个算法的可视化实例，读者需要安装CodeBlocks或Visual Studio 2015社区版。以上工具均可以免费下载。如果读者的计算机运行的还是VC ++6.0，我们强烈建议您放弃它。因为它的编译器版本太低，不支持C/C++新标准，并且对模板的支持不够。

本书共有8章，内容如下。

第1章字符串。主要介绍字符串拷贝、连接、与数的转换、查找、删除，以及字典比较等各种字符串操作。其后，给出若干字符串处理常见问题的解决方法。本章最后给出综合编程实例：公民数据模拟。

第2章排序和查找。主要介绍桶排序、qsort快速排序、STL中std::sort排序、std::greater用法、二分查找算法、std::find用法，并给出两个综合实例：员工KPI排名与MOOC期终成绩。

第3章栈、链表与队列。主要介绍STL中std::stack、std::list、std::queue与std::deque的用法。对以上数据结构分别给出了若干综合编程实例，如关于栈的火车调度问题、链表的约瑟夫环问题、队列的卡片游戏等。

第4章树与图。树的内容主要包括完全二叉树定义、二叉树遍历、手写二叉树的遍历、二叉树高度计算，以及二叉树删除，其后给出4个关于树的综合编程实例。图内容主要包括图基本操作、图表示方法，最后给出3个关于图的综合编程实例。

第5章递归与分治。主要介绍7个典型的递归与分治问题：汉诺塔、子串组合、数组组合、格子排列、八皇后、循环赛日程安排与棋盘覆盖。

第6章集合与映射。主要介绍STL集合容器std::set、映射容器std::map、多键映射容器std::multimap，以及哈希映射的用法。同时给出集合相似度与哈希冲突解决的综合实例，

第7章Win32 GUI编程基础。主要介绍使用Win32 API开发图形界面程序的基础。在实际工程中，算法的过程或者结果通常都需要可视化，一方面可以用来调试程序，另一方面可以用来展示算法效果。因此本章使用CodeBlocks或者Visual Studio2010及以上版本开发图形界面程序。内容涉及Win32消息基础和图形设备接口GDI。同时给出综合编程实例：简单多边形的创建、绘制、平移与旋转。

第8章介绍4个综合编程课程设计实例。分别是扑克洗牌、二叉树重建可视化、L-System分形树建模，以及迷宫实现。这些实例要求读者能将算法实现和图形界面编程进行结合，从而把最终的算法和交互过程展现出来。

本书由丁展、梁颖红和李广水主编。在编写过程中，我们力求精益求精，但难免存在一些不足之处，如果读者使用本书时遇到问题，可以发送E-mail到dingzh@jit.edu.cn，我们会及时给您回复。

编 者

2018年5月

第1章　字符串处理 1

1．1 字符串基本操作 1

1．1．1　字符串拷贝 1

1．1．2 字符串连接 3

1．1．3 反转字符串 6

1．1．4 大小写转换 8

1．1．5 字符串与数的转换 10

1．1．6 字符串查找 14

1．1．7 删除字符 16

1．1．8 字符串字典比较 17

1．2　字符串处理常见问题 20

1．2．1 居民身份证号的表示 20

1．2．2 std：：string与const char*转换 21

1．2．3 字符串与buffer缓冲 21

1．2．4 设置浮点数精度 22

1．2．5 得到一行输入的字符串 23

1．2．6 统计一行文本中单词个数 24

1．2．7 std：：stream的高速缓冲方法 25

1．3 综合编程实例：公民数据模拟 27

第2章　排序和查找 34

2．1 桶排序（bucket sort） 34

2．2 qsort排序 34

2．2．1 整型数组的qsort 35

2．2．2 浮点型数组的qsort 36

2．2．3 字符型数组的qsort 37

2．2．4 字符串数组的qsort 38

2．2．5 结构类型数组的qsort 40

2．3 std：：sort排序 43

2．3．1 std：：sort基本用法 44

2．3．2 std：：greater基本用法 46

2．3．3 自定义类型排序 46

2．4 二分查找算法 48

2．5 std：：find查找 51

2．6 综合编程实例 52

第3章　栈、链表与队列 64

3．1 栈 64

3．1．1 std：：stack 64

3．1．2 综合编程实例 65

3．2 链表 74

3．2．1 std：：list 75

3．2．2 综合编程实例 77

3．3 队列 80

3．3．1 std：：queue 80

3．3．2 std：：deque 81

3．3．3 综合编程实例：卡片游戏 82

第4章　树与图 84

4．1　二叉树 84

4．1．1 完全二叉树 84

4．1．2 二叉树遍历 85

4．1．3 手写二叉树的遍历 86

4．1．4 二叉树高度计算 87

4．1．5 二叉树删除 88

4．1．6 综合编程实例 88

4．2 图 102

4．2．1 图的基本操作 102

4．2．2 图的表示方法 102

4．2．3 综合编程实例 103

第5章　递归与分治 112

5．1 汉诺塔 112

5．2 子串组合 113

5．3 数组组合 115

5．4 格子排列 118

5．5 八皇后 122

5．6 循环赛日程安排 124

5．7 棋盘覆盖 128

第6章　集合与映射 132

6．1　集合 132

6．1．1 std：：set 132

6．1．2 集合求交 set_intersection 133

6．1．3 集合求并 set_union 135

6．1．4 集合求差 set_difference 136

6．1．5 综合编程实例：集合相似度 137

6．2 映射 139

6．2．1 std：：map 139

6．2．2 std：：multimap 140

6．3 哈希映射 142

6．3．1 常用的哈希函数 142

6．3．2 哈希冲突的处理方法 142

6．3．3 综合编程实例 143

第7章　Win32 GUI编程基础 148

7．1 Win32 GUI 148

7．1．1 CodeBlocks第一个Win32教程 148

7．1．2 Visual Studio 2015第一个Win32 GUI程序 150

7．1．3 代码分析 151

7．2 Win32 消息基础 155

7．2．1 窗口关闭消息WM_CLOSE 155

7．2．2 窗口大小调整消息 WM_SIZE 156

7．2．3 窗口创建消息 WM_CREATE 157

7．2．4 菜单或其他按钮消息 WM_COMMAND 158

7．2．5 鼠标消息 159

7．2．6 绘制消息WM_PAINT 160

7．2．7 键盘消息WM_KEYDOWN 和 WM_KEYUP 161

7．3 综合编程实例：简单多边形的创建、绘制、平移与旋转 162

7．4 Win32 图形设备接口GDI 176

7．4．1 线段和曲线绘制 177

7．4．2 笔、画刷、填充绘制 180

7．4．3 字体和文本 184

7．4．4 光栅操作 186

7．4．5 双缓冲机制 188

第8章　综合编程实例 190

8．1　扑克洗牌 190

8．2 二叉树重建可视化 194

8．3 L-System分形树建模 204

8．4 迷宫问题 218

参考文献 226

丁展、梁颖红、李广水主编的《C\\C++程序设计实用案例教程（高等教育应用型人才计算机类专业规划教材）》主要利用C／C++语言进行综合课程设计学习。书中案例涵盖了字符串处理、排序与查找、栈、链表与队列、树与图、递归与分治、集合与映射，以及Win32GUI编程基础等知识。在本书的最后给出了四个综合课程设计的开发案例，每个案例都提供了完整的源代码，结合书与示例代码，读者可以很容易理解。

本书可以作为应用型本科院校程序设计课程的教材，也可作为软件开发人员的指导用书。