计算机科学导论讲稿

《计算机科学导论讲稿》由会员分享，可在线阅读，更多相关《计算机科学导论讲稿（84页珍藏版）》请在金锄头文库上搜索。

1、,第4章 程序设计基础,学习目标 了解程序设计的基础知识、程序设计风格的重要性、基本的查找和排序方法。 掌握结构化程序设计方法和面向对象程序设计方法的思想、几种基本的数据结构。 学习计算机首先要学习程序设计，良好的程序设计技能和风格有助于加深对计算机的理解和进一步学习。,第4章 程序设计基础,4.1 程序设计基础,程序设计步骤如下： (1)确定要解决的问题。 (2)分析问题。在着手解决问题之前，应该通过分析，充分理解问题，明确原始数据、解题要求、需要输出的数据及形式等。 (3)选择计算方法。 (4)确定数据结构和算法。算法是解题的过程。首先集中精力于算法的总体规划，然后逐层降低问题的抽象性，逐

2、步充实细节，直到最终把抽象的问题具体化成可用程序语句表达的算法。这是一个自上而下、逐步细化的过程。,4.1 程序设计基础,(5)绘制流程图。 (6)编写程序。利用程序设计语言表示算法，编写代码。 (7)调试并测试程序。调试程序包括编译和连接等操作。程序员还要对程序执行的结果进行分析，只有能够得到正确结果的程序才是所需的程序。 (8)整理资料，交付使用。 高质量程序设计目标是结构化程度高、可读性好、效率高、可靠性高、便于维护。,1自上而下与自下而上 先将一个大问题分解成若干个子问题，把比较复杂的子问题继续分解成更加简单的二级子问题，直至每个子问题都有显而易见的解决办法，然后在实现时采用自下而上的

3、方法，逐一编写解决各个子问题的程序。设计程序时采用自上而下的方法比采用自下而上的方法效率要高得多。,4.2.1 结构化程序设计方法,采用自上而下解决问题的思路如图:,4.2.1 结构化程序设计方法,用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。,2结构化方法 结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法，并且可以在具体编码过程中提供指导。,4.2.1 结构化程序设计方法,结构化方法通常遵循以下原则: (1) 用户参与的原则 (2) 先分析、再设计、后实现的原则。 (3) 自上而下的原则 (4) 阶段成果文档化,4.

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

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

6、的值。,3结构化程序设计方法 使用顺序、选择、循环3种基本控制结构。,4.2.1 结构化程序设计方法,4模块化方法 一个复杂的问题可以划分为多个简单问题的组合。 在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化。 模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。,4.2.1 结构化程序设计方法,模块设计的方法： 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。,在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这

7、个过程采用自顶向下方法来实现。,4.2.2 面向对象的程序设计方法,1面向对象的思想 OO(Object Oriented，面向对象)的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征)，形成类。,对象 对象(Object)是具有某些特性的具体事物的抽象。对象在现实生活中到处可见。凡是我们要处理的事物都可成为处理的对象，包括可见的事物（如人、汽车、电话等）和非可见的事物（如感情、思想等）。 例如，一个人是一个对象，一台PC机是一个对象；再将一台PC机拆开看，便有显示器、机箱、硬盘、主板、处理器、鼠标等，这每一个部件又是一个对象，即PC机对

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

9、,4.2.2 面向对象的程序设计方法,消息 消息是面向对象系统中实现对象间的通讯和请求任务的操作。 消息传递是程序运行的基本处理活动。,4.2.2 面向对象的程序设计方法,类的特性 （1）继承性 子类不但具有父类的全部属性和方法，而且允许用户根据需要对已有的属性和方法进行修改，或添加新的属性和方法，这种特性称为类的继承性。 （2）封装性 类的封装性是指类的内部信息对用户是隐蔽的。如同一台电视机的使用者只需了解其外部按钮（用户接口）的功能与用法，而无需知道电视机的内部构造与工作原理一样。 （3）多态性 类的多态性是指一些相关联的类包括同名的方法程序，但方法程序的内容不同。,4.2.2 面向对象的

10、程序设计方法,4.3 基本数据结构,数据结构(Data Structure)是系统设计和程序开发的重要基础。,4.3.1 基本概念,1数据、数据类型 数据是对客观事物的符号表示。在计算机系统内，数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合。例如，数字、字母、汉字、图形、图像、声音等信息在计算机内部的表示都是数据，可以是数值数据，也可以是非数值数据。 数据类型是指具有相同取值范围和可以实施同种操作的数据的集合。例如，在程序设计语言中，通常定义了字符型、整数型、数组等多种数据类型。,2数据元素、数据项、数据对象 能够独立并完整地描述客观世界实体的基本数据单元称为数据元素，它是组成数

