《计算机应用基础》 第9章 程序设计与软件工程基础

《《计算机应用基础》 第9章 程序设计与软件工程基础》由会员分享，可在线阅读，更多相关《《计算机应用基础》 第9章 程序设计与软件工程基础（82页珍藏版）》请在金锄头文库上搜索。

1、第9章 程序设计与软件工程基础p 9.1 程序设计基础p 9.2 数据结构与算法p 9.3 软件工程基础1 19.1 程序设计基础p9.1.1 程序设计语言发展p9.1.2 程序设计方法与风格p9.1.3 结构化程序设计p9.1.4 面向对象程序设计2 2程序设计n指令：能被计算机直接识别与执行的指示计算机 进行某种操作的命令，CPU每执行一条指令，就完 成一个基本运算。n程序：指令的序列即让计算机解决某一问题而写 出的一系列指令（C+程序）n程序设计：编写程序的过程n程序设计语言：用于描述计算机所执行的操作 语言（Visual Basic、Visual FoxPro、C/C+. ）3 34

2、49.1.1 程序设计语言发展p机器语言：采用计算机指令格式并以二进制编码表 达各种操作的语言（计算A=5+11）10110000 00000101 (把5放到累加器A中)00101100 00001011 （11与累加器A中的值相加，结果仍放入A中）11110100 （结束，停机）p汇编语言：一种符号语言，采用助记符来表达指令 功能（计算A=5+11）MOV A,5ADD A,11HLTp高级语言：是一种面向问题的语言（计算A=5+11）A=5+11PRINT AENDp第四代语言：是非过程化语言5 59.1.2 程序设计方法与风格良好程序设计风格的侧重：p 源程序文档如使用的符号名应具有一

3、定的含义， 以便对程序功能的理解；对源程序适当的进行注解 ，以便读者理解程序；在程序中利用空格、空行、 缩进等技巧使程序层次清楚p 对程序中的数据进行适当说明p 程序中的语句结构应该简单直接，语句不复杂化p 要对程序的所有输入数据检查其合法性，检查输 入项的各种重要组合的合理性，输入格式要简单， 输入允许默认值，输入一批数据后最好使用结束标 志，在交互式输入/输出中使用屏幕提示信息格式6 69.1.3 结构化程序设计结构化程序设计的原则u 自顶向下u 逐步求精u 模块化u 限制使用GOTO语 句主模块子模块2子模块1子模块3子模块21 子模块227 7结构化程序设计的基本结构与特点n 顺序结构

4、：按照程序语句行的自然顺序 ，一条语句一条语句的往后执行程序n 选择结构：又称分支结构，它根据设定 的条件，判断应该选择哪一条分支执行相 应的语句序列n 循环结构：又称重复结构，它根据给定 的条件，判断是否需要重复执行某一相同 的或相似的程序段9.1.3 9.1.3 结构化程序设计结构化程序设计8 8结构化程序设计的基本结构ABABA表达式A表达式表达式顺序结构选择结构循环结构循环结构TTTFFF9 9结构化程序设计的优点自顶向下逐步求精的方法符合人类解决复杂问题的普遍规律 ，可以显著提高软件开发的成功率和生产率先全局后局部、先整体后细节、先抽向后具体的逐步求精过 程开发出的程序有清晰的层次结

5、构，使程序容易阅读和理解使用单入口单出口控制结构而不使用GOTO语句，使得程序的 静态结构和它的动态执行情况一致控制结构有确定逻辑模式，编写程序代码只限于使用很少几 种直截了当的方式，使源程序清晰流畅，易读易懂而且容易 测试程序清晰和模块化使得在修改和重新设计一个软件时可以重 用的代码量最大程序的逻辑结构清晰，有利于程序正确性证明10109.1.4 面向对象的程序设计面向对象方法的主要特点： 从问题域中客观存在的事物出发来构造软件系 统，用对象作为对这些事物的抽象表示，并以 此作为系统的基本构成单位 事物的静态特征用对象的属性表示，动态特征 用对象的服务表示 对象的属性与服务结合为一个独立的实

