资源描述：
《第9章实验-直接插入、折半插入排序-教案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、湖北第二师范学院计算机学院2012至2013学年第上学期一数据结构》课程教案课稈编码：B0310008课程类别：专业基础学分：3.5总学吋/周学吋：68/5上课学吋：_54_实验学吋：18开课时间：2012年9月4日第1周至第17周授课年级、专业、班级：2011级、计算机科学与技术（嵌入式）、11计科4使用教材：《数据结构一一C语言描述》（第二版）授课教师与职称：鲁静讲师周次第周时间年力日第节授课方式（请打丿）理论课、讨论课口实验课习题课口其他口2扌?2授课题目（教学章、节或主题）：第9章：排序主题：直接插入排序、折半插入排序实验教学目的、要求
2、（分掌握、熟悉、了解三个层次）：掌握：直接插入排序、折半插入排序方法熟悉：直接插入排序、折半插入排序算法了解：直接插入排序、折半插入排序效率教学重点及难点：教学重点：直接插入排序、折半插入排序的过程教学难点：直接插入排序、折半插入排序的调试教学基本内容1.预习要求学生在实验前应做好各项准备工作。首先要学习教材上与本实验内容相关的章节；其次对己学过的知识进行回顾与总结；然后按题目的要求进行分析和思考，在反复推敲的基础之上，描述自己的算法思想及实现方式；最后编写程序初稿并在有条件的情况下，尽可能地把编好的程序输入到计算机试运行。2.实验操作方面要求
3、实验要求在PC机上VC++6.0环境下实现。因此，学生应该尽快地熟悉该运行环境，并能够熟练运用高级语言的程序调试器DEBUG调试程序。Ftl于本课程实验内容对应的程序一般都比较大，因此，要求学生在进实验室前，已基本完成程序的录入工作。在实验室，主要是在老师的帮助下进行程序的调试，通过不断地修正错误，最终能圆满完成实验任务并通过指导老师的验收。3.实验报告要求实验报告的开头应给出题H、班级、姓名、学号和完成日期，并包扌舌以下七个方面的内容：（1）需求分析（2）概要设计（3）详细设计（4）调试分析（5）测试结果（6）源程序清单（或提交电子文件）（7
4、）总结与提高4个函数。1输入2——直接插入排序3—一折半插入0推出程序：#include#defineMAXSIZE20typedefstruct{intrfmaxsize+1];intlength;}sqlist;typedefsqlist^pointer;intlow,high;pointerp,l;inti,j,n;scanfelem（）{printf（“请输入:n=9y）;}方法及手段(可增加页)(i=l;i<=n;i++){printf(<4r[%d]=M,i);scanf(t<%d,,,&L->r[i]);}；
5、L->length=n;}insertsort(){for(i=2;i<=L->length;++i)if(L->r[i]<=L->r[i-l]){L->r[0]=L->r[i];L->r[il=L->r[i-l];For(j=i-2;L->r[0]<=L->rfjl;-j)L->rU+l]=L->r[j]；L->r[j+l]=L->r[0];}for(i=l;i<=L->length;i++)printf(t4%d,L->r[i];}binsertsort(){intm;for(i=2;i<=L->length;++i){L->r[0]=L
6、->r[i];Low=l;high=i-1;While(low<=high){m=(low+high)/2;if(L->r[0]<=L->r[m])high二m-1;elselow=m+l;}for(j=i-1;j>=high+1j)L->r[j+l]=L->r[j];L->r[high+l]=L->r[OJ;}for(i=l;i<=L->length;i++)printf(“％d",L・>r[i];)main(){intk=l;while(k){printfCl—输入“)；printf(u2一直接插入排序“)；printf(u3—折半插入
7、“)；printfCO一退出iT);printf(“请选择E);scanf(“％d",&k);switch(k){case1:scanfelem();break;case2:insertsort();break;case3:binsertsort();break;case0:break;}}}上机实验理论联系实际作业、讨论题、思考题：1写出使用直接选择排序法对下列数据进行从小到大排序的中间过程和最后结果。[83,40,63,13,84,35,96,57,39,79,61,15]2写出使用折半插入排序法对下列数据进行从小到大排序的中间过程和最后
8、结果。[83,40,63,13,84,35,96,57,39,79,61,15]课后小结：1掌握常用排序算法的特点，以便根据实际情况选择使用。。2要求
