第一章 程序设计基础

1、编辑课件1程序设计基础程序设计基础(上上)主讲：袁宁主讲：袁宁计算机软件教研室计算机软件教研室邮箱地址邮箱地址: ise_2编辑课件2导言程序设计基础的学科地位 程序设计基础是计算机专业基础课，它为以后的面向对象技术的学习以及C可视化软件的学习奠定了基础，同时C语言也是数据结构和操作系统等计算机专业主干课程的上机工具，要求学生充分重视。3编辑课件3导言如何学好程序设计基础（仅供参考）勤学课内、课外；中文、英文 多练 实践是检验真知的唯一标准好问不“知”下问善于思考“学而不思则罔”4编辑课件4教学要求 通过课堂授课与上机实验相结合的方式，使通过课堂授课与上机实验相结合的方式，使学生能够学生能够深

2、刻理解结构化程序设计的思想与方法深刻理解结构化程序设计的思想与方法掌握掌握C C语言的基础知识语言的基础知识能够在计算机上熟练使用能够在计算机上熟练使用C C语言的编辑环境来语言的编辑环境来编写、调试、运行程序编写、调试、运行程序具有一定实践体会和相关的编程能力，能编写具有一定实践体会和相关的编程能力，能编写超过超过10001000行的行的C C语言应用程序语言应用程序 。5编辑课件5主要参考书目谭浩强，谭浩强，C C语言程序设计，清华大学出版社，语言程序设计，清华大学出版社，1999.1999.全国计算机等级考试二级全国计算机等级考试二级C C教材。教材。C语言教学网站: http:/6编辑

3、课件6考核办法课程考核办法：课程考核办法：最终成绩最终成绩=平时成绩平时成绩*30%+期末考试成绩期末考试成绩*70%平时成绩平时成绩=出勤出勤*10%+作业作业*40%+实验实验*50% 7编辑课件7计算机是计算机是20世纪世纪40年代人类的伟大创造。年代人类的伟大创造。当今计算机应用日益普及，它广泛应用于科学计算、过程当今计算机应用日益普及，它广泛应用于科学计算、过程控制、信息传递和数据处理，而且已渗透到办公、教育、控制、信息传递和数据处理，而且已渗透到办公、教育、家庭等许多领域。家庭等许多领域。计算机系统计算机系统能够按人的要求接收和存储信息，能对信息进能够按人的要求接收和存储信息，能对

4、信息进行处理并提供所需结果，其结果（输出信息）取决于所接行处理并提供所需结果，其结果（输出信息）取决于所接收的信息（输入信息）及相应的处理算法。收的信息（输入信息）及相应的处理算法。计算机系统包括计算机系统包括计算机硬件计算机硬件和和计算机软件计算机软件两大部分。两大部分。计算机硬件计算机硬件是借助电、磁、光、机械等原理构成的各种物是借助电、磁、光、机械等原理构成的各种物理部件的组合，是系统赖以工作的实体。理部件的组合，是系统赖以工作的实体。计算机软件计算机软件一般指计算机系统中的程序及其文档，用于指一般指计算机系统中的程序及其文档，用于指挥和管理整个系统按指定的要求进行工作。挥和管理整个系统

5、按指定的要求进行工作。 1.0 计算机简介计算机简介8编辑课件81.0 计算机简介计算机简介计算机硬件组成计算机硬件组成n主机主机n输入设备输入设备: 输入程序和数据，如键盘、鼠标输入程序和数据，如键盘、鼠标n输出设备输出设备: 输出计算结果，如显示器、打印机输出计算结果，如显示器、打印机9编辑课件9输入设备输入设备10编辑课件10输入设备输入设备11编辑课件11输出设备输出设备12编辑课件12外部存贮器外部存贮器( (外存外存) ): :储存各种数据储存各种数据, ,如硬盘、如硬盘、软盘、软盘、U U盘盘存储设备：硬盘和软盘存储设备：硬盘和软盘13编辑课件13存储设备：光盘和优盘存储设备：光

