最新大学计算机第四章PPT课件.ppt

《最新大学计算机第四章PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新大学计算机第四章PPT课件.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大学计算机第四章大学计算机第四章计算机二级考试公共基础知识计算机二级考试公共基础知识q 基本数据结构与算法基本数据结构与算法(教材教材4.2节节)q 程序设计基础程序设计基础q 软件工程基础软件工程基础q 数据库设计基础数据库设计基础(教材第教材第8章自学章自学)二级考试科目分成二级语言程序设计二级考试科目分成二级语言程序设计(C、C、Java、Visual Basic)和二级数据库程序设计和二级数据库程序设计(Visual FoxPro、Access)两类。两类。公共基础知识在各科笔试中的比重为公共基础知识在各科笔试中的比重为30%(教材教材4.1节自学节自学)2ACB变量变量C是一个是一个

2、临时工作单元，临时工作单元，用来保存中间用来保存中间结果。结果。算法举例算法举例算法举例算法举例 两个变量的值交换两个变量的值交换 有红、蓝两个墨水瓶，要求将其互换。有红、蓝两个墨水瓶，要求将其互换。C=BB=AA=C高级语言语句实现第一步第一步第二步第二步第三步第三步9 计数器和累加器计数器和累加器 计数器计数器(统计入场人数，统计入场人数，统计入场人数，统计入场人数，超过超过超过超过100100人结束人结束人结束人结束)i=i+1i=i+1 累加器累加器sum=sum+x进入一个人进入一个人i=100i=i+10iy输入输入XSUM=SUM+X输出输出SUM0SUMX=0)ABDFECGH

3、IJKMn 根：根：only onen 若若n=0，则称为空树；，则称为空树；n 否则，当否则，当n1时，其余结时，其余结点被分成点被分成m(m0)个互不相交个互不相交的子集的子集T1，T2，.，Tm，每，每个子集又是一棵树。由此可个子集又是一棵树。由此可以看出，树的定义是递归的。以看出，树的定义是递归的。n Question：如何辨别根？：如何辨别根？A只有一个只有一个结点的树结点的树39树型结构的常用术语树型结构的常用术语树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn 结点的度结点的度结点的度结点的度 一个结点的子树的个一个结点的子树的个数数；Q：结点结点A、D的度数？的度

4、数？()()n 树的度树的度树的度树的度 树中所有结点度的最大值树中所有结点度的最大值；Q：右图中树的度？右图中树的度？()()n 终端终端终端终端(叶子叶子叶子叶子)结点结点结点结点 度为度为0的结点的结点；Q：图中叶子结点有几个？图中叶子结点有几个？()n n 非终端结点非终端结点非终端结点非终端结点 度不为度不为0的结点的结点；Q：图中非终端结点有几个？图中非终端结点有几个？()337540树型结构的常用术语树型结构的常用术语树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn 结点的层次结点的层次结点的层次结点的层次 树中根结点的层次树中根结点的层次为为1，根结点子树的根为第

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

6、构的区别是：树形结构的区别是：n 每个结点最多有两棵子树；每个结点最多有两棵子树；n 子树有左右之分，次序不能任意颠倒。子树有左右之分，次序不能任意颠倒。二叉树的二叉树的5种基本形态种基本形态42二叉树的性质二叉树的性质二叉树的性质二叉树的性质【性质1】在二叉树的第在二叉树的第i层上最多有层上最多有2i-1个结点个结点(i1)ABCDFEHGI I=1 2i-1=1I I=2 2i-1=2I I=3 2i-1=443【性质2】深度为深度为h的二叉树最多有的二叉树最多有2h-1个结点个结点(h 1)n n满二叉树：满二叉树：满二叉树：满二叉树：如果一个深度为如果一个深度为k的二叉树拥有的二叉树拥

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

8、全二叉树完全二叉树12138910114567123 完全二叉树是满二叉树 满二叉树也是完全二叉树叶子结点只能出现在最后两层451213891011456123非完全二非完全二叉树叉树深度为深度为4的的完全二叉树完全二叉树84567123456712391213891011412深度为深度为4的的完全二叉树完全二叉树356746【性质3】二叉树上叶子结点数比度为二叉树上叶子结点数比度为2的结点数多的结点数多1ABCDFEHG度为2的结点叶子结点47 N=N0+N1+N2 (1)除根结点外每个结点均有一个分除根结点外每个结点均有一个分支进入支进入,设二叉树中所有进入分设二叉树中所有进入分支数为支

