程序设计与软件工程基础讲义

《程序设计与软件工程基础讲义》由会员分享，可在线阅读，更多相关《程序设计与软件工程基础讲义（69页珍藏版）》请在金锄头文库上搜索。

1、第九章 程序设计与软件工程基础,主要内容,9.1 程序设计基础9.2 数据结构和算法9.3 软件工程基础,9.1 程序设计基础,程序设计语言发展程序设计方法与风格结构化程序设计面向对象程序设计,程序设计,指令：能被计算机直接识别与执行的指示计算机进行某种操作的命令，CPU每执行一条指令，就完成一个基本运算。程序：指令的序列即让计算机解决某一问题而写出的一系列指令。程序设计：编写程序的过程。程序设计语言：用于描述计算机所执行的操作语言。,9.1.1 程序设计语言发展,机器语言：采用计算机指令格式并以二进制编码表达各种操作的语言。汇编语言：一种符号语言，采用助记符来表达指令功能。高级语言：是一种面

2、向问题的语言。第四代语言：是非过程化语言。,9.1.2 程序设计方法与风格,良好程序设计风格的侧重于：源程序文档如使用的符号名应具有一定的含义，以便对程序功能的理解；对源程序适当的进行注解，以便读者理解程序；在程序中利用空格、空行、缩进等技巧使程序层次清楚；对程序中的数据进行适当说明；程序中的语句结构应该简单直接，语句不复杂化；要对程序的所有输入数据检查其合法性，检查输入项的各种重要组合的合理性，输入格式要简单，输入允许默认值，输入一批数据后最好使用结束标志，在交互式输入/输出中使用屏幕提示信息格式。,9.1.3 结构化程序设计,结构化程序设计的原则:自顶向下逐步求精模块化限制使用GOTO语句

3、,顺序结构：按照程序语句行的自然顺序，一条语句一条语句的往后执行程序。选择结构：又称分支结构，它根据设定的条件，判断应该选择哪一条分支执行相应的语句序列。循环结构：又称重复结构，它根据给定的条件，判断是否需要重复执行某一相同的或相似的程序段。,结构化程序设计的基本结构与特点,结构化程序设计的优点,自顶向下逐步求精的方法符合人类解决复杂问题的普遍规律，可以显著提高软件开发的成功率和生产率； 先全局后局部、先整体后细节、先抽向后具体的逐步求精过程开发出的程序有清晰的层次结构，使程序容易阅读和理解； 使用单入口单出口控制结构而不使用GOTO语句，使得程序的静态结构和它的动态执行情况一致； 控制结构有

4、确定逻辑模式，编写程序代码只限于使用很少几种直截了当的方式，使源程序清晰流畅，易读易懂而且容易测试； 程序清晰和模块化使得在修改和重新设计一个软件时可以重用的代码量最大； 程序的逻辑结构清晰，有利于程序正确性证明。,9.1.4 面向对象的程序设计,面向对象方法的主要特点： 从问题域中客观存在的事物出发来构造软件系统，用对象作为对这些事物的抽象表示，并以此作为系统的基本构成单位； 事物的静态特征用对象的属性表示，动态特征用对象的服务表示； 对象的属性与服务结合为一个独立的实体，对外屏蔽其内部细节，称作封装； 把具有相同属性和相同服务的对象归为一类，类是这些对象的抽象描述，每个对象是它的类的一个实

5、例；,通过在不同程度上运用抽象的原则，可以得到较一般的类和较特殊的类； 复杂的对象可以用简单的对象作为其构成部分，称为聚合； 对象之间通过消息进行通信，以实现对象之间的动态联系； 通过关联表达对象之间的静态关系。,面向对象方法的主要特点（续）：,面向对象方法的概念,面向对象：面向对象=对象+类+继承+通信如果一个软件系统是使用这样四个概念设计和实现的，则认为这个软件系统是面向对象的。面向对象的程序的每一组成部分都是对象，计算是通过建立新的对象和对象之间的通信来执行的。,对 象,对象是构成世界的一个独立单位，它具有自己的静态特征和动态特征。 静态特征：指可以用某种数据来描述的特征。 动态特征：指

