计算机科学导论讲稿课件.ppt

学习目标u了解程序设计的基础知识、程序设计风格的重要性、基本的查找和排序方法u掌握结构化程序设计方法和面向对象程序设计方法的思想、几种基本的数据结构u学习计算机首先要学习程序设计，良好的程序设计技能和风格有助于加深对计算机的理解和进一步学习第第4 4章章 程序设计基础程序设计基础4.1 程序设计基础程序设计步骤如下：(1)确定要解决的问题2)分析问题在着手解决问题之前，应该通过分析，充分理解问题，明确原始数据、解题要求、需要输出的数据及形式等3)选择计算方法4)确定数据结构和算法算法是解题的过程首先集中精力于算法的总体规划，然后逐层降低问题的抽象性，逐步充实细节，直到最终把抽象的问题具体化成可用程序语句表达的算法这是一个自上而下、逐步细化的过程4.1 程序设计基础(5)(5)绘制流程图绘制流程图6)(6)编写程序编写程序利用程序设计语言表示算法，编写利用程序设计语言表示算法，编写代码7)(7)调试并测试程序调试并测试程序调试程序包括编译和连接等调试程序包括编译和连接等操作程序员还要对程序执行的结果进行分析，只操作程序员还要对程序执行的结果进行分析，只有能够得到正确结果的程序才是所需的程序。

有能够得到正确结果的程序才是所需的程序8)(8)整理资料，交付使用整理资料，交付使用高质量程序设计目标是结构化程度高、可读性好、效率高质量程序设计目标是结构化程度高、可读性好、效率高、可靠性高、便于维护高、可靠性高、便于维护u1自上而下与自下而上先将一个大问题分解成若干个子问题，把比较复杂的子问题继续分解成更加简单的二级子问题，直至每个子问题都有显而易见的解决办法，然后在实现时采用自下而上的方法，逐一编写解决各个子问题的程序设计程序时采用自上而下的方法比采用自下而上的方法效率要高得多4.2.1 结构化程序设计方法结构化程序设计方法采用自上而下解决问题的思路如图:4.2.1 结构化程序设计方法结构化程序设计方法 用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止这种方法就叫 做“自顶向下，逐步细化”u2结构化方法结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法，并且可以在具体编码过程中提供指导4.2.1 结构化程序设计方法结构化程序设计方法u结构化方法通常遵循以下原则:(1)用户参与的原则(2)先分析、再设计、后实现的原则3)自上而下的原则(4)阶段成果文档化4.2.1 结构化程序设计方法结构化程序设计方法u3结构化程序设计方法 使用顺序、选择、循环3种基本控制结构。

4.2.1 结构化程序设计方法结构化程序设计方法A AB Ba ab b顺序结构示意图顺序结构示意图 顺序结构顺序结构 顺序结构是一种最简单、最基本的结构，在顺序结顺序结构是一种最简单、最基本的结构，在顺序结构内，构内，各块是按照它们出现的先后顺序依次执行各块是按照它们出现的先后顺序依次执行下图表示了一个顺序结构形式，从图中可以看出它下图表示了一个顺序结构形式，从图中可以看出它有一个入口有一个入口a a点，一个出口点，一个出口b b点，在结构内点，在结构内A A框和框和B B框框都是顺序执行的处理框都是顺序执行的处理框已知梯形两底已知梯形两底a、b和高和高h，设计一个求梯形面积的算，设计一个求梯形面积的算法，并画出流程图法，并画出流程图选择结构选择结构 选择结构中包含一个判断框，根据给定的条件选择结构中包含一个判断框，根据给定的条件S S是否成立而选择执行是否成立而选择执行A A框或框或B B框，当条件成立时，执框，当条件成立时，执行行A A，否则执行，否则执行B B判断框中的两个分支，执行完判断框中的两个分支，执行完A A或或B B后都必须汇合在一起，从出口后都必须汇合在一起，从出口b b 退出，然后接着执退出，然后接着执行其后的过程。

