大学信息技术基础：第6章 软件设计基础

《大学信息技术基础：第6章 软件设计基础》由会员分享，可在线阅读，更多相关《大学信息技术基础：第6章 软件设计基础（56页珍藏版）》请在装配图网上搜索。

1、第6章 软件设计基础n主要内容：l6.1 6.1 算法与程序算法与程序l6.2 6.2 数据结构数据结构l6.3 6.3 程序设计方法程序设计方法l*6.4 6.4 软件工程软件工程n本章小结n思考与练习n6.1.1 算法的基本概念l1.什么是算法u通俗点说，算法就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。u计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个具体的算法来实现。l2.算法的特征u（1）可行性针对实际问题设计的算法，人们总是希望能够得到满意的结果。6.1 算法与程序u（2）确定性算法的

2、确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。u（3）有穷性算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。u（4）输入通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。u（5）输出一个算法有一个或多个输出，以反映对输入数据加工后的结果。6.1 算法与程序n6.1.2 算法的表示l1.自然语言u自然语言是人们日常所用的语言，如汉语、英语、德语等。l2.传统流程图u流程图是描述算法的常用工具，可以很方便地表示顺序、选择和循环结构，因此流程图可以表

3、示任何程序的逻辑结构。u美国国家标准化协会ANSI规定了如下一组图形符号来表示算法。(见课本P144)6.1 算法与程序u例3 用传统流程图描述求1+2+3+100之和的算法。如图6-1所示。6.1 算法与程序图图6-1 传统流程图传统流程图l3.N-S图u主要特点是不带有流向线，整个算法完全写在一个大矩形框中，这种流程图被称为N-S图。N-S图特别适合于结构化程序设计。u图6-2给出了N-S图中各种基本的结构图框，其中(a)表示顺序结构，(b)表示选择结构，(c)表示当型循环结构，(d)表示直到型循环结构。6.1 算法与程序u例4 用N-S图描述求1+2+3+100之和的算法。如图6-3所示

4、。6.1 算法与程序l4.伪代码u伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。u例5 用伪代码描述求1+2+3+100之和的算法。Begin/*算法开始*/X=1 Y=2 while（Y=100）do/*循环执行，直到条件不成立为止*/XX+Y YY+1 Print X/*输出结果*/End/*算法结束*/6.1 算法与程序l5.计算机程序设计语言u因此用自然语言、流程图和伪代码等语言描述的算法最终还必须转换为具体的计算机程序设计语言编写的程序。u算法和程序是有区别的。算法是对解题步骤（过程）的描述，可以与计算机无关；而程序是利用某种计算机语言对算法的具体实现。n6.1

5、.3 算法设计的基本方法l1.列举法u列举法又称为穷举法或枚举法，其基本思想是：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。6.1 算法与程序l2.归纳法u归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。l3.递推法u所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。l4.递归法u这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，直至最终解决原问题，这就是递归的基本思想。u递归分为直接递归与间接递归两种。6.1 算法与程序

6、u递推与递归的实现方法是大不一样的，递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到达递归边界而后进行回归的。l5.分治法u所谓分治法，就是对问题分而治之。尽可能地把复杂问题分解为若干较小的问题，找出各个较小问题的解之后，再组合成整个问题的解。l6.回溯法u通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到了问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。6.1 算法与程序n6.1.4 算法的评价l1.正确性u正确性是指算法的执行结果应该满足预先规定的功能和性能要求。l2.可读性u一个算法应该思

7、路清晰、层次分明、简单明了、易读易懂。l3.健壮性u算法的健壮性指的是，算法应对非法输入的数据做出恰当反映或进行相应处理。l4.复杂性6.1 算法与程序u算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。u算法的复杂性有时间复杂性和空间复杂性之分。n6.1.5 程序与程序设计语言l1.程序u为需要求解的问题设计好的算法，用程序设计语言表达出来后，就得到程序。u计算机程序包含两方面的内容：对象及对象之间的关系；描述对这些对象进行处理的加工规则。l2.程序设计语言u程序设计是根据特定的问题，使用某种程序设计语言，设计计算机执行的指令序列。6.1 算法与程序u（1）机器语言u为编写计算机所能理

