大学计算机第四章

1、第四章第四章 软件基础软件基础第2页计算机二级考试公共基础知识计算机二级考试公共基础知识q 基本数据结构与算法基本数据结构与算法(教材教材4.2节节)q 程序设计基础程序设计基础q 软件工程基础软件工程基础q 数据库设计基础数据库设计基础(教材第教材第8章自学章自学)二级考试科目分成二级语言程序设计二级考试科目分成二级语言程序设计(c、c、java、visual basic)和二级数据库程序设计和二级数据库程序设计(visual foxpro、access)两类。两类。公共基础知识在各科笔试中的比重为公共基础知识在各科笔试中的比重为30% (教材教材4.1节自学节自学)第3页 算法的基本概念算

2、法的基本概念 算法的表示算法的表示 常用算法常用算法 算法的评价算法的评价 数据结构的概念数据结构的概念 线性表线性表 栈和队列栈和队列 树与二叉树树与二叉树 查找技术查找技术 排序技术排序技术 第4页 程序程序用计算机语言描述的算法用计算机语言描述的算法 流程图流程图图形化的算法图形化的算法(机械图机械图) 算法是程序设计的核心算法是程序设计的核心input rs=r*r*3.14ptint s开始开始输入输入r rs=r*r*3.14输出输出s s结束结束问题：输入园的半径，计算园的面积起止框起止框输入输出框输入输出框处处理理框框第5页算法分为两类：算法分为两类：n 求数值解求数值解n 特

3、点：少量的输入、输出，复杂的运算特点：少量的输入、输出，复杂的运算n 数据处理数据处理n 特点：大量的输入、输出，简单的运算特点：大量的输入、输出，简单的运算第6页算法的两个要素：算法的两个要素： n 算术运算算术运算n 关系运算关系运算n 逻辑运算逻辑运算n 数据传输数据传输n 顺序顺序n 选择选择n 循环循环第7页 算法的基本特征算法的基本特征 是一组严谨地定义运算顺序的规则，每一个规则都是有效是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。的，是明确的，此顺序将在有限的次数下终止。n 有穷性有穷性n 确定性确定性n 可行性可行性n 输入输入n

4、输出输出算法在执行有穷步骤后结束，且每一步都能在算法在执行有穷步骤后结束，且每一步都能在有限时间内完成。有限时间内完成。算法中的每一步操作的内容和顺序必须含义确算法中的每一步操作的内容和顺序必须含义确切，不能有二义性切，不能有二义性。算法中的每一步操作都必须是可执行的，也称算法中的每一步操作都必须是可执行的，也称之为有效性之为有效性。算法中有零个或多个输入。这些输入数据应在算法中有零个或多个输入。这些输入数据应在算法操作前提供。算法操作前提供。算法的目的是用来解决一个给定的问题，因此，算法的目的是用来解决一个给定的问题，因此，它应向人们提供产生的结果它应向人们提供产生的结果。拥有足够的情报拥有

5、足够的情报第8页 描述算法的方法有多种：描述算法的方法有多种：n自然语言自然语言n传统流程图传统流程图nn-s流程图流程图n伪代码伪代码n计算机语言计算机语言第9页acb变量变量c是一个是一个临时工作单元，临时工作单元，用来保存中间用来保存中间结果。结果。 两个变量的值交换两个变量的值交换 有红、蓝两个墨水瓶，要求将其互换。有红、蓝两个墨水瓶，要求将其互换。c=bb=aa=c高级语言语句实现第一步第一步第二步第二步第三步第三步第10页 计数器和累加器计数器和累加器 sum=sum+x进入一个人进入一个人i=100i=i+10iy输入输入xsum=sum+x输出输出sum0sumx=0) abd

