第19题  设有下面程序

c_choice19-03

则程序执行后的输出结果是

­      A    5,1,9,7,3,

­      B    3,7,9,1,5,

­      C    9,7,5,3,1,

­      D    1,3,5,7,9,

答案  C

程序解析:

用简单选择排序法对整型数组从大到小排序。

程序从函数main开始执行。声明:

­        int s[5] = {5, 1, 9, 7, 3};
­        int i, j, t;

定义长度为5的整型数组s,分配存储,并初始化,作为待排序数据。定义整型变量i、j,t,分配存储,未作初始化,i、j用于循环控制与索引,t用于辅助排序。凡未经初始化的变量,其初值无意义,仅反映新分配内存的当前随机性物理状态。至此,当前存储状态如下图所示,变量的无意义垃圾值以空白表示。注意:数组名本质上是指向数组首元素的常量指针,常量指针只供引用但不能被赋值,其存储空间是在有关表达式计值过程中临时自动分配的,并不是数组存储块的组成部分。因此,s是整型指针。由于机器内存是一维连续字节序列的本性,数组元素顺次占据一段内存。数组下标从0开始。例如:s是指向第0元素的指针,通过s[i]或∗(s+i)可访问数组s的第i元素。一般而言,若p为整型指针,则通过∗p可访问p所指向的整型变量。

c_choice19-10

首先,执行下列语句,用简单选择排序法完成排序

­        for (i = 0; i < 4; i++)
­           for (j = i+1; j < 5; j++)
­               if (s[i] < s[j]) {
­                    t = s[i];
­                    s[i] = s[j];
­                    s[j] = t;
­               }

看似复杂,在语法上,这只是一条for语句,其循环体也是for语句,这种搭配叫二重for循环,内层for语句的循环体是if语句,而if语句下辖一条块语句(block statement),也叫花括号语句。执行过程是:变量i依次取值0、1、2、3,4,当i取4时,外层循环因i < 4为假而结束。对于i的其余每个取值,均重复执行内层for语句。同理,对于内层for语句,变量j依次取值i+1、i+2、…、4,5,当j取5时,内层循环因j < 5为假而结束。对于j的其余每个取值,均重复执行if语句,若条件s[i] < s[j]成立则执行块语句。

当i取0时,j依次取值1、2、3、4,对j的每个取值,均执行if语句,若条件s[0] < s[j]成立则执行块语句,借助于变量t交换s[0]与s[j]的值,该执行片段的效果是,s[0]一定得到原s[0]至s[4]的最大值,即整个数组的老大9。至此,当前存储状态如下图所示:

c_choice19-11

当i取1时,j依次取值2、3、4,对j的每个取值,均执行if语句,若条件s[1] < s[j]成立则执行块语句,借助于变量t交换s[1]与s[j]的值,该执行片段的效果是,s[1]一定得到原s[1]至s[4]的最大值,即整个数组的老二7。至此,当前存储状态如下图所示:

c_choice19-12

当i取2时,j依次取值3、4,对j的每个取值,均执行if语句,若条件s[2] < s[j]成立则执行块语句,借助于变量t交换s[2]与s[j]的值,该执行片段的效果是,s[2]一定得到原s[2]至s[4]的最大值,即整个数组的老三5。至此,当前存储状态如下图所示:

c_choice19-13

当i取3时,j只取值4,执行if语句,若条件s[3] < s[4]成立则执行块语句,借助于变量t交换s[3]与s[4]的值,该执行片段的效果是,s[3]一定得到原s[3]至s[4]的最大值,即整个数组的老四3,而此时剩下的唯一元素s[4]一定是整个数组的老幺1。至此,当前存储状态如下图所示,整个排序过程完成。

c_choice19-14

综上可知,该排序法的思想是,通过比较和交换依次选择整个数组的老大、老二、…、老幺,从而实现由大到小排序,属于选择排序法,因其简单故称简单选择排序法,还有冒泡排序法、堆排序法都属于选择排序,只是选择方式和效率更高而已。

如果只把if语句的条件s[i] < s[j]改成s[i] > s[j],其它代码均不变,就可实现从小到大排序。如果是N个元素参加排序,只需改变循环条件如下:

­        for (i = 0; i < N−1; i++)
­           for (j = i+1; j < N; j++)
­               if (s[i] < s[j]) {
­                    t = s[i];
­                    s[i] = s[j];
­                    s[j] = t;
­               }

像循环中的0、i+1、N−1、N这些边界值的确定,是需要仔细斟酌的!

接着,执行下面语句输出排序结果:

­        for (i = 0; i < 5; i++)
­           printf(″%d,″, s[i]);

知识点

① 二重for循环的执行过程。

② 简单选择排序法的基本思想。

③ 边界值的确定。

练习题

试为自己设计一道孪生题,举一反三。

孪生题1  设有下面程序

c_choice19-01

则程序执行后的输出结果是

­      A    def,abc,khij,glmno,abxy,

­      B    abxy,glmno,khij,abc,def,

­      C    khij,glmno,def,abxy,abc,

­      D    abc,abxy,def,glmno,khij,

答案  C

解析: 本题同样采用简单选择排序法,但不再是整数参加排序,而是字符串参加排序,字符串按字典序由大到小排序。注意比较两个程序的异同。

程序从函数main开始执行。声明:

­        char a[5][6] = {″def″, ″abc″, ″khij″, ″glmno″, ″abxy″};
­        char ∗s[5], ∗t;
­        int i, j;