6、盘和优盘14编辑课件141.0 计算机简介计算机简介一、计算机主机的组成一、计算机主机的组成1 1、中央处理器、中央处理器( (CPU)CPU) 运算器运算器 控制器控制器 寄存器组寄存器组对数据进行运算对数据进行运算控制计算机各部分协调工作控制计算机各部分协调工作存放指令和数据等存放指令和数据等15编辑课件151.0 计算机简介计算机简介2 2、存储器、存储器( (内存内存): ): 存放程序代码及数据存放程序代码及数据3 3、主板、主板、声卡、显卡、数据线、电源等声卡、显卡、数据线、电源等16编辑课件1617编辑课件17二、计算机基本结构二、计算机基本结构外部设备外部设备中央处理器中央处理

7、器 (CPU)存储器存储器输入输入/输出输出接口电路接口电路数据总线数据总线控制总线控制总线地址总线地址总线1.0 计算机简介计算机简介18编辑课件18高级语言高级语言编译系统编译系统操作系统操作系统( (Operating System)Operating System): : OSOS是各种软件的核心与基础是各种软件的核心与基础功能功能: : cpucpu管理、存储管理、文件管理、设备管理、作业管理管理、存储管理、文件管理、设备管理、作业管理常用的常用的OS:OS: MS-DOSMS-DOS、WindowsWindows、UnixUnix、LinuxLinux操作系统操作系统用户源程序用户

8、源程序裸机裸机编译系统和高级语言环境编译系统和高级语言环境用户源程序用户源程序1.0 计算机简介计算机简介19编辑课件191.1.1 程序设计语言程序设计语言一、程序的概念一、程序的概念二、计算机软件二、计算机软件程序程序是是计算任务计算任务的的处理对象处理对象和和处理规则处理规则的描述。的描述。计算机软件计算机软件 = = 程序程序 + + 文档文档1. 计算机处理的任务都是计算机处理的任务都是计算任务计算任务。2. 处理对象是处理对象是数据数据。3. 处理规则是指处理规则是指处理的动作和步骤处理的动作和步骤。三、软件语言三、软件语言软件语言是书写计算机软件语言是书写计算机软件软件的语言的语

9、言20编辑课件201.1.1 程序设计语言程序设计语言四、程序设计语言四、程序设计语言程序设计语言是用于程序设计语言是用于书写计算机程序书写计算机程序的语言。的语言。基本成分：基本成分：1. 数据成分：描述程序所涉及的数据数据成分：描述程序所涉及的数据2. 运算成分：描述程序所包含的运算运算成分：描述程序所包含的运算3. 控制成分：表达程序的控制构造控制成分：表达程序的控制构造4. 传输成分：表达程序的数据传输传输成分：表达程序的数据传输判断判断程序设计语言程序设计语言 = 软件语言软件语言21编辑课件211.1.1 程序设计语言程序设计语言五、程序设计语言的发展五、程序设计语言的发展 机器语

10、言机器语言 二进制代码二进制代码表示的计算机表示的计算机能能直接直接识别和识别和执行执行的一种机器指的一种机器指令集合。令集合。 执行速度快，但较难掌握，执行速度快，但较难掌握，不同型号的计算机，其语言也不不同型号的计算机，其语言也不同。同。根据语言与硬件的关联程度，程序设计语言分为：根据语言与硬件的关联程度，程序设计语言分为：低级语言低级语言和和高级语言高级语言发展过程是发展过程是从低级到高级从低级到高级22编辑课件221.1.1 程序设计语言程序设计语言2. 汇编语言汇编语言 用助记符号描述的指令系统。用助记符号描述的指令系统。如如: ADD a ,b 汇编语言汇编语言机器不能直接执行机器