6、fecghijkmn 根：根：only onen 若若n=0，则称为空树；，则称为空树；n 否则，当否则，当n1时，其余结时，其余结点被分成点被分成m(m0)个互不相交个互不相交的子集的子集t1，t2，.，tm，每个子集又是一棵树。由此每个子集又是一棵树。由此可以看出，树的定义是递归可以看出，树的定义是递归的。的。n question：如何辨别根？：如何辨别根？a只有一个只有一个结点的树结点的树第40页abdfecghijkmn 一个结点的子树的个一个结点的子树的个数数； q：结点结点a、d的度数？的度数？( )( )n 树中所有结点度的最大值树中所有结点度的最大值； q：右图中树的度？右图中

7、树的度？( )( )n 度为度为0的结点的结点； q：图中叶子结点有几个？图中叶子结点有几个？( ) 度不为度不为0的结点的结点； q：图中非终端结点有几个？图中非终端结点有几个？( )3375第41页abdfecghijkmn 树中根结点的层树中根结点的层次为次为1，根结点子树的根为第，根结点子树的根为第2层，层，以此类推；以此类推； q：图中结点图中结点f的层次？的层次？n 树中所有结点层次树中所有结点层次的最大值；的最大值； q：图中树的深度？图中树的深度？n 如果树中每如果树中每棵子树从左向右的排列拥有一定棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序的顺序，不得互换，则称为

8、有序树，否则称为无序树。树，否则称为无序树。第42页 二叉树是一种有序的树形结构。它与一般二叉树是一种有序的树形结构。它与一般树形结构的区别是：树形结构的区别是：n 每个结点最多有两棵子树；每个结点最多有两棵子树；n 子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。 二叉树的二叉树的5种基本形态种基本形态第43页【性质1】 在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点个结点(i1)abcdfehgi i=1 2i-1=1i i=2 2i-1=2i i=3 2i-1=4第44页【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h -1个结点个结点(h 1)

9、如果一个深度为如果一个深度为k的二叉树拥有的二叉树拥有2k-1个结个结点，则将它称为点，则将它称为满二叉树满二叉树。有一棵深度为有一棵深度为k，具有，具有n个结点的二叉树，个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为的每个结点分别与满二叉树中编号为1n的结点位置的结点位置一一对应，则称这棵二叉树为一一对应，则称这棵二叉树为完全二叉树完全二叉树。 第45页121314158910114567123满二叉树满二叉

10、树完全二叉树完全二叉树12138910114567123 完全二叉树是满二叉树 满二叉树也是完全二叉树叶子结点只能出现在最后两层第46页1213891011456123非完全二非完全二叉树叉树深度为深度为4的的完全二叉树完全二叉树845671234567123912138910114123567第47页【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1abcdfehg度为2的结点叶子结点第48页 n=n0+n1+n2 (1)除根结点外每个结点均有一个分除根结点外每个结点均有一个分支进入支进入,设二叉树中所有进入分设二叉树中所有进入分支数为支数为m,总结点数总结点

11、数:n=m+1 (2)由于分支是由非叶子结点射入由于分支是由非叶子结点射入, 结点度为结点度为1射入射入1个分支个分支, 结点度为结点度为2射入射入2个分支个分支,故故m=n1+2n2 (3)将将(3)代入代入(2)式有式有n=n1+2n2+1 (4)比较比较(1)式与式与(4)有有n0+n1+n2=n1+2n2+1化简后得化简后得n0=n2+1即叶子结点数比结点度为即叶子结点数比结点度为2的结的结点数多点数多1.abcdfehgn0为结点度为为结点度为0,即叶子结点数即叶子结点数 n1为结点度为为结点度为1的结点数的结点数n2为结点度为为结点度为2的结点数的结点数n为树的总结点数为树的总结点

