大学计算机第四章ppt课件

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页算法分为两类：算法分为两类： 数值计算算法数值计算算法 求数值解求数值解 特点：少量的输入、输出，复杂的运算特点：少量的输入、输出，复杂的运算 非数值计算算法非数值计算算法 数

3、据处理数据处理 特点：大量的输入、输出，简单的运算特点：大量的输入、输出，简单的运算第6页算法的两个要素：算法的两个要素： 操作 算术运算 关系运算 逻辑运算 数据传输第7页 算法的基本特征算法的基本特征 是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。次数下终止。n 有穷性有穷性n 确定性确定性n 可行性可行性n 输入输入n 输出输出算法在执行有穷步骤后结束，且每一步都能在算法在执行有穷步骤后结束，且每一步都能在有限时间内完成。有限时间内完成。算法中的每一步操作的内容和

4、顺序必须含义确算法中的每一步操作的内容和顺序必须含义确切，不能有二义性切，不能有二义性。算法中的每一步操作都必须是可执行的，也称算法中的每一步操作都必须是可执行的，也称之为有效性之为有效性。算法中有零个或多个输入。这些输入数据应在算法中有零个或多个输入。这些输入数据应在算法操作前提供。算法操作前提供。算法的目的是用来解决一个给定的问题，因此，算法的目的是用来解决一个给定的问题，因此，它应向人们提供产生的结果它应向人们提供产生的结果。拥有足够的情报拥有足够的情报第8页第9页ACB变量变量C是一个是一个临时工作单元，临时工作单元，用来保存中间用来保存中间结果。结果。C=BB=AA=C高级语言语句实

5、现第一步第一步第二步第二步第三步第三步第10页 计数器和累加器计数器和累加器 进入一个人进入一个人i=100i=i+10iy输入输入XSUM=SUM+X输出输出SUM0SUMX=0) ABDFECGHIJKMn 根：根：only onen 若若n=0，则称为空树；，则称为空树；n 否则，当否则，当n1时，其余结时，其余结点被分成点被分成m(m0)个互不相交个互不相交的子集的子集T1，T2，.，Tm，每个子集又是一棵树。由此每个子集又是一棵树。由此可以看出，树的定义是递归可以看出，树的定义是递归的。的。n Question：如何辨别根？：如何辨别根？A只有一个只有一个结点的树结点的树第40页AB

6、DFECGHIJKMn 结点的度结点的度 一个结点的子树的个数；一个结点的子树的个数；n Q：结点：结点A、D的度数？的度数？( )n 树的度树的度 树中所有结点度的最大值；树中所有结点度的最大值；n Q：右图中树的度？：右图中树的度？( )n 终端终端(叶子叶子)结点结点 度为度为0的结点；的结点；n Q：图中叶子结点有几个？：图中叶子结点有几个？( )n 非终端结点非终端结点 度不为度不为0的结点；的结点；n Q：图中非终端结点有几个？：图中非终端结点有几个？( )3375第41页ABDFECGHIJKMn 结点的层次结点的层次 树中根结点的层次为树中根结点的层次为1，根结点，根结点子树的

7、根为第子树的根为第2层，以此类推；层，以此类推；n Q：图中结点：图中结点F的层次？的层次？n 树的深度树的深度 树中所有结点层次的最大值；树中所有结点层次的最大值； Q：图中树的深度？图中树的深度？n 有序树、无序树有序树、无序树 如果树中每棵子树从左向右如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。序树，否则称为无序树。第42页 定义：二叉树是一种有序的树形结构。它与一般定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：树形结构的区别是： 每个结点最多有两棵子树；每个结点最多有两棵子树； 子树有左右之

8、分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。 二叉树的二叉树的5种基本形态种基本形态第43页【性质1】 在二叉树的第i层上最多有2i-1个结点(i1)ABCDFEHGI=1 2i-I=1 2i-1=11=1I=2 2i-I=2 2i-1=21=2I=3 2i-I=3 2i-1=41=4第44页【性质2】深度为h的二叉树最多有2h -1个结点(h 1)满二叉树：如果一个深度为k的二叉树拥有2K-1个结点，则将它称为满二叉树。完全二叉树：有一棵深度为k，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二

