全国计算机二级公共基础知识ppt课件.ppt

《全国计算机二级公共基础知识ppt课件.ppt》由会员分享，可在线阅读，更多相关《全国计算机二级公共基础知识ppt课件.ppt（132页珍藏版）》请在三一办公上搜索。

1、第10章 公共基础知识,本章属于VFP程序设计扩展内容。主要学习程序算法设计理论思想、软件工程思想、数据库设计应用理论、程序设计方法等内容，以便把这些设计思想应用到VFP程序设计中去。,第10章 公共基础知识,本章知识点在笔试考试中的分析明细表(1),本章知识点在笔试考试中的分析明细表(2),10.1 数据结构与算法,1.算法 1)算法的基本概念 算法是对特定问题求解步骤的一种描述。它是指令的有限序列，其中每一条指令表示一个或多个操作。 算法的基本特征 ：有穷性：指算法要在执行有穷步骤之后结束，且每一步都在有穷时间内完成。确定性：指算法中每条指令都有确切的含义，不存在二义性，且相同的输入只能得

2、到相同的输出。可行性：指算法中的操作都是可以通过实现的基本运算执行有限次来实现的。拥有足够的情报：一般地，当为算法所提供的情报足够多时，算法才是有效的。,10.1 数据结构与算法,1.算法 1)算法的基本概念 算法的基本要素对数据对象的运算和操作指令系统，是指一个计算机系统能执行的所有指令的集合。一个算法即为按照题目要求从指令系统中选择合适的指令组成的一组指令序列。因此算法就是计算机能进行的操作所组成的指令序列。不同的计算机系统， 指令系统是有差异的， 但一般的计算机系统中都包括一下4类基本运算：算术运算、逻辑运算、关系运算和数据传输。 算法的控制结构 算法的控制结构是指算法中各操作之间进行的

3、顺序。算法的效果不仅取决于所选用的操作指令，还与各操作之间的进行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构等。,10.1 数据结构与算法,1.算法 1)算法的基本概念 算法设计的基本方法算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法等。不同的方法间存在着联系，在实际应用中，不同方法通常会交叉使用。,10.1 数据结构与算法,2)算法复杂度算法的时间复杂度:是指执行算法所需要的计算工作量. 一般地，算法的计算工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即： 算法的工作量 f(n)（其中n是问题规模）例如，两个NN矩阵

4、相乘所需要的基本预算次数为n3 ，即计算量为n3 ，也就是时间复杂度为n3 。 另外，在同一问题规模下，若算法执行所需的基本运算次数取决于某一特定输入数据时，我们可以用平均性态分析和最坏情况分析两种方法来分析算法的工作量。顾名思义，平均性态分析即输入所有可能的平均值，相应的时间复杂度为算法的平均时间复杂度，最坏情况分析则是以最坏的情况估算算法执行时间的一个上界。一般情况下，后者更为常用。,10.1 数据结构与算法,2)算法的空间复杂度 算法的空间复杂度是指，执行此算法期间所需要占用的内存空间。包括3部分：算法程序所占的空间；输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 实际

5、应用中，为了减小算法所占用的存储空间，通常采用压缩存储技术，用于减小不必要的额外空间。,10.1 数据结构与算法,2.数据结构的基本概念1)什么是数据结构 数据结构是指相互有关联的数据元素的集合。而数据元素具有广泛含义，一般来说，现实世界中客观存在的一切个体都可以是数据元素。它可以是一个数或一个字符，也可以是一个具体的事物，或者其他更复杂的信息。 (1)数据的逻辑结构 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（即前后件关系）的逻辑结构。它包括数据元素的信息和数据元素之间的前后关系两个要素。,10.1 数据结构与算法,2.数据结构的基本概念1)什么是数据结构(2)数据的存储结构 所谓数据

6、的存储结构，又称为数据的物理结构，是指数据的逻辑结构在计算机存储空间中的存放方式。 因为数据元素在计算机中的存放的位置很可能与逻辑关系不一样，所以在存储数据时，不仅要存放数据的信息，还要存放数据间的前后件的信息。只有这样才能更好表示计算机存储空间中数据之间的逻辑关系。 数据结构的存储方式包括顺序存储、链式存储、索引存储和散列存储等方法。而采用不同的存储结构，其数据处理的效率是不同的，所以我们在进行数据处理时，选择合适的存储结构就显得十分重要。,10.1 数据结构与算法,2.数据结构的基本概念2)数据结构的图形表示 前后件关系是数据元素之间最基本的关系。所谓前后件关系即每一个二元组，都可以用图形