11、不能直接执行, 必须翻译成机器语言，较难掌握。必须翻译成机器语言，较难掌握。汇编语言汇编语言机器语言机器语言编译编译不能直接执行不能直接执行较为简单，一一对应替换较为简单，一一对应替换23编辑课件231.1.2 程序设计程序设计3. 高级语言高级语言 接近于自然语言的计算机程序设计语言。不能直接运行，接近于自然语言的计算机程序设计语言。不能直接运行，需要转换为机器语言。通常有需要转换为机器语言。通常有解释解释和和编译编译两种。两种。 使用较普遍的高级语言：使用较普遍的高级语言：FORTRAIN, ALGOL, BASIC, PASCAL, C, C+, JAVA, Delphi等。等。高级语言

12、高级语言机器语言机器语言解释解释编译编译类似于自然语言类似于自然语言需要专门的编译需要专门的编译器、解释器，过器、解释器，过程较为复杂。程较为复杂。24编辑课件241.1.2 程序设计程序设计三种语言的比较三种语言的比较高级语言高级语言汇编语言汇编语言机器语言机器语言25编辑课件251.1.2 程序设计程序设计六、程序设计的具体步骤：六、程序设计的具体步骤：方案确定：方案确定： 建立问题的数学模型建立问题的数学模型算法描述：描述处理规则算法描述：描述处理规则数据描述：描述处理对象数据描述：描述处理对象编写程序编写程序（编码编码）：转换为程序语言）：转换为程序语言程序测试：检测程序的正确性程序测

13、试：检测程序的正确性注：编写程序只是程序设计的一个步骤，不等于程序设计注：编写程序只是程序设计的一个步骤，不等于程序设计26编辑课件261.1.3 数据结构数据结构数据结构数据结构(Data Structure)：计算机存储、组织数据计算机存储、组织数据的方式。的方式。数据结构一般包括三个方面的内容：数据结构一般包括三个方面的内容：数据之间的数据之间的逻辑关系逻辑关系，也称数据的逻辑结构，也称数据的逻辑结构(Logical Structure)数据元素及其关系在计算机存储器内的表示，称为数据数据元素及其关系在计算机存储器内的表示，称为数据的的存储结构存储结构（Storage Structure

14、）数据的数据的运算运算，即对数据施加的操作。，即对数据施加的操作。 数据结构数据结构 = = 逻辑结构逻辑结构 + + 存储结构存储结构 + + 运算运算27编辑课件271.1.4 算法概述算法概述一、一、 算法的概念及特性算法的概念及特性 1 1、算法的概念、算法的概念 广义上讲，广义上讲，算法就是为解决一个问题而采取的算法就是为解决一个问题而采取的 方法和步骤方法和步骤。 对同一个问题可能有不同的解决方法和步骤，对同一个问题可能有不同的解决方法和步骤，即不同的算法为了快速有效的解决问题，在保证即不同的算法为了快速有效的解决问题，在保证算法正确的基础上，还要考虑算法的质量，选择算法正确的基础

15、上，还要考虑算法的质量，选择较优的算法。（方法较优的算法。（方法简单，运算步骤少，运算快，简单，运算步骤少，运算快，内存开销小的算法内存开销小的算法 ）28编辑课件28数据结构数据结构+算法算法=程序程序对数据的描述对数据的描述对操作的描述对操作的描述2、计算机算法的分类：、计算机算法的分类：(1) 数值运算算法数值运算算法 - 用于求数值解，如求解一个多元方程用于求数值解，如求解一个多元方程(2) 非数值运算算法非数值运算算法 - 多用于管理领域，如图书管理多用于管理领域，如图书管理 著名计算机科学家沃思提出的一个公式：著名计算机科学家沃思提出的一个公式：1.1.4 算法概述算法概述29编辑