11、据的基本单位。在不同的应用环境中，数据元素有时可以称为结点、记录等。 数据项是组成数据元素的不可分割的最小单位。最简单的数据元素是由一个数据项构成的。 同类数据元素的集合称为数据对象。,4.3.1 基本概念,表中的每一行是一个结点（或记录），即数据元素； 它是由学号、姓名、各科成绩及平均成绩等数据项组成。,4.3.1 基本概念,2数据元素、数据项、数据对象,3数据结构 数据结构是指数据元素之间的相互关系的集合，包括了数据的逻辑结构、物理结构以及数据的运算。,4.3.1 基本概念,31,数据结构主要研究： 数据集合中数据元素之间所固有的关系，即数据逻辑结构； 数据处理时数据在计算机中的存储关系，

12、即数据存储结构； 对数据所进行的操作，即算法。,4.3.1 基本概念,4.3.1 基本概念,33,数据逻辑结构 数据结构中数据元素之间所固有的关系描述成前后件（前驱与后继）关系。 数据之间前后件关系是它们之间的逻辑关系，与它们在计算机中存储位置无关，因此将这种关系称为数据逻辑结构。,34,一个数据结构可以表示为： S=（D，R）,S: 数据结构 D: 数据元素集合 R: D中数据元素之间前后件关系集合， 即数据逻辑结构 两个元素之间前后件关系用一个二元组表示，如：(a1,a2),35,事实上可能有： 如树形结构中的一个元素有多个后件 或如网状结构中的一个元素有多个前件 因此一般来说，数据之间有

13、4种基本逻辑结构： 集合 线性 树形 图形,36,37,非线性结构：有多个开始结点和多个终端结点，每个结点可有多个前件和多个后件,线性结构：有且只有一个开始结点和一个终端结点，并且每个结点最多只有一个前件和一个后件，线性结构也称为线性表。,根据前后件关系的复杂程度，数据逻辑结构分为2类。,38,数据物理结构 定义：数据在计算机存储器中的存储方式 称为数据存储结构（或数据物理结构）。 数据结构中数据元素之间在计算机中的位置关系与逻辑关系不一定相同。,在数据存储结构中，不仅要存放各个数据元素信息，还要存放数据元素之间前后件关系信息。 数据存储结构是逻辑结构在计算机存储器中的表示,39,数据元素在计

14、算机中通常有四种存储方式： 顺序 链式 索引 散列 常用顺序存储结构和链式存储结构。,数据物理结构,40,顺序存储结构 在存储器中开辟一块连续的单元用于存放数据，逻辑上相邻的结点在物理位置上也邻接，结点之间的逻辑关系是由存储单元相邻关系来体现。,41,链式存储结构 结点由两部分组成： 数据域用于存放数据元素值 指针域用于存放前件或后件的存储地址 链式存储结构是通过指针反映数据间的逻辑关系。,回 顾,程序设计步骤 程序设计方法 结构化程序设计方法 面向对象的程序设计方法 数据结构的基本概念,4.3.2 几种典型的数据结构,1线性表,2栈,3队列,4线性表,5图,定义 线性表是一组特征相同数据的有

15、限序列，表示为： L=(a1,a2,a3,an)。 有限个同类的数据元素构成的序列。,4.3.2 几种典型的数据结构,1线性表,有且仅有一个“第一个”数据元素 有且仅有一个“最后一个”数据元素 除第一个数据元素外，其它元素有且仅有一个直接前驱 除最后一个数据元素外，其它元素有且仅有一个直接后继,4.3.2 几种典型的数据结构,1线性表,例如英文字母表（A，B，C，Z）是线性表，表中的每个字母就是一个数据元素。 一副扑克的点数（2，3，4，J，Q，K，A）也是线性表，其中每一张牌的点数是一个数据元素。,4.3.2 几种典型的数据结构,1线性表,线性表通常采用顺序和链表两种物理实现。对于经常变化的

16、表，通常采取链表结构。 线性表常用的运算主要有：插入、删除、查询和遍历。,4.3.2 几种典型的数据结构,1线性表,48,2. 栈 栈是只能在表的一端进行插入和删除运算的线性表 允许插入和删除运算的一端称为栈顶，另一端称为栈底。 插入元素操作称为入栈 删除元素操作称为出栈,4.3.2 几种典型的数据结构,49,a1,a2,an,栈底bottom,栈顶top,入栈,出栈,4.3.2 几种典型的数据结构,栈是一种“后进先出”或“先进后出”的数据结构。,例如用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。,4.3.2 几种典型的数据结构,52,3. 队列 只允许：在一端进行插入运算， 而在另一端进行删除运算的线性表。 允许删除的一端称为队首（队头） 允许插入的一端称为队尾,4.3.2 几种典型的数据结构,53,3. 队列,4.3.2 几种典型的数据