7、来表示。用中间标有元素值的方框表示数据元素，一般称为数据结点，简称结点。对于每一个二元组，用一条有向线段从前件指向后件。例如，一年四季的数据结构可以用图1所示的图形来表示。,10.1 数据结构与算法,2.数据结构的基本概念2)数据结构的图形表示 又例如数据结构的知识体系可以用下图所示的图形来表示。,10.1 数据结构与算法,2.数据结构的基本概念3)线性结构与非线性结构 根据数据结构中各数据元素之间前后关系的复杂程度，一般可将数据结构分为两大类型：线性结构和非线性结构。若一非空的数据结构有且只有一个根结点，并且每个结点最多有一个直接前驱后直接后继，则称该数据结构为线性结构，也称线性表。 不满足

8、上述条件的数据结构则称为非线性结构。 由上我们可以判断，图一为线性结构，图二为非线性结构。,10.1 数据结构与算法,3.线性表及其顺序存储结构1)线性表的基本概念 在数据结构中，线性表是最简单也是最常用的一种数据结构。 线性表是由n(n0) 数据结构元素x1，x2，x3，xn 组成的一个有限序列。除了表中的第一个元素外，有且只有一个直接前驱；除了最后一个元素外，有且只有一个直接前驱。将线性表表示为(x1，x2，x3，xn)，其中xi (i=1,2,n)是线性表的数据元素，也称为为线性表的一个结点。线性表中的数元素必须具有相同的属性，即属于同种数据对象。 比如:字母表（A，B，C，Z）就是一个

9、长度为26的线性表 比如:矩阵可以看做一个比较复杂线性表，在矩阵中，既可以把每一行看成一个数据元素，也可以把每一列看成一个数据元素。,10.1 数据结构与算法,3.线性表及其顺序存储结构2)线性表的顺序存储结构将线性表中的元素在计算机中一段相邻的存储区域中连续存储，称为线性表的顺序存储。线性表的顺序存储结构具有以下两个基本特点：所有元素所占的存储空间必须是连续的；所有元素在存储空间的位置是按逻辑顺序存放的。由其基本特点我们可以看到，线性表中元素之间逻辑上的相邻关系即元素在计算机内物理位置上的相邻关系。所以只要确定了首地址，线性表内所有元素的地址都可以方便地查找出来。,10.1 数据结构与算法,

10、插入4,（a）插入前线性表n=5,（b）插入元素4后线性表n=6,图4 线性表的顺序存储结构插入前后的状况,3.线性表及其顺序存储结构3)线性表的插入运算在对线性表的插入操作时，若在第i个元素之前插入一个新元素，完成插入操作主要有以下个步骤：原来第n个结点至第i结点依次往后移一个位置；把新结点放在第i个位置上；线性表的结点数加1。如图4所示：,10.1 数据结构与算法,3.线性表及其顺序存储结构3)线性表的插入运算当在线性表尾进行插入运算时，则只需在表的末尾增加一个元素即可，不需要移动线性表中的元素。当在线性表头位置插入新的元素，则需要移动表中所有的元素。一般地，线性表会事先开辟出一个大于线性

11、表长度的空间，但当多次插入运算后，可能出现在存储空间已满的情况下仍继续进行插入运算，此时将会产生错误，此类错误称为“溢出”。,10.1 数据结构与算法,3.线性表及其顺序存储结构4)线性表的删除运算在对线性表的删除操作时，若在第i元素之前插入一个新元素，完成插入操作主要有以下个步骤：把第i元素之后（不包括第i个元素） 的-i个元素依次前移一个位置；线性表的结点数减1。当删除运算在线性表尾进行时，即删除第n个元素，不需要移动线性表中的元素。当要删除第1个元素时，则需要移动表中所有的元素。,10.1 数据结构与算法,4.栈和队列1) 栈及其基本运算 (1)栈的基本概念 栈，实际上也是一种线性表，只