6、对象所表现的行为或对象所具有的功能。 定义：对象是系统中用来描述客观事物的一个实体，它是构成系统的一个基本单位。一个对象由一组属性和对这组属性进行操作的一组方法构成。 属性：用来描述对象静态特征的一个数据项。 方法：用来描述对象动态特征的一个操作序列。,消息和方法,一个系统由若干个对象组成，各个对象之间相互联系、相互作用。计算机系统中，消息就是对象之间的纽带，是用来通知、命令或请求对象执行某个处理或回答某些信息。消息可以是数据流，也可以是控制流。一条消息可以发送给不同的对象，而消息的解释则完全由接收对象完成。不同的对象对相同形式的消息可以有不同的解释。,类和实例,类和对象之间的关系 如同一个模

7、具与用这个模具铸造出来的铸件之间的关系。类给出了属于该类的全部对象的抽象定义，而对象则是符合这种定义的一个实体。 一个对象又称为类的一个实例（Instance） 类也可称作对象的模板（Template）,继 承 性,定义：特殊类的对象拥有其一般类的全部属性与方法，称作特殊类对一般类的继承。 继承关系是传递的。 继承性对于软件重用有很大益处。,封 装 性,封装具有两个涵义： 一、是把对象的全部属性和全部方法结合在一起，形成一个不可分割的独立单位（即对象）。 二、也称作“信息隐蔽”，即尽可能隐蔽对象的内部细节，对外形成一个边界，只保留有限的对外接口使之与外部发生联系。,多 态 性,对象的多态性：指

8、在一般类中定义的属性或方法被特殊类继承之后，可以具有不同的数据类型表现出不同的行为。这使得同一个属性或方法名在一般类及其各个特殊类中具有不同的语义。,9.2 数据结构与算法,算法数据结构的基本概念及术语线性表栈队列树与二叉树查找与排序,9.2.1 算法,定义：是对特定问题求解步骤的一种描述。或者说，是为求解某问题而设计的步骤序列。 特征： 有穷性确定性有效性零个或多个输入一个或多个输出,算法复杂度,评价一个算法优劣的主要标准是：算法的执行效率与存储需求 算法的效率：指的是时间复杂度（Time Complexity） 存储需求：指的是空间复杂度（Space Complexity ）一般情况下，算

