c++b.txt

C语言是一种面向过程的计算机程序设计语言。最初为unix而生。它既有高级语言的特点

 4．27 (八皇后：强制算法)这个练习要用几个强制算法解决练习4.26介绍的八皇后问题。
    a)用练习4．25介绍的随机强制算法解决八皇后问题。
    b)用穷举法，即测试八个皇后在棋盘上的各种组合。
    c)说明穷举法为什么不适用于骑士旅行问题?
    d)比较随机强制算法与穷举法。

4．28(骑士旅行：闭合线路)在骑士旅行问题中，骑士经过64格中的每一格一次，且只经过一次。闭合线路就是最后又回到出发的地方。修改练习4．24的骑士旅行程序，测试闭合线路是否走遍了棋盘。

4．29(Eratosthenes筛选法)质数是只能被1和本身整除的数。Eratesthenos筛选法是一种寻找质数的方法，这个方法如下所示：
    a)生成一个数组，将所有元素初始化为1(真)。下标为质数的数组元素保持1，所有其他数组元素最终设置为o。
    b)从数组下标1开始(下标1为质数)，每次找到数值为1的数组元素时，对数组余下部分循环，将下标为该下标倍数的元素设置为0。对于数组下标2，数组中下标为2的倍数的所有元素(除2本身，如4、6、8、10等等)都设置为0；对于数组下标3，数组中下标为3的倍数的所有元素(除3本身，如1、6、9、12、15等等)都设置为0,依次类推。
    这个过程完成之后，如果数组元素还是1，则下标为质数。这些下标可以打印出来。编写一个程序，用1000个元素的数组确定和打印1到999之间的素数，忽略数组中的元素0。

4．30(桶排序)桶排序从要排序的单下标正整数的数组开始，并有一个双下标整数数组，行下标为0到9，列下标为。到n-1，其中n为要排序数组中的数值个数。每一行双下标整数数组称为一个桶。编写一个bucketSorL函数，取整数数组和数组长度参数，并进行下列操作：
    a)将单下标数组的每个值放到桶数组的行中(根据该值的个位)。例如，97放在第7行，3放在第3行，100放在第0行，称为“分布传递”。
    b)一行一行地对桶数组进行循环，将值复制回原数组，称为“收集传递”。上述值在单下标数组中的新顺序为100、3、97。
    c)对十位、百位、千位等重复上述过程。
    第二遍，100放在第0行，3放在第0行(因为3没有十位)，97放在第9行。经过收集传递之后，上述值在单下标数组中的新顺序为100、3、97。第三遍，将100放在第1行，3和97放在第行0行。经过收集传递之后，上述值在单下标数组中的新顺序为所要的排序结果。
    注意，双下标桶数组的长度是要排序的整数数组长度的10倍。这种排序方法提供比冒泡排序更好的性能，但要求更多的内存。冒泡排序方法只要多一个数据元素的空间。这就是用空间交换时间的范例：桶排序方法比冒泡排序更快，但使用更多内存。这个存储桶排序方法要求每遍都将所有数据复制回原数组中。另一种方法是生成第二个双下标数组，在两个桶数组之间重复交换数据。

递归练习

4．3l(选择排序)选择排序查找数组中的最小元素。然后将最小元素与数组中第一个元素交换。从第二个数组元素开始的子数组重复这个过程。每一次都把一个元素放到正确的位置。这种排序与冒泡排序相似，对于n个元素的数组，要n-l遍，对每个子数组，要用n-1次比较以求得最小值。处理包含一个元素的子数组时，数组已经排序完毕。编写递归函数selectionSort，完成这个算法。

4．32(回文)回文就是正读反读都一样的字符串，例如“radar"，“able was i ere i saw elba”和"a man a plan a canal panama"(如果忽略空格)。编写递归函数testPalindrome，在数组中的字符串为回文时返回true，否则返回false。函数忽略字符串中的空格和标点符号。

4．33(线性查找)修改图4.19．用递归函数linearsearch对数组进行线性查找，函数应收到整型数组和数组长度参数。如果找到查找健，则返回数组下标，否则返回-1。
4．34(折半查找)修改图4．20，用递归函数binarySearch对数组进行折半查找。函数应收到整型数组和开始下标与结束下标参数。如果找到查找键，则返回数组下标，否则返回-1。
4．35(八皇后)修改练习4．26的八皇后程序，用递归方法解决问题。
4．36 (打印数组)编写递归函数pritArray，取数组和长度参数，不返回任何内容。函数在收到长度为0的数组时停止处理并返回。
4．37(逆向打印字符串)编写函数stringReverse，取包含字符串的字符数组参数，逆向打印字符串且不返回任何内容。函数在收到null终止符时停止处理并返回。
4．38(寻找数组中的最小值)编写递归程序recursiveMinimum，取数组和长度参数并返回数组中的最小元素，当函数在收到长度为1的数组时停止处理并返回。





[Amber demo]



发表日期：2003年5月19日  出处：C++大学教程  作者：C语言之家整理  已经有2048位读者读过此文