8、解的程序，人们最早使用的语言是机器语言。u（2）汇编语言u汇编语言是用助记符来表示每一条机器指令。u由汇编语言编写的源程序必须经过翻译转变成机器语言程序，计算机才能识别和执行。u（3）高级语言u高级语言同人类的自然语言和数学表达方式相当接近，其功能更强、可读性更好、编程也更加方便。u高级语言处理程序有编译程序和解释程序两种。6.1 算法与程序l3.程序与算法、数据结构之间的关系u算法是处理问题的方法和步骤，数据结构是算法要处理的数据构造的逻辑表示形式，最后问题的解由计算机程序给出。u程序的构成是和数据结构不可分割的。u算法思想决定了程序的质量和性能，好的算法可大大提高程序运行的效率，减少时间和

9、空间复杂性。u算法是建立在数据结构基础上的，未确定对数据如何操作就无法决定如何构造数据。6.1 算法与程序图图6-5 编译型语言处理程序功能示意图编译型语言处理程序功能示意图n数据结构主要研究和讨论以下3个方面的问题：l数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。l在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。l对各种数据结构进行的运算。n6.2.1 数据结构的基本概念l 1.数据u数据是描述客观事物的所有能输入到计算机中并被计算机程序处理的符号的总称。6.2 数据结构l2.数据元素u数据元素是数据的基本单位，在计算机中通常作为一个整体加以考虑和处理。u

10、作为某种处理，其中的数据元素一般具有某种共同特征。l3.数据对象u数据对象是性质相同的数据元素的集合，是数据的一个子集。l4.数据类型u数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称。6.2 数据结构l5.数据结构u数据结构是指相互之间存在着一定关系的数据元素的集合以及定义在其上的操作。u（1）数据的逻辑结构u所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。u在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前件与后件关系来描述。u一个数据结构可以

11、用二元组表示，也可以直观地用图形表示。6.2 数据结构u在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的圆表示，一般称之为数据结点，简称为结点。u例6-8和例6-9的数据结构可以用图形来表示，如图6-6和图6-7所示。u在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点。6.2 数据结构图图6-6 一年四季数据结构的图形表示一年四季数据结构的图形表示图图6-7 家庭成员关系数据结构的图形表示家庭成员关系数据结构的图形表示u（2）数据的存储结构u数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。u为了表示存放在计算机存储空间中的各数据元素之间

12、的逻辑关系，在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接和索引等。u（3）对数据结构中数据元素的操作u为了在计算机上解决具体问题，数据结构的研究内容为如何表示数据、如何组织数据，以及如何对它们进行操作。u以下给出对数据结构中数据元素的几个基本操作：6.2 数据结构插入删除 更新查找排序遍历l6.线性结构与非线性结构u根据数据结构中各数据元素之间前后件关系，一般将数据结构分为两大类型：线性结构与非线性结构。6.2 数据结构6.2 数据结构n6.2.2 线性结构l1.线性表u

13、（1）线性表的概念u这些数据元素之间除了在表中的排列次序即先后次序不同外，没有其他的联系，这一类的表属于线性表。u从数据结构的角度出发，线性表是n（n0）个数据元素组成的有限序列，记为：（al，a2，an）u（2）线性表的存储结构u在计算机中存储线性表，最简单的方法是顺序存储。u线性表的顺序存储结构具有以下两个基本特点：6.2 数据结构u线性表中所有元素所占的存储空间是连续的。u线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。l2.栈u栈（stack）实际上也是线性表，它是一种限定只在线性表的一端进行插入与删除操作的特殊的线性表。u在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除

14、的另一端称为栈底。u如图6-8所示，即栈是按照“先进后出”或“后进先出”的原则组织数据的。u往栈中插入一个元素称为入栈运算，从栈中删除一个元素称为出栈运算。6.2 数据结构l3.队列u队列（Queues）也是一种操作受限的线性表，要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。图图6-8 栈的示意图栈的示意图u队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。u在计算机系统中，队列的思想常用于操作系统的资源调度。l4.线性链表u在链式存储方式中，要求每个结点由两部分组成，一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针