行其后的过程SABabYN选择结构流程图选择结构流程图设计一个算法，输出设计一个算法，输出a，b，c中的最大值中的最大值循环结构循环结构 循循环环结结构构是是指指在在一一定定条条件件下下反反复复执执行行一一个个程程序序块块的的结结构构循循环环结结构构也也是是只只有有一一个个入入口口，一个出口一个出口whilewhile循环循环 当当给给定定的的条条件件S S成成立立时时，执执行行A A框框操操作作，执执行行完完A A操操作作后后，再再判判断断S S条条件件是是否否成成立立，如如果果成成立立，再再次次执执行行A A操操作作，如如此此重重复复执执行行A A操操作作，直直到到判判断断p p条条件件不不成成立立才才停停止止循循环环此此时时不不执执行行A A操操作作，而从出口而从出口b b脱离循环结构脱离循环结构ASabYNabYNSA do-whiledo-while循环循环 先先执执行行A A框框操操作作，然然后后判判断断给给定定条条件件S S是是否否成成立立，如如果果成成立立，再再次次执执行行A A操操作作；然然后后再再对对S S进进行行判判断断，如如此此反反复复，直直到到给给定定的的S S条条件件不不成成立立为为止止。

此此时时不不再再执执行行A A框，从出口框，从出口b b脱离循环脱离循环设计一个算法，计算1+2+3+100的值u3结构化程序设计方法 使用顺序、选择、循环3种基本控制结构4.2.1 结构化程序设计方法结构化程序设计方法u4模块化方法一个复杂的问题可以划分为多个简单问题的组合在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化模块化便于问题的分析，模块体现了信息隐藏的概念模块常用子程序加以实现4.2.1 结构化程序设计方法结构化程序设计方法模块设计的方法：模块化设计的思想实际上是一种模块化设计的思想实际上是一种“分而治之分而治之”的思想，把一个大任务分为若干个子任务，的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了每一个子任务就相对简单了在拿到一个程序模块以后，根据程序模块的在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块的规模还嫌大，还再可以划分为更小的模块这个过程采用自顶向下方法来实现这个过程采用自顶向下方法来实现4.2.2 面向对象的程序设计方法u1面向对象的思想OO(Object Oriented，面向对象)的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征)，形成类。

对象对象 对对对对象象象象(Object)(Object)(Object)(Object)是是是是具具具具有有有有某某某某些些些些特特特特性性性性的的的的具具具具体体体体事事事事物物物物的的的的抽抽抽抽象象象象对对象象在在现现实实生生活活中中到到处处可可见见凡凡凡凡是是是是我我我我们们们们要要要要处处处处理理理理的的的的事事事事物物物物都都都都可可可可成成成成为为为为处处处处理理理理的的的的对对对对象象象象，包包包包括括括括可可可可见见见见的的的的事事事事物物物物（如如如如人人人人、汽汽汽汽车车车车、电电电等）和非可见的事物（如感情、思想等）话等）和非可见的事物（如感情、思想等）话等）和非可见的事物（如感情、思想等）话等）和非可见的事物（如感情、思想等）例例例例如如如如，一一个个人人是是一一个个对对象象，一一台台PCPC机机是是一一个个对对象象；再再将将一一台台PCPC机机拆拆开开看看，便便有有显显示示器器、机机箱箱、硬硬盘盘、主主板板、处处理理器器、鼠鼠标标等等，这这每每一一个个部部件件又又是是一一个个对对象象，即即PCPC机机对对象象是是由由多多个个“子子”对对象象组组成成的的，此此时时PCPC机机可可看看作作为为一一个容器对象。

