欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    (8.4.1)--(25)《数据结构》教案.pdf

    • 资源ID:50072242       资源大小:241.96KB        全文页数:5页
    • 资源格式: PDF        下载积分:10金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    (8.4.1)--(25)《数据结构》教案.pdf

    1 第第8章章 内部排序内部排序(共共 6 时时,包括实训内容包括实训内容)课题课题 8.5 归并排序 8.6 计数排序 理论理论课时课时 1 学时 实实训训课时课时 1 学时 教学内容教学内容 归并排序、计数排序 教学目标教学目标 掌握归并排序、计数排序的思想和方法 教学重点教学重点 归并排序、计数排序 教学难点教学难点 归并排序的非递归算法 教学教学活动及主要活动及主要内容内容 学生活动学生活动 一、创设一、创设情境情境,导入新课(,导入新课(2 分钟)(分钟)(直接导入法直接导入法)导入:前面我们学习了归并排序、计数排序,其实还有很多排序的方法比如归并排序、计数排序,那么这两种排序的具体过程是什么样的?效率会不会更高?下面我们来学习归并排序和计数排序。二、新课二、新课讲讲解解(共共计计 16 分钟)(讲解法、提问法、分钟)(讲解法、提问法、演示演示法)法)8.5 8.5 归并排序归并排序 1.基本思想基本思想 归并排序的基本思想来源于有序序列的合并,即将两个或多个有序序列合并为一个大的有序序列。在内部排序中,通常采用的是 2路归并排序,即将两个位置相邻的有序子序列归并为一个有序序列,再不断地扩大有序序列的长度。直到整个序列有序。初始时认为每一个记录都是自身有序的。2.递归的归并排序算法递归的归并排序算法 有序表合并算 void Merge(SortList*SR,SortList*TR,int i,int m,int n)/*将有序序列 SRi.m和 SRm+1.n归并为有序序列 TRi.n*/int j2=m+1,j1=i,k=i;while(j1=m&j2rj1rj2)TR-rk+=SR-rj1+;else TR-rk+=SR-rj2+;while(j1rk+=SR-rj1+;/*将 SRi.m中剩余的记录复制到 TR*/while(j2rk+=SR-rj2+;/*将 SRm+1.n中剩余的记录复制到 TR*/for(k=i;krk=TR-rk;void Msort(SortList*SR,SortList*TR,int s,int t)/*将 SRs.t2_路归并排序为 TRs.t*/激 发 学 生学习归并排序、计 数 排 序的兴趣。学 生 应 掌握归 并 排 序的思 想 和 算法并动手练习 2 int m;if(s=t)TR-rs=SR-rs;else m=(s+t)/2;/*将 SRs.t平分为 SRs.m和 SRm+1.t*/Msort(SR,TR,s,m);/*递归地将 SRs.m归并为有序的 TRs.m*/Msort(SR,TR,m+1,t);/*递归地将 SRm+1.t归并为有序的 TRm+1.t*/Merge(SR,TR,s,m,t);/*归并*/void mergesort(SortList*L)SortList T;Msort(L,&T,1,L-length);【例例 8.12】已知整数序列70,83,100,65,10,32,7,65,9,请给出采用递归的归并排序法对该序列做升序排列的排序的过程。排序过程如图 8.14 所示 图 8.14 归并排序示例 3.非递归的归并排序算法非递归的归并排序算法 1)有序表合并算法 void Msort1(SortList*Q,int b,int d)3/*将两个有序表 Qb.b+d-1与 Qb+d.b+2d-1合并成一个有序表 Qb.b+2d-1*/int i,j,k=0;ElemType*t;t=(ElemType*)malloc(sizeof(ElemType)*(2*d);/*临时空间,能排下两组数据*/i=b;j=b+d;/*各组数据的起始点*/while(ib+d&jlength&jrirj)tk+=Q-ri+;else tk+=Q-rj+;while(iri+;while(jlength&jrj+;for(i=b;iri=ti-b;2)归并排序算法 void mergesort1(SortList*Q)int i,j;for(i=1;ilength;i*=2)/*i 为每组排序时的元素个数,按 2i-1 递增*/j=1;while(jlength)Msort1(Q,j,i);j+=2*i;/*j 为每组排序时的起始位置*/4.算法分析算法分析 由于 2 路归并排序算法通过递归划分有序段的,且递归的深度恰好与 n 个结点的完全二叉树的深度相同,每个有序段的长度均不超过 n,所以两个有序段的合并算法时间数量级不会超过 O(n)。因此,对 n 个记录进行归并排序的时间性能 T(n)=O(nlog2n)。空间上,递归的排序算法需要两个与待排序记录序列空间等长的辅助空间及递归时深度为 log2n的栈空间,因此,总的空间需求为 S(n)=O(n+log2n)。非递归的排序算法仅需要一个与待排序记录序列空间等长的辅助空间,因此,总的空间需求为 S(n)=O(n)。从空间性能上看,非递归的排序算法比递归的算法要好些。归并排序算法是稳定的排序方法。8.6 计数排序计数排序 1.基本思想基本思想 计数排序是通过记录关键字的比较,计算每个记录应该存放的位序。也就是对每个记录,统计记录序列中按关键字值排在它前面的记录个数,然后把每个记录调整到相应位置。2.计数排序算法计数排序算法 void countsort(SortList*L)SortList Q;学 生 应 掌握计 数 排 序的思 想 和 算法并动手练习 4 int i,j,*c;c=(int*)malloc(L-length+1)*sizeof(int);/*开辟一个计数数组*/Q=*L;/*记录序列另存*/for(i=1;ilength;i+)ci=1;/*计数数组各分量初值置 1*/for(i=1;ilength;i+)/*即序号从 1 开始*/for(j=i+1;jlength;j+)if(Q.riQ.rj)ci+;/*计算第 i 条记录排列位置序号*/else cj+;/*计算第 j 条记录的位置序号*/for(i=1;ilength;i+)*按记录序号安排记录顺序*/L-rci=Q.ri;【例例 8.14】已知整数序列70,83,100,65,10,32,7,65,9,请给出采用计数的归并排序法对该序列做升序排列的排序的过程。排序过程如图 8.16 所示 图 8.16 记数排序示例 3.算法分析算法分析 计数排序算法与记录序列的初始状态无关,比较次数固定为 n(n-1)/2,记录移动次数固定为 2n,所以时间性能 T(n)=O(n)。空间上,需要一个与原记录序列空间大小一样的空间及一个计数数组空间,所以,空间性能 S(n)=O(n)。当记录序列接近于反序时,可比简单选择排序移动记录次数少些,这时,计数排序的时间性能比简单选择排序的时间性能好些。计数排序算法是稳定的排序方法。课堂思政:课堂思政:学习学习交换排序交换排序和和选择选择排序排序,要善于总结排序方法,抓住问题关键要善于总结排序方法,抓住问题关键。三三、归纳总结,再度提升归纳总结,再度提升(1 分钟)(讲解法)分钟)(讲解法)1.归并排序 2.计数路径 四四、作业作业,预习任务预习任务(1 分钟)(激趣法)分钟)(激趣法)课后习题:实现递归的归并排序算法和计数排序算法,编写配套的 main 函数,并测试。复习第 8 章内容 学 生 记 录作业 和 预 习内容。5 板 书 设 计 第第 8 8 章章 内部排序内部排序 8.5 8.5 归并排序归并排序 1.基本思想 2.归并排序算法 3.算法分析 8.6 8.6 计数排序计数排序 1.基本思想 2.归并排序算法 3.算法分析

    注意事项

    本文((8.4.1)--(25)《数据结构》教案.pdf)为本站会员(奉***)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开