教学目标
    ●能够使用指针
    ●能用指针按引用调用向函数传递参数
    ●了解指针、数组与字符串之间的密切关系
    ●了解指针在函数中的使用
    ●能够声明和使用字符串数组

5．1  简介
    本章介绍“C++编程语言一个最强大的特性——指针。指针是C++中最难掌握的问题之一。第3章介绍了引用可以用于实现按引用调用。指针使程序可模拟按引用调用，生成与操作动态数据结构，即能够伸缩的数据结构，如链表、队列、堆栈和树。本章介绍基本的指针概念，而且强调了数组、指针与字符串之间的密切关系．并包括一组很好的字符串操作练习。
    第6章介绍结构中的指针使用。第9章和第10章介绍如何用指针和引用进行面向对象编程。第15章介绍动态内存管理技术以及生成和使用动态数据结构的例子。
    把数组和字符串看成指针是从C语言演变而来的。本书后面会介绍把数组和字符串当作成熟的对象。

5．2  指针变量的声明与初始化
    指针变量的值为内存地址。通常变量直接包含特定值，而指针则包含特定值变量的地址。因此可以说，变量名直接(directly)引用数值，而指针间接(indirectly)引用数值(如图5．1)。通过指针引用数值称为间接引用。
    指针和任何其他变量一样，应先声明后使用。下列声明：
    int  *countPtr，  count;
  声明变量countPtr的类型为int*(即指向整型值的指针)，或者说成"countPtr是int的指针"或"countPtr指向整数类型的对象"。变量count声明为整数，而不是整型值的指针。声明中的*只适用于countPtr。
  声明为指针的每个变量前面都要加上星号(*)。例如，下列声明：
    float  *xPtr，*yPtr；
  表示xPtr和yPtr都是指向float值的指针。声明中以这种方式使用*时，它表示变量声明为指针。指针可以声明为指向任何数据类型的对象。 

    常见编程错误5．1
    假设对指针的声明会分配到声明中逗号分隔的指针变量名列表中的所有指针变量名，从而将指针声明为非指针。声明为指针的每个变量前面都要加上星号(*)。
    编程技巧5．1
    尽管不是必需的，但在指针变量名中加上Ptr字样能更清楚地表示这些变量是指针，需要相应的处理。



?????????????????????流敢???潃癮牥整??金??吠楲污瘠牥楳湯??????????????????

                            图5．1  直接和间接引用变量

    指针应在声明时或在赋值语句中初始化。指针可以初始化为0、NULL或—个地址。数值为0或NULL的指针不指任何内容。NULL是头文件<iostream.h>(和另外几个标准库头文件)中定义的符号化常量。将指针初始化为NULL等于将指针初始化为0，但C++中优先选择0。指定0时，它变为指针的相应类型。数值0是惟一可以不将整数转换为指针类型而直接赋给指针变量的整数值。5．3节将介绍将变量地址赋给指针。

    测试与调试提示5．1
    初始化指针以防止其指向未知的或未初始化的内存区。

5．3  指针运算符
&(地址)运算符是个一元运算符，返回操作数的地址。例如，假设声明：
    int  y = 5；
    int *yPtr；
则下列语句：
    yPtr = &y；
将变量y的地址赋给指针变量yPtr。变量yPtr“指向”y。图5．2显示了执行上述语句之后的内存示
意图。图中从指针向所指对象画一个箭头．表示“指向关系”。
    图5．3显示了指针在内存中的表示，假设整型变量y存放在地址600000，指针变量yPtr存放在
地址500000。地址运算符的操作数应为左值，(即要赋值的项目，如变量名)．地址运算符不能用于
常量、不产生引用的表达式和用存储类regtster声明的变量。
    ”*”运算符通常称为间接运算符(indirection operator)或复引用运算符(dereferencing operator)，
返回操作数(即指针)所指对象的同义词、别名或浑名。例如(图5．2再次引用)，下列语句：
 cout  <<  * yPtr  <<  endl；
指向变量y的值(5)，如同下列语句：
    cout  <<  y  <<  endl；


?????????????????????流敢???潃癮牥整??金??吠楲污瘠牥楳湯??????????????????

                                          图5．2  指针指向内存中整数变量的示意图

    这里使用*的方法称为复引用指针(dereferencing a pointer)。注意复引用指针也可以用于赋值语句左边，例如下列语句：
    *yPtr = 9；
将数值9赋给图5．3中的y。复引用指针也可用于接收输入值，例如：
    cin>> *yPtr；
复引用的指针是个左值。
                                 yptr               y
                       500000    600000    600000    5

                          图 5．3  指针在内存中的表示

    常见编程错误5．2
    如果指针没有正确地初始化或没有指定指向内存中的特定地址，则复引用指针可能造成致命的运行时错误，或者意外修改重要数据。虽然运行完程序，但得到的是错误结果。
    常见编程错误5．3
    复引用非指针是个语法错误。
    常见编程错误5．4
    复引用0指针通常是个致命的运行时错误。
    图5.4的程序演示了指针运算符。本例中通过<<用十六进制整数输出内存地址(十六进制整数见附录“数值系统”)。
    可移植性提示 5. 1
    输出指针的格式与机器有关，有些系统用十六进制整数，而有些系统用十进制整数。
    注意a的地址和aPtr的值在输出中是一致的，说明a的地址实际赋给了指针变量aptr。&和*运算符是互逆的，如果两者同时作用于aPtr，则打印相同的结果。图5．5显示了前面所介绍的运算符的优先级和结合律。