个容器对象4.2.2 面向对象的程序设计方法面向对象的程序设计方法类类 类类类类是是是是具具具具有有有有共共共共同同同同属属属属性性性性、共共共共同同同同操操操操作作作作性性性性质质质质的的的的对对对对象象象象的的的的集集集集合合合合在在例例例例如如如如：桥桥梁梁是是抽抽象象的的概概念念,重重庆庆长长江江大大桥桥、西西湖湖断断桥桥就就是是具具体体的的我我们们把把抽抽象象的的“桥桥”看看成成类类,而而具具体体的的一一座座桥桥，如重庆长江大桥看成是对象如重庆长江大桥看成是对象类类类类是是是是对对对对象象象象的的的的抽抽抽抽象象象象描描描描述述述述，对对对对象象象象则则则则是是是是类类类类的的的的实实实实例例例例类类是是抽抽象象的，对象是具体的的，对象是具体的类类类类可可可可以以以以划划划划分分分分为为为为基基基基类类类类(根根根根类类类类)和和和和子子子子类类类类(派派派派生生生生类类类类)子子子子类类类类以以以以其其其其基类为起点，并可继承基类的特征基类为起点，并可继承基类的特征基类为起点，并可继承基类的特征基类为起点，并可继承基类的特征如如水水果果是是基基类类，苹苹果果是是子子类类，而而红红富富士士、黄黄元元帅帅等等苹苹果果品品种种又又是是苹苹果果类类的的子子类类，在在这这里里，水水果果也也称称为为是是苹苹果果的的父父类类，苹苹果果也也可可称称为为是是红红富富士士、黄黄元元帅帅等等的的父父类类。

具具体体的的一个红富士苹果就是一个对象一个红富士苹果就是一个对象4.2.2 面向对象的程序设计方法面向对象的程序设计方法消息消息消消消消息息息息是是是是面面面面向向向向对对对对象象象象系系系系统统统统中中中中实实实实现现现现对对对对象象象象间间间间的的的的通通通通讯讯讯讯和和和和请请请请求求求求任任任任务的操作务的操作务的操作务的操作消息传递是程序运行的基本处理活动消息传递是程序运行的基本处理活动消息传递是程序运行的基本处理活动消息传递是程序运行的基本处理活动4.2.2 面向对象的程序设计方法面向对象的程序设计方法类的特性类的特性（1 1 1 1）继承性）继承性）继承性）继承性 子子类类不不但但具具有有父父类类的的全全部部属属性性和和方方法法，而而且且允允许许用用户户根根据据需需要要对对已已有有的的属属性性和和方方法法进进行行修修改改，或或添添加加新新的的属属性性和和方方法法，这种特性称为类的继承性这种特性称为类的继承性2 2 2 2）封装性）封装性）封装性）封装性 类类类类的的的的封封封封装装装装性性性性是是是是指指指指类类类类的的的的内内内内部部部部信信信信息息息息对对对对用用用用户户户户是是是是隐隐隐隐蔽蔽蔽蔽的的的的。

如如同同一一台台电电视视机机的的使使用用者者只只需需了了解解其其外外部部按按钮钮（用用户户接接口口）的的功功能能与与用法，而无需知道电视机的内部构造与工作原理一样用法，而无需知道电视机的内部构造与工作原理一样3 3 3 3）多态性）多态性）多态性）多态性 类的多态性是指一些相关联的类包括同名的方法程序类的多态性是指一些相关联的类包括同名的方法程序类的多态性是指一些相关联的类包括同名的方法程序类的多态性是指一些相关联的类包括同名的方法程序，但，但方法程序的内容不同方法程序的内容不同4.2.2 面向对象的程序设计方法面向对象的程序设计方法4.3 基本数据结构u数据结构(Data Structure)是系统设计和程序开发的重要基础4.3.1 基本概念u1数据、数据类型数据是对客观事物的符号表示在计算机系统内，数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合例如，数字、字母、汉字、图形、图像、声音等信息在计算机内部的表示都是数据，可以是数值数据，也可以是非数值数据数据类型是指具有相同取值范围和可以实施同种操作的数据的集合例如，在程序设计语言中，通常定义了字符型、整数型、数组等多种数据类型。

u2数据元素、数据项、数据对象能够独立并完整地描述客观世。