6、体，对 外屏蔽其内部细节，称作封装 把具有相同属性和相同服务的对象归为一类， 类是这些对象的抽象描述，每个对象是它的类 的一个实例1111面向对象方法的主要特点： 通过在不同程度上运用抽象的原则，可以得到 较一般的类和较特殊的类 复杂的对象可以用简单的对象作为其构成部分 ，称为聚合 对象之间通过消息进行通信，以实现对象之间 的动态联系 通过关联表达对象之间的静态关系9.1.4 9.1.4 面向对象的程序设计面向对象的程序设计1212面向对象方法的概念面向对象：面向对象=对象+类+继承+通信如果一个软件系统是使用这样四 个概念设计和实现的，则认为这个软件 系统是面向对象的。面向对象的程序的 每一

7、组成部分都是对象，计算是通过建 立新的对象和对象之间的通信来执行的1313对 象对象是构成世界的一个独立单位，它具有自己 的静态特征和动态特征。 静态特征：指可以用某种数据来描述的特征 动态特征：指对象所表现的行为或对象所具有的 功能 定义：对象是系统中用来描述客观事物的一个实 体，它是构成系统的一个基本单位。一个对象 由一组属性和对这组属性进行操作的一组方法 构成。 属性：用来描述对象静态特征的一个数据项 方法：用来描述对象动态特征的一个操作序列1414消息和方法一个系统由若干个对象组成，各个对象之 间相互联系、相互作用。计算机系统中，消息就是对象之间的纽带 ，是用来通知、命令或请求对象执行

8、某个 处理或回答某些信息。消息可以是数据流，也可以是控制流。一条消息可以发送给不同的对象，而消息 的解释则完全由接收对象完成。不同的对 象对相同形式的消息可以有不同的解释1515类和实例n类和对象之间的关系 如同一个模具与 用这个模具铸造出来的铸件之间的关系。 类给出了属于该类的全部对象的抽象定义 ，而对象则是符合这种定义的一个实体。n一个对象又称为类的一个实例（Instance ）n类也可称作对象的模板（Template）1616继 承 性p定义：特殊类的对象拥有其一般类的 全部属性与方法，称作特殊类对一般类 的继承p继承关系是传递的p继承性对于软件重用有很大益处1717封 装 性封装具有两

9、个涵义： 一、是把对象的全部属性和全部方法结 合在一起，形成一个不可分割的独立 单位（即对象） 二、也称作“信息隐蔽”，即尽可能隐蔽 对象的内部细节，对外形成一个边界 ，只保留有限的对外接口使之与外部 发生联系1818多 态 性对象的多态性：指在一般类中定义的属性或方法被特 殊类继承之后，可以具有不同的数据类 型表现出不同的行为。这使得同一个属 性或方法名在一般类及其各个特殊类中 具有不同的语义19199.2 数据结构与算法u 算法u 数据结构的基本概念及术语u 线性表u 栈u 队列u 树与二叉树u 查找u 排序20209.2.1 算法p定义：是对特定问题求解步骤的一种 描述。或者说，是为求解

10、某问题而设计 的步骤序列p特征： 有穷性确定性有效性输入输出2121n例9.1 有黑和蓝两个墨水瓶，但却错把黑 墨水装在了蓝墨水瓶里，而蓝墨水错装在 了黑墨水瓶里，要求将其互换。9.2.1 算法1.将黑瓶中的蓝墨水装入白瓶中 ； 2.将蓝瓶中的黑墨水装入黑瓶中 ； 3.将白瓶中的蓝墨水装入蓝瓶中 ； 4.交换结束。2222n例9.2 计算函数M(x)的 值。函数M(x)为：bx+a2, xa 其中，a,b,c为常数。 9.2.1 算法M(x)=输入a,b,c,x值到计算机中X, 链式存储结构：2929 数据的运算p检索：在数据结构里查找满足一定条件的结 点。p插入：往数据结构里增加新的结点。p

