第5章 程序设计基础.ppt

第10章程序设计基础,10.1程序设计的概念10.2算法10.3程序设计方法10.4程序设计语言10.5程序设计范例10.6扩充与提高知识,10.1程序设计的概念,程序：解题方法、步骤的描述；指令序列。程序的核心：数据结构和算法。,程序设计（编程序）：先对问题进行分析并建立数学模型，然后考虑数据的组织方式和算法，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果。,程序设计的基本步骤：(1)分析问题，确定数学模型或方法。(2)设计算法，画出流程图。(3)选择编程工具，按算法编写程序。(4)调试程序，分析输出结果。,10.2算法,10.2.1算法概述1.算法的概念计算机解决问题的方法和步骤，就是计算机解题的算法。算法举例：例1一个选择结构。例2输入10个数，要求找出其中最大的数。,2算法的特性(1)有穷性。算法中执行的步骤总是有限次数的，不能无止境地执行下去。(2)确定性。算法中的每一步操作必须具有确切的含义，不能有二义性。(3)有效性。算法中的每一步操作必须是可执行的。(4)要有数据输入。算法中操作的对象是数据，因此应提供有关数据。(5)要有结果输出。,3算法评价标准（1）正确性。（2）可读性。（3）通用性。（4）高效率。4.算法效率的度量（1）时间度量（占用机时）（2）空间度量(运行和存储),10.2.2算法的描述,1.用流程图描述算法(传统page301图10-2)2.用N-S图描述算法（1）程序的三种基本结构：顺序结构、选择结构和循环结构。(page302图10-3-4-5)（2）结构化流程图（N-S图）(page303图10-6-7)例5-3用N-S图来描述例5-1和例5-2的算法。(page175左右),例：输入10个数，要求找出其中最大的数。,i计数器Max装最大数,顺序结构：由若干个前后衔接的矩形块顺序组成，依次顺序执行不同的程序块，是最简单的基本结构。,流程图,N-S图,选择结构：在此结构内有两个分支，它表示当给定的条件P满足时执行A块的操作，否则执行B块的操作,循环结构解决重复执行(运行)的问题,循环结构解决重复执行(运行)的问题,例9-5计算1+3+5+7+99,s=0Fori=1To99Step2s=s+iNexti注：s加法器i控制变量、又产生加数,例：求1！+2！+3！+n！要求输入任意的N，求1到N的阶乘。求1！+3！+5！+(n+2)！求1！+2！+41+,当型循环结构A块可能一次也不运行,直到型循环结构A块至少运行一次,流程图,N-S图,例5算法：输入10个数，要求找出其中最大的数。输入一个数，放在存储单元max中。设置用来统计比较次数的单元i，初始值为1。若imax，则将x的值送给max，否则，max值不变。i增加1。返回到第3）步。输出max中的数，此时max中的数就是10个数中最大的数,用N-S图表示:,Procmysum把第一个值送给Max1iWhilei9把下一个值送给xifxmaxxmaxendifi+1iPrintmaxend,用伪代码表示:,10.2.3算法示例,1迭代算法建立在循环基础上的算法用来进行数值计算，不断用变量原来的值递推求解新的值的过程。如累加和累乘：例：计算1+3+5+7+99s=0Fori=1To99Step2s=s+iNexti,例：用Do语句计算1+2+3+4+，直到累加和第一次大于1000为止，输出和值以及最后一次所加的数s=0,i=1DoWhiles=1000i=i+1s=s+iLoopPrints,i,10.2.3算法示例,2.穷举法：对众多可能的解，按照某种顺序逐一穷举和检验，从中找出符合要求的可能解,但计算量大。如：对于不定方程x+2y+5z=100求整数解。方程有多组解,可以设定x、y的值，再求得z的值,根据需要确定一组解,10.2.3算法示例,3.排序算法所谓排序，就是将一组数据元素按照某个关键字递增或递减的次序排列起来。（1）选择排序(SelectionSort)(p306)选择排序法的实现过程是：首先找出表中关键字最小的元素，将其与第一个元素进行交换，然后，再在其余元素中找出关键字最小的元素，将其与第二个元素进行交换。依次类推，直到将表中所有关键字按由小到大的顺序排列好为止。,（2）冒泡排序(BubbleSort)(p307)冒泡法排序法是每趟将相邻的两个数两两进行比较，若满足升序(降)次序，则进行下一次比较，若不满足升序(降)次序，则交换这两个数，直到最后。总的比较次数为n-1次，此时最后的元素为最大数(最小)，此为一趟排序。接着进行第二趟排序，方法同前，只是这次最后一个元素不再参与比较，比较次数为n-2次，依次类推。,4查找算法查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若表中存在这样的数据元素，称此查找是成功的。若表中不存在关键字等于给定值的数据元素，称此查找是不成功的。用计算机查找首先要将原始数据整理成线性表，并按照一定的存储结构存储到计算机中去，然后编制算法进行查找。,4查找算法,（1）顺序查找顺序查找是最常用的查找方法，其查找过程为：从第一个元素起，逐个将给定值与数据元素的关键字进行比较，若某个元素的关键字与给定值相等，则认为查找是成功的，否则，查找失败。不足：查找量大、慢。,（2）折半查找作为折半查找的表必须是顺序存储的有序表，即表采用顺序结构存储，表中的元素按关键字值递增（或递减）排列。,假设表中的关键字值递增排列，则折半查找的实现方法是：首先取整个有序表的中间元素Am的关键字同给定值x比较，若相等，则查找成功；否则，若：Am的关键字小于x，则说明待查元素只可能落在表的后半部分中，接着只要在表的后半部分子表中查找即可；若：Am的关键字大于x，则说明待查元素只可能落在表的前半部分中，接着只要在表的前半部分子表中查找即可。,这样，经过一次关键字的比较，就缩小一半的查找空间，重复进行下去，直到找到关键字为x的元素，或者表中没有待查元素（此时查找区间为空）为止。,10.3程序设计方法,随着计算机技术的不断发展，人们对程序设计方法的研究也在不断深入。早期程序设计的好坏常以运行速度快、占用内存少为主要标准，然而在计算机的运算速度大大提高，存储容量不断扩大的情况下，程序具有良好的结构成为第一要求，一个结构良好的程序虽然在效率上不一定最好，但结构清晰，易于阅读和理解，便于验证(修改)其正确性。这对传统的程序设计方法提出了严重的挑战，从而促使了程序设计方法的进步。引入面向对象程序设计、软件工程概念(课程),10.3.1结构化程序设计(p319),传统的结构化程序设计采用：自顶向下、逐步求精、和模块化的分析方法，从而有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子程序，便于开发和维护。,10.3.1结构化程序设计,传统的程序设计是基于求解过程来组织程序流程。在这类程序中，数据和施加于数据的操作是独立设计的，以对数据进行操作的过程作为程序的主体。(数据和操作是分开的),10.3.2面向对象程序设计,面向对象程序设计则以对象作为程序的主体。对象是数据和操作的“封装体”，封装在对象内的程序通过“消息”(事件)来驱动运行。在图形用户界面上，消息(事件)可通过键盘或鼠标的某种操作来传递。,（1）对象(Object)对象是指现实世界中具体存在的实体。每一个对象都有自己的属性(包括自己特有的属性和同类对象的共同属性)。属性反映对象自身状态变化，表现为当前的属性值如：学生(姓名,年龄,身高等)。方法是用来描述对象动态特征的一个操作序列(可以做什么，命令序列)。（2）类(Class)类是具有相同属性和方法的一组对象的集合，它为属于该类的全部对象提供了统一的抽象描述。(如全班同学),(3)消息(事件)：对象之间进行通信的数据叫做消息。当一个消息发送给某个对象时，包含要求接收对象去执行某些活动的信息，接收到消息的对象对其进行解释，然后予以响应。这种通信机制叫做消息传递。一个消息由下列三个元素组成：消息名；零个或多个参数列表，为接收对象提供数据信息；对接收对象的引用。,(4)封装：,是把一组相关软件元素组织到一起的方法。其目的在于将对象的使用者和设计者分开，使用者不必知道对象行为实现的细节，只须用设计者提供的对象接口来访问对象。利用封装来隐藏那些不允许对外的对象属性。封装的定义为：对所有对象的内部软件范围的边界进行限定；对各对象之间相互作用的接口进行描述；对每个对象的内部实现（操作程序和数据）进行保护。,(5)继承：继承性是类层次结构中的一个重要特点,A-父类,B-子类,继承是软件重用的一个基本机制。当通过继承定义一个新类时，新类获得了已存在类的属性和行为。新类称为子类，而已存在类称为父类。子类又可以是其他类的父类，这就形成了继承层次结构。这样：可以减轻程序开发中的工作量,(6)多态性：,在收到消息时，不同的对象收到同一消息可能产生多种不同的结果（会有多种不同行为方式产生)。在使用多态时，用户可以发送一个通用的消息，而实现的细节则由接收对象自行决定。多态的实现受到继承性的支持。把具有通用功能的消息存放在高层次，而实现这一功能的不同的行为放在较低层次，则在这些低层次上生成的对象就能对通用消息做出不同的响应。,好处：系统很灵活，易扩充：发送者只知道另一个实例可以执行某个行为，但不需知道该实例属于哪个类。如打印功能，打印某页到某页，发送print命令，打印设备可以是任意类型。增加一种新的打印设备，不必修改发送打印命令的类，也不必修改其它设备的类。,10.4程序设计语言,5.4.1程序设计语言的分类1机器语言（Machinelanguage）机器语言：机器指令的总称。特点：繁琐冗长、不直观、容易出错、程序不通用。2汇编语言（Assemblylanguage）用助记符表示的机器指令。特点：直观性增强了，但与机器指令一一对应。,3高级语言（Highlevellanguage）高级语言：接近自然语言和数学表达式的一种语言。特点：直观、通用性，便于推广交流。两种执行方式：编译方式和解释方式。,10.4.补充高级语言的基本特征,1数据类型各种高级语言都提供了丰富的数据类型，这些数据类型可以分为两大类：简单类型和构造类型。其中简单类型一般有整型、实型、字符型、逻辑型、指针类型等，构造类型有数组类型、集合类型、记录类型、文件类型等。,2运算与表达式（1）常量（2）变量（3）表达式3语句（1）赋值语句（2）输入输出语句（3）程序的控制结构语句4子程序、函数与过程,10.4.3常用高级语言,1.传统高级语言（1）FORTRAN语言：FORTRAN66、FORTRAN77、FORTRAN90。（2）BASIC语言：BASIC、VisualBasic、VisualBasic.NET。（3）PASCAL语言（4）C语言：C、C+、C。（5）COBOL语言,2网络编程语言（1）Java语言（2）脚本语言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。3科学计算语言：MATLAB讨论：如何学习一种高级语言？如何选择高级语言？,10.5程序设计范例,各种高级语言有自己的特点，但它们的语句基本上是相同的。在使用这些编程语言进行编程时，编程的方法也基本相同。下面是用不同的程序设计语言编写的解决同一个问题的程序，读者可以从中体会程序设计的步骤和用不同语言编写程序的特点。,10.6扩充与提高知识,著名公式：算法+数据结构=程序5.6.1数据结构基础1.数据结构的定义数据结构（DataStructure）是指数据元素之间存在着的一种或多种特定的关系。数据结构作为一门学科主要研究数据的各种逻辑结构、物理结构以及对数据的各种运算。,2.数据的逻辑结构数据元素之间的逻辑关系就是数据的逻辑结构。根据数据元素之间关系的不同特性，将数据结构划分为四种类型：(1)集合(2)