12、不过是一种特殊的线性表。其特殊性体现在，它的插入和删除运算都只在线性表的一端进行，而另一端是封闭的，不进行任何操作。在栈中，允许进行插入删除操作的一端称为栈顶，另一端则称为栈底。当栈中没有元素时称为空栈。由于其操作的特殊性，栈也被称为“先进后出”表或“后进先出”表。,10.1 数据结构与算法,(2)栈的特点栈底元素总是最早被插入的元素，最晚被删除的元素；栈顶元素总是最后被插入的元素，最早被删除的元素；栈具有记忆作用；顺序栈的插入和删除运算都不需要移动表中其他的数据元素；栈顶指针动态反映了栈中元素的变化情况。,10.1 数据结构与算法,(3)栈的顺序存储及其运算 栈的基本运算有3种： 入栈运算：

13、即栈的插入，在栈顶位置插入一个新数据。出栈运算：即栈的删除，就是取出栈顶元素赋予指定变量。读栈顶元素：即将栈顶元素（即栈顶指针top指向的元素）的值赋给某个变量。,10.1 数据结构与算法,4.栈和队列2)队列及其基本运算 (1)队列的基本概念队列是同栈完全相反的线性结构，它是允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素；允许删除的一端称为队头，通常用一个称为头指针（front）的指针指向头元素的前一个位置。队列又称为“先进先出”的线性表。,10.1 数据结构与算法,(2)循环队列及其运算循环队列，顾名思义，就是将队

14、列存储空间的最后一个位置绕到第一个位置， 形成逻辑上的环状空间，线性结构供队列循环使用。在循环队列中，用尾指针（rear）指向队列的尾元素，用头指针（front）指向头元素的前一个位置。所以，我们可以知道从头指针（front） 所指向的后一个位置直到尾指针（rear）指向的位置之间所有的元素均为队列中的元素。,10.1 数据结构与算法,由此判断队列空和队列满这两种情况：当S = 0时，循环队列为空；当S = 1时，且front = rear时，循环队列满。,(2)循环队列及其运算当 rear front时，循环队列的状态有两种：可能是队列满，也可能是队列空。为了区分这两种情况，我们通常增加一个

15、标志量S，S值的定义如下：,10.1 数据结构与算法,2)循环队列及其运算循环队列的基本运算主要有两种：入队运算入队运算是指在循环队列的队尾加入一个新元素。首先队尾指针进1（即rear=rear1），然后在rear指针指向的位置，插入新元素。当S = 1时，且front = rear时，循环队列满。此时进行入队运算，会发生“上溢”错误。 出队运算出队运算是指在循环队列的排头位置退出一个元素，并赋给指定的变量。首先，头指针进1（即front=front1），然后删除front指针指向的位置上的元素。当S = 0时，循环队列为空， 此时进行出队运算，会发生“下溢”错误。,10.1 数据结构与算法,

16、5.线性链表前面主要介绍了线性表的顺序存储结构及其基本运算。线性表的顺序存储结构的特点是简单、运算方便，对于小线性表或长度固定的线性表，采用顺序存储结构的优越性显而易见。但是线性表的顺序存储结构在数据量大，运算量大的时候就显得不方便，运算效率不高。 此时，我们就要用到链接存储方式。前面在介绍一般的线性表以及栈和队列时，主要介绍了相应的顺序存储，下面我们将讲解线性表的链接存储。,10.1 数据结构与算法,5.线性链表1)线性链表的基本概念 线性表的链式存储结构称为线性链表。线性表链式存储结构的特点是用一组不连续的存储单元存储线性表中的各个元素。 为了存储线性表中的每一个元素，一方面要存储数据元素

17、的值，另一方面要存储各数元素之间的前后关系。为此，在链式存储方式中，每个结点由两部分组成：一部分称为数据域，用于存放数据元素的值；另一部分称为指针域，用于存放下一个数据元素的地址。链式存储结构既可以表示线性结构，也可以表示非线性结构。 线性链表，就是指线性表的链式存储结构，简称链表。 由于这种链表中，每个结点只有一个指针域，故又称为单链表。,10.1 数据结构与算法,5.线性链表1)线性链表的基本概念栈和队列也可以采用链式存储结构表示，将其组织成一个单链表。这种数据结构称为带链的栈和带链的队列。栈和队列中的元素对应链表中的一个结点。 顺序表和链表的优缺点比较可见下表：,10.1 数据结构与算法

18、,5.线性链表2)线性链表的基本运算对线性链表进行的运算主要包括查找、插入、删除、合并、分解、逆转、复制和排序。其中线性链表的查找、插入和删除运算是学习的重点。 (1)在线性链表中查找指定元素在链表中查找指定元素必须从队头指针出发，沿着指针域Next逐个结点搜索，直到找到指定元素或链表尾部为止，而非像顺序表那样，知道了首地址后去计算出任意元素的存储。因此，线性链表不是随机存储结构。在链表中，扫描到等于指定元素值的结点时，返回该结点的位置，如果链表中没有元素的值等于指定元素，则扫描完所有元素后，返回空。,10.1 数据结构与算法,(2)线性链表的插入线性链表的插入是指在链式存储结构下的线性表中插