16、课件29 有穷性：有穷性：空间有穷空间有穷：一个算法包含有限的操作步骤；：一个算法包含有限的操作步骤；时间有穷时间有穷：算法可以在合理的时间内运行完。：算法可以在合理的时间内运行完。 确切性：算法中的每一个步骤是确定的，确切性：算法中的每一个步骤是确定的，含义是唯一的含义是唯一的 可行性：算法中每一个步骤是可行的。可行性：算法中每一个步骤是可行的。 有有零个零个或多个输入或多个输入 有有一个一个或多个输出或多个输出3、算法的五大特性、算法的五大特性1.1.4 算法概述算法概述30编辑课件30例例1-1：对于给定的有序数列：对于给定的有序数列3，5，11，17，21，23，28，30，32，50

17、，如何查找如何查找30这个数据元素。这个数据元素。1.1.4 算法概述算法概述算法一：将算法一：将30按顺序与给定数列逐一比较直到找到为止。这种按顺序与给定数列逐一比较直到找到为止。这种算法在最坏的情况可能需要比较整个序列。算法在最坏的情况可能需要比较整个序列。算法二：查找过程中采用跳跃式方式查找，即先以有序数列算法二：查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一

18、半。比较，将查找区间缩小一半。31编辑课件31 递推法递推法 递归法递归法 穷举搜索法穷举搜索法 贪婪法贪婪法 分治法分治法 动态规划法动态规划法 迭代法迭代法4、算法设计与分析常用的方法、算法设计与分析常用的方法1.1.4 算法概述算法概述32编辑课件32一、一、 算法的表示方法算法的表示方法常用的算法表示方法：自然语言、常用的算法表示方法：自然语言、流程图、流程图、N-S图、图、伪代码、程序语言等。伪代码、程序语言等。1、自然语言表示法、自然语言表示法 用自然语言描述的算法。用自然语言描述的算法。例例1-2:用自然语言表示求两个数的和用自然语言表示求两个数的和(如如2+3)1.2 算法表示

19、方法算法表示方法Step1:将输入的第一个数将输入的第一个数2存入存入xStep2:将输入的第二个数将输入的第二个数3存入存入yStep3:将将x和和y相加的结果存入相加的结果存入zStep4:输出结果输出结果z通俗易懂，通俗易懂，比较冗余，比较冗余，容易出现歧容易出现歧义义33编辑课件332、流程图表示法、流程图表示法 用图框表示各种操作，用箭头表示算法流程用图框表示各种操作，用箭头表示算法流程 1.2 算法表示方法算法表示方法调用子程序调用子程序双边矩形框双边矩形框循环循环尖头框尖头框流程的起点或终点流程的起点或终点圆弧边框圆弧边框判断判断菱形菱形输入或输出输入或输出平行四边形平行四边形连

20、接点连接点圆形圆形处理功能处理功能矩形矩形流向或路径流向或路径箭头箭头含义含义名称名称符号符号34编辑课件342、流程图表示法、流程图表示法 用图框表示各种操作，用箭头表示算法流程用图框表示各种操作，用箭头表示算法流程 用流程图表示求两个数的和用流程图表示求两个数的和1.2 算法表示方法算法表示方法开始开始Zx+y 结束结束输出输出z输入输入x输入输入y直观形象直观形象, 易于理解易于理解流程线没流程线没有严格限有严格限制。制。35编辑课件35 C语言是一种结构化程序设计语言，结构化程序语言是一种结构化程序设计语言，结构化程序设计主要采用自上而下、逐步细化的方法。设计主要采用自上而下、逐步细化

21、的方法。结构化程结构化程序有三种基本结构：序有三种基本结构：顺序结构顺序结构选择结构选择结构循环结构循环结构ABPAB成立成立不成立不成立不成立不成立AP成立成立AP成立成立不成立不成立“当型当型”循循环环“直到型直到型”循循环环1.2.2 流程图表示法流程图表示法36编辑课件36结束结束输入输入a,b,cab?bc?ac?输出输出c输出输出b输出输出c输出输出a开始开始YNYYNN37编辑课件37即结构化程序设计流程图，提供了描述三种基本逻辑即结构化程序设计流程图，提供了描述三种基本逻辑结构的图形工具，与传统的程序流程图对照描述如下：结构的图形工具，与传统的程序流程图对照描述如下：1、顺序结

