第9章实验-直接插入、折半插入排序-教案.doc

湖北第二师范学院计算机学院

20 12 至20 13 学年 第 上 学期

________数据结构》_____________课程

教

案

课程编码：B0310008 课程类别：专业基础 学分：_3.5_

总学时/周学时： 68 / 5 上课学时： 54 实验学时： 18

开课时间： 2012 年 9 月 4 日 第 1 周至第 17 周

　　　　 授课年级、专业、班级：2011级、计算机科学与技术(嵌入式)、11计科4

使用教材： 《数据结构－－ C语言描述》（第二版）

授课教师与职称：　　　鲁静 讲师______________

周 次
第 周
时间
年 月 日 第 节
授课方式
（请打√）
理论课、讨论课□ 实验课√□ 习题课□ 其他□
课时
安排
2
授课题目（教学章、节或主题）：
第9章：排序
主题：直接插入排序、折半插入排序实验
教学目的、要求（分掌握、熟悉、了解三个层次）：
掌握：直接插入排序、折半插入排序方法
熟悉：直接插入排序、折半插入排序算法
了解：直接插入排序、折半插入排序效率

教学重点及难点：
教学重点：直接插入排序、折半插入排序的过程
教学难点：直接插入排序、折半插入排序的调试

教 学 基 本 内 容
1．预习要求
学生在实验前应做好各项准备工作。首先要学习教材上与本实验内容相关的章节；其次对已学过的知识进行回顾与总结；然后按题目的要求进行分析和思考，在反复推敲的基础之上，描述自己的算法思想及实现方式；最后编写程序初稿并在有条件的情况下，尽可能地把编好的程序输入到计算机试运行。
2．实验操作方面要求
实验要求在PC机上VC++6.0环境下实现。因此，学生应该尽快地熟悉该运行环境，并能够熟练运用高级语言的程序调试器DEBUG调试程序。由于本课程实验内容对应的程序一般都比较大，因此，要求学生在进实验室前，已基本完成程序的录入工作。在实验室，主要是在老师的帮助下进行程序的调试，通过不断地修正错误，最终能圆满完成实验任务并通过指导老师的验收。
3．实验报告要求
实验报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个方面的内容：
（1）需求分析
（2）概要设计
（3）详细设计
（4）调试分析
（5）测试结果
（6）源程序清单（或提交电子文件）
（7）总结与提高
4个函数。
1――输入
2――直接插入排序
3――折半插入
0――推出

程序：
#include<stdio.h>
  #define MAXSIZE 20
  typedef struct
  {
int r[maxsize+1];
int length;
}sqlist;
typedef sqlist *pointer;
int low,high;
pointer p,l;
int i,j,n;

scanfelem()
{
printf(“请输入：n=”);
}

方法及手段
（可增加页）(i=1;i<=n;i++)
{
printf(“\nr[%d]=”,i);
scanf(“%d”,&L->r[i]);
}；L->length=n;
} 
insertsort()
{for(i=2;i<=L->length;++i)
if(L->r[i]<=L->r[i-1])
{L->r[0]= L->r[i];
L->r[i]= L->r[i-1];
For(j=i-2; L->r[0]<= L->r[j];--j)
L->r[j+1]= L->r[j];
L->r[j+1]= L->r[0];
}
for(i=1;i<= L->length;i++)printf(“%d”, L->r[i];
} 
binsertsort()
{int m;
for(i=2;i<= L->length;++i)
{L->r[0]= L->r[i];Low=1;high=i-1;
While(low<=high)
{m=(low+high)/2;
if(L->r[0]<= L->r[m]) high=m-1;
else low=m+1;
}
for(j=i-1;j>=high+1;--j)  L->r[j+1]= L->r[j];
L->r[high+1]= L->r[0];
}
for(i=1;i<= L->length;i++)
printf(“%d”, L->r[i];
} 
main()
{int k=1;
while(k)
{printf(“\n1—输入“);
printf(“2—直接插入排序“);
printf(“3—折半插入“);
printf(“0—退出\n”);
printf(“请选择\n”);
scanf(“%d”,&k);
switch(k)
{case 1:scanfelem();break;
case 2:insertsort();break;
case 3:binsertsort();break;
case 0:break;
}
}
}

上机实验
理论联系实际
作业、讨论题、思考题：
1写出使用直接选择排序法对下列数据进行从小到大排序的中间过程和最后结果。
[83，40，63，13，84，35，96，57，39，79，61，15]
2写出使用折半插入排序法对下列数据进行从小到大排序的中间过程和最后结果。
[83，40，63，13，84，35，96，57，39，79，61，15]

课后小结：
1掌握常用排序算法的特点，以便根据实际情况选择使用。。
2要求学生按要求完成实验报告。重点考查实验过程是否认真、是否主要是经过学生自己的努力完成的实验；考察实验报告是否书写完整、清晰、整洁。