19、入一个新元素。要在线性链表中数据域为M的结点之前插入一个新元素n，首先要给n分配一个新的结点，然后在线性链表中查找数据域为M的结点，将其前件的存储序号存放在变量q中，将新结点p的指针域内容设置为指向数据域为M的结点，最后将结点q的指针域内容改为指向新结点p。,10.1 数据结构与算法,5.线性链表2)线性链表的基本运算(3)线性链表的删除线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。在线性链表中删除数据域为M的结点，首先在线性链表中查找包含元素M的结点，将该结点的存储序号存放在p中，然后把p结点的前指针放在变量q中，将q结点的指针修改为指向p结点的指针所指向的结点，最后把

20、数据域为M的结点删除。,10.1 数据结构与算法,5.线性链表3)循环链表及其基本运算(1)循环链表的定义在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，将最后一个结点的指针域的值由null改为指向表头结点，这样的链表称为循环链表。循环链表中，所有结点的指针构成了一个环状链。,10.1 数据结构与算法,(2)循环链表与单链表的比较单链表的访问方法是顺序访问，即从其中的某一结点出发，可以访问它的直接后继而无法访问它的直接前驱。而且空表与非空表的操作也不一样，对于空表和非空表的第一结点的处理都必须单独考虑。而在循环链表中，只要得到表中任一结点的位置，就可以从它出发访问到全表所有的结点

21、。且由于表头结点是循环链表所固有的结点，因此即使在表中没有数据元素的情况下，表中也至少会有一个结点存在，从而使空表和非空表的运算得到统一。,10.1 数据结构与算法,6.树和二叉树1)树的基本概念 树是一种简单的非线性结构，它是以分支关系定义的层次结构。它和自然界的树结构形式很类似，所以我们称之为树。树结构在客观世界中是大量存在的。例如，物种分类（门、纲、目、科、属、种等），组织机构（处、科、室等），行政区（国家、省、市、区），这些具有层次关系的数据，都可以用树这种数据结构来描述。在用图形表示数据结构中元素之间的前后关系时，一般使用有向箭头，如上文中图1和图2所示，但在树形结构中，一般去掉箭头

22、也不会引起歧义，常常使用无向线段代表数据元素之间的逻辑关系。,10.1 数据结构与算法,6.树和二叉树1)树的基本概念父结点：结点A是树的根结点。子结点和叶子结点：结点D，H，I，F，G均为叶子结点。度：在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。例如，在图9中，根结点A和结点E的度为2，结点B的度为3，结点C的度为1，叶子结点D，H，I，F，G的度为0。所以，该树的度为3。,深度：定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。例如，在图9中，根结点A在第1层，结点B，C在第2层，结点D，E，F

23、，G在第3层，结点H，I在第4层。该树的深度为4。子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。,10.1 数据结构与算法,6.树和二叉树2)二叉树及其基本性质 (1)二叉树的定义 二叉树是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。二叉树具有以下特点：二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树；二叉树的子树有左右之分，其次序不能任意颠倒。,10.1 数据结构与算法,(2)满二叉树和完全二叉树满二叉树指除最后一层外，每一层上的所有结点都有两个子

24、结点的二叉树。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。满二叉树与完全二叉树的关系：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。,10.1 数据结构与算法,(3)二叉树的主要性质一棵非空二叉树的第k层上最多有2k-1个结点（k 1）；深度为m的满二叉树中有2m-1个结点；对任何一棵二叉树而言，度为0的结点（即叶子结点）总是比度为的结点多一个；具有n个结点的完全二叉树的深度k为log2n1，其中log2n表示取log2n的整数部分。,10.1 数据结构与算法,注意：对于满二叉树与完全二叉树可以按层次进行顺序存储。,6.树和二叉树3)二叉

25、树的存储结构在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由数据域和指针域组成。由于每个元素可以有两个后件（即两个子结点），所以用于存储二叉树的存储结点的指针域有两个：一个指向该结点的左子结点的存储地址，称为左指针域；另一个指向该结点的右子结点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。二叉树的一个存储结点如图10所示：,10.1 数据结构与算法,6.树和二叉树4)二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历有前序遍历、 中序遍历和后序遍历等。前序遍序（DLR）首先访问根结点， 然后遍历左子树， 最后遍历右子树。中序

