C语言课程课件 二级C语言等级考试 公共基础知识 part2
71页1、第1页知识点复习:先(前)序遍历(DLR)根左右中序遍历(LDR)左根右后序遍历(LRD)左右根uu 二叉树的性质:二叉树的性质: 在二叉树的第i层上最多有2i-1个结点二叉树上叶子结点数比度为2的结点数多1uu 二叉树的遍历:二叉树的遍历:第2页u 设有下列二叉树:对此二叉树前序遍历的结果为 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPTu 设有下列二叉树:对此二叉树的中序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA第3页排序方法插入排序选择排序交换排序归并排序简单插入排序 希尔排序简单选择排序 堆排序起泡排序快速排序第4页1.7.2.2 插入排序 简单插入、希尔排序1、简单插入排序: 基本思想:从数组的第2号元素开始,顺序 从数组中取出元素,并将该元素插入到其左端 已排好序的数组的适当位置上。第5页待排元素序列:53 27 36 15 69 42第一次排序: 27 53 36 15 69 42第二次排序: 27 36 53 15 69 42第三次排序: 15 27 36 53 69 42
2、第四次排序: 15 27 36 53 69 42第五次排序: 15 27 36 42 53 69 直接插入排序示例对于有n个数 据元素的待排 序列,插入操 作要进行n-1 趟最坏情况下:需要n(n-1)/2次比较 最好:n-1次比较第6页希尔排序:希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体 记录进行一次直接插入排序.最坏情况下:需要O(n1.5 )次比较(O代表不超过括号内数值 的最大整数值。)第7页1、简单选择排序 思想:首先从1n个元素中选出关键字最小的记录交换 到第一个位置上。然后再从第2 个到第n个元素中选出次 小的记录交换到第二个位置上,依次类推。1.7.2.3 选择排序 简单选择排序、堆排序简单选择排序法, 最坏情况需要n(n-1)/2次比较; 第8|92页n初态: 15,14,22,30,37,15,11n第一趟: 11 14,22,30,37,15,15n第二趟: 11,14 22,30,37,15,15n第三趟: 11,14,15 30,37,22,15n第四趟: 11,14,15,15
3、37,22,30n第五趟: 11,14,15,15,22 37,30n第六趟: 11,14,15,15,22,30 37有序序列例:设待排数据元素的关键字为(15,14,22,30 ,37,11),每一趟排序后的序列状态如图所示:第9页2、堆排序(也是一种选择排序)堆是具有特定条件的顺序存储的完全二叉树897624331510112536497856(a):堆顶元素取最大值(b):堆顶元素取最小值堆排序需要比较的 次数为O(nlog2n)(1) 堆的示例 第10页1.7.2.4 交 换 排 序交换排序的特点在于交换。有冒泡和快速排序两种。 1、冒泡排序(起泡排序)思想:小的浮起,大的沉底。从左端开始比较。第一趟:第1个与第2个比较,大则交换;第2个与第3个比较, 大则交换,关键字最大的记录交换到最后一个位置上;第二趟:对前n-1个记录进行同样的操作,关键字次大的记录交换 到第n-1个位置上;依次类推,则完成排序。第11页冒泡排序冒泡排序 u 冒泡排序的方法:n扫描整个线性表,逐次对相邻的两个元素进行比较,若 为逆序,则交换;第一趟扫描的结果使最大(或最小)的 元素排到表的最后(或最前)
4、 ;n除最后(或最前)一个元素,对剩余的元素重复上述过程 ,将次大(或次小)的数排到表的倒数(或正数)第二个位置;n重复上述过程;n对于长度为n的线性表,冒泡排序需要对表扫描n-1遍。 第12页初始 第一趟 第二趟 第三趟 第四趟 第五趟 序列 排序后 排序后 排序后 排序后 排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54设待排数据元素的关键字为( 26,18,32,54,47,9,15 )冒泡排序法,需要比较的次数为n(n-1)/2; 第13页2、快速排序 (对冒泡排序的改进)思想:通过一趟排序将待排序列分成两部分, 使其中一部分记录的关键字均比另一部分小,再分 别对这两部分排序,以达到整个序列有序。时间复杂度:O(log2n) 当待排序列逆序时,蜕变成冒泡排序,时间复杂度: O(n(n-1)/2)第14|92页排序法小结:排序法小结:u 简单选择排序法, 最坏情况需要n(n-1)/2次比较;u 冒泡排序法, 最坏情况需要n(n-1)/2次比较;
《C语言课程课件 二级C语言等级考试 公共基础知识 part2》由会员杨****分享,可在线阅读,更多相关《C语言课程课件 二级C语言等级考试 公共基础知识 part2》请在金锄头文库上搜索。
金属材料与热处理课程总复习课件(ppt)
金属切削原理课件 第8章 工件材料切削加工性
Java EE 课程ppt课件 第13章 Spring基础
Java EE 课程ppt课件 第6章 Struts 2的其他应用
Java EE 课程ppt课件 第2章 Struts 2基础
制作精良优美的高质量PPT模版 紫色主色调简洁风
制作精良优美的高质量PPT模版 数码风格论文答辩模版
制作精良优美的高质量PPT模版 蓝白主色调简洁风
制作精良优美的高质量PPT模版 答辩报告毕业设计 蓝色主色调
弹性力学与有限元教学课件第6.2章 ANSYS软件的应用
机械优化设计课件 绪论第1章 优化设计概述
金属切削原理课件 第9章 切削液
制作精良优美的高质量PPT模版 枣红色 毕业答辩论文模版
制作精良优美的高质量PPT模版 论文答辩 星空背景简洁风
制作精良优美的高质量PPT模版 毕业实习答辩 灰色风格
制作精良的论文答辩PPT模版 橙色主色调
艺术花色文艺风ppt模板
数值分析 第八章 常微分方程数值解法
郑州大学概率论与数理统计课程 第8章 假设检验part2
郑州大学概率论与数理统计课程 第4.4章 大数定律
2023-04-12 16页
2021-07-26 46页
2021-07-26 27页
2021-07-26 14页
2021-07-26 26页
2021-07-26 43页
2021-07-26 10页
2021-02-01 20页
2021-02-01 44页
2021-02-01 15页