11、删除：把指定的结点从数据结构里去掉。p更新：改变指定结点的一个或多个域的值。p排序：保持线性结构的结点序列里结点数不 变，把结点按某种指定的顺序重新排列。9.2.2 9.2.2 数据结构的基本概念及术语数据结构的基本概念及术语30309.2.3 线性表线性表是最常用的一种数据结构。线性表的 逻辑结构是n个数据元素的有限序列 （a1,a2,an）顺序表：指用顺序存储结构存储的线性表链表：用链式存储结构存储的线性表栈和队列：是对线性表的插入、删除运算可 以发生的位置加以限制的两种特 殊的线性表31311.顺序表和一维数组各种高级语言里的一维数组就是用顺序方式存储的 线性表，因此常用一维数组称呼顺序

12、表若顺序表中结点个数为n，则：插入一个结点平均需要移动之结点个数为n/2， 算法的时间复杂度是O(n)；删除一个结点平均需移动结点个数为（n-1）/2， 算法的时间复杂度是O(n)32322.链表n线性链表（单链表）：n插入算法的时间复杂度为O(n)，其主要执行时间是搜 索插入位置。n删除算法的时间复杂度为O(n)，其主要执行时间是搜 索删除位置。n循环链表：指链表的最后一个结点的指针值指向第 一个结点，整个链表形成一个环（如下图）结点1结点2结点n33339.2.4 栈 栈：是一种特殊的线性表，是限定仅在表尾进 行插入和删除运算的线性表，表尾称为 栈顶（top），表头称为栈底（bottom）

13、 。 空栈：指表中无元素p 栈中有元素a1,a2,an，如下页图所示，称a1为 栈底元素。新元素进栈要置于an之上，删除或退栈 先对an进行，即“后进先出”（LIFO）的操作原则p 栈的物理存储可以用顺序存储结构或链式存储结构p 栈的运算还有取栈顶元素，检查栈是否为空，清 除等。3434栈的插入和删除AB AC B AB AF E B A ATOPTOPTOPTOPTOPTOPan a2 a1进栈出栈栈底栈结构(3)(1)(2)(5)(4)(6)35359.2.5 队列n队列：是限定所有的插入都在表的一端 进行，所有的删除都在表的另一端进行的 线性表。进行删除的一端叫队列的头，进 行插入的一端

14、叫队列的尾，如下页图所示 。n 在队列中，新元素总是加入到队尾 ，每次删除的总是对头元素，即当前“最 老的”元素，这就是“先进先出”（FIFO ）的操作原则n队列的物理存储可以用：顺序存储结构，也可用链式存储结构3636队列的示意（如下图）出队列 a1 a2 a3 an 入队列头 尾3737队列的插入和删除示例初 态插 入 A插 入 B删 除 A插 入 C插 入 D删 除 B插 入 EF RAFRRRRRRFFFFFFBABBBCCCCDDD溢出38389.2.6 树与二叉树树形结构是一类重要的非线性结构，树和 二叉树是最常见的树形结构树（Tree）:是一个或多个结点组成的有限 集合T，有一个

15、特定的结点称为根（Root） ，其余的结点分为m（m0）个不相交的集 合T1，T2，Tm，每个集合又是一棵树 ，称作这个根的子树（Subtree)ABCDEFGHIJ3939树形结构的常用术语结点的度（Degree）：一个结点的子树的个数。树的度：树中各结点的度的最大值。树叶（Leaf）：度为0的结点。分支结点：度不为0的结点。双亲（Parent）、子女（Child）：结点的各子树 的根称作该结点的子女；相应的该结点称作其子女 的双亲。兄弟（Sibling）：具有相同双亲的结点互为兄弟 。结点的层数（Level）：根节点的层数为1。树的深度（Depth）:树中各节点的层的最大值。森林（Forest）:0棵或多棵不相交的树的集合。4040二 叉 树p二叉树（Binary Tree）:是n（n0)个结点的 有限集合，这个集合或者为空集（n=0），或者由 一个根结点及两棵不相交的、分别称作这个根的左 子树和右子树的二叉树组成二叉树不是树的特殊情形，二者的区别：二叉树为有序树p性质： 1、在二叉树的i层上，最多有2i-1个结点（i1） 2、 深度为k的二叉树最多有2k-1个结点(k1)4141完全二叉树p一棵深度为k且具有2k-1个结点的二叉树称为满二 叉树（Full Binary Tree ）p深度为k，有n个结点的二叉树，当且仅当其每一个 结点都与深度为k