程序设计基础是专门为高等院校理工类特别是新工科学生编写的教材。全书共分3部分：结构化程序设计方法，面向对象程序设计方法，数据结构和算法。本书通过对一些精选问题求解思路和方法的分析，以及针对初学者容易出现错误和困惑的地方提供了大量的提示，帮助读者更好地理解使用计算机解决问题的基本原理和方法、提高他们的计算思维能力、使他们初步具备使用C 程序设计语言解决实际问题的能力 本书面向初学者，不要求读者有相关的概念和计算机高级程序设计语言方面的背景知识。本书还是学堂在线的程序设计基础（上）和程序设计基础（下）MOOC课程使用的教材，同时还配套了《程序设计基础上机实习及习题》。因此，本书适合高等院校理工类、特别是新工科学生使用，也适合结合MOOC课程自主学习的读者使用。

近年来，计算机基础教学内容不断更新，注重学生计算思维能力和应用创新能力的培养；教学方式不断变革，基于MOOC、微课、翻转课堂等多种教学方法和手段相结合。基于此，面向理工类特别是新工科的计算机基础课程的教学需要配合新的教学方式进行重新编写，提供配套的在线资源，以新形态教材方式呈现；同时为方便ＭＯＯＣ／ＳＰＯＣ课程提供以知识点为单位的配套教材以及与本教材配套的《程序设计基础实验与习题集》教材。
本书面向高等院校理工类学生, 针对如何使用计算机求解问题、能够具有主动使用计算机解决生活和学科问题的意识和能力的需求，计算机学科*基础性的问题编写的教材。全书共分3部分：结构化程序设计方法，面向对象程序设计方法，数据结构和算法。除了讲解计算进行基本的概念、方法，还给出了完整的实现代码。几乎每一章还给出了拓展学习的内容，读者可以通过扫面二维码进行进一步的学习和提高。同时在配套教材《程序设计基础上机实习及习题》中还为每一章配套了上机实习习题和课后习题参考答案等内容。