15、域。6.2 数据结构图图6-9 具有具有6个元素的队列示意图个元素的队列示意图6.2 数据结构u在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。u链式存储方式既可用于表示线性结构，也可用于表示非线性结构。u在线性链表中，用一个专门的指针Head指向线性链表中第一个数据元素的结点。6.2 数据结构n6.2.3 非线性结构l1.树形结构u树（Tree）是一种重要的非线性数据结构，在这类结构中，元素之间存在着明显的分支和层次关系。6.2 数据结构图图6-13 学校行政关系结构树学校行政关系结构树6

16、.2 数据结构u（1）树的定义树是由一个或多个结点组成的有限集合，如图6-14所示。树结构的特点是：必有一个特定的称为根的结点，根的每个分支称为子树，子树也是一棵树。图图6-14 树型结构树型结构 图图6-15 两棵不同的二叉树两棵不同的二叉树u（2）二叉树二叉树的特点是：树中的每个结点最多只有两棵子树。二叉树的子树有左右之分，称为左子树和右子树。而且子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清楚。例如图6-15是两棵不同的二叉树。u（3）二叉树的遍历所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。树的遍历实质上是将二叉树

17、的各个结点转换成为一个线性序列来表示。二叉树的遍历可分为先序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。6.2 数据结构l2.图形结构u“图”（Graph）是图形结构的简称。u图结构与表结构、树结构的不同之处表现在结点之间的关系上，图是一种更为复杂的数据结构。在图中，任意两个元素中均有可能相关。u一个图由有限的顶点（Vertices）和边（Edge）组成，所以可形式化地用G（V，E）代表一个图。u图6-16中的每一个小圆圈代表图的一个顶点，这个图有4个顶点，顶点之间有5条边。因为图中的边都没有方向箭头，只是表示顶点间的关系，所以称为“无向图”。图6-17当然就应该称作“有向图”了。

18、6.2 数据结构6.2 数据结构图图6-16 无向图无向图 图图6-17 有向图有向图n6.3.1 程序设计的一般过程l1.问题描述u程序设计的最终目的是为了利用计算机求解某一特定问题，因此程序设计面临的首要任务是得到问题的完整和确切的定义。l2.算法设计u解题过程都是由一定的规则、步骤组成的，这种规则就是算法。u为了描述算法，可以使用多种方法。常用的有自然语言、传统流程图、NS流程图、伪代码和计算机语言等。l3.代码编制6.3 程序设计方法u问题定义和算法描述已经为程序设计规划好了蓝本，下一步就是用真正的计算机语言表达了。u有人说代码编制的过程是算法到计算机语言程序的翻译过程。l4.调试运行

19、u通过“编译程序”或“解释程序”使人们编写的程序能够最终得到执行的工作方式，称为程序的编译方式和解释方式。u编译方式是指将用高级语言编写好的程序，经编译程序翻译，形成可由计算机执行的机器指令程序的过程。u解释方式则是将用高级语言编写好的程序逐条解释，解释一句立即执行一句，然后再解释下一句。l5.编写程序文档6.3 程序设计方法u文档记录程序设计的算法、实现以及修改的过程，保证程序的可读性和可维护性。n6.3.2 结构化程序设计l1.结构化程序的基本结构与设计思想u按照结构化程序设计的观点，任何算法功能都可以通过由程序模块组成的三种基本程序结构（即顺序结构、选择结构和循环结构）的组合来实现。u结

20、构化设计思想是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块（图6-18），一个模块可以是一条语句、一段程序、一个函数等。u按照结构化设计方法设计出的程序具有结构清晰、可读性好、易于修改和容易验证的优点。6.3 程序设计方法6.3 程序设计方法图图6-18 结构化设计思想是以模块化设计为中心结构化设计思想是以模块化设计为中心l2.结构化程序设计的基本原则u结构化程序设计的基本原则是采用“自顶向下，逐步求精”的程序设计方法和“单入口单出口”的控制结构，并限制使用goto语句，因为会破坏程序的结构化，降低程序的可读性。u首先从问题本身开始，找出解决问题的基本思路，并将其用结构化框