12、数n=n0+n1+n2n=3+2+2=8第49页【性质4】具有具有n个结点的个结点的完全二叉树的深度完全二叉树的深度为为 log2n +1其中，其中， log2n 的结果是不大于的结果是不大于log2n的最大整数的最大整数a babcabcfe log22 +1=2 log25 +1=3取整的表示取整的表示第50页u 一棵二叉树第六层一棵二叉树第六层(根结点为第一层根结点为第一层)的结点数最多的结点数最多为为 _ 个。个。u 某二叉树中度为某二叉树中度为2的结点有的结点有18个，则该二叉树中有个，则该二叉树中有_ 个叶子结点。个叶子结点。 u 在深度为在深度为5的完全二叉树中，度为的完全二叉树

13、中，度为2的结点数最多的结点数最多为为 _ 。练习：练习：321915分析分析:完全二叉树的特例完全二叉树的特例 是满二叉树是满二叉树,总结点数为总结点数为 n=25-1=31 n=n0+n1+n2=n0+n2 n=n2+1+n2=2n2+12n2+1=31 故故n2=15 n0=n2+1=? 26-1=?为为0第51页u 在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。llinkinforlink二叉树的存储结点的结构二叉树的存储结点的结构abdcfge a g e f b c dt第52页u 遍历指遍历指不重复地不重复地访问二叉树中的访问二叉树中的所有结所有

14、结点点。u 二叉树的遍历的次序与树型结构上的大二叉树的遍历的次序与树型结构上的大多数运算有联系。多数运算有联系。(1)先先(前前)序遍历序遍历(dlr) 若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n访问根结点；访问根结点；n先序遍历左子树；先序遍历左子树；n先序遍历右子树。先序遍历右子树。abcdfehg第53页(2)中序遍历中序遍历(ldr) 若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n中序遍历左子树；中序遍历左子树；n访问根结点；访问根结点；n中序遍历右子树。中序遍历右子树。(3)后序遍历后序遍历(lrd) 若二叉树为空，则结束遍历操作；

15、否则若二叉树为空，则结束遍历操作；否则n后序遍历左子树；后序遍历左子树；n后序遍历右子树；后序遍历右子树；n访问根结点。访问根结点。abcdfehg第54页u先序序列：先序序列：abdgcefhu中序序列：中序序列：dgbaechfu后序序列：后序序列：gdbehfcaabcfhdeg下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：第55页u 查找是数据处理的重要内容。查找是数据处理的重要内容。u 查找指在一个给定的数据结构中查找指定的元素，查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。该元素也称关键字。u 若找到了满足条

16、件的结点，称查找成功；否则称若找到了满足条件的结点，称查找成功；否则称查找失败。查找失败。 u衡量一个查找算法的主要标准是查找过程中对关键衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。 u 通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同的查找方法：n 顺序查找顺序查找n 二分查找二分查找第56页u 顺序查找是线性表中最简单的查找方法。顺序查找是线性表中最简单的查找方法。u 顺序查找的方法：从线性表的第一个元素开始，顺序查找的方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，依次将线性表中的元素与

17、关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较则查找成功；若将所有元素都与关键字进行了比较但不相等，则查找失败。但不相等，则查找失败。u 顺序查找法的适用场合：顺序查找法的适用场合：n 对线性表中元素的排列次序没有要求；对线性表中元素的排列次序没有要求；n 对线性表的存储结构没有要求，链式结构和顺对线性表的存储结构没有要求，链式结构和顺序结构均可。序结构均可。u查找不成功的比较次数为查找不成功的比较次数为 n第57页u 二分查找法是一种效率较高的查找方法，但是只适合顺二分查找法是一种效率较高的查找方法，但是只适合顺序存储的序存储的有序表有序表。查找不成功的比较次数为。查找

18、不成功的比较次数为log2nu二分查找的方法：首先将关键字与线性表中间位置的结点二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为功或子表长度为0。u 二分查找法的适用场合：二分查找法的适用场合：n 线性表中的线性表中的元素按关键字值递增或递减的次序排列元素按关键字值递增或递减的次序排列；n 线性表采用线性表采用顺序存储结构顺序存储结构。第58页查找总结查找总结查找方法查找方法 最坏

