ITEEDU

5．6 按引用调用的冒泡排序

下面将图4．16的冒泡排序程序修改成用两个函数bubbleSort和swap(如图5．15)。函数bubbleSort进行数组排序，它调用函数swap，变换数组元素array[j)和array[j+1]记住，C++强制函数之间的信息隐藏，因此swap并不能访问bubbleSort中的各个元素。由于bubbleSort要求swap访问交换的数组元素，因此bubbleSort要将这些元素按引用调用传递给swap．每个数组元素的地址显式传递。

尽管整个数组自动按引用调用传递，但各个数组元素是标量，通常按值调用传递。因此，bubbleSort对swap调用中的每个数组元素使用地址运算符(&)，如下所示的语句：

swap(   &array[ j ]， array[j+   1])；

实现按引用调用。函数swap用指针变量element1Ptr接收&array[j]。由于信息隐藏，swap并不知道名称&array[j]，但swap可以用*element1Ptr作为&array[j]的同义词。这样，swap引用*element1Ptr时，实际上是引用bubbleSort中的&array[j]。同样，swap引用*element2Ptr时，实际上是引用bubbleSort中的array[j+1]。虽然swap不能用：

hold = array [ j ]; 
array[ j ] = array[ j + 1 ]; 
array[ j + 1 ] = hold; 

但图5．15中的swaP函数用

hold = * element1Ptr; 
*element1Ptr = *element2Ptr; 
*element2Ptr = hold; 

达到相同的效果。

// Fig. 5.15: fig05_15.cpp
 // This program puts values into an array, sorts the values into
 // ascending order, and prints the resulting array.
 #include <iostream.h>
 #include <iomanip.h>
 void bubbleSort{ int *, const int );
int main(}
{
   const int arraySize = 10;
   int a[ arraySize ) = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
   int i;
   cout << "Data items in original order\n";
   for ( i = 0; t < arraySize; i++ )
      cout << setw( 4 ) << a[ i ];
   bubbleSort( a, arraySize );        // sort the array
   cout << "\nData items inascending order\n";
   for ( i = 0; i < arraySize; i++ )
      cout << setw( 4 ) << a[ i ];
   cout << endl;
   return 0;
 }
 void bubbleSort( int *array, const int size )
 {
   void swap( int *, iht * );
   for (int pass = 0; pass < size - 1; pass++ )
     for (int j = 0; j < size - 1; j++ )
             if  ( array[ j ]  > array[ j + 1 ]  )
          swap( &array[ j ], &arra[ j + 1 ] );
 }
 void swap( int *element1Ptr, int *element2Ptr )
 {
   int hold = *elementlPtr;
   *element1Ptr = *element2Ptr;
   *element2Ptr = hold;
 }

输出结果：

Data item： in Original Order

2 6 4 8 10 12 89 68 45 37

Data items in ascendinq Order

2 4 6 8 lO 12 37 45 68 89

图5．15 按引用调用的冒泡排序

注意函数bubbleSort中的几个特性。函数首部中将array声明为int* array而不是int array[]，表示bubbleSort接收单下标数组作为参数(这些符号是可以互换的)。参数size声明为const以保证最低权限原则。尽管参数size接收main中数值的副本，且修改该副本并不改变main中的值，但是bubbleSort不必改变size即可完成任务。bubbleSort执行期间数组的长度保持不变，因此，size声明为const以保证不被修改。如果排序过程中修改数组长度，则排序算法无法正确执行。

软件工程视点5．4

将函数原型放在其他函数中能保证最低权限原则，只能从该原型所在函数中正确地调用。

注意函数bubbleSort接收数组长度参数。函数必须知道数组长度才能排序数组。数组传递到函数时，函数接收数组第一个元素的内存地址。数组长度要单独传递给函数。

通过将函数bubbleSort定义成接收数组长度作为参数，可以让函数在排序任何长度单下标整型数组的程序中使用。

软件工程视点5．5

向函数传递数组时，同时传递数组长度(而不是在函数中建立数组长度信息)，这样能使函数更加一般化，以便在许多程序中复用。

数组长度可以直接编程到函数内，这样会把函数的使用限制在特定长度的数组并减少其复用性。程序中只有处理特定长度的单下标整型数组时才能使用这个函数。

C++提供一元运算符sizeof，确定程序执行期间的数组长度或其他数据类型长度(字节数)。采用数组名时(如图5.16所示)，sizeof算符返回数组中的总字节数为size_t类型的值，通常是unsigned int类型。这里使用的计算机将float类型的变量存放在4字节内存中，array声明为20个元素，因此array使用80字节内存空间。在接收数组参数的函数中采用指针参数时，sizeof运算符返回指针长度的字节数(4)而不是数组长度。

常见编程错误5. 7

在函数中用sizeof运算符寻找数组参数长度的字节数时返回指针长度的字节数而不是数组长度的字节数。

// Fig. 5.16: fig05_16.cpp
 // Sizeof operator when used on an array name
 // returns the number of bytes in the array.
 #include < iostream.h>
 size_t getSize( float * );
 int main()
 {
   float array[ 20 ];
   cout << "The number of bytes in the array is"
       << sizeof( array )
       << "\nThe number of bytes returned by getSize is"
       << getSize( array ) << endl;
   return 0;
 }
 size_t getSize( float *ptr )
 {
   return sizeof( ptr );
 }

输出结果：

The number of bytes in the array is 80

The number of bytes returned by getSize is 4 

图5.16 采用数组名时，sizeof运算符返回数组中的总字节数

数组中的元素个数也可以用两个sizeof操作的结果来确定。例如，考虑下列数组声明：

double realArray[ 22   ]；  

如果double数据类型的变量存放在8个字节的内存中，则数组realArray总共包含176个字节。要确定数组中的元素个数，可以用下列表达式：

sizeof   realArray/sizeof(double)  

这个表达式确定realArray数组中的字节数．并将这个值除以内存中存放—个double值的字节数，图5．17的程序用size运算符计算我们所用的个人计算机上存放每种标准数据类型时使用的字节数。

可移植性提示 5．3

存放特定数据类型时使用的字节数随系统的不同而不同。编写的程序依赖于数据类型长度而且要在几个计算机系统上运行时，用sizeof确定存放这种数椐类型时使用的宇节数。

The number of bytes in the array is 80

The number of bytes returned by getSize is 4 

输出结果:

sizeof c = 1 sizeof(char) = 1

sizeof s = 2 sizeof(short) = 2

sizeof i = 4 sizeof(int) = 4

sizeof l = 4 sizeof(long) = 4

sizeof f = 4 sizeof(float) = 4

sizeof d = 8 sizeof(double) = 8

sizeof ld = 8 sizeof(long double) = 8

sizeof array =

图 5．17 用sizeof运算符计算存放每种标准数据类型时使用的字节数

sizeof运算符可以用于任何变量名、类型名或常量值。用于变量名(不是数组名)和常量值时，返回存放特定变量或常量类型所用的字节数。注意，如果提供类型名操作数，则sizeof使用的括号是必需的；如果提供变量名操作数则sizeof使用的括号不是必需的。记住，sizeof是个运算符而不是个函数。

常见编程错误5．8

如果提供类型名操作数，而不在sizeof操作中使用括号则是个语法错误。

性能提示5．2

sizeof属于编译时的一元运算符，而不是个执行时函数。这样，使用sizeof并不对执行性能遣成不良影响。