定义5×6的字符型数组a,分配存储,并初始化。该二维数组等价于长度为5的一维数组,该一维数组的元素是长度为6的一维字符型数组,而每个长度为6的一维字符型数组可以存储长度不超过5的字符串(因串尾标记空字符′\0′不计入串长,但要占用一个字符位置)。因此,5×6的字符型数组a可容纳5个长度不超过5的待排序字符串。定义长度为5的字符型指针数组s,分配存储,不作初始化,可以存储5个字符型指针。定义字符型指针t,分配存储,不作初始化。 s、t均用于辅助排序。定义整型变量i、j,分配存储,未作初始化,用于循环控制与索引。凡未经初始化的变量,其初值无意义,仅反映新分配内存的当前随机性物理状态。至此,当前存储状态如下图所示,变量的无意义垃圾值以空白表示。C语言把数组名定义为指向首元素的常量指针,只供引用但不能被改变,该指针的存储空间是(在含有数组名的表达式求值过程中)临时自动分配的,并不是数组存储块的组成部分,因此,二维数组名a是指向其第0元素(长度为6的一维字符型数组)的常量指针,必须通过指针式∗(a+i)才能访问二维数组a的第i元素(长度为6的一维字符型数组),但也可采用下标式a[i]访问a的第i元素,a[i]会自动转换为∗(a+i)。因为∗(a+i)或a[i]仅代表a的第i元素(长度为6的一维字符型数组),是一维数组名,可继续套用数组名定义,因此∗(a+i)或a[i]是指向其第0元素(字符型值)的常量指针,必须通过指针式∗(∗(a+i)+j)才能访问一维字符型数组∗(a+i)或a[i]的第j元素,但也可采用下标式(∗(a+i))[j]或a[i][j]访问一维字符型数组∗(a+i)或a[i]的第j元素,(∗(a+i))[j]或a[i][j]会自动转换为∗(∗(a+i)+j)。上面推理是比较费解的,对考生而言,记住用下标式a[i]访问二维数组的第i行字符串就行了!机器内存是一维连续字节阵列,数组元素连续占据一段内存,数组下标从0开始。二维数组a由5个长度为6的一维字符型数组组成,其存储结构如下图所示,这5个一维字符型数组连续占据一段内存,二维数组名a这个指针指向首元素即第0个长度为6的一维字符型数组,以红色矩形框表示,一维数组名a[0]、a[1]、…、a[4]分别指向各一维字符型数组的首字符。一维数组s由5个字符型指针值组成,其存储结构如下图所示,这5个字符型指针值连续占据一段内存,数组名s这个指针指向首元素即第0个字符型指针值。

c_choice19-04

首先,执行下面语句

­        for (i = 0; i < 5; i++)
­             s[i] = a[i];

令字符指针数组s的5个字符指针分别指向a中的5个字符串的首字符,后面程序将通过字符指针s[0]、s[1]、…、s[4]访问5个待排序字符串,当需要交换字符串时,只交换相应指针值,从而避免字符串的实际移动,以提高算法效率。

c_choice19-05

接着,执行下列语句,用简单选择排序法完成排序

­        for (i = 0; i < 4; i++)
­           for (j = i+1; j < 5; j++)
­               if (strcmp(s[i], s[j]) < 0) {
­                    t = s[i];
­                    s[i] = s[j];
­                    s[j] = t;
­               }

同上面程序完全类似,只是用strcmp(s[i], s[j]) < 0充当if语句条件,调用库函数strcmp完成s[i]与s[j]的比较,根据字典序,若s[i]小于s[j],则返回某个负值;若s[i]大于s[j],则返回某个正值;若s[i]等于s[j],则返回0。strcmp要求 #include <string.h>支持。

当i取0时,j依次取值1、2、3、4,对j的每个取值,均执行if语句,若条件strcmp(s[0], s[j]) < 0成立则执行块语句,借助于指针变量t交换s[0]与s[j]的指针值,该执行片段的效果是,指针s[0]一定指向原s[0]至s[4]的最大值字符串(字典序),即整个数组的老大″khij″。至此,当前存储状态如下图所示:

c_choice19-06

当i取1时,j依次取值2、3、4,对j的每个取值,均执行if语句,若条件strcmp(s[1], s[j]) < 0成立则执行块语句,借助于指针变量t交换s[1]与s[j]的指针值,该执行片段的效果是,指针s[1]一定指向原s[1]至s[4]的最大值字符串(字典序),即整个数组的老二″glmno″。至此,当前存储状态如下图所示:

c_choice19-07

当i取2时,j依次取值3、4,对j的每个取值,均执行if语句,若条件strcmp(s[2], s[j]) < 0成立则执行块语句,借助于指针变量t交换s[2]与s[j]的指针值,该执行片段的效果是,指针s[2]一定指向原s[2]至s[4]的最大值字符串(字典序),即整个数组的老三″def″。至此,当前存储状态如下图所示:

c_choice19-08

当i取3时,j只取值4,执行if语句,若条件strcmp(s[3], s[4]) < 0成立则执行块语句,借助于指针变量t交换s[3]与s[4]的指针值,该执行片段的效果是,指针s[3]一定指向原s[3]至s[4]的最大值字符串(字典序),即整个数组的老四″abxy″,而此时剩下的唯一元素s[4]一定指向老幺″abc″。至此,当前存储状态如下图所示,整个排序过程完成。

c_choice19-09

接着,执行下面语句输出排序结果:

­        for (i = 0; i < 5; i++)
­           printf(″%s,″, s[i]);

孪生题2  设有下面程序

c_choice19-02

则程序执行后的输出结果是

­      A    def,abc,khij,glmno,abxy,

­      B    abxy,glmno,khij,abc,def,

­      C    khij,glmno,def,abxy,abc,

­      D    abc,abxy,def,glmno,khij,

答案  D

解析: 本题对字符串按字典序由小到大排序。注意比较与孪生题1的异同,仅将strcmp中的小于号换成了大于号,其它代码完全相同。

这两道孪生题是本题重点,要想拿分,必须理解消化!

返回