大学计算机基础教程（第三版）课件第7章 程序设计基础.ppt

1、第7章 程序设计基础第7章 程序设计基础第7章 程序设计基础本章学习要求掌握逐步求精的结构化程序设计方法掌握基本数据结构及其操作掌握算法的基本概念及基本排序和查找算法掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力掌握数据库的基本知识，了解关系数据库的设计2第7章 程序设计基础本章大纲本章大纲7.1程序设计基本概念7.2软件工程基础7.3数据结构基础7.4 思维与算法7.5 数据库设计基础3第7章 程序设计基础7.17.1程序设计基本概念程序设计基本概念初始程序程序设计方法程序设计语言412/23/2023第7章 程序设计基础7.2软件工程基础7.2.1 软件工程的基本概念7.2

2、.2 软件开发过程7.2.3 结构化分析方法7.2.4 结构化设计方法7.2.5 软件测试第7章 程序设计基础7.1.17.1.1初始程序初始程序1程序计算机程序或者软件程序（简称程序）是指一组指示计算机每一步动作的指令，用某种程序设计语言编写，运行于某种目标体系结构上。2程序设计6第7章 程序设计基础7.1.27.1.2程序设计方法程序设计方法1程序设计方法结构化程序设计方法面向对象的程序设计方法2.程序设计风格主要应注重和考虑以下几个因素：源程序文档化；数据说明方法化；语句的结构；输入和输出。712/23/2023第7章 程序设计基础7.1.3 程序设计语言第一代 机器语言第二代 汇编语言

3、第三代 高级语言第四代 非过程化语言12/23/2023第7章 程序设计基础7.2.1 软件工程的基本概念1软件的定义软件（software）是与计算机系统操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据的集合。2软件的特点3软件危机与软件工程12/23/2023第7章 程序设计基础7.2.2 软件开发过程图7-3 软件开发过程图12/23/2023第7章 程序设计基础7.2.3 结构化分析方法需求分析软件需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。结构化分析方法结构化分析方法结构化分析的常用工具软件需求规格说明书12/23/2023第7章 程序设计基

4、础7.2.4 结构化设计方法1软件设计的基本概念软件设计的基础软件设计的基本原理结构化设计方法2概要设计概要设计的任务包括：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审。面向数据流的设计方法结构化设计的准则3详细设计常用的设计工具有：图形工具：程序流程图，N-S，PAD，HIPO；表格工具：判定表；语言工具：PDL（伪码）。12/23/2023第7章 程序设计基础7.3数据结构基础7.3.1 数据结构的概念7.3.2 线性表7.3.3 栈和队列7.3.4 树与二叉树12/23/2023第7章 程序设计基础7.2.5 软件测试1软件测试的目的及准则包括需求定义阶段的

5、需求测试、编码阶段的单元测试、集成测试以及其后的确认测试、系统测试，验证软件是否合格、能否交付用户使用等。2软件测试技术和方法综述静态测试与动态测试白盒测试方法与测试用例设计黑盒测试方法与测试用例设计软件测试的实施软件测试的实施过程主要有4个步骤：单元测试、集成测试、系统测试、验收测试。12/23/2023第7章 程序设计基础7.3.1 数据结构的概念数据结构的含义数据结构是数据的组织，存储和运算的总和。它是信息的一种组织方式，是以数据按某种组织关系起来的一批数据，其目的是为了提高算法的效率，然后用一定的存储方式存储到计算机中，并且它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中

6、的数据进行某种操作。数据结构的基本术语数据数据元素数据对象数据结构数据的逻辑结构l数据的逻辑结构l数据的逻辑结构l数据的存储结构l数据类型l抽象数据类型12/23/2023第7章 程序设计基础7.3.2 线性表线性表的逻辑结构线性表是由 n(n=0)个具有相同性质的数据元素组成的有限序列。记为：List =(a0,a1,a2.,an)线性表的运算线性表的顺序表示及实现线性表在计算机内的存储结构一般有两种方式：一种是顺序（静态）存储一种是链式（动态）存储。12/23/2023第7章 程序设计基础7.3.3 栈和队列1栈（1）栈的定义12/23/2023第7章 程序设计基础（2）栈的顺序存储一般地