26、遍历（LDR）首先遍历左子树， 然后访问根结点， 最后遍历右子树。后序遍历（LRD）首先遍历左子树， 然后遍历右子树， 最后访问根结点。,10.1 数据结构与算法,对于下图进行二叉树的遍历结果:前序:A，B，D，H，E，I，C，F，G； 中序:H，D， B，E，I，A，C，G，F； 后序:H，D， I，E，B，G， F，C，A ；,10.1 数据结构与算法,7.查找技术查找，即在某种数据结构中，找出满足指定条件的元素。查找是插入和删除等运算的基础，是数据处理的重要内容。对于不同的数据结构，应选用不同的查找算法，以获得更高的查找效率。在众多查找算法中，顺序查找和二分法查找的应用最为广泛。1)顺序

27、查找顺序查找是一种最简单的查找方法。它的基本思想是：从线性表的第一个元素开始，将目标元素与线性表中的元素逐个进行比较，如果相等，则查找成功，返回结果；若整个线性表扫描完毕后，未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败，返回空。,10.1 数据结构与算法,1)顺序查找例如，在一维数组2，4，2，9，5，7，8中，查找数据元素9，首先从第1个元素2开始进行比较，与要查找的数据不相等，接着与第2个元素4进行比较，以此类推， 当进行到与第4个元素比较时，它们相等，所以查找成功。如果查找数据元素1，则整个线性表扫描完毕，仍未找到与1相等的元素，表示线性表中没有要查找的元素，查找

28、不成功。,10.1 数据结构与算法,在最好的情况下，第一个元素就是目标元素，则查找次数为1次。在最坏的情况下，最后一个元素是目标元素，顺序查找需要比较n次。在平均情况下，需要比较n/2次。因此查找算法的时间复杂度为O(n) 。顺序查找法虽然效率很低，但在以下两种情况中，它是查找运算唯一的选择：若线性表中元素是无序排列，则无论是顺序存储结构还是链式存储结构，都只能进行顺序查找；即便是有序线性表，若采用链式存储结构，也只能进行顺序查找。,10.1 数据结构与算法,2)二分查找 二分法查找也称折半查找，是一种较为高效的查找方法。但是使用二分法查找的线性表，必须满足用顺序存储结构，线性表是有序表两个条

29、件。为了简化问题阐述，有序表在本书中特指线性表中的元素按值非递减排列（即从小到大， 但允许相邻元素值相等）。 对于长度为n的有序线性表，利用二分法查找元素X的过程如下。将X与线性表的中间项比较：如果X的值与中间项的值相等，则查找成功，结束查找；如果X小于中间项的值，则在线性表的前半部分以二分法继续查找；如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。,10.1 数据结构与算法,2)二分查找 举个例子，长度为8的线性表的关键码序列为：4，11，24，29，37，45，46，77，被查找元素为37，首先将与线性表的中间项比较，即与第4个数据元素29相比较，37大于中间项29，则在线性表

30、37，45，46，77继续查找；接着与中间项比较，即与第2个元素45相比较，37小于45，则在线性表37继续查找，最后一次比较相等，查找成功。我们容易得到，相较于顺序查找法每一次比较，查找范围减少1，而二分法查找每比较一次，查找范围则减少为原来的一半，效率大为提高。容易证明得到，在最坏情况下，对于长度为n的有序线性表，二分法查找只需比较log2n次，而顺序查找需要比较n次。,10.1 数据结构与算法,8.排序技术 排序，是指将一个无序序列整理成按值非递减顺序排列的有序序列的过程。排序的方法有很多，对于不同待排序序列的规模以及对数据处理的要求，应当采用不同的排序方法。 我们在这里主要介绍一些常用

31、的排序方法。1)交换类排序法交换类排序法，指借助数据元素的“交换”来进行排序的一种方法。主要包括冒泡排序法和快速排序法。,10.1 数据结构与算法,1)交换类排序法(1)冒泡排序法冒泡排序法是最简单的一种交换类排序方法。在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止。,10.1 数据结构与算法,冒泡排序法的基本过程如下：从表头开始往后查找线性表，在查找过程中逐次比较相邻两元素的大小，若在相邻两元素中，前面的元素大于后面的元素，则将其交换，这样最后元素便为线性