9、叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。 第45页1213 141589 10 114567123满二叉树满二叉树完全二叉树完全二叉树121389 10 114567123 完全二叉树是满二叉树 满二叉树也是完全二叉树叶子结点只能出现在最后两层第46页121389 10 11456123非完全二非完全二叉树叉树深度为深度为4的的完全二叉树完全二叉树8456712345671239121389 10 114123567第47页【性质3】二叉树上叶子结点数比度为2的结点数多1ABCDFEHG度为2的结点叶子结点第48页 N=N0+N1+N2 (1)除根结点外每个结点均有一个

10、分除根结点外每个结点均有一个分支进入支进入,设二叉树中所有进入分设二叉树中所有进入分支数为支数为M,总结点数总结点数: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,即叶子结点数即叶子结点数

11、 N1为结点度为为结点度为1的结点数的结点数N2为结点度为为结点度为2的结点数的结点数N为树的总结点数为树的总结点数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

12、在深度为在深度为5的完全二叉树中，度为的完全二叉树中，度为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 遍历指不重复地访

13、问二叉树中的所有结遍历指不重复地访问二叉树中的所有结点。点。u 二叉树的遍历的次序与树型结构上的大二叉树的遍历的次序与树型结构上的大多数运算有联系。多数运算有联系。u(1)先先(前前)序遍历序遍历(DLR)u 若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则u访问根结点；访问根结点；u先序遍历左子树；先序遍历左子树；u先序遍历右子树。先序遍历右子树。ABCDFEHG第53页(2)中序遍历中序遍历(LDR) 若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。(3)后序遍历

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

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

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

17、点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。u 二分查找法的适用场合：u 线性表中的元素按关键字值递增或递减的次序排列；u 线性表采用顺序存储结构。第58页查找总结查找总结查找方法查找方法 最坏情况的比较最坏情况的比较次数次数使用条件使用条件N线性表中的元素值是无序线性表中的元素值是无序,也也可是有序的可是有序的;线性表中的元素线性表中的元素个数不多的情况个数不多的情况.二分查找二分查找log2N线性表中的元素按关键字值线性表中的元素按关键字值递增或递减的次序排列；线递增或递减的次序排列；线性表中的元素个数很多的情性表

18、中的元素个数很多的情况况.第59页u 排序也是数据处理的重要内容。u 排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。u 这里讨论的排序方法，其排序对象一般是顺序存储的线性表。 u 根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：u 冒泡排序u 选择排序u 插入排序第60页u 冒泡排序的方法：冒泡排序的方法：u 扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；则交换；第一趟扫描的结果使最大的元素排到表的最后；u 除最后一个元素，对剩余的元素重复上述过程，

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

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

21、: 本趟排序未发生交换，终止排序算法本趟排序未发生交换，终止排序算法 第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 选择排序的方法：选择排序的方法：u扫描整个线性表，从中找出最小的元素，与第一个元扫描整个线性表，从中找出最小的元素，与第一

22、个元素交换；素交换；u除第一个元素，对剩下的子表采用相同的方法找出次除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；小的数，与第二个数交换；u重复上述过程；重复上述过程；u对于长度为对于长度为n的线性表，选择排序需要对表扫描的线性表，选择排序需要对表扫描n-1遍。遍。u在最坏的情况下，选择排序需要比较在最坏的情况下，选择排序需要比较n(n-1)/2次次第65页选择排序方法：先找出表中关键字最小的元素，将选择排序方法：先找出表中关键字最小的元素，将其与第一个元素交换，然后在其余元素中找出关其与第一个元素交换，然后在其余元素中找出关键字最小的元素，将其与第二个元素交换，依次键

23、字最小的元素，将其与第二个元素交换，依次类推，最终所有关键字按从小到大排列。类推，最终所有关键字按从小到大排列。例：设待排数据元素的关键字为例：设待排数据元素的关键字为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，14，15，15 37，22，30u第五趟： 11，14，15，15，22 37，30u第六趟： 11，14，15，15