2.3 数组的概念和实现

二、综合应用题

　　1．综合应用题题目部分
　　 ● 习题1：在n行n列的矩阵中，每行都有最大的数，本程序求这n个最大数中的最小一个。要求将下面的程序填写完整。

　　● 习题2：函数void rcr(int a[],int n,int k)的功能是：将数组a中的元素a[0]～a[n-1]循环向右平移k个位置。
　　为了达到总移动次数不超过n的要求，每个元素都必须只经过一次移动到达目标位置。在函数rcr中用如下算法实现：首先备份a[0]的值，然后计算应移动到a[0]的元素的下标p，并将a[p]的值移至a[0]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p]；依此类推，直到将a[0]的备份值移到正确位置。
　　若此时移动到位的元素个数已经为n，则结束；否则，再备份a[1]的值，然后计算应移动到a[1]的元素的下标p，并将a[p]的值移至a[1]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p]；依此类推，直到将a[1]的备份值移到正确位置。
　　若此时移动到位的元素个数已经为n，则结束；否则，从a[2]开始，重复上述过程，直至将所有的元素都移动到目标位置时为止。
　　例如，数组a中的6个元素如图2-2（a）所示，循环向右平移两个位置后元素的排列情况如图2-2（b）所示。

　　2．综合应用题答案与分析
　　习题1分析：
　　此程序比较简单，就是求最大最小数问题，我们直接来分析程序。

　　上句的for循环结合if语句是用于查找第row行的最大数。max有实初值a[row][0]，所以当后面的数a[row][col]比max大时，要对max进行更新，因此，（1）空应填max<a[row][col]。

　　现在的max中存的是第row行的最大值，当row行的最大值小于min时，应对min更新。所以应有条件max < min。但只有当min有值时才能进行条件max<min的判断，现在看程序中对min赋予的初值是什么？经查找发现程序并没有对min赋予初值，所以上面的两个min=max中，第一个是对min赋予初值。当求出第0行的最大值时，便可对min赋予初值了。因此，（2）空应填row == 0，（3）空应填max < min。
　　习题2分析：
　　（1）后面的注释可知条件（1）应判断k是否是n的倍数，又因为前面有k = k%n，所以当k为0时，原来的k是n的倍数。因此，第（1）空应填k!= 0或k。
　　（2）、（3）根据题目所说的规则“若此时移动到位的元素个数已经为n，则结束；否则，再备份a[1]的值，然后计算应移动到a[1]的元素的下标p，并将a[p]的值移至a[1]；接着计算应移动到a[p]的元素的下标q，并将a[q]的值移至a[p]；依此类推，直到将a[1]的备份值移到正确位置”。可知j是前面所说的p，而t是前面的q，所以第（3）空的答案已经很明显了，就是更新t的值为j。第（2）空是计算j，从循环体内部的语句可以看出，j是要移到t位置元素的下标，又因为题目提到的例子是右移，所以以右移k位为规则，来计算j的值，即j位置应存放它左边的第k个元素，因此j =(j-k+n)%n。
　　（4）当j == i时，退出上面的循环，也就是说此时a[i]的右边第k个元素的下标为t（因为前面有j = (j-k+n)%n,t = j），所以应把原来的a[i]存入a[t]，即把temp存到a[t]，因此，第（4）空应填a[t]。
　　（5）因为题目提到：“若此时移动到位的元素个数已经为n，则结束；否则，从a[2]开始，重复上述过程，直至将所有的元素都移动到目标位置时为止”。所以第（5）空应填i的下一个元素，即i++。
　　3．训练自测表（如表2-11所示）

表2-11 选择题练习自测表