22、构、顺序结构A模块模块B模块模块A模块模块B模块模块1.2.3 N-S图表示法图表示法(b) N-S图表示图表示(a) 流程图表示流程图表示38编辑课件382、选择结构（分支结构）、选择结构（分支结构）A模块模块B模块模块判断条件判断条件成立吗？成立吗？判断条件判断条件成立吗？成立吗？成立成立 不成立不成立A模块模块B模块模块1.2.3 N-S图表示法图表示法(b) N-S图表示图表示(a) 流程图表示流程图表示39编辑课件39由分支结构派生出来的多分支结构由分支结构派生出来的多分支结构A1块块判断条件判断条件成立吗？成立吗？A2块块An块块1.2.3 N-S图表示法图表示法(a) 流程图表示

23、流程图表示(b) N-S图表示图表示K=?K1 K2 KnA1块块 A2块块 An块块40编辑课件403、循环结构、循环结构a.当型循环结构：先判断循环条件是否满足，当条件满足，执行当型循环结构：先判断循环条件是否满足，当条件满足，执行一遍循环体，再判断循环条件，仍满足再执行一遍循环体一遍循环体，再判断循环条件，仍满足再执行一遍循环体直直到不满足条件，则退出循环，执行循环体后的下一语句。若第一到不满足条件，则退出循环，执行循环体后的下一语句。若第一次判断条件就不满足，则一次也不执行循环体。次判断条件就不满足，则一次也不执行循环体。循环体循环体循环条件循环条件满足吗？满足吗？不满足不满足满足满足

24、1.2.3 N-S图表示法图表示法(b) N-S图表示图表示(a) 流程图表示流程图表示 循环体循环体循环条件满足吗？循环条件满足吗？41编辑课件41(b) N-S图表示图表示b.直到型循环结构：先执行一遍循环体，再判断循环条件是否满足直到型循环结构：先执行一遍循环体，再判断循环条件是否满足，如不满足再执行一遍循环体，如不满足再执行一遍循环体直到条件满足，则退出循环，执直到条件满足，则退出循环，执行循环体后的下一语句。这种循环结构至少要执行一遍循环体。行循环体后的下一语句。这种循环结构至少要执行一遍循环体。不满足不满足满足满足循环体循环体循环条件循环条件满足吗？满足吗？1.2.3 N-S图表示

25、法图表示法(a) 流程图表示流程图表示 直到循环条件满足为止直到循环条件满足为止循环体循环体42编辑课件422、N-S流程图表示法流程图表示法ABAB成立成立不成立不成立P A当当P成立成立 直到直到P不成立不成立 A 顺序结构顺序结构选择结构选择结构循环结构循环结构“当型当型”循循环环“直到型直到型”循循环环1.2.3 N-S图表示法图表示法43编辑课件43例例 描述求描述求n!的值的算法的值的算法1.2.3 N-S图表示法图表示法44编辑课件44例：输入例：输入10个数，找出其中最大的数，并输出。个数，找出其中最大的数，并输出。step6:step6: 若若i=9imaxxmax，则将，则

26、将x x的值送入的值送入max,max,45编辑课件45输入一个数输入一个数 maxmax1 1 i i输入输入 x x x x max?max?是是否否x x max maxi+1 i+1 i i当当 i = 9i = 9输出输出 maxmax#include void main( ) int x , max , i ; scanf(“%d”, &max); i=1; do scanf(“%d”, &x); if (xmax) max=x; i=i+1; while ( i=9) ; printf(“max=%d” , max) ;46编辑课件461.3 程序设计方法程序设计方法一、一、 结构化程序