19、情况的比较最坏情况的比较次数次数使用条件使用条件n线性表中的元素值是无序线性表中的元素值是无序,也也可是有序的可是有序的;线性表中的元素线性表中的元素个数不多的情况个数不多的情况.二分查找二分查找log2n线性表中的元素按关键字值线性表中的元素按关键字值递增或递减的次序排列；线递增或递减的次序排列；线性表中的元素个数很多的情性表中的元素个数很多的情况况.第59页u 排序也是数据处理的重要内容。排序也是数据处理的重要内容。u 排序指将一个无序序列整理成按关键字值递增或排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。递减排列的有序序列。u 这里讨论的排序方法，其排序对象一般是这里讨论

20、的排序方法，其排序对象一般是顺序存顺序存储的线性表储的线性表。 u 根据排序序列的规模以及数据处理的要求，可以根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：采用不同的排序方法：n 冒泡排序冒泡排序n 选择排序选择排序n 插入排序插入排序第60页u 冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；序，则交换；第一趟扫描的结果使最大的元素排到表的最后；n除最后一个元素，对剩余的元素重复上述过程，将次大的数除最后一个元素，对剩余的元素重复上述

21、过程，将次大的数排到表的倒数第二个位置；排到表的倒数第二个位置；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，冒泡排序需要对表扫描的线性表，冒泡排序需要对表扫描n-1遍。遍。n 在最坏的情况下，冒泡排序需要比较在最坏的情况下，冒泡排序需要比较n(n-1)/2次次第61页冒泡排序的方法冒泡排序的方法u 设待排数据元素的关键字为（18，20，15，32，4，25），冒泡排序后的序列状态如图所示：u18 20 15 32 4 25u 18 20 15 32 4 25u 18 15 20 32 4 25u 18 15 20 32 4 25u 18 15 20 4 32 25u 18

22、15 20 4 25 32 最大数第62页q：第二趟冒泡排序后的结果是什么样的？达到：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最了最终的排序目标吗？一共需要多少次能够最后成为有序序列？后成为有序序列？q：你觉得冒泡排序的效率如何？如果是你，你：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？会用什么方法来排序？ 冒泡排序比较简单，当初始序列基本有序时，冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序有较高的效率，反之效率较低。u冒泡排序终止条件冒泡排序终止条件: 本趟排序未发生交换，终止排序算法本趟排序未发生交换

23、，终止排序算法 第63页初始初始 第一趟第一趟 第二趟第二趟 第三趟第三趟 第四趟第四趟 第五趟第五趟序列序列 排序后排序后 排序后排序后 排序后排序后 排序后排序后 排序后排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2647 9 15 329 15 4715 54设待排数据元素的关键字为（26,18,32,54,47,9,15 )第64页u 选择排序的方法：选择排序的方法：n扫描整个线性表，从中找出最小的元素，与第一个扫描整个线性表，从中找出最小的元素，与第一个元素交换；元素交换；n除第一个元素，对剩下的子表采用

24、相同的方法找出除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；次小的数，与第二个数交换；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，选择排序需要对表扫描的线性表，选择排序需要对表扫描n-1遍。遍。n在最坏的情况下，选择排序需要比较在最坏的情况下，选择排序需要比较n(n-1)/2次次第65页选择排序方法：选择排序方法：先找出表中关键字最小的元素，将先找出表中关键字最小的元素，将其与第一个元素交换其与第一个元素交换，然后在其余元素中找出关，然后在其余元素中找出关键字最小的元素，将其与第二个元素交换，依次键字最小的元素，将其与第二个元素交换，依次类推，最终所有关键字按从小到大排列。类推，最终所有关键字按从小到大排列。例：设待排数据元素的关键字为（例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：），每一趟排序后的序列状态如图所示：第66页u初态： 15，14，22，30，37，15，11u第一趟： 11 14，22，30，37，15，15u第二趟： 11，14 22，30，37，15，15u第三趟： 11，14，15 30，37，22，15u第四趟： 11，