7、说，栈有两种实现方法：顺序存储和链接存储，12/23/2023第7章 程序设计基础其中：（a）表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶指针Top=0。此时如果作退栈运算，则产生“下溢”。（b）表示栈中只含一个元素A，在（a）基础上用进栈运算PUSH（sq，A），可以得到这种状态。此进栈顶指针Top=1。（c）表示在（b）基础上又有二个B，C先后进栈，此进栈顶指针Top=3。（d）表示在（c）状态下栈顶元素C退栈，这可执行一次POP（sq）运算得到。此时（新）栈顶指针Top=2。故B为当前的栈顶元素（注意，数据元素C虽并未擦去，但已不起作用）。（e）表示栈中有5个元素，这种状态可在

8、（d）的基础上通过连续执行PUSH（sq，D），PUSH（sq，E），PUSH（sq，F）得到。这种状态称为栈满。如果此时再作进栈运算，由于栈中已无空闲空间，因而发生“上溢”。12/23/2023第7章 程序设计基础2队列（1）队列的定义包括5种基本运算：队列初始化INIQUEUE（Q）、入队列INQUEUE（Q，X）、出队列OUTQUEUE（Q）、判队列空EMPTY（Q）、读队头GETHEAD（Q）。（2）队列的顺序实现两种实现方法，即顺序实现和链接实现。12/23/2023第7章 程序设计基础7.3.4 树与二叉树树的定义树是n（n0）个结点的有穷集合，满足：有且仅有一个称为根的结点；其余