21、图表示出来。u其次对框图中的那些比较抽象的、用文字描述的程序模块做进一步的分析细化，每次细化的结果仍用结构化框图表示。u最后，对如何求解问题的所有细节都弄清楚了，便可以根据这些框图直接写出相应的程序代码。6.3 程序设计方法u先进行“顶层设计”，如图6-19所示，把要做的三部分工作分别用A、B、C表示。u这三部分还不够具体，要进一步细化。A部分可以细化为如图6-20所示。先输入n，然后将1输入给x1，2输入给x2，1000输入给X1000。B部分可以细化为如图6-21所示。6.3 程序设计方法图图6-19 顶层设计流程图顶层设计流程图 图图6-20 对对A的细化的细化u图6-20中的B1与B2

22、不能再分了。B1处理的方法是：使x1=0，即哪个数不是素数，就使它等于0，以后把不等于0的数打印出来就是所求的素数表。B3中的循环体内以D标志的部分还要进一步细化，对D细化为如图6-22所示。6.3 程序设计方法图图6-21 对对B的细化的细化 图图6-22 对对D的细化的细化u图6-22中的E部分还不够具体，再进一步细化为如图6-23所示。u图6-23中的F部分又细化为如图6-24所示。因为首先要判断某一个xj是否已被去掉，如已被去掉则不必考虑被xi除。至此，已不能也不需要再分解了。6.3 程序设计方法图图6-23 对对E的细化的细化 图图6-24 对对F的细化的细化u再对图6-19中的C部

23、分进行细化，如图6-25所示。u对图6-25中的G部分进行细化，如图6-26所示。u至此，已将图6-19分解成为最基本的操作了，将以上这些图合起来就得到了总的流程图。6.3 程序设计方法图图6-25 对对C的细化的细化 图图6-26 对对G的细化的细化n6.3.3 面向对象程序设计l结构化程序设计方法虽已得到了广泛的使用，但有两个问题仍未得到很好的解决。u一是结构化程序设计主要是面向过程的，模块分割主要针对控制流，仍然还含有与人的思维方式不协调的地方。u二是该方法在实现中只突出了实现功能的操作方法，而被操作的数据处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起。l面向对象的分解突

24、出真实世界和抽象的对象，考虑的是做什么（What to do）。它将大量的工作由相应的对象来完成，程序员在应用程序中只需说明要求对象完成的任务。6.3 程序设计方法l面向对象的程序设计给软件的发展带来了以下益处：u（1）符合人们习惯的思维方法，便于分析复杂而多变的问题。u（2）易于软件的维护和功能的增减。u（3）可重用性好，能用继承的方式减少程序开发所花的时间。u（4）与可视化技术相结合，改善了工作界面。6.3 程序设计方法l1.面向对象的一些基本概念l（1）类（class）u类是创建对象实例的模板，是同种对象的集合与抽象，它包含所创建对象的属性描述和行为特征的定义。l（2）对象（object

25、）u对象是面向对象程序设计的核心。u在面向对象的程序设计中，对象的概念就是对现实世界中实体的模型化（图6-27），它是代码和数据的组合，同样具有自己的状态和行为。u 属性属性用来表示对象的特性。6.3 程序设计方法u 方法方法是对对象的各种操作。6.3 程序设计方法图图6-27 对象的概念就是对现实世界中实体的模型化对象的概念就是对现实世界中实体的模型化u 事件对象的事件是指由系统事先设定的、能被对象识别和响应的动作。事件过程：当在对象上发生了事件后，应用程序就要处理这个事件，而处理的步骤就是事件过程。事件驱动：在传统的面向过程的应用程序中，应用程序自身控制了代码的执行顺序，即代码的执行是从第

26、一行开始，随着程序流程执行代码的不同部分。l2.面向对象程序设计的特点u（1）抽象抽象就是忽略一个主题中与当前目标无关的那些方面，以便更充分地注意与当前目标有关的方面。面向对象的软件设计而言，抽象包括两个方面，一是数据抽象，二是行为（操作与方法）抽象。6.3 程序设计方法u（2）封装将数据（属性）和操作数据的过程（方法）衔接起来，构成一个具有类的对象的描述称为封装。封装一方面通过数据抽象，把相关信息结合在一起，另一方面简化了接口。封装保证了模块具有较好的独立性，使得程序维护修改较为容易。u（3）继承表示类之间相似性的机制。也就是可以从一个类生成另一个类，派生类（也称子类）继承了父类和祖先类的数