9、数为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,即叶子结点数即叶子结点数 N1为结点度为为结点度为1的结点数的结点数N2为结点度为为结点度为2的结点数的结点数N为树的总

10、结点数为树的总结点数N=N0+N1+N2N=3+2+2=848【性质4】具有具有n个结点的个结点的完全二叉树的深度完全二叉树的深度为为 log2n+1其中，其中，log2n 的结果是不大于的结果是不大于log2n的最大整数的最大整数A BABCABCFE log22+1=2 log25+1=3取整的表示取整的表示49u 一棵二叉树第六层一棵二叉树第六层(根结点为第一层根结点为第一层)的结点数最多的结点数最多为为 _ 个。个。u 某二叉树中度为某二叉树中度为2的结点有的结点有18个，则该二叉树中有个，则该二叉树中有_ 个叶子结点。个叶子结点。u 在深度为在深度为5的完全二叉树中，度为的完全二叉树

11、中，度为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=?为为050二叉树的存储二叉树的存储二叉树的存储二叉树的存储u 在计算机中，二叉树通常采用链式存储结构。在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构二叉树的存储结点的结构ABDCFGE A G E F B C Dt51二叉树的遍历二叉树的遍历二叉树的遍

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

13、中序遍历右子树。(3)后序遍历后序遍历(LRD)若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则n后序遍历左子树；后序遍历左子树；n后序遍历右子树；后序遍历右子树；n访问根结点。访问根结点。ABCDFEHG53u先序序列：先序序列：ABDGCEFHu中序序列：中序序列：DGBAECHFu后序序列：后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：54 查找技术查找技术查找技术查找技术u 查找是数据处理的重要内容。查找是数据处理的重要内容。u 查找指在一个给定的数据结构中查找指定的

14、元素，查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。该元素也称关键字。u 若找到了满足条件的结点，称查找成功；否则称查若找到了满足条件的结点，称查找成功；否则称查找失败。找失败。u衡量一个查找算法的主要标准是查找过程中对关键衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。字进行的平均比较次数。u 通常根据不同的数据结构，采用不同的查找方法：通常根据不同的数据结构，采用不同的查找方法：n 顺序查找顺序查找n 二分查找二分查找55顺序查找顺序查找顺序查找顺序查找u 顺序查找是线性表中最简单的查找方法。顺序查找是线性表中最简单的查找方法。u 顺序查找的方法：从线性表

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

16、 二分查找法是一种效率较高的查找方法，但是只适合顺序二分查找法是一种效率较高的查找方法，但是只适合顺序存储的存储的有序表有序表。查找不成功的比较次数为。查找不成功的比较次数为LOG2Nu二分查找的方法：首先将关键字与线性表中间位置的结点二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为功或子表长度为0。u 二分查找法的适用场合：二分查找法的适用场合：n 线性表中的线性表中的元素按关键

17、字值递增或递减的次序排列元素按关键字值递增或递减的次序排列；n 线性表采用线性表采用顺序存储结构顺序存储结构。57查找总结查找总结查找方法查找方法 最坏情况的比较最坏情况的比较次数次数使用条件使用条件顺序查找顺序查找顺序查找顺序查找N线性表中的元素值是无序线性表中的元素值是无序,也也可是有序的可是有序的;线性表中的元素线性表中的元素个数不多的情况个数不多的情况.二分查找二分查找log2N线性表中的元素按关键字值线性表中的元素按关键字值递增或递减的次序排列；线递增或递减的次序排列；线性表中的元素个数很多的情性表中的元素个数很多的情况况.58 排序技术排序技术排序技术排序技术u 排序也是数据处理的

18、重要内容。排序也是数据处理的重要内容。u 排序指将一个无序序列整理成按关键字值递增或递排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。减排列的有序序列。u 这里讨论的排序方法，其排序对象一般是这里讨论的排序方法，其排序对象一般是顺序存储顺序存储的线性表的线性表。u 根据排序序列的规模以及数据处理的要求，可以采根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：用不同的排序方法：n 冒泡排序冒泡排序n 选择排序选择排序n 插入排序插入排序59冒泡排序冒泡排序冒泡排序冒泡排序u 冒泡排序的方法：冒泡排序的方法：n扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，扫描整