9、法中的基本操作重复操作执行的次数是问题规模n的某个函数f(n),算法的时间复杂度记做 T(n)=O(f(n),9.2.2 数据结构的基本概念及术语,数据与数据结构 数据: 是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合。 数据元素: 是数据的基本元素，即数据集合中的个体。 数据项: 具有独立意义的最小数据单位。 数据对象: 具有相同特性的数据元素的集合，是数据的子集。 结构: 被计算机加工的数据元素之间存在的关系。 数据结构: 带有结构特性的数据元素的集合。,数据的逻辑结构,集合线性结构树形结构图状或网状结构,数据的存储结构,一、顺序存储结构 主要特点：结点

10、中只有自身信息域，没有连接信息域，因此存储密度大，存储空间利用率高；可以通过计算直接确定数据结构中第i个结点的存储地址Li，计算公式：L0+（i-1）m。（其中L0为第一个结点的存储地址，m为每个结点所占用的存储单元个数；插入、删除运算不便，会引起大量结点的移动。,二、链式存储结构,主要特点：结点中除自身信息之外，还有表示连接信息的指针域，因此比顺序存储密度小，存储空间利用率低；逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示；插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。,数据的运算,检索：在数据结构里查找满足一定条件的结点插入：往数据结构里增

11、加新的结点删除：把指定的结点从数据结构里去掉更新：改变指定结点的一个或多个域的值排序：保持线性结构的结点序列里结点数不变，把结点按某种指定的顺序重新排列,9.2.3 线性表,线性表是最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列。 （a1，a2，an）顺序表：指用顺序存储结构存储的线性表。链表：用链式存储结构存储的线性表。栈和队列：是对线性表的插入、删除运算可以发生的位置加以限制的两种特殊的线性表。,顺序表和一维数组,各种高级语言里的一维数组就是用顺序方式存储的线性表，因此常用一维数组称呼顺序表。 若顺序表中结点个数为n，则：插入一个结点平均需要移动之结点个数为 n/2，算法的

12、时间复杂度是O(n)；删除一个结点平均需移动结点个数为 （n-1）/2，算法的时间复杂度是O(n)。,链 表,线性链表（单链表）：删除算法的时间复杂度为O(n)，其主要执行时间是搜索删除位置。循环链表：指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环（如下图）。,9.2.4 栈,栈：是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。 空栈：指表中无元素。栈中有元素a1,a2,an，如下页图所示，称a1为栈底元素。新元素进栈要置于an之上，删除或退栈先对an进行，即“后进先出”（LIFO）的操作原则;栈的物理存储可以

13、用顺序存储结构或链式存储结构;栈的运算还有取栈顶元素，检查栈是否为空，清除等。,栈的插入和删除,TOP,TOP,TOP,TOP,TOP,TOP,进栈,出栈,栈底,栈结构,(3),(1),(2),(5),(4),(6),9.2.5 队列,队列：是限定所有的插入都在表的一端进行，所有的删除都在表的另一端进行的线性表。进行删除的一端叫队头，进行插入的一端叫队尾，如下页图所示。在队列中，新元素总是加入到队尾，每次删除的总是对头元素，即当前“最老的”元素，这就是“先进先出”（FIFO）的操作原则。 队列的物理存储可以用：顺序存储结构，也可用链式存储结构,队列的示意图,出队列 a1 a2 a3 an 入队

14、列头 尾,队列的插入和删除示例,初态,插入A,插入B,删除A,插入C,插入D,删除B,插入E,F,R,A,F,R,R,R,R,R,R,F,F,F,F,F,F,B,A,B,B,B,C,C,C,C,D,D,D,溢出,9.2.6 树与二叉树,树形结构是一类重要的非线性结构，树和二叉树是最常见的树形结构。树（Tree）:是一个或多个结点组成的有限集合T，有一个特定的结点称为根（Root），其余的结点分为m（m0）个不相交的集合T1，T2，Tm，每个集合又是一棵树，称作这个根的子树（Subtree)。,树形结构的常用术语,结点的度（Degree）：一个结点的子树的个数。树的度：树中各结点的度的最大值。树

15、叶（Leaf）：度为0的结点。分支结点：度不为0的结点。双亲（Parent）、子女（Child）：结点的各子树的根称作该结点的子女；相应的该结点称作其子女的双亲。兄弟（Sibling）：具有相同双亲的结点互为兄弟。结点的层数（Level）；树的深度（Depth）森林（Forest）,二 叉 树,二叉树（Binary Tree）:是n（n0)个结点的有限集合，这个集合或者为空集（n=0），或者由一个根结点及两棵不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树是树的特殊情形，二者的区别：二叉树为有序树。 性质： 1、在二叉树的i层上，最多有2i-1个结点（i1） 2、深度为k的二叉树最

16、多有2k-1个结点(k1),完全二叉树,一棵深度为k且具有2k-1个结点的二叉树称为满二叉树（Full Binary Tree）。深度为k，有n个结点的二叉树，当且仅当其妹一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。,树的二叉树表示,在树（森林）与二叉树间有一个自然的一一对应的关系，每一棵树都能唯一的转换到它所对应的二叉树。把树和森林转化成对应的二叉树：凡是兄弟就用线连起来，然后去掉双亲到子女的连线，只留下道第一个子女的连线不去掉。,二叉树的存储,二叉树的存储通常采用:链接方式。每个结点除存储结点自身的信息外再设置两个指针域IIink和rlink，分别指向结点的左子女和右子女，当结点的某个指针为空时，则相应的指针值为空（NIL）。 结点的形式为：,二叉树的遍历,遍历一个树形结构是指：按一定次序系统的访问该结构中的所有结点，使每个结点恰好被访问一次。 前序遍历法（NLR次序）访问根，按前序遍历左子树，按前序遍历右子树。 后序遍历法（LRN次序）按后序遍历左子树，按后序遍历右子树，访问根。 中序遍历法（LNR次序）按中序遍历左子树，访问根，按中序遍历右子树。,