32、表的最大值；从后到前查找剩下的线性表，在查找过程中逐次比较相邻两个元素的大小，若在相邻两元素中，后面的元素小于前面的元素，则将其交换；对剩下的线性表重复上述过程，直到剩下的线性表变空为止，表示线性表排序完成。最坏的情况下，当线性表的长度为n时，冒泡排序经过n/2遍的从前往后的扫描和n/2遍的从后往前扫描，需要比较n（n-1）/2次，其数量级为n2。,10.1 数据结构与算法,1)交换类排序法(2)快速排序法 快速排序法是冒泡排序一种本质上的改进。其基本思路如下：在线性表中逐个选取元素，对表进行分割，直到所有元素全部选取完毕，此时线性表即排序结束。 快速排序的具体做法是：设两个指针low和hig

33、h，它们的初值分别指向线性表的第一个元素（K元素）和最后一个元素。首先从high所指向的位置向前扫描，找到第一个小于K元素的元素并与K元素互相交换。然后从low所指位置起向后扫描，找到第一个大于K元素的数据元素并与K元素交换。重复这两个步骤，直到low=high为止。这时，线性表已经是排好序的了。 快速排序的平均时间效率最高为O（nlog2n），最坏情况下，也就是每次划分，都只得到一个子序列，此时时间效率为O（n2）。,10.1 数据结构与算法,2)插入类排序法插入排序是指将无序序列中的各元素依次插入到有序的线性表中。这里我们主要介绍简单插入排序法和希尔排序法。(1)简单插入排序法简单插入排序

34、是把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表则包含剩余的n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确的位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后当有序表的长度为n，无序表为空时，排序完成。在简单插入排序中，每一次比较后最多移掉一个逆序，因此该排序方法的效率与冒泡排序法相同。在最坏的情况下，简单插入排序需要进行n（n-1）/2次比较。,10.1 数据结构与算法,(2)希尔排序法希尔排序也是一种插入类排序的方法，但希尔排序比简单插入排序更有效率。希尔排序的基本思想是： 将整个无序序列分割成若干

35、个小的子序列并分别进行插入排序。其分割方法如下：将相隔某个增量h的元素构成一个子序列；在排序过程中，逐次减少这个增量，直到h减到1时进行一次插入排序，排序即可完成。我们容易看出，希尔排序的效率与所选取的增量序列有关。,10.1 数据结构与算法,3)选择类排序法 (1)简单选择排序法 简单选择排序的基本思想是：首先从所有n个待排序的数据元素中选择最小的元素， 将该元素与第1个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换。重复操作直到所有的元素有序(2)堆排序法堆排序属于选择类的排序方法。所谓堆，即若有n个元素的序列，将元素按顺序组成一棵完全二叉树，所有结点的值大于或等于左右子

36、结点的值，或所有结点的值小于或等于左右子结点的值，前者称之为大根堆，后者称之为小根堆。我们在这里只讨论大根堆的情况。,10.1 数据结构与算法,4)排序方法比较,10.2 程序设计基础,1.程序设计方法与风格 1)程序设计方法 程序设计，指设计、编制、调试程序的方法和过程。程序设计方法是研究问题求解如何进行系统构造的软件方法学。常用的程序设计方法有：结构化程序设计方法、软件工程方法和面向对象方法。 2)程序设计风格程序设计风格，指编写程序时所表现出的特点、习惯和逻辑思路。良好的程序设计风格可以使程序结构清晰合理，程序代码便于维护，因此，程序设计风格深深地影响着软件的质量和维护。,10.2 程序

37、设计基础,3)程序设计时应遵循的规范：源程序文档化,即在源程序中可包含一些内部文档， 以帮助阅读和理解源程序。数据说明方法；次序应规范化：使数据说明次序固定，使数据的属性容易查找，也有利于测试、排错和维护； 变量安排有序化：当多个变量出现在同一个说明语句中时，变量名应按字母顺序排序，以便于查找； 使用注释：在定义一个复杂的数据结构时，应通过注释来说明该数据结构的特点 。语句的结构：为使程序简单易懂，语句构造应该简单直接，每条语句都能直接了当地反映程序员的意图，不能为了提高效率而把语句复杂化。 输入和输出 ：输入和输出信息是用户直接关心的，也直接影响系统能否被用户接受， 故设计一定要合理、规范、