19、个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；则交换；第一趟扫描的结果使最大的元素排到表的最后；n除最后一个元素，对剩余的元素重复上述过程，将次大的数排除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；到表的倒数第二个位置；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，冒泡排序需要对表扫描的线性表，冒泡排序需要对表扫描n-1遍。遍。n 在最坏的情况下，冒泡排序需要比较在最坏的情况下，冒泡排序需要比较n(n-1)/2次次60冒泡排序的方法冒泡排序的方法u设待排数据元素的关键字为（18，20，15，3

20、2，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 15 20 4 25 32 最大数61Q：第二趟冒泡排序后的结果是什么样的？达到：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最了最终的排序目标吗？一共需要多少次能够最后成为有序序列？后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？会用什么方法来排序？

21、冒泡排序比较简单，当初始序列基本有序时，冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序有较高的效率，反之效率较低。u冒泡排序终止条件冒泡排序终止条件:本趟排序未发生交换，终止排序算法本趟排序未发生交换，终止排序算法 62初始初始 第一趟第一趟 第二趟第二趟 第三趟第三趟 第四趟第四趟 第五趟第五趟序列序列 排序后排序后 排序后排序后 排序后排序后 排序后排序后 排序后排序后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设待排数据元素的关键

22、字为（26,18,32,54,47,9,15)63选择排序选择排序选择排序选择排序u 选择排序的方法：选择排序的方法：n扫描整个线性表，从中找出最小的元素，与第一个扫描整个线性表，从中找出最小的元素，与第一个元素交换；元素交换；n除第一个元素，对剩下的子表采用相同的方法找出除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；次小的数，与第二个数交换；n重复上述过程；重复上述过程；n对于长度为对于长度为n的线性表，选择排序需要对表扫描的线性表，选择排序需要对表扫描n-1遍。遍。n在最坏的情况下，选择排序需要比较在最坏的情况下，选择排序需要比较n(n-1)/2次次64选择排序方法

23、：选择排序方法：先找出表中关键字最小的元素，将先找出表中关键字最小的元素，将其与第一个元素交换其与第一个元素交换，然后在其余元素中找出关，然后在其余元素中找出关键字最小的元素，将其与第二个元素交换，依次键字最小的元素，将其与第二个元素交换，依次类推，最终所有关键字按从小到大排列。类推，最终所有关键字按从小到大排列。例：设待排数据元素的关键字为（例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：），每一趟排序后的序列状态如图所示：65u初态：15，14，22，30，37，15，11u第一趟：11 14，22，30，37，15，15u第二趟：11，

24、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，22，30 37 有序序列66插入排序插入排序12 23 11 15 56 77待排序元素待排序元素12 所谓插入排序是将无序列中的各元素依次插到已经有序的线所谓插入排序是将无序列中的各元素依次插到已经有序的线性表中。性表中。有序表有序表12 23 11 15 56 7711 122312 23 11 15 56 77 12 23231115在最坏的情况下，选择排序需要比较在最坏

25、的情况下，选择排序需要比较n(n-1)/2次，还不算移动次，还不算移动67练习:1.长度为长度为n的线性表进行顺序查找，在最坏情况下所需要的比的线性表进行顺序查找，在最坏情况下所需要的比较次数为较次数为【B】A.n+1 B.n C.(n+1)/2 D.n/22在长度为在长度为N的线性表中进行二分查找，在最快的情况下，的线性表中进行二分查找，在最快的情况下，需要比较的次数为需要比较的次数为【log2N】。3.长度为长度为N的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数为为【】。N*(N+1)/2 *(1/N)=(N+1)/268练习:4.设待排数据元素的关键字为（设待排数据元素的关键字为（67，43，14，22，33，15，11，43），用选择法将其按升序排序，需要比较的次数），用选择法将其按升序排序，需要比较的次数为为【】。N(N+1)/25.设待排数据元素的关键字为（设待排数据元素的关键字为（18，24，75，24，33，15），），用冒泡法将其按升序排序，画出每一趟冒泡排序后的序列用冒泡法将其按升序排序，画出每一趟冒泡排序后的序列状态图状态图.69