否则，先“迈一步”到达(g,h)点，而后再进行递归调用：solve(g, h, k+1, ok)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则通过引用参数ok返回true（否则返回false）。 点评：
（1）也可编制第二种解法的主函数：将棋盘上的n平方个点依次作为巡游起点的初始坐标位置(x1,y1)，判断从每一位置出发是否有解或无解（输出“OK!”或“NO!”，但并不输出“路线图”）。 （2）若更改程序中的n值（如改为4或6等），便可求解其他阶数的巡游“路线图”。
（3）可改用非递归方法设计并编写solve函数，那样的话，通常要增加一个记录摆放“棋子”信息的数组，可记录下是沿着什么方向到达了当前的什么位置（在那儿摆放了“棋子”）等，而且对上述数组可按照栈（stack）的方式来使用（栈总是采用FILO即所谓的先进后出使用方式），以便在“无路可走”的情况下，回退（回溯）到上一个位置，接着按照另外的方向去寻找其他的“行走”方法。
32． 编写程序对八皇后问题进行求解：在8行8列的棋盘上放置8个皇后，使任一个皇后都不能吃掉其他的7个皇后（注：皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子），并将结果以某种方式显示出来。
例如，当求出下述的一个解时，可输出如下信息来表示该解（输出了表示摆放皇后的坐标位置以及“棋盘状态”— 棋盘中有皇后的位置放一个“Q”字符，其他位置为“+”字符）。 (1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8) Q + + + + + + + + + + + + + Q + + + + + Q + + + + + + + + + + Q + Q + + + + + + + + + Q + + + + + + + + + Q + + + + Q + + + + + 提示:
（1） 通过“int LineNum[9]; bool a[9], b[15], c[15];”说明具有全局作用域的4个数组。其中的： LineNum[i]表示第i列的皇后要放的行位置（只用其中的列号1到8）； a[i]为true（i =1，2，…，8）表示第i行上尚未放皇后；
b[i]为true（i =0，1，2，…，14）表示第i条斜对角线上尚未放皇后（斜对角线指的是“/”状对角线，该对角线上各点的行列号之和i+j为一个常数）；
c[i]为true（i=0，1，2，…，14）表示第i条反斜对角线上尚未放皇后（反斜对角线指的是“\\”状对角线，该对角线上各点的行列号之差i-j为一个常数）。
从而当使用语句“if ( a[j] && b[i+j-2] && c[i-j+7] ) LineNum[i]=j;”时，可用于判断并实现：如果在第j行的第i列上放置皇后安全的话，则将一枚皇后放置到那儿。
（2）编制一个具有如下原型的递归函数solve，它负责往第i列开始的连续8-i+1列上均放上皇后，若成功则通过引用参数ok返回true（否则返回false）。 void solve(int i, bool& ok);
摆放皇后之后，若i=8即已放满时则递归出口；否则通过solve(i+1,ok);进行递归调用。 （3）编制主函数，首先初始化一个“空棋盘”，即将a、b、c数组的各元素均置为true（表示当前棋盘的8个行、15条斜对角线以及15条反斜对角线上都尚未摆放皇后）。而后执行调用语句“solve(1, ok);”，它负责往第1列开始的连续8列上均放上皇后，若成功则通过引用参数ok返回true（否则返回false）。
点评：
（1）可改用非递归方法设计并编写solve函数，那样的话，通常要设置数组来记录皇后的摆放位置信息，还要记录这些皇后所产生的“影响面”（所建立的“势力范围”）— 使得哪些行列位置不可再摆放皇后。当在新的行列位置摆放了皇后、但此时又无法进一步摆放其他的皇后时，要回退（回溯）到上一个位置接着去考虑另外的“行走”方法（若还有的话）等等。但注意，“回退”一步后，要同时“撤销”由于该步的回退而关联的那些“影响面”（释放“势力范围”）。
（2）本程序只是找到了某一种“摆放方案”而终止，还可进一步考虑寻找其他各种不同的“摆放方案”（实际上共有92种）。
（3）也可用同样的方法去处理其他“阶数”的皇后问题，如求解四皇后问题等。
第六章 指针，引用与动态内存分配
思 考 题
1． 什么是地址，什么是地址中的内容，两者的区别是什么？
2． 运算符“&”和“*”各有几种用法？各自的使用方式以及使用含义是什么？ 3． 什么是指针？地址和指针有什么样的关系？ 4． 如下3处出现的*pi的使用含义有什么不相同吗？ int i=23, *pi=&i; cout<<*pi; *pi=56;
5． 指针的值和类型是怎样规定的？指针的值与其他类型变量的值是否有区别？
6． 假设程序中有“int a[20]；int *pa=a；”的说明，要表示数组元素a[i]时（0≤i≤19），有几种方法可以使用呢？
7． 指针可以进行哪些运算？和普通数据类型的运算有什么不同？
8． 假设程序中有“int a[10]，b[10][10]；”的说明，请问数组名a以及b[i]都与地址及指针有某些关系吗（0≤i≤9）？a[i]与b[i]的使用含义相同吗？a+1与b+1的含义有什么不同？a[2]+1与b[2]+1的使用含义相同吗？
9． 下面按9种不同方式所定义的p有什么区别与联系？如何对每一种p进行使用？ int p； int *p； int **p；
int p[10]； int *p[10]； int （*p）[10]； int p（）； int *p（）； int（*p）（）；
10． 在“2．4．1 主函数”一节中，给出过带参数的main函数的如下一般使用格式： void main（int argc， char * argv[]）{…} 你能细致地描述参数argv所表达的数据结构吗?
11． 试述指针在函数的参数传递中的作用及其使用方法。指针参数与数组参数是否有某种形式的关联？
12． 怎样使用动态分配运算符new来生成无名的动态变量以及无名的动态数组？如何对这种动态变量及动态数组进行使用？如何使用delete来配合new释放上述的动态存储空间？ 13． 什么是引用？引用和指针的区别是什么？引用型参数具有哪些优点？ 14． 引用型的函数返回值与非引用型的函数返回值是否有某些不相同？
15． 如何定义结构类型？如何说明与使用结构变量及其分量？结构与数组的定义与使用有哪些异同？
16． 假设某结构的分量中含有指向本结构的指针（如下面的person结构类型），请问如何通过使用new及某些相关步骤来生成一个链表呢？ struct person {
．．．
person * next; };
17． 在上一题person结构类型的基础上，如下的程序“构架”是否可以用来实现生成一个具有n个项的链表（而总将新链表项加入到当前已有链表的末尾）？ person *head, *tail, *temp;//head指向链表首项，tail指向末项 tail = head = NULL; //使head及tail均指向“空”，表示空链表 for(i=0; i temp=new person; //生成一个person型的动态新表项 temp->next=NULL; //新表项将充当链表末项，将其next域置为NULL ．．． //如，通过cin输入（*temp）结构（变量）的其它各分量之值等 if(head==NULL) head=tail=temp; //链表为空时，新表项既为首项又为末项 else { //链表非空时 tail->next=temp; //新表项加入到原链表的末项之后 tail=temp; //新表项成为链表的新末项 } } //i循环体结束 18． 在C++语言中使用指针有哪些优点？指针在程序安全方面是否会有负面影响？ 练 习 题 1． 读程序写结果。程序中使用了与指针相关的常用运算：取内容运算*，取地址运算&，指针加减一个常数（结果仍为指针），两个指针进行比较等。 #include *(p+3)=13; *(q-5)=*(p+3)+1; for (int i=5; i<10; i++) *(p+i)=80+i; cout<<\ cout<<\ for (i=3; i<8; i++) cout<<*(a+i)<<\ \ cout<<\ cout<<\ while (q>&a[4]) cout<<*q--<<\ \ cout<<\} 2． 读程序，写出运行结果。注意其中通过指针参数实现了主调函数与被调函数间的“双向传值”。 #include void split(double x, int *iPart, double *fPart) { *iPart=int(x); *fPart=x-*iPart; } double f(double *a, int n) { int i, intPt; double fracPt, maxfracPt=0; for(i=0; i split( *(a+i), &intPt, &fracPt ); if( fracPt>maxfracPt) maxfracPt=fracPt; *(a+i)=intPt; } return maxfracPt; } void main() { int i; double maxfr, a[6]={1.1, 2.2, 3.3, 9.9, 6.6, 5.0}; maxfr=f(a, 6); cout<<\ for(i=0; i<6; i++) cout< 提示：函数split负责“分离”出x的整数部分与小数部分，分别放于*iPart与*fPart处，由于形参iPart与fPart都是指针，从而可实现“双向传值”而将这两个结果同时“带回去”。函数f负责从指针a为首地址的位置开始，对最前面的n个double型数进行处理：通过调用split改变数组各元素值（只要整数部分），并返回“分离”后之小数部分的大者。 点评：当被调函数的形参是指针，而又在该被调函数中更改此形参指针所指向的变量值的话，就意味着是更改主调函数中相应实参指针所指向的变量值，从而可实现所谓的“双向传值”。 3． 读程序写结果。注意，并非只要使用指针参数就必然能实现“双向传值”。 #include cout<<\} void f2(char* s) { cout<<\ char a[20]=\ s=a; cout<<\} void main() { int a=2, b=5; f1(&a, &b); cout<<\ char e[10]=\ cout<<\ f2(e); cout<<\} 点评：被调函数f1中，通过“p=new int;”改变了形参指针p的值，使它指向了另外的位置，从而使随后的“*p=66;”无法实现“双向传值”！而被调函数f2中通过“s=a;”改变了形参指针的值，使它指向了另外的位置，这样也不可实现“双向传值”！注意，只有在被调函数中改变形参指针所指变量的值（那时改变的将是主调函数中实参指针所指变量的值），才能真正实现“双向传值”。 4． 假设在main函数中有如下的说明（数组a中存放了n个字符串，即名字）： const int n=10; char a[n][31] = {\ \ \ \ \ \ \da\ \ \编制具有如下原型的自定义函数： int search(char (*p)[31], int n, char* name); 负责在字符串数组p的前n个字符串（名字）中，查找给定串name的出现位置（下标值）并返回，若p中不出现name的话，返回-1。 并编制主函数，输入要查找的某个名字（字符串）name，而后通过如下形式的语句对上述函数进行调用，之后输出相关结果（出现位置，即下标值）： int idx = search(a, n, name); //从a数组的第一个名字（0下标，第1行）开始查找 int idx = search(a+3, n, name); //从a数组的第四个名字（3下标，第4行）开始查找 提示：函数search的第一个参数p为指向一维数组的指针，按照“char (*p)[31]”所说明的p实际上可看作是一个二维字符数组，即是说，p[i]即*(p+i)为一个一维字符数组（字符串，至多可存放31个字符）；要查找给定串name在p中的出现位置（下标值），可使用如下形式的if语句来实现“if( strcmp(p[i], name) == 0 ) return (i);。” 点评：若将形参说明“char (*p)[31]”修改为“char p[][31]”，而且其他一切都不必修改，同样可实现本题所给出的求解任务，从而可体会到指向一维数组的指针形参p与二维形参数组p的密切关系。 若将a数组中的名字（字符串）按照“字典序”进行了升序排列的话，search函数中除可使用顺序查找方式之外，还可按照折半法（二分法）来进行查找。 5． 编制具有如下原型的函数FindPlace，该函数返回字符串str中第一次出现字符c的位置（地址值，即指向字符c的指针）。如果没有c字符则返回空指针NULL。并编制主函数对它进行调用以验证其正确性。 char * FindPlace（char *str，char c）； 注意：若返回的字符指针值为p的话，那么，通过“cout< 思考：若寻找并返回c字符在字符串str中最后一次出现的位置的话，实现方式与此类似。 6． 编制具有如下原型的函数findFirst以及 findLast，而后编制主函数，任意输入两个字符串，将它们用作实参来调用这两个函数，以验证其正确性。 char * findFirst(char * sourceStr, char * subStr); char * findLast(char * sourceStr, char * subStr); findFirst函数的功能为：返回源串sourceStr中第一次出现subStr子字符串的头字符位置（地 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库第一章 绪论(4)在线全文阅读。
相关推荐：
