第一章程序设计基础.

程序设计基础(上)主讲：袁宁计算机软件教研室邮箱地址:[e-mail]2导言程序设计基础的学科地位程序设计基础是计算机专业基础课，它为以后的面向对象技术的学习以及C可视化软件的学习奠定了基础，同时C语言也是数据结构和操作系统等计算机专业主干课程的上机工具，要求学生充分重视。3导言如何学好程序设计基础（仅供参考）勤学——课内、课外；中文、英文……多练——实践是检验真知的唯一标准好问——不“知”下问善于思考——“学而不思则罔”4教学要求通过课堂授课与上机实验相结合的方式，使学生能够深刻理解结构化程序设计的思想与方法掌握C语言的基础知识能够在计算机上熟练使用C语言的编辑环境来编写、调试、运行程序具有一定实践体会和相关的编程能力，能编写超过1000行的C语言应用程序。5主要参考书目谭浩强，C语言程序设计，清华大学出版社，1999.全国计算机等级考试二级C教材。C语言教学网站:考核办法课程考核办法：最终成绩=平时成绩*30%+期末考试成绩*70%平时成绩=出勤*10%+作业*40%+实验*50%7计算机是20世纪40年代人类的伟大创造。当今计算机应用日益普及，它广泛应用于科学计算、过程控制、信息传递和数据处理，而且已渗透到办公、教育、家庭等许多领域。计算机系统能够按人的要求接收和存储信息，能对信息进行处理并提供所需结果，其结果（输出信息）取决于所接收的信息（输入信息）及相应的处理算法。计算机系统包括计算机硬件和计算机软件两大部分。计算机硬件是借助电、磁、光、机械等原理构成的各种物理部件的组合，是系统赖以工作的实体。计算机软件一般指计算机系统中的程序及其文档，用于指挥和管理整个系统按指定的要求进行工作。1.0计算机简介81.0计算机简介计算机硬件组成主机输入设备:输入程序和数据，如键盘、鼠标输出设备:输出计算结果，如显示器、打印机9输入设备10输入设备11输出设备12外部存贮器(外存):储存各种数据,如硬盘、软盘、U盘存储设备：硬盘和软盘13存储设备：光盘和优盘141.0计算机简介一、计算机主机的组成1、中央处理器(CPU)运算器控制器寄存器组对数据进行运算控制计算机各部分协调工作存放指令和数据等151.0计算机简介2、存储器(内存):存放程序代码及数据3、主板、声卡、显卡、数据线、电源等1617二、计算机基本结构外部设备中央处理器(CPU)存储器输入/输出接口电路数据总线控制总线地址总线1.0计算机简介18高级语言编译系统操作系统(OperatingSystem):OS是各种软件的核心与基础功能:cpu管理、存储管理、文件管理、设备管理、作业管理常用的OS:MS-DOS、Windows、Unix、Linux操作系统用户源程序裸机编译系统和高级语言环境用户源程序1.0计算机简介191.1.1程序设计语言一、程序的概念二、计算机软件程序是计算任务的处理对象和处理规则的描述。计算机软件=程序+文档1.计算机处理的任务都是计算任务。2.处理对象是数据。3.处理规则是指处理的动作和步骤。三、软件语言软件语言是书写计算机软件的语言201.1.1程序设计语言四、程序设计语言程序设计语言是用于书写计算机程序的语言。基本成分：1.数据成分：描述程序所涉及的数据2.运算成分：描述程序所包含的运算3.控制成分：表达程序的控制构造4.传输成分：表达程序的数据传输判断程序设计语言=软件语言211.1.1程序设计语言五、程序设计语言的发展1.机器语言二进制代码表示的计算机能直接识别和执行的一种机器指令集合。执行速度快，但较难掌握，不同型号的计算机，其语言也不同。根据语言与硬件的关联程度，程序设计语言分为：低级语言和高级语言发展过程是从低级到高级221.1.1程序设计语言2.汇编语言用助记符号描述的指令系统。如:ADDa,b汇编语言机器不能直接执行,必须翻译成机器语言，较难掌握。汇编语言机器语言编译不能直接执行较为简单，一一对应替换231.1.2程序设计3.高级语言接近于自然语言的计算机程序设计语言。不能直接运行，需要转换为机器语言。通常有解释和编译两种。使用较普遍的高级语言：FORTRAIN,ALGOL,BASIC,PASCAL,C,C++,JAVA,Delphi等。高级语言机器语言解释编译类似于自然语言需要专门的编译器、解释器，过程较为复杂。241.1.2程序设计三种语言的比较高级语言汇编语言机器语言251.1.2程序设计六、程序设计的具体步骤：1.方案确定：建立问题的数学模型2.算法描述：描述处理规则3.数据描述：描述处理对象4.编写程序（编码）：转换为程序语言5.程序测试：检测程序的正确性注：编写程序只是程序设计的一个步骤，不等于程序设计261.1.3数据结构数据结构(DataStructure)：计算机存储、组织数据的方式。数据结构一般包括三个方面的内容：1.数据之间的逻辑关系，也称数据的逻辑结构(LogicalStructure)2.数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）3.数据的运算，即对数据施加的操作。数据结构=逻辑结构+存储结构+运算271.1.4算法概述一、算法的概念及特性1、算法的概念广义上讲，算法就是为解决一个问题而采取的方法和步骤。对同一个问题可能有不同的解决方法和步骤，即不同的算法为了快速有效的解决问题，在保证算法正确的基础上，还要考虑算法的质量，选择较优的算法。（方法简单，运算步骤少，运算快，内存开销小的算法）28数据结构+算法=程序对数据的描述对操作的描述2、计算机算法的分类：(1)数值运算算法----用于求数值解，如求解一个多元方程(2)非数值运算算法----多用于管理领域，如图书管理著名计算机科学家沃思提出的一个公式：1.1.4算法概述29有穷性：空间有穷：一个算法包含有限的操作步骤；时间有穷：算法可以在合理的时间内运行完。确切性：算法中的每一个步骤是确定的，含义是唯一的可行性：算法中每一个步骤是可行的。有零个或多个输入有一个或多个输出3、算法的五大特性1.1.4算法概述30例1-1：对于给定的有序数列{3，5，11，17，21，23，28，30，32，50}，如何查找30这个数据元素。1.1.4算法概述算法一：将30按顺序与给定数列逐一比较直到找到为止。这种算法在最坏的情况可能需要比较整个序列。算法二：查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。31递推法递归法穷举搜索法贪婪法分治法动态规划法迭代法4、算法设计与分析常用的方法1.1.4算法概述32一、算法的表示方法常用的算法表示方法：自然语言、流程图、N-S图、伪代码、程序语言等。1、自然语言表示法用自然语言描述的算法。例1-2:用自然语言表示求两个数的和(如2+3)1.2算法表示方法Step1:将输入的第一个数2存入xStep2:将输入的第二个数3存入yStep3:将x和y相加的结果存入zStep4:输出结果z通俗易懂，比较冗余，容易出现歧义332、流程图表示法用图框表示各种操作，用箭头表示算法流程1.2算法表示方法调用子程序双边矩形框循环尖头框流程的起点或终点圆弧边框判断菱形输入或输出平行四边形连接点圆形处理功能矩形流向或路径箭头含义名称符号342、流程图表示法用图框表示各种操作，用箭头表示算法流程用流程图表示求两个数的和1.2算法表示方法开始Zx+y结束输出z输入x输入y直观形象,易于理解流程线没有严格限制。35C语言是一种结构化程序设计语言，结构化程序设计主要采用自上而下、逐步细化的方法。结构化程序有三种基本结构：①顺序结构②选择结构③循环结构ABPAB成立不成立不成立AP成立AP成立不成立“当型”循环“直到型”循环1.2.2流程图表示法36传统的程序流程图例图结束输入a,b,cab?bc?ac?输出c输出b输出c输出a开始YNYYNN37即结构化程序设计流程图，提供了描述三种基本逻辑结构的图形工具，与传统的程序流程图对照描述如下：1、顺序结构A模块B模块A模块B模块1.2.3N-S图表示法(b)N-S图表示(a)流程图表示382、选择结构（分支结构）A模块B模块判断条件成立吗？判断条件成立吗？成立不成立A模块B模块1.2.3N-S图表示法(b)N-S图表示(a)流程图表示39由分支结构派生出来的多分支结构A1块判断条件成立吗？A2块An块…1.2.3N-S图表示法(a)流程图表示(b)N-S图表示K=?K1K2…KnA1块A2块…An块403、循环结构a.当型循环结构：先判断循环条件是否满足，当条件满足，执行一遍循环体，再判断循环条件，仍满足再执行一遍循环体……直到不满足条件，则退出循环，执行循环体后的下一语句。若第一次判断条件就不满足，则一次也不执行循环体。循环体循环条件满足吗？不满足满足1.2.3N-S图表示法(b)N-S图表示(a)流程图表示循环体循环条件满足吗？41(b)N-S图表示b.直到型循环结构：先执行一遍循环体，再判断循环条件是否满足，如不满足再执行一遍循环体……直到条件满足，则退出循环，执行循环体后的下一语句。这种循环结构至少要执行一遍循环体。不满足满足循环体循环条件满足吗？1.2.3N-S图表示法(a)流程图表示直到循环条件满足为止循环体422、N-S流程图表示法ABAB成立不成立PA当P成立直到P不成立A①顺序结构②选择结构③循环结构“当型”循环“直到型”循环1.2.3N-S图表示法43例描述求n!的值的算法1.2.3N-S图表示法F=1,i=1开始输入ni≤n?F=F*i输出F结束i=i+144例：输入10个数，找出其中最大的数，并输出。step6:若i=9，则返回step3，继续执行，否则输出max中的数，此时max中的数即为最大数。step1:输入一个数，存放在一个变量max中；step2:设置用来累计比较次数的计数器i(也是一个变量)1i；step3:输入一个数，存放在另一个变量x中；step5:i增加1，即i+1i；否则，max的值不变；step4:比较max和x中的数，若xmax，则将x的值送入max,45输入一个数max1i输入xxmax?是否xmaxi+1i当i=9输出max#includestdio.hvoidmain(){intx,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);}461.3程序设计方法一、结构化程序设计(SP方法)1.程序的基本单元是函数。2.SP方法主张使用顺序、选择、循环三种基本结构来嵌套连结成具有复杂层次的“结构化程序”，严格控制GOTO语句（无条件转移）的使用。3.“自顶而下，逐步求精”的设计思想，“独立功能，单出、入口”的模块仅用3种(顺序、分支、循环)基本控制结构的编码原则。4.C语言就是结构化设计语言。47结构化程序设计方法1、自顶向下2、逐步细化3、模块化设计4、结构化编码需要解决的问题P子问题p1子问题p2子问题p3p12p11p32p31p33设计设计设计设计设计设计编码编码编码编码编码编码48程序结构图491.3程序设计方法二、面向对象程序设计(OOP)1.这种语言把现实世界看成是由许多对象所组成的,对象之间通过互相发送和接收消息进行联系。2.程序的基本单元是对象。3.具有三大特性：封装性、继承性和多态性。4.C++语言就是面向对象的程序设计语言。50类关系图511.3程序设计方法三、面向服务的程序设计(SOA方法)1.基本结构单元是：组件。2.独立于实现服务的硬件平台、操作系统和编程语言。52