2.6 本章真题解析

　　例题29
　　在n行n列的矩阵中，每行都有一个最大的数，本程序求这n个最大数中的最小一个。要求将下面的程序填写完整。
　　
　　例题29分析
　　此程序比较简单，就是求最大最小数问题，我们直接来分析程序。
　　
　　上句的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”。
　　例题30
　　函数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-12（a）所示，循环向右平移2个位置后，元素的排列情况如图2-12（b）所示。

图2-12 数组循环右移2个位置

　　
　　例题30分析
　　由后面的注释可知，条件（1）应判断k是否是n的倍数，又因为前面有“k = k % n”，所以，当k为0时，原来的k是n的倍数。因此，第（1）空应填写“k!= 0”或“k”。
　　根据题目所说的规则：若此时移动到位的元素个数已经为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”。
　　当j=i时，退出上面的循环，也就是说，此时a[i]的右边第k个元素的下标为t（因为前面有j=(j-k+n) % n，t=j），所以，应把原来的a[i]存入a[t]，即temp存到a[t]，因此，第（4）空应填写“a[t]”。
　　因为题目提到：若此时移动到位的元素个数已经为n，则结束；否则，从a[2]开始，重复上述过程，直至将所有的元素都移动到目标位置时为止。所以，第（5）空应填写i的下一个元素，即i++。
　　例题31
　　设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由(x0，x1，…，xn-1)变换为(xp，xp+1，…，xn-1，x0，x1，…，xp-1)。要求：
　　（1）给出算法的基本设计思想。
　　（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
　　（3）说明设计算法的时间复杂度和空间复杂度。[2010年试题42]
　　例题31分析
　　本题在本质上与例题30相同，例题30中要求循环向右平移，而本题要求循环向左平移，方法和思路是一样的。在例题30给出的算法中，时间复杂度为O(n2)，空间复杂度为O(1)。
　　为了介绍不同的方法，下面借助一个辅助队列，将数组R中的内容进行移动，从而达到题目的要求。
　　（1）建立一个可以放p个整数的辅助数组（队列），将数组R中的前p个整数依次进入队列，将R中后面的n-p个整数依次前移p个位置，将队列中的数据依次出队，放入R中第n-p个整数开始的位置。
　　（2）使用C语言描述的算法如下：
　　
　　根据以上算法描述可知，该算法的时间复杂度为O(n+p)，空间复杂度为O(p)。
　　例题32
　　采用十字链表存储结构的稀疏矩阵，设计一个查找指定元素值位置的算法。
　　例题32分析
　　十字链表就是既带行指针向量，又带列指针向量的链接存储。在这种链接存储中，每个三元组结点既处于同一行的单链中，又处于同一列的单链表中。本题既可按行序，也可按列序扫描十字链表中的每个结点，当其值等于指定的元素值时，查找成功。
　　下面的算法采用的是行扫描。定义十字链接存储中每个结点类型如下：
　　
　　稀疏矩阵的十字链表存储类型如下：
　　
　　实现算法描述如下：