前言

程序设计基础21世纪人类步入信息社会，大数据、人工智能、互联网+、物联网、区块链等已经融入人们日常的生活中，正在影响和改变着人们工作、学习和生活的方式，而这些都离不开计算机。

“计算”本身是一门学科，它在发展的同时也促进了其他学科的发展。21世纪科学上最重要的、经济上最有前途的研究前沿都有可能通过与计算科学进行学科融合而得到解决。计算机不仅为不同专业提供了解决专业问题的有效方法和手段，而且还提供了一种独特的处理问题的思维方式——计算思维。逻辑思维、实证思维和计算思维三大科学思维构成了现代科技创新的三大支柱。计算思维不仅仅属于计算机科学家所特有，它已经成为每个人应该具备的基本能力。因此，在培养学生的解析能力时，不仅要掌握阅读、写作和算术（Reading,wRiting,and aRithmetic——3R）能力，还要使学生接触计算的方法和模型，学会计算思维。

众所周知，计算机可以进行数值计算（科学计算）问题的求解，例如解方程(组)、函数求值、概率统计等，用来解决如气象预报、石油探测等问题。更多的时候，人们利用计算机进行非数值计算问题的求解，例如字符、图形、图像、声音、动画等，来解决文字处理、飞机售票、学生信息管理、道路交通管理等问题。对于计算机的处理对象，特别是非数值计算的问题求解，需要研究计算机的操作对象（数据元素）以及它们之间的关系和运算。

人类使用计算机求解实际问题的基本步骤是：首先将实际问题抽象成数学模型，即分析问题，从中抽象出操作的对象和相应的操作，找出这些操作对象之间的关系，并用数学的语言加以描述；其次设计实现这些操作的算法，并编写程序实现相应的算法；最后才是运行程序对实际问题进行求解。如何表示信息和如何处理信息，这正是计算机科学研究的主要问题。人类进行抽象和形式化，就需要学习和掌握常用的计算思维方式。

程序设计方法、数据结构和算法是计算机科学与工程的基础性领域知识，是开发高效计算机程序、解决各领域应用问题的核心。在寻求和实现数学模型的过程中，计算机算法与数据的结构密切相关。学习程序设计方法、数据结构和算法课程，不仅可以使学生掌握计算机基础课程的基本方法，更是训练学生计算思维的有效途径。

本书面向高等院校理工类特别是新工科学生掌握如何使用计算机求解问题、具有主动使用计算机解决生活和学科问题的意识和能力的需求，针对计算机学科最基础性的问题编写的教材。全书共分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月于南开园 程序设计基础