计算机科学导论第第4章讲稿程序设计基础

第4章程序设计基础2019/8/302计算机科学导论学习目标了解程序设计的基础知识、程序设计风格的重要性、基本的查找和排序方法。掌握结构化程序设计方法和面向对象程序设计方法的思想、几种基本的数据结构。学习计算机首先要学习程序设计，良好的程序设计技能和风格有助于加深对计算机的理解和进一步学习。第4章程序设计基础2019/8/303计算机科学导论4.1程序设计基础程序设计步骤如下：(1)确定要解决的问题。(2)分析问题。在着手解决问题之前，应该通过分析，充分理解问题，明确原始数据、解题要求、需要输出的数据及形式等。(3)选择计算方法。(4)确定数据结构和算法。算法是解题的过程。首先集中精力于算法的总体规划，然后逐层降低问题的抽象性，逐步充实细节，直到最终把抽象的问题具体化成可用程序语句表达的算法。这是一个自上而下、逐步细化的过程。2019/8/304计算机科学导论4.1程序设计基础(5)绘制流程图。(6)编写程序。利用程序设计语言表示算法，编写代码。(7)调试并测试程序。调试程序包括编译和连接等操作。程序员还要对程序执行的结果进行分析，只有能够得到正确结果的程序才是所需的程序。(8)整理资料，交付使用。高质量程序设计目标是结构化程度高、可读性好、效率高、可靠性高、便于维护。2019/8/305计算机科学导论1．自上而下与自下而上先将一个大问题分解成若干个子问题，把比较复杂的子问题继续分解成更加简单的二级子问题，直至每个子问题都有显而易见的解决办法，然后在实现时采用自下而上的方法，逐一编写解决各个子问题的程序。设计程序时采用自上而下的方法比采用自下而上的方法效率要高得多。4.2.1结构化程序设计方法2019/8/306计算机科学导论采用自上而下解决问题的思路如图:......…二级子问题二级子问题二级子问题需要解决的复杂问题…三级子问题三级子问题三级子问题.........…最小问题最小问题最小问题4.2.1结构化程序设计方法2019/8/307计算机科学导论用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫做“自顶向下，逐步细化”2019/8/308计算机科学导论2．结构化方法结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法，并且可以在具体编码过程中提供指导。4.2.1结构化程序设计方法2019/8/309计算机科学导论结构化方法通常遵循以下原则:(1)用户参与的原则(2)先分析、再设计、后实现的原则。(3)自上而下的原则(4)阶段成果文档化4.2.1结构化程序设计方法2019/8/3010计算机科学导论3．结构化程序设计方法使用顺序、选择、循环3种基本控制结构。4.2.1结构化程序设计方法2019/8/3011计算机科学导论ABab顺序结构示意图⑴顺序结构顺序结构是一种最简单、最基本的结构，在顺序结构内，各块是按照它们出现的先后顺序依次执行。下图表示了一个顺序结构形式，从图中可以看出它有一个入口a点，一个出口b点，在结构内A框和B框都是顺序执行的处理框。2019/8/3012计算机科学导论已知梯形两底a、b和高h，设计一个求梯形面积的算法，并画出流程图。2019/8/3013计算机科学导论⑵选择结构选择结构中包含一个判断框，根据给定的条件S是否成立而选择执行A框或B框，当条件成立时，执行A，否则执行B。判断框中的两个分支，执行完A或B后都必须汇合在一起，从出口b退出，然后接着执行其后的过程。SABabYN选择结构流程图2019/8/3014计算机科学导论设计一个算法，输出a，b，c中的最大值。2019/8/3015计算机科学导论⑶循环结构循环结构是指在一定条件下反复执行一个程序块的结构。循环结构也是只有一个入口，一个出口。①while循环当给定的条件S成立时，执行A框操作，执行完A操作后，再判断S条件是否成立，如果成立，再次执行A操作，如此重复执行A操作，直到判断p条件不成立才停止循环。此时不执行A操作，而从出口b脱离循环结构。ASabYN2019/8/3016计算机科学导论abYNSA②do-while循环先执行A框操作，然后判断给定条件S是否成立，如果成立，再次执行A操作；然后再对S进行判断，如此反复，直到给定的S条件不成立为止。此时不再执行A框，从出口b脱离循环。2019/8/3017计算机科学导论设计一个算法，计算1+2+3+…+100的值。2019/8/3018计算机科学导论3．结构化程序设计方法使用顺序、选择、循环3种基本控制结构。4.2.1结构化程序设计方法2019/8/3019计算机科学导论4．模块化方法一个复杂的问题可以划分为多个简单问题的组合。在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化。模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。4.2.1结构化程序设计方法2019/8/3020计算机科学导论模块设计的方法：•模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。•在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。2019/8/3021计算机科学导论4.2.2面向对象的程序设计方法1．面向对象的思想OO(ObjectOriented，面向对象)的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征)，形成类。2019/8/3022计算机科学导论对象对象(Object)是具有某些特性的具体事物的抽象。对象在现实生活中到处可见。凡是我们要处理的事物都可成为处理的对象，包括可见的事物（如人、汽车、电话等）和非可见的事物（如感情、思想等）。例如，一个人是一个对象，一台PC机是一个对象；再将一台PC机拆开看，便有显示器、机箱、硬盘、主板、处理器、鼠标等，这每一个部件又是一个对象，即PC机对象是由多个“子”对象组成的，此时PC机可看作为一个容器对象。4.2.2面向对象的程序设计方法2019/8/3023计算机科学导论类类是具有共同属性、共同操作性质的对象的集合在例如：桥梁是抽象的概念,重庆长江大桥、西湖断桥就是具体的。我们把抽象的“桥”看成类,而具体的一座桥，如重庆长江大桥看成是对象。类是对象的抽象描述，对象则是类的实例。类是抽象的，对象是具体的。类可以划分为基类(根类)和子类(派生类)。子类以其基类为起点，并可继承基类的特征。如水果是基类，苹果是子类，而红富士、黄元帅等苹果品种又是苹果类的子类，在这里，水果也称为是苹果的父类，苹果也可称为是红富士、黄元帅等的父类。具体的一个红富士苹果就是一个对象。4.2.2面向对象的程序设计方法2019/8/3024计算机科学导论消息消息是面向对象系统中实现对象间的通讯和请求任务的操作。消息传递是程序运行的基本处理活动。4.2.2面向对象的程序设计方法2019/8/3025计算机科学导论类的特性（1）继承性子类不但具有父类的全部属性和方法，而且允许用户根据需要对已有的属性和方法进行修改，或添加新的属性和方法，这种特性称为类的继承性。（2）封装性类的封装性是指类的内部信息对用户是隐蔽的。如同一台电视机的使用者只需了解其外部按钮（用户接口）的功能与用法，而无需知道电视机的内部构造与工作原理一样。（3）多态性类的多态性是指一些相关联的类包括同名的方法程序，但方法程序的内容不同。4.2.2面向对象的程序设计方法2019/8/3026计算机科学导论4.3基本数据结构数据结构(DataStructure)是系统设计和程序开发的重要基础。2019/8/3027计算机科学导论4.3.1基本概念1．数据、数据类型数据是对客观事物的符号表示。在计算机系统内，数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合。例如，数字、字母、汉字、图形、图像、声音等信息在计算机内部的表示都是数据，可以是数值数据，也可以是非数值数据。数据类型是指具有相同取值范围和可以实施同种操作的数据的集合。例如，在程序设计语言中，通常定义了字符型、整数型、数组等多种数据类型。2019/8/3028计算机科学导论2．数据元素、数据项、数据对象能够独立并完整地描述客观世界实体的基本数据单元称为数据元素，它是组成数据的基本单位。在不同的应用环境中，数据元素有时可以称为结点、记录等。数据项是组成数据元素的不可分割的最小单位。最简单的数据元素是由一个数据项构成的。同类数据元素的集合称为数据对象。4.3.1基本概念2019/8/3029计算机科学导论学号姓名高等数学大学英语政治经济学平均成绩1王五807678782李四907887853张三888989894高二789095875苏三80999491表中的每一行是一个结点（或记录），即数据元素；它是由学号、姓名、各科成绩及平均成绩等数据项组成。4.3.1基本概念2．数据元素、数据项、数据对象2019/8/3030计算机科学导论3．数据结构数据结构是指数据元素之间的相互关系的集合，包括了数据的逻辑结构、物理结构以及数据的运算。4.3.1基本概念2019/8/3031计算机科学导论31数据结构主要研究：1.数据集合中数据元素之间所固有的关系，即数据逻辑结构；2.数据处理时数据在计算机中的存储关系，即数据存储结构；3.对数据所进行的操作，即算法。4.3.1基本概念2019/8/3032计算机科学导论4.3.1基本概念2019/8/3033计算机科学导论33数据逻辑结构数据结构中数据元素之间所固有的关系描述成前后件（前驱与后继）关系。数据之间前后件关系是它们之间的逻辑关系，与它们在计算机中存储位置无关，因此将这种关系称为数据逻辑结构。2019/8/3034计算机科学导论34一个数据结构可以表示为：S=（D，R）S:数据结构D:数据元素集合R:D中数据元素之间前后件关系集合，即数据逻辑结构两个元素之间前后件关系用一个二元组表示，如：(a1,a2)2019/8/3035计算机科学导论35事实上可能有：如树形结构中的一个元素有多个后件或如网状结构中的一个元素有多个前件因此一般来说，数据之间有4种基本逻辑结构：集合线性树形图形2019/8/3036计算机科学导论36线性结构一对一关系集合松散关系树形结构一对多关系图形结构多对多关系2019/8/3037计算机科学导论37非线性结构：有多个开始结点和多个终端结点，每个结点可有多个前件和多个后件线性结构：有且只有一个开始结点和一个终端结点，并且每个结点最多只有一个前件和一个后件，线性结构也称为线性表。根据前后件关系的复杂程度，数据逻辑结构分为2类。2019/8/3038计算机科学导论38数据物理结构定义：数据在计算机存储器中的存储方式称为数据存储结构（或数据物理结构）。数据结构中数据元素之间在计算机中的位置关系与逻辑关系不一定相同。在数据存储结构中，不仅要存放各个数据元素信息，还要存放数据元素之间前后件关系信息。数据存储结构是逻辑结构在计算机存储器中的表示2019/8/3039计算机科学导论39数据元素在计算机中通常有四种存储方式：顺序链式索引散列常用顺序存储结构和链式存储结构。数据物理结构2019/8/3040计算机科学导论40顺序存储结构在存储器中开辟一块连续的单元用于存放数据，逻辑上相邻的结点在物理位置上也邻接，结点之间的逻辑关系是由存储单元相邻关系来体现。数据地址A12000HA22001HA32002HA42003H…………2019/8/3041计算机科学导论41链式存储结构结点由两部分组成：数据域——用于存放数据元素值指针域——用于存放前件或后件的存储地址链式存储结构是通过指针反映数据间的逻辑关系。a14003Ha22506Ha32509Ha42000H2001H4003H3004H2506H25