38、人性化。,10.2 程序设计基础,2.结构化程序设计 1)结构化程序设计的原则 由于软件危机的出现， 人们开始研究程序设计方法， 其中最受关注的是结构化程序设计方法，其重要原则是自顶向下、逐步求精、模块化及限制使用goto语句。自顶向下：设计的原则是应先总体，后细节；先全局目标，后具体问题。逐步求精：对复杂问题，应设计一些小问题做过渡，细分为逐个的小问题各依次求解。模块化：把程序要解决的总目标分解为若干目标，再进一步分解为具体的小目标，每个小目标称为一个模块。限制使用goto语句，滥用goto语句导致程序结构混乱的现象，应尽量避免。,10.2 程序设计基础,2)结构化程序设计的基本结构 (1)

39、顺序结构 顺序结构是指按照程序语句行的先后顺序，自始至终一条语句一条语句地顺序执行，它是最简单也是最常用的基本结构。 (2)选择结构选择结构又称分支结构，简单选择结构和多分支选择结构都属于这类基本结构。但对于一次具体的执行，只能执行其中之一，不可能既执行A，又执行B。 (3)循环结构重复结构又称循环结构，可根据给定条件，判断是否需要重复执行某一部分相同的运算（循环体）。利用重复结构可以大大简化程序的语句，有两类主要的循环结构：当型（WHILE型）循环结构和直到型（UNTIL型）循环结构。,10.2 程序设计基础,2.结构化程序设计 3)结构化程序设计的原则和方法的应用 结构化程序设计是一种面向

40、过程的程序设计方法。在结构化程序设计的具体实施中， 需要注意以下几个问题： 使用程序语言的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；选用的控制结构只能有一个入口和一个出口；用程序语句组成容易识别的块，每块只有一个入口和一个出口；应用嵌套的基本控制结构进行组合嵌套来实现复杂结构；采用前后一致的方法来模拟语言中所没有的控制结构；严格控制goto语句的使用。,10.2 程序设计基础,3.面向对象的程序设计 1)面向对象方法的基本概念 面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域

41、。 人们对面向对象的方法概念有许多不同的看法和定义，但是都涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。,10.2 程序设计基础,3.面向对象的程序设计 (1)对象 面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体，它既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。例如，书本、课桌、老师、电脑等都可看作是一个对象。 对象有以下基本特点：标识唯一性：一个对象通常可由对象名、属性和操作三部分组成；分类性：指可以将具有相同属性和操作的对象抽象成类；多态性：指同一个操作可以是不同对象的行为，不同对象执行同一操作产生不同的结果；封装性：从外面

42、看只能看到对象的外部特性，对象的内部对外是不可见的；模块独立性好：由于完成对象功能所需的元素都被封装在对象内部，所以模块独立性好。,10.2 程序设计基础,3.面向对象的程序设计 (2)类和实例类，是具有共同属性、共同方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。实例，是一个具体对象则是其对应类的一个实例。要注意的是：实例必然是指一个具体的对象。对象则既可以指一个具体的对象，也可以泛指一般的对象。 类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。 (3)消息消息传递是对象间通信的手段，一个对象发送消息给另一对象来请求其服务。消息只告

43、诉接收对象需要完成的操作，消息完全由接收者解释，独立决定采用什么方法来完成所需的操作。,10.2 程序设计基础,(4)继承 广义地说，继承是指能够直接获得已有的性质和特征，而不必重复地定义它们。 继承是面向对象软件技术的最强有力的功能和突出的优点。 继承是使用已有的类定义作为基础建立新类的定义技术。在面向对象技术中，类组成为具有层次结构的系统： 一个类的上层可有父类，下层可有子类；一个类直接继承其父类的描述（数据和操作） 或特性，子类自动地共享基类中定义的数据和方法。 继承具有传递性，如果类C继承类B，类B继承类A，则类C继承类A。因此， 一个类实际上继承了它上层的全部基类的特性，即属于某类的

44、对象除了具有该类定义的特性外， 还具有该类上层全部基类定义的特性。一个子类只有唯一的一个父类， 这种继承称为单继承。一个子类也可以有多个父类，它可以从多个父类中继承特性， 这种继承称为多重继承。,10.2 程序设计基础,3.面向对象的程序设计 (5)多态性多态性，是指对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为。在面向对象的软件技术中， 多态性是指子类对象可以像父类对象那样使用， 同样的消息既可以发送给父类对象也可以发送给子类对象。多态性机制不仅使得面向对象软件系统更加灵活，减少了信息冗余，而且显著提高了软件的可重用性和可扩充性。,10.2 程序设计基础,3