1 // Fig. 5.4: fig05_04.cpp
2 // Using the & and * operators
3 #include <iostream.h>
4
5 int main()
6{
7   int a;      // a is an integer
8   iht *aPtr;   // aPtr is a pointer to an integer
9
10   a = 7;
11   aPtr = &a;   // aPtr set to address of a
12
13   cout << "The address of a is "<< &a
14       << "\nThe value of aPtr is" << aPtr;
15
16   cout << "\n\nThe value of a is "<<a
17       << "\nThe value of *aPtr is" << *aPtr;
18
19   cout << "\n\nShowing that * and & are inverses of"
20       << "each other.\n&*aPtr =" << &*aPtr
21       << "\n*&aPtr =" << *&aPtr << endl;
22   return 0;
23 }

输出结果：
The address of a is Ox0064FDF4
The value of aPtr is 0x0064FDF4
The value of a is 7
The value of *aPtr is 7
Showing that * and & are inverses of each other.
&*aPtr = 0x0064FDF4
*&aPtr = 0x0064FDF4

                             图 5.4 &与*指针运算符

        ------------------------------------------------------------------------------
            运算符                                结合律                类型
        ------------------------------------------------------------------------------
            ()  []                               从左向右               括号
            ++  --  +  -  static_cast<type>()    从右向左               一元  
            &  *
            *  /  %                              从左向右               乘
            +  -                                 从左向右               加
            <<  >>                               从左向右               插入/读取
            <  <=  >  >=                         从左向右               关系
            ==  !=                               从左向右               相等
            &&                                   从左向右               逻辑AND
            ||                                   从左向右               逻辑或
            ?:                                   从右向左               条件
            =  +=  -=  *=  /=  %=                从右向左               赋值
            ,                                    从左向右               逗号
        ------------------------------------------------------------------------------
                                图 5.5 运算符的优先级和结合律

5．4  按引用调用函数
   C++用三种方式向函数传递数值：按值调用(call-by-value)、用引用参数按引用调用(call-by-reference reference argument)和用指针参数按引用调用(call-by-reference pointer argument)。第3章比较了按引用调用与按值调用，本章主要介绍用指针参数按引用调用。
    第3章曾介绍过，return可以从被调用函数向调用者返回一个值(或不返回值而从被调用函数返回控制)。我们还介绍了用引用参数将参数传递给函数，使函数可以修改参数的原有值(这样可以从函数“返回”多个值)，或将大的数据对象传递给函数而避免按值调用传递对象的开销(即复制对象所需的开销)。指针和引用一样，也可以修改调用者的一个或几个变量，或将大的数据对象指针传递给函数而避免按值调用传递对象的开销。
    在C++中，程序员可以用指针和间接运算符模拟按引用调用(就像C语言程序中的按引用调用一样)。调用函数并要修改参数时，传递该参数地址，通常在要修改数值的变量名前面加上地址运算符(&)。第4章曾介绍过，数组不能用地址运算符(&)传递，因为数组名是内存中数组的开始位置(数组名等同于&arrayName[0])，即数组名已经是个指针。向函数传递参数地址时，可以在函数中使用间接运算符形成变量名的同义词、别名或浑名，并可用其修改调用者内存中该地址的
值(如果变量不用const声明)。
    图5．6和5．7的程序是计算整数立方函数的两个版本cubeByValue和cubeByReference。图5．6按值调用将变量number传递给函数cubeByValue。函数cubeByValue求出参数的立方，并将新值用return语句返回main，井在main中将新值赋给number。可以先检查函数调用的结果再修改变量值。例如，在这个程序中，可以将cubeByValue的结果存放在另一变量中，检查其数值，然后再将新值赋给number。

1 // Fig. 5,6: fig0506,cpp
2 // Cube a variable using call-by-value
3 #include <iostream.h>
4
5 int cubeByValue( int );  // prototype
6
7 int main()
8 {
9   int number = 5;
10
11   cout << "The original value of number is "<< number;
12   number = cubeByValue( number );
13   cout << "\nThe new value of number is" << number << endl;
14   return 0;
15 }
16
17 int cubeByValue( int n )
   {
18
19   return n * n * n;  // cube local variable n
2O }

输出结果:
The original value of number is 5
The new value of number is 125

                                                              图5．6 按值调用求出参数的立方

 图5．7的程序按引用调用传递变量nunber(传递number的地址)到函数cubeByReference。函
数cubeByReference取nPtr(int的指针)作为参数。函数复引用指针并求出nPtr所指值的立方，从
而改变main中的number值。图5．8和5．9分别分析了图5．6和1．7所示程序。
1 // Fig. 5.7: fig05_07.cpp
2 // Cube a variable using call-by-reference