27、据和操作。u（4）多态性多态性是指同一命名方法提供了多态性结果，也就是当同样的消息被不同的对象接受时，导致完全不同的行为。6.3 程序设计方法n本章论述的主要内容以“数据结构+算法=程序”为主线展开。算法是求解问题的方法和步骤。构成算法有两个要素，即基本操作和控制结构。算法要在计算机上实现，必须转化为某种计算机语言描述的程序。高级程序设计语言都提供有描述算法控制结构的三种基本结构和完成操作的各种语句，同时也提供各种数据类型供程序设计人员组织程序中的数据。但任何语言所提供的数据类型都是有限的，远远不能满足实际问题求解的需要，因此我们需要研究数据结构，以便合理有效地组织实际问题涉及的全部数据并交给

28、程序处理。本章小结n数据结构主要研究数据的逻辑结构、数据的存储结构以及对数据结构中数据元素的操作。数据结构分为线性结构（线性表、栈、队列等）与非线性结构（树、图等）两大类，在解决实际问题时选择合适的数据结构，可以把用户从数据存储细节（如存储单元和地址）中解脱出来，以更方便有效的方法访问数据。程序设计就是把算法和数据结构融为一体，用最少的代价开发出最好的程序的技术和方法学。常用的程序设计方法主要有结构化程序设计、面向对象技术、软件工程方法等。程序编制完毕，需要调试程序和测试程序，以发现程序中的错误并纠正之。本章小结n一、思考题l1.什么是算法？算法的特征和基本设计方法有哪些？l2.请给出表示算法

29、的几种基本方法。l3.什么是数据的逻辑结构？什么是数据的存储结构？数据的逻辑结构包含哪两个要素？l4.什么是线性表？什么是栈？栈和队列的区别是什么？l5.什么是树？什么是二叉树？二叉树有哪些遍历方式？l6.非线性数据结构中，树结构与图结构有何区别？l7.请结合日常生活的观察与经验，列举出下列结构的例子来：l列表堆栈队列树l8.请图示说明组成程序模块的三种基本程序结构。l9.简述进行程序设计的一般步骤。l10.简述程序、数据结构及算法三者之间的关系。l11.计算机能不能直接执行高级语言程序？为什么？l12.什么是结构化程序设计方法？思考与练习l12.什么是类？什么是对象？什么是对象的属性、方法和

30、事件？l13.面向对象程序设计的特点是什么？l*14.软件生命周期包含哪几个阶段？l*15.软件的开发模型主要有哪些？l*16.什么是软件测试？什么是静态测试和动态测试？什么是白盒测试和黑盒测试？n二、练习与实践l1.早在公元前300年左右出现的著名的“欧几里得算法”，就描述了求解两个整数的最大公因子的解题步骤。要求解的问题描述为：“给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大整数”。l请用自然语言、形式化语言或程序流程图描述欧几里得算法的求解步骤。l2.汉诺塔问题l汉诺塔问题源自于印度神话。l传说上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着6

31、4片黄金圆盘。思考与练习 上帝命令婆罗门（婆罗门是祭司贵族。它主要掌握神权,占卜祸福）把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。l有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。汉诺塔问题在数学算法方面有很高的研究价值，而且至今还在被一些数学家们所研究，因此让我们逻辑性地思考一下汉诺塔与宇宙寿命关系。l为使问题简单一些，我们将问题简化成汉诺塔上有3个圆盘，那么从A柱的圆盘移动到B柱上的过程如图(见下页)所示：l考虑如果汉诺塔上有4个圆盘，需要移动多少次？请画出移动步骤。l考虑如果汉诺塔上有64个圆盘，移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，需要多少时间？l（提示：当汉诺塔有n个圆盘的时候，移动次数为2的n次方减1，n=64的时候是即需要移动264-1次）思考与练习思考与练习