45、.面向对象的程序设计 2)面向对象方法的优点 与人类习惯的思维方法一致；稳定性好；可重用性好；易于开发大型软件产品；可维护性好。,10.3 软件工程基础,1.软件工程基本概念 1)软件定义与软件特点 我国国家标准中对计算机软件完整的定义是：软件是与计算机系统操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。它由两部分构成： 一是机器可执行的程序和数据；二是机器不可执行的， 与软件开发、 运行、 维护、 使用等有关的文档。,10.3 软件工程基础,软件主要包括以下特点：(1)软件是一种逻辑实体，具有抽象性 软件和一般的、看得见摸得着的、属于物理实体的工程对象不同，人们只能看到它的存

46、储介质，而无法看到它本身的形态。只有运用逻辑思维才能把握软件的功能和特性。(2)软件的生产与硬件不同，它没有明显的制作过程 硬件研制成功后，在重复制造时要进行质量控制来保证产品合格；而软件一旦研制成功，就可以得到大量的、成本极低的，并且完整精确的拷贝。因此，软件的质量控制必须着重于软件开发。,10.3 软件工程基础,软件定义与软件特点 ：(3)软件在运行、使用期间，不存在磨损、老化问题软件价值的损失方式也不同于物理实体的工程， 软件会为了适应硬件、 环境以及需求的变化而进行修改， 而这些修改会不可避免地引入错误， 导致软件失效率升高，从而使得软件退化。当修改的成本变得难以接受时，软件的生命周期

47、就到了尽头。(4)软件的开发、运行对计算机系统具有依赖性软件的开发、运行受计算机系统的限制，这导致了软件移植的问题 。,10.3 软件工程基础,(5)软件复杂性高，成本昂贵软件涉及人类社会的各行各业、 方方面面， 软件开发常常涉及其他领域的专业知识。软件开发需要投入大量、高强度的脑力劳动，成本高，风险大。 (6)软件开发涉及诸多的社会因素 软件除了本身具有的复杂性以外， 在开发过程中， 涉及的社会因素也是非常复杂的。,10.3 软件工程基础,1.软件工程基本概念 2)软件危机与软件工程软件危机泛指在计算?软件的开发和维护中所遇到的一系列严重问题。具体地说， 在软件开发和维护过程中， 软件危机主

48、要表现在以下几个方面：不能满足软件需求的增长；无法控制软件的开发成本和进度；难以保证软件质量；软件不可维护或维护程度非常低；软件的成本不断提高；软件开发生产率的提高跟不上硬件的发展和应用需求的增长。,10.3 软件工程基础,1.软件工程基本概念 2)软件危机与软件工程我国国家标准中对软件工程完整的定义是：软件工程是应用于计算机软件的定义、 开发和维护的一整套方法、 工具、 文档、 实践标准和工序。软件工程包含3个要素： 方法、工具和过程。方法：方法是完成软件开发各项任务的技术手段。工具：工具支持软件的开发、 管理、 文档生成。过程：过程支持软件开发的各个环节的控制、 管理。,10.3 软件工程

49、基础,1.软件工程基本概念 3)软件工程过程与软件生命周期(1)软件工程过程 软件工程过程就是把输入转化为输出的一组彼此相关的资源和活动。 软件工程过程所进行的基本活动主要包含4种，如表3所示：,10.3 软件工程基础,1.软件工程基本概念 3)软件工程过程与软件生命周期(2)软件生命周期 通常把软件产品从提出、 实现、 使用、 维护到停止使用、退役的过程称为软件生命周期。 软件生命周期主要包括软件定义、软件开发及软件运行维护等3个阶段。其中软件生命周期的主要活动阶段主要任务包括问题的定义，可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试和运行维护等。,10.3 软件工程基础,1.

50、软件工程基本概念 4)软件工程的目标与原则(1)软件工程的目标软件工程的目标是：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。 (2)软件工程的原则软件工程发展到现在， 已经总结出若干基本原则， 所有的软件项目都应遵循这些原则， 以达到软件工程的目标。 软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、 一致性、完备性和可验证性。,10.3 软件工程基础,5)软件开发工具与软件开发环境 (1)软件工程的目标 软件开发工具的产生、发展和完善促进了软件的开发速度和质量的提高。 软件开发工具从初期