前言
程序设计基础21世纪人类步入信息社会，大数据、人工智能、互联网 、物联网、区块链等已经融入人们日常的生活中，正在影响和改变着人们工作、学习和生活的方式，而这些都离不开计算机。
计算本身是一门学科，它在发展的同时也促进了其他学科的发展。21世纪科学上最重要的、经济上最有前途的研究前沿都有可能通过与计算科学进行学科融合而得到解决。计算机不仅为不同专业提供了解决专业问题的有效方法和手段，而且还提供了一种独特的处理问题的思维方式计算思维。逻辑思维、实证思维和计算思维三大科学思维构成了现代科技创新的三大支柱。计算思维不仅仅属于计算机科学家所特有，它已经成为每个人应该具备的基本能力。因此，在培养学生的解析能力时，不仅要掌握阅读、写作和算术（Reading,wRiting,and aRithmetic3R）能力，还要使学生接触计算的方法和模型，学会计算思维。
众所周知，计算机可以进行数值计算（科学计算）问题的求解，例如解方程(组)、函数求值、概率统计等，用来解决如气象预报、石油探测等问题。更多的时候，人们利用计算机进行非数值计算问题的求解，例如字符、图形、图像、声音、动画等，来解决文字处理、飞机售票、学生信息管理、道路交通管理等问题。对于计算机的处理对象，特别是非数值计算的问题求解，需要研究计算机的操作对象（数据元素）以及它们之间的关系和运算。
人类使用计算机求解实际问题的基本步骤是：首先将实际问题抽象成数学模型，即分析问题，从中抽象出操作的对象和相应的操作，找出这些操作对象之间的关系，并用数学的语言加以描述；其次设计实现这些操作的算法，并编写程序实现相应的算法；最后才是运行程序对实际问题进行求解。如何表示信息和如何处理信息，这正是计算机科学研究的主要问题。人类进行抽象和形式化，就需要学习和掌握常用的计算思维方式。
程序设计方法、数据结构和算法是计算机科学与工程的基础性领域知识，是开发高效计算机程序、解决各领域应用问题的核心。在寻求和实现数学模型的过程中，计算机算法与数据的结构密切相关。学习程序设计方法、数据结构和算法课程，不仅可以使学生掌握计算机基础课程的基本方法，更是训练学生计算思维的有效途径。
本书面向高等院校理工类特别是新工科学生掌握如何使用计算机求解问题、具有主动使用计算机解决生活和学科问题的意识和能力的需求，针对计算机学科最基础性的问题编写的教材。全书共分3部分： ①结构化程序设计方法； ②面向对象程序设计方法； ③基本数据结构和算法。书中除了讲解计算的基本概念、方法，还给出了完整的实现代码。几乎每一章都给出了拓展学习的内容，读者可以通过扫描二维码进一步学习和提高。同时在配套教材《程序设计基础上机实习及习题集》中，还为每一章配套了课程实习课后习题和课后习题参考答案等内容。
全书共16章，主要内容如下。
程序设计基础 前言 第1～6章为结构化程序设计方法。其中：
第1章 如何让计算机进行计算。首先介绍计算思维和程序流程图的基本画法；然后介绍程序设计的基本概念、步骤和方法；最后介绍C 源程序的基本结构和组成元素以及Visual studio 2010集成开发环境。
第2章 计算机如何表示与处理数据。首先介绍二进制数及几种基本数据类型的二进制数据表示方法，包括不同数制数据之间的转换方法，整数、实数、字符和逻辑型数据的二进制表示方法等；然后介绍如何通过C 语言实现这些基本数据类型在计算机中的存储，以及如何对这些基本数据类型的数据进行处理的方法。
第3章 选择与迭代算法。介绍处理问题时的选择算法和迭代算法，以及如何使用C 语言实现选择和迭代算法。
第4章 结构化数据的处理。介绍多记录数据和多属性数据的存储方法，以及如何使用C 语言实现这些数据的存储和处理。
第5章 模块化。介绍模块化的思想，以及如何使用C 语言编写模块化程序。
第6章 数据存储。重点介绍计算机中数据存储的基本原理，以及如何使用C 语言编写程序去操作内存中的数据。
第7～10章为面向对象程序设计方法。其中：
第7章 面向对象方法。介绍面向对象方法的基本概念,以及用C 语言实现面向对象程序设计的基本方法。
第8章 继承与多态。介绍如何使用C 语言来实现面向对象程序设计的两个重要特性继承和多态。
第9章 输入输出流。介绍标准输入输出的基本方法，即输入输出流和文件输入输出流两方面的内容。
第10章 模板。介绍模板的基本概念,以及C 中函数模板和类模板的定义及使用方法等。
第11～16章为基本的数据结构和算法。其中：
第11章 数据结构与算法的基本概念。首先介绍数据结构的基本术语、抽象数据类型、数据结构的存储结构和逻辑结构,然后介绍算法的基本概念和算法分析方法,最后介绍算法设计基本方法与常用的算法设计策略。
第12章 线性表。介绍线性表的逻辑结构，并给出线性表的抽象数据类型；还介绍线性表的顺序存储和链式存储的表示和实现方法等。
第13章 栈和队列。介绍栈的逻辑结构和抽象数据类型，并分别给出栈的顺序存储和链式存储的表示和实现方法；介绍队列的逻辑结构和抽象数据类型，并分别给出队列的顺序存储和链式存储的表示及实现方法等。
第14章 树和二叉树。介绍树的基本概念、二叉树的基本特性；二叉树的顺序表示、链式表示，二叉树的遍历和其他常用操作及其实现方法；哈夫曼树和哈夫曼码等。
第15章 图。介绍图的基本概念；图在计算机中常用的3种表示方法、图的遍历方法及其实现方法；结合具体应用问题，讲解最小生成树和最短路径的问题等。
第16章 算法设计策略及应用实例。介绍分治、贪心、动态规划、回溯和分支限界5种算法设计策略，并给出相应的应用实例。启发读者在遇到实际问题时，使用合理的策略设计出理想的算法。
为了便于练习，本书不仅给出算法的描述，还给出完整的程序代码。读者可直接或稍加改动就可以复用这些代码来解决自己的实际问题。
本书是由南开大学计算机学院公共计算机基础教学部的教师结合多年的教学经验及目前理工类和新工科大学生对计算机基础知识的需要编写的，教材综合考虑了MOOC和SPOC课程知识碎片化的特点，方便教师、学生和其他读者使用。赵宏负责第1～3章、第7章、第10～13章和第16章的编写并统编全书，王恺负责第4～6章、第8章、第9章、第14章和第15章的编写。
在本书的编写过程中，得到了清华大学出版社张瑞庆编审的大力支持,在此表示真诚的感谢！
本书还参考了国内外的一些程序设计方面的开放课程网站和书籍，力求有所突破和创新。由于编者能力和时间的限制，书中难免有不妥之处，恳请同行和读者指正，在此表示真诚谢意！

　编者
2019年4月于南开园 程序设计基础