9、结点分为m(m0)个互不相交的非空集合T1，T2，.，Tm，这些集合中的每一个都是一棵树，称为根的子树。12/23/2023第7章 程序设计基础2二叉树（1）二叉树的定义二叉树是n(n=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树，且互不相交的二叉树构成。（2）二叉树的特点每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。12/23/2023第7章 程序设计基础（3）满二叉树和完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。特点：每一层上的结点数都是最大结点数，第层上有2k-1个结点；深

10、度为的满二叉树有2m-1个结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1。12/23/2023第7章 程序设计基础（4）二叉树的主要性质 在二叉树的第 i 层上至多有2i-1 个结点。(i1)深度为 k 的二叉树上至多含 2k-1 个结点（k1）。对任何一棵二叉树，度为0的叶子结点总是比度为 2 的结点多一个，则必存在关系式：n0=n2+1。12/23/2023第7章 程序设计基础（5）二叉树的遍历二叉树的遍历有三种

11、方式，如下：前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。中序遍历（LDR），首先遍历左子树，然后访问根结点，最后右子树。简记左-根-右。后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。12/23/2023第7章 程序设计基础7.4 思维与算法7.4.1计算思维的内容7.4.2计算思维的特性7.4.3 算法的思想7.4.4 算法的概念和复杂度7.4.5 查找技术12/23/2023第7章 程序设计基础7.4.1计算思维的内容计算思维是一种递归思维它是并行处理。它是把代码译成数据又把数据译成代码。它是由广义量纲分析进行的类

12、型检查。对于别名或赋予人与物多个名字的做法，它既知道其益处又了解其害处。对于间接寻址和程序调用的方法，它既知道其威力又了解其代价。它评价一个程序时，不仅仅根据其准确性和效率，还有美学的考量，而对于系统的设计，还考虑简洁和优雅。12/23/2023第7章 程序设计基础7.4.2计算思维的特性1根本的，不是刻板的技能2是人的，不是计算机的思维方式3数学和工程思维的互补与融合4是思想，不是人造物12/23/2023第7章 程序设计基础7.4.3 算法的思想算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。从熟悉的问题出发，体会算

13、法的程序化思想，学会用自然语言来描述算法。算法的特征包括：有穷性确切性输入输出 可行性12/23/2023第7章 程序设计基础7.4.4 算法的概念和复杂度算法的定义广义地说，算法就是为解决问题而采取的步骤和方法，在程序设计中，算法是在有限步骤内求解某一问题所使用的一组定义明确的指令序列，通俗的讲算法，就是计算机解题的过程。每条指令表示一个或多个操作。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法，前者是算法实现的逻辑推理，后者是算法实现的具体操作。算法的表示为了表示一个算法，可以用多种不同的应运实现。常用的有自然语言，传统流程图，结构化流程图，N-S图，伪代码，计算机语言表

14、示法等。12/23/2023第7章 程序设计基础算法的时间复杂度分析 算法运算时间的度量 事后统计方法事前分析估算方法算法运行时间的分析规则 算法的空间复杂度分析 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用的存储空间主要分为三部分：算法源代码本身占用的存储空间、算法输入输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。12/23/2023第7章 程序设计基础7.4.5 查找技术1顺序查找一般是在线性表中查找指定的元素。基本操作方法是：从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素均查找完毕后都

15、不相等，则该元素在指定的线性表中不存在。顺序查找的最好情况是要查找的元素在线性表的第一个元素，则查找效率最高；最差情况是如果要查找的元素在线性表的最后或根本不存在，则查找需要搜索所有的线性表元素。12/23/2023第7章 程序设计基础【例7-1】现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是：整个线性表的长度为5查找计次n=1，将元素6与序列的第一个7元素进行比较，不等，继续查找n=2，将6与第二个元素2进行比较，不等，继续n=3，将6与第三个元素1进行比较，不等，继续n=4，将6与第四个元素5进行比较，不等，继续n=5，将6与第五个元素9进行比较，不等，继续n=6，

16、将6与第六个元素4进行比较，不等，继续n=7，超出线性表的长度，查找结束，则该表中不存在要查找的元素。12/23/2023第7章 程序设计基础2二分查找二分查找只适用于顺序存储的有序表。此处所述的有序表是指线性中的元素按值非递减排列（即由小到大，但允许相邻元素值相等）。二分查找的过程如下：将要查找的元素与有序序列的中间元素进行比较：如果该元素比中间元素大，则继续在线性表的后半部分（中间项以后的部分）进行查找；如果要查找的元素的值比中间元素的值小，则继续在线性表的前半部分（中间项以前的部分）进行查找。这个查找过程一直按相同的顺序进行下去，一直到查找成功或子表长度为0（说明线性表中没有要查找的元素

17、）。12/23/2023第7章 程序设计基础【例7-2】有非递减有序线性表：1、2、4、5、7、9，要查找元素6。二分查找的过程：序列长度为n=6，中间元素的序号m=(n+1)/2=3查找计次k=1，将元素6与中间元素即元素4进行比较，不等，64查找计次k=2，查找继续在后半部分进行，后半部分子表的长度为3，计算中间元素的序号：m=3+(3+1)/2=5，将元素与后半部分的中间项进行比较，即第5个元素中的7进行比较，不等，67查找计次k=3，继续查找在后半部分序列的前半部分子序列中查找，子表长度为1，则中间项序号即为m=3+(1+1)/2=4，即与第4个元素5进行比较，不相等，继续查找的子表长

18、度为0，则查找结束。12/23/2023第7章 程序设计基础7.4.6 排序技术1交换类排序法交换类排序法，即是借助于数据元素之间的互相交换进行排序的方法。（1）冒泡排序法冒泡排序法即是利用相邻数据元素之间的交换逐步将线性表变成有序序列的操作方法。操作过程如下所述：从表头开始扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若相邻两个元素中前一个元素的值比后一个元素的值大，将两个元素位置进行交换，当扫描完成一遍时，则序列中最大的元素被放置到序列的最后。再继续对序列从头进行扫描，这一次扫描的长度是序列长度减1，因为最大的元素已经就位了，采用与前相同的方法，两两之间进行比较，将次大数移到子序列的

19、末尾。按相同的方法继续扫描，每次扫描的子序列的长度均比上一次减1，直至子序列的长度为1时，排序结束。12/23/2023第7章 程序设计基础【例7-3】有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。采用冒泡排序法，具体操作步骤如下：序列长度n=7，如下图7-12所示。12/23/2023第7章 程序设计基础2插入类排序法（1）简单插入排序插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。插入排序操作的思路：在线性表中，只包含1个元素的子表，作为该有序表。从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序的子表中。该方法与冒泡排序方法的效

20、率相同，最坏的情况下需要n(n-1)/2次比较。12/23/2023第7章 程序设计基础例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。采用简单插入排序法，具体操作步骤如下：序列长度n=7，如图7-13所示。12/23/2023第7章 程序设计基础（2）希尔排序法希尔排序法的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序的过程中，逐次减小这个增量，最后当h减小到1时，再进行一次插入排序操作，即完成排序。增量序列一般取ht=n/2k(k=1,2,log2n)，其中n为待排序序列的长度。12/23/20

21、23第7章 程序设计基础（3）选择类排序法简单选择排序法基本思路：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对后面的子表采用相同的方法，直到子表为空为止。对于长度为n的序列，需要扫描n-1次，每一次扫描均找出剩余的子表中最小的元素，然后将该最小元素与子表的第一个元素进行交换。【例7-4】有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。采用简单选择排序法，具体操作步骤如图7-14所示：12/23/2023第7章 程序设计基础堆排序法堆排序法属于选择类排序方法。堆的定义：具有n个元素的序列（h1,h2,hn），当且仅当满足时称之为堆。本节只讨论满足前者条件的堆。由堆

22、的定义看，堆顶元素（即第一个元素）必为最大项。可以用一维数组或完全二叉树来表示堆的结构。用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左右子树的根结点的值，因此堆顶（完全二叉树的根结点）元素必须为序列的n个元素中的最大项。12/23/2023第7章 程序设计基础【例7-5】有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。利用堆排序法将该序列进行排序。操作方式即：先将无序堆的根结点5与左右子树的根结点2、9进行比较，5，T.B(S)运算，其结果如表7-15所示：12/23/2023第7章 程序设计基础（4）自然连接(Natural Join)运算自然连接是最常用的连接之一，简记

23、为NJN，它是指从两个关系的笛卡尔积中选择出公共属性值相等的元组所构成的新的关系。下面看一下从笛卡尔积的角度定义的自然连接。定义：设关系R和关系S具有相同的属性集U，U=Al，A2，Ak从关系R和关系S的笛卡尔积中，取满足R.U=S.U的所有元组，且去掉S.Al、S.A2、S.Ak，所得的新关系RS=il，i2，i3，ik(R.Al=S.A1R.A2=S.A2R.Ak=S.Ak(RS)记为关系R和关系S的自然连接，也可简记为(R)NJN(S)。12/23/2023第7章 程序设计基础【例7-15】取表7-12、表7-13中关系R和关系S的数据，做自然连接(R)NJN(S)，得到的结果如表7-1

24、9所示。12/23/2023第7章 程序设计基础7.5.4 数据库设计与管理1数据库设计概述数据库设计的两种方法：面向数据的方法：以信息需求为主，兼顾处理需求。面向过程的方法：以处理需求为主，兼顾信息需求。数据库设计一般采用生命周期法，分为如下几个阶段：需求分析阶、段概念设计阶、段逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。12/23/2023第7章 程序设计基础2.数据库设计的需求分析第一阶段：需求收集和分析，收集基本数据和数据流图。主要的任务是：通过详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统的工作概况，明确用户的各种需求，在此基础上确定

25、新系统的功能。对数据库的要求包括：信息要求、处理要求、安全性和完整性的要求。数据字典是各类数据的集合，它包括五个部分：数据项，即数据的最小单位数据结构，是若干数据项有意义的集合数据流，可以是数据项，也可以是数据结构，用来表示某一处理过程的输入或输出数据存储，处理过程中存取的数据，通常是手工凭证、手工文档或计算机文件处理过程12/23/2023第7章 程序设计基础3数据库概念设计（1）概念设计概述集中式模式设计法根据需求由一个统一的机构或人员设计一个综合的全局模式。适合于小型或并不复杂的单位或部门。视图集成设计法将系统分解成若干个部分，对每个部分进行局部模式设计，建立各个部分的视图，再以各视图为

26、基础进行集成。比较适合于大型与复杂的单位，是现在使用较多的方法。（2）数据库概念设计的过程选择局部应用根据系统情况，在多层的数据流图中选择一个适当层次的数据流图，将这组图中每一部分对应一个局部应用，以该层数据流图为出发点，设计各自的E-R图。视图设计视图设计的三种次序：自顶向下：先从抽象级别高且普遍性强的对象开始逐步细化、具体化和特殊化。由底向上：先从具体的对象开始，逐步抽象，普遍化和一般化，最后形成一个完整的视图设计。由内向外：先从最基本与最明显的对象开始，逐步扩充至非基本、不明显的对象。12/23/2023第7章 程序设计基础（3）视图集成是将所有局部视图统一与合并成一个完整的数据模式。视

27、图集成的重点是解决局部设计中的冲突，常见的冲突主要有如下几种方式：命名冲突：有同名异义或同义异名；概念冲突：同一概念在一处为实体而在另一处为属性或联系；域冲突：相同的属性在不同视图中有不同的域；约束冲突：不同的视图可能有不同的约束。视图经过合并生成E-R图时，其中还可能存在冗余的数据和冗余的实体间联系。冗余数据和冗余联系容易破坏数据库的完整性，给数据库维护带来困难。对于视图集成后所形成的整体的数据库概念结构必须进行验证，满足下列要求：整体概念结构内部必须具有一致性，即不能存在互相矛盾的表达；整体概念结构能准确地反映原来的每个视图结构，包括属性、实体及实体间的联系；整体概念结构能满足需求分析阶段

28、所确定的所有要求；整体概念结构还需要提交给用户，征求用户和有关人员的意见，进行评审、修改和优化，最后定稿。12/23/2023第7章 程序设计基础（4）数据库的逻辑设计从E-R模型向关系模式转换E-R模型向关系模式的转换包括：E-R模型中的属性转换为关系模式中的属性；E-R模型中的实体转换为关系模式中的元组；E-R模型中的实体集转换为关系模式中的关系；E-R模型中的联系转换为关系模式中的关系。转换中存在的一些问题：命名与属性域的处理。名称不要重复，同时，要用关系数据库中允许的数据类型来描述类型；非原子属性处理。在E-R模型中允许非原子属性存在，但在关系模式中不允许出现非原子属性，因此，要将非原

29、子属性进行转换。联系的转换。通常联系可转换为关系，但有的联系需要归并到相关联的实体中逻辑模式规范化及调整、实现对逻辑模式进行调整以满足RDBMS的性能、存储空间等要求，包括如下内容：调整性能以减少连接运算；调整关系大小，使每个关系数量保持在合理水平，从而可以提高存取效率；尽量采取快照，提高查询速度。12/23/2023第7章 程序设计基础（5）关系视图设计逻辑设计又称外模式设计。关系视图是关系模式基础上所设计的直接面向操作用户的视图。关系视图的作用：提供数据逻辑独立性，能适应用户对数据的不同需求，有一定数据保密功能（6）数据库的物理设计物理设计的主要目标是对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。12/23/2023第7章 程序设计基础（7）数据库管理数据库管理包括：数据库的建立数据库的调整数据库的重组数据库的故障恢复数据安全性控制与完整性控制数据库监控