4.10 循环（重复）结构
循环结构在本质上是一种包含选择结构（循环条件的判断）的重复执行的一组语句序列。标准C++/C语言提供了3种循环结构：do/while、while和for。循环结构基本上可以分为确定循环、不确定循环和无限循环，它们分别又可以叫做计数器控制的循环、标志控制的循环和死循环（busy-loop）。
这3种循环结构的基本语法如下：
它们都在条件表达式为true（非0值）时执行体内的语句序列。但是do/while结构在执行语句序列之后才测试条件表达式的真假，因此它至少要执行体内的语句序列一次，除非像下面这样来用它：
do {
if(条件表达式is false)break;
语句序列
} while (条件表达式);
但是我们强烈建议不要这样使用。
另外两个结构在一开始就判断条件表达式的值，如果为true则执行体内语句序列，否则退出循环。
for结构等价于下面的while结构：
循环控制变量初始化语句;
while (循环控制条件表达式) {
if (循环控制变量不等于其初始值)
修改循环控制变量;
语句序列
}
如果循环体中出现了continue语句，则要防止它跳过循环控制变量的修改语句。for结构中把循环控制变量的修改放在前面而不是后面就是这个道理。
可以使用它们中的任何一种来编写确定循环或不确定循环，但是我们建议：如果你的循环是确定的，最好使用for结构，否则使用while结构，do/while结构不常用。确定循环还有一个不常见的用法：起到延迟作用。
【提示4-19】： 标准C++/C语言允许在for语句中声明（定义）变量，并且它的作用范围为该for语句块内。不过有些语言实现可能没有遵循这个语义，例如，Visual C++就会把这样声明的变量挪到for语句块外，从而它的作用域与for语句相同，在for语句块结束后它仍然有效。这一点要重视。
4.10.1 for语句的循环控制变量
不要使用浮点数做计数器来控制循环，因为它可能是不精确的。
不要在循环体内修改循环变量——除了循环控制变量的递增递减，防止循环失去控制，尤其是for循环。在后面讲到容器的时候也有一条类似的规则：不要在遍历（迭代）容器的过程中对容器进行插入、删除元素的操作。
【建议4-3】： 如果计数器从0开始计数，则建议for语句的循环控制变量的取值采用“前闭后开区间”写法。要防止出现“差1”错误。
例如，示例4-11中的两种风格：
示例4-11
其中x属于前闭后开区间[0, N)，起点到终点的间隔为N，循环次数为N。y属于闭区间[0, N-1]，起点到终点的间隔为N-1，循环次数为N。相比之下，前一种写法更加直观，尽管两者的功能是相同的。
4.10.2 循环语句的效率
标准C++/C循环语句中，for语句使用频率最高，while语句其次，do/while语句很少用。我们着重讨论一下使用for语句遍历多维数组的效率问题。
【建议4-4】： 对于多维数组来说，正确的遍历方法要看语言以什么顺序来安排数组元素的存储空间。比如Fortran是以“先列后行”的顺序在内存中连续存放数组元素，而C++/C则是以“先行后列”的顺序来连续存储数组元素。
因此，以“先列后行”存储的数组，就应该以“先列后行”的顺序遍历，以“先行后列”存储的数组就应该以“先行后列”的顺序遍历。
如示例4-12所示。
示例4-12
double array[1024][512];
for (int r = 0; h < 1024; ++h)
for (int c = 0; c < 512; ++c) {
std::cout << array[r][c] << std::endl;
}
就C++/C多维数组来说，“先行后列”遍历效率肯定好于“先列后行”遍历，不管其行数远大于列数还是情况相反甚至接近，即使在最坏的情况下也至少与“先列后行”遍历的效率相当。影响效率的实际上主要是大型数组导致的内存页面交换次数以及cache命中率的高低，而不是循环次数本身。
我们以二维int类型数组为例来说明这种情况，其他类型的二维数组或二维以上的数组也是同样的道理。
在C++中，二维数组以“先行后列”的顺序存储在连续的内存中。例如，int a[10][3]在内存中的映像如图4-6所示（假设一个int大小为4字节，这是在MSVC下某次执行时打印出来的逻辑地址）。
我们来比较一下“先行后列”遍历和“先列后行”遍历的过程。
“先行后列”：
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 3; ++j)
{
a[i][j] = 0;
}
即外层循环走过每一个行，在走到特定的某一行时，内层循环走过该行包含的每一列的所有元素。显然内层循环执行时地址跳跃的幅度很小，都是连续地依次访问每
一个内存位置相邻的元素，没有跨行存取。
图4-6 C++/C数组的内存映像
“先列后行”：
for (int j = 0; j < 3; ++j)
for (int i = 0; i < 10; ++i)
{
a[i][j] = 0;
}
外层循环依次走访每一列，对于其中的某一列，内层循环依次访问该列包含的每一个元素，但是这些元素的内存位置不再是相邻的，而是跨行的。很显然，地址跳跃的幅度较大。
数组元素的访问是真正的随机访问（直接地址计算）。如果整个数组能够在一个内存页中容纳下，那么在对整个数组进行操作的过程中至少不会为了访问数组元素而出现缺页中断、页面调度和页面交换等情况，只需要一次外存读取操作就可以将数组所在的整个页面调入内存，然后直接访问内存就可以了。此时“先行后列”和“先列后行”的遍历效率差不多（仅有的差别是cache命中率不同，但是差别不大）。
但是如果整个数组内容需要多个内存页来容纳的话，情况就大不一样了，尤其是列数较大的情况下。我们就考虑一种特殊的情况：假设一个内存页的大小为4096字节，并且定义一个int数组，其列数为1024（即每一行的元素恰好占用一页），行数远小于列数，假设为128行。虽然这个假设比较特殊，但是足以说明问题。我们来计算一下“先行后列”遍历和“先列后行”遍历分别需要进行多少次页面交换。
数组定义：
int b[128][1024];
这就是说，该数组每行包含1024个int类型数，正好占据一个内存页的空间，因此整个数组将占据128个内存页。
“先行后列”：
for (int i = 0; i < 128; ++i)
for (int j = 0; j < 1024; ++j)
{
b[i][j] = 0;
}
外层循环走过每一个行，在走到特定的某一行时，内层循环走过该行的1024个元素，正好走完一页，没有发生页面调度，且cache命中率高；当循环进入下一行时操作系统从外存调入下一页。因此可以得知，遍历完整个数组发生页面调度的次数最多为128次（假设一次调度一页）。
“先列后行”：
for (int j = 0; j < 1024; ++j)
for (int i = 0; i < 128; ++i)
{
b[i][j] = 0;
}
在遍历某一列的时候，由于它包含的每一个元素都恰好分别位于每一个行内，因此内层循环每执行一次就会发生一次页面调度，遍历一列下来就会发生128次页面调度，显然总共发生的页面调度次数将可能达到1024×128次（假设一次调度一页），也就是“先行后列”遍历的1024倍。不过实际情况并没有这么坏，因为如果物理内存足够，页面调度和页面交换的次数往往会减少很多。但是可以肯定的是：“先列后行”遍历发生的页面交换次数要比“先行后列”多，且cache命中率相对也低。这恰恰就是导致“先列后行”遍历效率降低的真正原因。
结论（针对大型数组，大规模矩阵）：
（1）当行数远大于列数的时候(m≫n)，“先行后列”遍历的效率高于“先列后行”遍历的效率，这是显然的，但可能不明显。
（2）反之当列数远大于行数的时候(n≫m)，“先行后列”遍历的效率必然高于“先列后行”遍历的效率，这是从上面分析可以得出的结论。
（3）即使行数和列数接近的时候（m≈n），“先行后列”的效率还是高于“先列后行”遍历的效率。
事实胜于雄辩！下面我们就来做一个实际测试，测试代码如示例4-13所示。
示例4-13
const int MAX_ROW = 500;
const int MAX_COLUMN = 10000;
int (*a)[MAX_COLUMN] = new int[MAX_ROW][MAX_COLUMN];
std::cerr << "int array(MAX_ROW = " << MAX_ROW \
<< ", MAX_COLUMN = " << MAX_COLUMN << ")\n";
// 先行后列
DWORD start = GetTickCount();
for (int i = 0; i < MAX_ROW; ++i)
for (int j = 0; j < MAX_COLUMN; ++j)
a[ i ][ j ] = 1;
DWORD end = GetTickCount();
std::cerr << "Stepthrough by row-first-column-last takes " \
<< (end - start) << "毫秒\n";
delete []a;
--------------------------------------------------------------------------------------------------------------------------------
const int MAX_ROW = 500;
const int MAX_COLUMN = 10000;
int (*a)[MAX_COLUMN] = new int[MAX_ROW][MAX_COLUMN];
std::cerr << "int array(MAX_ROW = " << MAX_ROW \
<< ", MAX_COLUMN = " << MAX_COLUMN << ")\n";
// 先列后行
DWORD start = GetTickCount();
for (int j = 0; j < MAX_COLUMN; ++j)
for (int i = 0; i < MAX_ROW; ++i)
a[ i ][ j ] = 1;
DWORD end = GetTickCount();
std::cerr << "Stepthrough by column-first-row-last takes " \
<<(end-start)<<" 毫秒\n";
delete []a;
表4-3是某次不同行列配对下的一组测试结果（单位：ms），测试平台：Intel CPU 1.7GHz + Windows 2000 + MSVC++6.0。
表4-3 多维数组遍历测试结果
比较一下测试结果，看看每种情况下所花费时间的相对大小，一切就都明白了。
【建议4-5】： 如果循环体内存在逻辑判断，并且循环次数很大，宜将逻辑判断移到循环体的外面。
在示例4-14中，左侧的写法比右侧的写法多执行了N-1次逻辑判断，并且前者的逻辑判断打断了循环的“流水线”作业，使得编译器不能对循环进行优化处理，降低了效率。如果N非常大，最好采用右侧的写法，可以提高效率。如果N非常小，两者效率差别并不明显，采用左侧的写法比较好，因为程序更加简洁。
示例4-14
我们举一个循环结构的例子来结束本节：求两个整数的最大公约数和最小公倍数。
求最大公约数可采用辗转相除法，其流程如图4-7所示。最小公倍数就是两个整数的乘积除以其最大公约数，程序见示例4-15。
图4-7 求最大公约数和最小公倍数的流程
示例4-15
int main()
{
unsigned long a,b,c=0; /* 两个整数和临时变量 */
unsigned long lcm=0,gcd=0; /* 最小公倍数和最大公约数 */
while (1) {
printf ( "Please input two positive integers(spacebar as separator): " );
scanf ( "%lu %lu", &a, &b );
if (a <= 0 || b <= 0) {
printf ( "Input error!\n" );
continue;
}
else
break;
}
unsigned long ra=a,rb=b; /* 保存原始数据 */
while (a % b != 0){
c = a % b;
a = b;
b = c;
}
gcd = b;
lcm=(ra*rb)/gcd; /* 使用原始数据计算lcm*/
printf("Their Greatest Common Divisor is %lu.\n", gcd);
printf("Their Least Common Multiple is %lu.\n", lcm);
return 0;
}
// testing
Input two positive integers:1240 85
Their Greatest Common Divisor is 5.
Their Least Common Multiple is 21080.
Input two positive integers:85 1240
Their Greatest Common Divisor is 5.
Their Least Common Multiple is 21080.