赵宏 硕士生导师，博士后，南开大学计算机学院副教授，公共计算机基础教学部主任。长期从事公共计算机基础课程的教学和科学研究工作。主讲南开大学计算机基础（理）、数据结构与算法、大数据分析基础-基于R语言等公共计算机基础课程。教学方面主要从事公共计算基础课教学与研究，2013-2017教育部高等学校教学指导委员会委员。科研方面主要进行计算机与环境科学交叉科学领域研究。负责/参加科研项目二十余项，负责/参加国家及学校教学改革项目9项，发表科研/教学论文30余篇，软件著作权6项。主编教材9本，参编教材5本，获得校级教学成果一等奖1项、校级教学成果二等奖4项及其他奖项若干。

王恺，男，1979年生人，南开大学计算机应用技术专业，博士。于2006年留校，任南开大学信息学院教师，副教授。研究方向为图像/视频中的智能信息检索、优化问题建模和求解算法。主主讲南开大学计算机基础（理）、数据结构与算法等公共计算机基础课程。主持科研项目4项，发表EI收录论文10余篇，参与编写教材4本。

目录
程序设计基础第1章如何让计算机进行计算1
1.1计算思维和程序流程图1
1.1.1计算思维1
1.1.2程序流程图2
1.2程序设计的基本概念4
1.2.1用计算机求解问题的过程4
1.2.2程序设计方法6
1.3高级程序设计语言C 7
1.4初识C 程序8
1.4.1简单C 程序实例9
1.4.2C 源程序的组成9
1.4.3C 源程序的组成元素12
1.5集成开发环境VS 201013第2章计算机如何表示与处理数据16
2.1常用数制及不同数制数值之间的转换17
2.1.1数制17
2.1.2不同数制之间的转换18
2.2整数在计算机中的表示20
2.2.1数据的单位20
2.2.2整数的表示方法20
2.3实数在计算机中的表示24
2.4非数值数据在计算机中的表示25
2.4.1字符型数据在计算机中的表示25
2.4.2字符串27
2.4.3逻辑型数据27
2.5C 中的基本数据类型和转义字符27
2.5.1C 的基本数据类型27
2.5.2C 中的转义字符28 程序设计基础 目录 2.6变量和常量29
2.6.1常量29
2.6.2变量30
2.7基本数据的处理31
2.7.1运算符和表达式31
2.7.2算术运算符与算术表达式31
2.7.3赋值运算符与赋值表达式32
2.7.4关系运算符与关系表达式33
2.7.5逻辑运算符与逻辑表达式34
2.7.6基本数据类型之间的转换35
2.8C 中的基本语句38
2.8.1定义/声明语句38
2.8.2表达式语句41
2.8.3复合语句和空语句41
2.8.4输入输出语句42
2.9C 中的几个特殊运算符42
2.9.1 和--42
2.9.2条件运算符43
2.9.3逗号运算符45
2.9.4sizeof运算符45
2.10更多关于C 的运算符和表达式46
2.10.1运算符的优先级和结合性46
2.10.2有副作用的表达式和无副作用的表达式48
2.10.3表达式的求值顺序49第3章选择与迭代算法50
3.1单路选择算法及其C 实现50
3.1.1单路选择问题50
3.1.2用C 的if语句编程解决单路选择问题51
3.2双路选择算法及其C 实现52
3.2.1双路选择问题52
3.2.2用C 提供的if…else语句编程解决双路选择问题53
3.3嵌套选择及其C 实现54
3.4多路选择算法及其C 实现56
3.4.1多路选择问题56
3.4.2用C 提供的switch语句编程解决多路选择问题56
3.5迭代算法及其for语句的实现58
3.5.1迭代算法59
3.5.2用C 提供的for语句实现迭代算法59
3.6迭代算法及其while语句的实现60
3.6.1用C 提供的while语句实现迭代算法60
3.6.2用C 提供的do…while语句实现迭代算法61
3.7迭代嵌套及其C 实现62
3.8迭代与选择嵌套及其C 实现64
3.8.1迭代与选择嵌套及其C 实现64
3.8.2选择与迭代嵌套及其C 实现65
3.9C 中的转向语句65
3.9.1break语句66
3.9.2continue语句66
3.9.3return语句67
3.9.4goto语句67第4章结构化数据的处理69
4.1一维数据及其C 实现69
4.1.1一维数据问题69
4.1.2用C 提供的一维数组存储一维数据71
4.2二维数据及其C 实现73
4.2.1二维数据问题73
4.2.2C 提供的一维数组或二维数组存储二维数据74
4.3字符串及其C 实现77
4.3.1字符串问题77
4.3.2用C 提供的一维数组存储字符串78
4.4多个字符串的处理79
4.4.1多个字符串问题79
4.4.2用C 提供的二维数组存储来多个字符串80
4.5多属性数据及其C 实现81
4.5.1多属性数据问题81
4.5.2用C 提供的结构体存储多属性数据81
4.6一组多属性数据的处理84
4.6.1一组多属性数据的问题84
4.6.2使用结构体数组对一组多属性数据进行存储和处理84
4.7C 中的枚举数据类型85
4.7.1枚举类型的定义85
4.7.2枚举变量的定义86
4.7.3枚举变量的使用86
4.8数组的应用选择排序87
4.8.1选择排序算法87
4.8.2用C 实现选择排序算法88第5章模块化90
5.1模块化及其C 实现90
5.1.1采用模块化思想处理问题91
5.1.2用C 实现结构化程序设计91
5.1.3函数的调用机制及内联函数94
5.1.4调用库函数95
5.2递归算法及其C 实现95
5.2.1递归算法95
5.2.2递归算法实例96
5.3默认形参值98
5.3.1指定默认形参值的位置98
5.3.2默认形参值的指定顺序99
5.4函数重载99
5.5编译预处理101
5.5.1文件包含101
5.5.2宏定义102
5.5.3条件编译103
5.6多文件结构105
5.6.1头文件105
5.6.2源文件106
5.6.3多文件结构程序实例106
5.6.4避免头文件被重复包含108
5.7变量和函数的作用域与生存期109
5.7.1全局变量的作用域与生存期109
5.7.2局部变量的作用域与生存期110
5.7.3函数的作用域112
5.8模块化应用实例二分查找法114
5.8.1二分查找法114
5.8.2二分查找法应用实例115第6章数据存储117
6.1数据存储的基本原理117
6.2地址与C 中的指针118
6.2.1指针变量的定义119
6.2.2指针变量的初始化119
6.2.3使用指针访问内存中的数据120
6.3指针与数组123
6.3.1数组在内存中的存储方式123
6.3.2使用指针操作数组124
6.3.3数组名与指针变量的区别125
6.3.4指向行的指针变量126
6.4指针与字符串127
6.5动态使用内存空间129
6.6二级指针133
6.7指针与函数134
6.7.1指针作为函数参数134
6.7.2指针作为函数返回值140
6.8引用与函数141
6.8.1引用的概念和声明141
6.8.2函数的传值调用142
6.8.3函数的引用调用143
6.8.4返回引用的函数144第7章面向对象方法146
7.1面向对象方法的基本概念147
7.2C 中的类和对象150
7.2.1类的定义150
7.2.2构造函数152
7.2.3对象的定义和对象的访问153
7.3类成员的访问控制156
7.4析构函数158
7.5拷贝构造函数160
7.6类声明与实现的分离162
7.7类的静态成员164
7.7.1静态数据成员164
7.7.2静态成员函数166
7.8类的常量成员168
7.8.1常量数据成员168
7.8.2常量成员函数168
7.9this指针169
7.10类的友元170
7.11类的对象成员174
7.12自定义类的运算符重载177
7.12.1类成员函数形式的运算符重载177
7.12.2类友元形式的运算符重载179第8章继承与多态184
8.1继承184
8.1.1继承概述184
8.1.2派生类的定义185
8.1.3访问控制方式和派生类的继承方式187
8.1.4成员函数重定义189
8.1.5派生类的构造函数和析构函数190
8.1.6多继承192
8.2多态199
8.2.1类型兼容和多态性的概念199
8.2.2多态性的实现202
8.3抽象类204
8.3.1抽象类的作用204
8.3.2抽象类的实现205第9章输入输出流207
9.1输入输出流概述207
9.2cout和cin对象以及插入和提取运算符208
9.2.1标准流对象208
9.2.2>>和<<运算符与标准输入输出208
9.3使用成员函数进行标准输出和输入210
9.3.1使用put()函数进行标准输出210
9.3.2使用get()函数进行标准输入210
9.3.3getline()函数进行标准输入212
9.4文件流对象以及插入和提取运算符213
9.4.1文件流对象213
9.4.2<<和>>运算符与文件输入输出216
9.5使用成员函数进行文件的输出和输入217
9.5.1使用put()函数进行文本文件输出217
9.5.2使用get()函数进行文本文件输入218
9.5.3使用getline()函数进行文本文件输入218
9.6按数据块进行输出和输入220
9.6.1使用write()函数按数据块进行输出220
9.6.2使用read()函数按数据块进行输入221
9.7文件的随机读写225
9.8自定义数据类型的输入输出227第10章模板231
10.1函数模板231
10.1.1函数模板的定义232
10.1.2函数模板的使用232
10.2类模板234
10.2.1类模板的定义235
10.2.2类模板的使用236
10.2.3类模板的静态成员和友元238第11章数据结构和算法的基本概念240
11.1数据结构的基本概念240
11.1.1基本术语241
11.1.2数据的逻辑结构242
11.1.3数据的存储结构244
11.1.4数据的操作245
11.2抽象数据类型246
11.3算法设计与算法分析基础248
11.3.1算法的基本概念248
11.3.2算法分析249
11.3.3算法分析实例254
11.4算法设计基本方法与策略基础256
11.4.1算法设计的方法256
11.4.2算法设计策略260第12章线性表269
12.1线性表及其抽象数据类型269
12.1.1线性表的基本概念270
12.1.2线性表的抽象数据类型270
12.2线性表的顺序存储结构及其实现271
12.2.1线性表的顺序表示271
12.2.2顺序表的实现273
12.2.3顺序表代码复用实例277
12.3线性表的链式表示方法及实现281
12.3.1链式存储结构281
12.3.2单向链表及其基本操作281
12.3.3单向链表代码复用实例288
12.3.4线性表的顺序存储与链式存储的比较291
12.3.5循环链表及其基本操作292
12.3.6双向链表及其基本操作294第13章栈和队列297
13.1栈的基本概念297
13.1.1栈的基本概念297
13.1.2栈的抽象数据类型298
13.2栈的表示及实现299
13.2.1栈的顺序表示及实现299
13.2.2顺序栈代码复用实例303
13.2.3栈的链式表示及实现304
13.3队列的基本概念307
13.3.1队列的基本概念307
13.3.2队列的抽象数据类型308
13.4队列的表示及实现308
13.4.1队列的顺序表示及实现309
13.4.2循环队列代码复用实例313
13.4.3队列的链式表示及实现315第14章树和二叉树319
14.1树的基本概念319
14.1.1树的定义321
14.1.2树的表示形式321
14.1.3树的基本术语322
14.2二叉树及其基本性质324
14.2.1二叉树的定义324
14.2.2二叉树的基本性质325
14.3二叉树的抽象数据类型和表示方式327
14.3.1二叉树的顺序表示及实现328
14.3.2二叉树的链式表示及实现333
14.4二叉树的遍历及常用操作339
14.4.1二叉树的遍历及其实现339
14.4.2二叉树其他常用操作的实现345
14.5二叉排序树350
14.5.1二叉排序树的定义350
14.5.2二叉排序树的生成350
14.5.3二叉排序树的查找353
14.6二叉树排序树应用示例355
14.7哈夫曼树和哈夫曼码356
14.7.1基本术语356
14.7.2哈夫曼树及其构造方法357
14.7.3哈夫曼码及其编解码方法358第15章图360
15.1图的基本概念及特性360
15.2图的抽象数据类型和表示方式364
15.2.1图的抽象数据类型364
15.2.2图的表示法365
15.2.3图的邻接矩阵表示法的实现367
15.3图的遍历370
15.3.1广度优先遍历及其实现371
15.3.2深度优先遍历及其实现373
15.4应用实例376
15.4.1图的应用376
15.4.2用图来描述和求解实际问题377第16章算法设计策略及应用实例380
16.1分治策略380
16.1.1分治策略概述380
16.1.2分治策略的算法设计步骤和程序模式381
16.1.3分治策略应用实例382
16.2贪心策略385
16.2.1最优化问题与最优化原理385
16.2.2贪心策略概述385
16.2.3贪心策略的算法设计步骤及程序模式386
16.2.4贪心策略应用实例387
16.3动态规划策略389
16.3.1动态规划策略概述390
16.3.2动态规划策略的相关概念392
16.3.3动态规划策略算法设计步骤及程序模式394
16.3.4动态规划策略应用实例395
16.4回溯策略398
16.4.1回溯策略概述398
16.4.2回溯策略算法设计步骤及程序模式399
16.4.3回溯策略应用实例400
16.5分支限界策略401
16.5.1堆401
16.5.2分支限界策略概述404
16.5.3分支限界策略算法设计步骤及程序模式405
16.5.4分支限界策略应用实例405