C 程序设计 [《C程序设计》中选择法排序教学方法的探讨]

《C程序设计》中选择法排序教学方法的探讨

摘 要：
C语言;
选择法;
数组 C语言因其数据结构丰富，语法简洁灵活，通用性和 可移植性好而成为应用最广泛的计算机语言。在各高校计算 机专业几乎把它开设成为基础课程，为后续课程做好铺垫。

因此，对于计算机专业的学生来说，熟练掌握C语言是至关 重要的。

本文以《C程序设计》中一维数组的经典算法“选择 法”为例，探讨一下教学方法。选择排序的算法步骤如下：
第1步：在未排序的n个数（a[0]～a[n-1]）中找到 最小数，将它与a[0]交换；

第2步：在剩下未排序的n-1个数（a[1]～a[n-1]） 中找到最小数，将它与a[1]交换；

…… 第n-1步：在剩下未排序的2个数（a[n-2]～a[n-1]） 中找到最小数，将它与a[n-1]交换[1]。

在教材中，先是直接列出程序，引出数组的定义形 式、数组元素的引用方式，最后列出选择法排序的思想。学 生本身对双重循环的运用不是太熟练，又引入数组的新知识，结果很难理解其编程思想。结合高职院校学生底子薄，编程 能力弱的情况，又该如何讲授选择法呢？ 1、以实例讲解选择法的思想 有6个数：38、65、97、76、49、27，要求将它们由小 到大排序。

先看课本了解选择法排序的思想，再用幻灯片演示排序 过程。图1为6个数的具体排序过程。用向上箭头指向序列的 第一个数，用向下箭头指向序列的最小数，单击后得到第一 次排序序列，找到序列的最小数，把序列分成了两部分：已 排序序列（方括号外的数据）和未排序序列（方括号内的数 据）；
第二次排序时对除27以外的未排序序列进行排序，单 击后得到第二次排序序列，找到序列的次小数；
依次类推， 排序五次后得到最后的序列。

图1 实例排序过程 通过实例讲解，幻灯片的动画演示，给学生进一步 抽化出选择法的排序步骤：
（1）从未排序的序列中找出最小的数。

（2）用最小的数和未排序序列中第一个数交换。

这样就把选择法转换成求解最小值和数据交换问题， 这两个操作在前面章节中学生已经掌握，从而使问题变得简 单一些。

2、引入数组并找规律 要完成选择法的程序，首先要选择数据结构来存储数据。我们选择一维整型数组来表示这6个数，数组的长度为6，数 据名为a：int a[6]。通过输入操作使a[0]=38，a[1]=65， a[2]=97，a[3]=76，a[4]=49，a[5]=27。列出每一轮每一次 比较的数据（用数组元素表示），就可找到选择法排序的规 律。

第一轮未排序序列：
a[0] a[1] a[2] a[3] a[4] a[5] 第二轮未排序序列：
a[1] a[2] a[3] a[4] a[5] 第三轮未排序序列：
a[2] a[3] a[4] a[5] 第四轮未排序序列：
a[3] a[4] a[5] 第五轮未排序序列：
a[4] a[5] 规律：
（1）在6个数排序中，总共有5组未排序的序列，由于 数组最小下标是0，所以循环从0算起，保证5个序列，可用 一个循环语句表示：“for(i=0;i<=4;i++)”。

（2）在每一轮求最小值时，总是把第一个数给min，第 一个数的下标恰是i的变化，则min=a[i]，求最小值时要和 后面的数组元素依次比较，每一组分别是a[1]到a[5]、a[2] 到a[5]、a[3]到a[5]、a[4]到a[5]，找到如下规律：起始值 的下标恰是i+1,终值的下标均是5,可用一个循环表示：
“for(j=i+1;
j<=5;
j++)”。

（3）未排序的第一个数分别是a[0]、a[1] 、a[2]、a[3] 、 a[4]，观察其下标恰是i的变化，则每组的第一个数用a[i]来表示。

（4）因为j是随着变量i的变化而变化，所以包含j的循 环要放在包含i的循环之内,每一个未排序序列的最小值min 要和第一个数a[i]交换。

为了得到每一次的排序结果，则选择法排序程序代码如 下：
#include ""stdio.h"" main() { int i,j,min,a[6],t;
printf(""input 6 numbers:"");
for(i=0;i<6;i++) scanf(""%d"",&a[i]);
/*输入6个数*/ printf(""output:n"");
for(i=0;
i<=4;
i++) { min=a[i];
for(j=i+1;
j<=5;
j++) if(min>a[j]) min=a[j];
/*找最小值*/ t=a[i];
a[i]=min;
min=t;
/*交换*/ for(j=0;j<6;j++)printf(""%d "",a[j]);
/*输出每一次的排序序 列*/ printf(""n"");
} } 3、验证程序，提出问题 通过上机调试，结果如图2所示。

图2 调试结果 根据图2发现，得到结果和图1的结果不一样，这是为什 么呢？观察图2中数据可以发现，数组中原有的数据被改变 了。为什么会造成这样的结果呢？通过单步跟踪调试程序让 学生观察变量min和数组元素a[0]到a[5]的变化，找到了原 因。原来是我们借助变量min求到了最小值，但和第一个数 交换的是min，而不是值为min的数组元素。在这里，给学生 强调一下数组元素和下标一对一的关系，从而解决了问题。

求最小值时不用变量min来存放，而用a[k]来表示，k代表最 小值的下标,找到了k也就找到了最小值a[k]，求最小值的过 程就变成了求最小值下标的过程。那么，选择法排序过程程 序代码改写如下：
for(i=0;
i<=4;
i++) { k=i;
for(j=i+1;
j<=5;
j++)if(a[k]>a[j]) k=j;
/*用下标找最小值*/ t=a[i];
a[i]=a[k];
a[k]=t;
/*交换*/ } 把这段代码替换上列程序相应部分，再把输出语句 放在最后（即循环外），就得到了最后的程序清单。

通过结合课件展示和推导编程实现程序设计的教学方 法,充分调动了学生学习的积极性和主动性, 对学生逻辑思 维能力和抽象思维能力的培养起到事半功倍的效果,学生对 选择法也有了非常深入的了解。即使不知道程序如何去写， 只要知道选择法的思想，知道求最小值和数据交换的过程， 充分利用循环变量的变化、数组元素和下标值变化之间的一 对一关系,即可推导出来程序。也就是说，不是让学生去背 程序，而是让学生学会理解程序，学会分析问题，并能够通 过程序来解决问题，增强学生独立解决实际问题的编程能力。

参考文献：
[1] 何钦铭 颜晖. C语言程序设计 [M]. 高等教育出 版社，2008 [2] 颜晖. C语言程序设计实验指导 [M]. 高等教育出 版社，2008