数据结构习题解析第5章

{ w = st.GetTop(); st.Pop( ); w.vm--; w.vn = v; st.Push( w ); }

} while ( st.IsEmpty( ) == 0 ); return v; }

5-3 【背包问题】设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1], w[2], …, w[n]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：）

Trues?0 此时背包问题 ??Falses?0 总重量不能为 ??KNAP(s,n)?Falses?0且n?1物品件数不能 ?

?KNAP(s,n?1)或 s?0且n?1所选物品中不w[n]时??KNAP(s?w[n],n?1)所选物品中包w[n]时 ?【解答】

根据递归定义，可以写出递归的算法。

enum boolean { False, True } boolean Knap( int s, int n ) { if ( s == 0 ) return True;

if ( s < 0 || s > 0 && n < 1 ) return False;

if ( Knap ( s – W[n], n-1 ) == True ) { cout << W[n] << ? , ?; return True; } return Knap( s, n-1 ); }

若设w = { 0, 1, 2, 4, 8, 16, 32 }，s = 51, n = 6。则递归执行过程如下

Knap(51, 6) return False Knap(3, 2) Knap(3-2, 1) Knap(1-1, 0) s = 0 return True, 完成 return True, 打印32 return True, 打印16 return True, 无动作 return True, 无动作 return True, 打印2 return True, 打印1 return True Knap(51-32, 5) Knap(19-16, 4) Knap(3-8, 3) return False Knap(3, 3) s = -1 < 0 递s = -5 < 0 归 return False Knap(3-4, 4) return False

5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行，…。第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提示：用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列。) 【解答】

此为典型的回溯法问题。

96

1# 次对角线

0 1 2 3 0 1 2 3

3# 次对角线 5# 次对角线

0# 次对角线 2# 次对角线 4# 次对角线

??????6# 次对角线

0# 主对角线

1# 主对角线

2# 主对角线 4# 主对角线 6# 主对角线 3# 主对角线 5# 主对角线

??

在解决8皇后时，采用回溯法。在安放第 i 行皇后时，需要在列的方向从 1 到 n 试探( j = 1, …, n )：首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。 解题时设置 4 个数组：

col [n] ：col[i] 标识第 i 列是否安放了皇后

md[2n-1] ：md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] ：sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] ：q[i] 记录第 i 行皇后在第几列 利用行号i和列号j计算主对角线编号k的方法是k = n+i-j-1；计算次对角线编号k的方法是k = i+j。n皇后问题解法如下：

void Queen( int i ) { 击

col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j;

for ( j = 0; j < n; j++ ) cout << q[j] << ‘,’; cout << endl; }

else { Queen ( i+1 );

} }

}

//在第i+1行安放皇后 //撤消第 i 行第 j 列的皇后

col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0;

//在第 i 行第 j 列安放皇后

if ( i == n ) {

//输出一个布局

for ( int j = 0; j < n; j++ ) {

if ( col[j] == 0 && md[n+i-j-1] == 0 && sd[i+j] == 0 ) {

//第 i 行第 j 列没有攻

5-5 已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：

(1) 求链表中的最大整数。 (2) 求链表的结点个数。 (3) 求所有整数的平均值。 【解答】

#include class List;

97

//定义在头文件\中

class ListNode { friend class List; private:

int data;

//链表结点类

//结点数据 //结点指针

ListNode *link;

public:

ListNode ( const int item ) : data(item), link(NULL) { } //构造函数

}; class List {

private: ListNode *first, current; int Max ( ListNode *f ); int Num ( ListNode *f );

float Avg ( ListNode *f, int& n ); public:

List ( ) : first(NULL), current (NULL) { } ~List ( ){ }

ListNode* NewNode ( const int item ); void NewList ( const int retvalue ); void PrintList ( );

int GetMax ( ) { return Max ( first ); } int GetNum ( ) { return Num ( first ); } float GetAvg ( ) { return Avg ( first ); }

};

ListNode* List :: NewNode ( const int item ) { ListNode *newnode = new ListNode (item); return newnode;

} void List :: NewList ( const int retvalue ) { first = NULL; int value; ListNode *q;

cout << \; cin >> value;

while ( value != retvalue ) {

q = NewNode ( value );

if ( first == NULL ) first = current = q; else { current->link = q; current = q; } cin >> value;

}

current->link = NULL;

}

void List :: PrintList ( ) {

cout << \;

ListNode *p = first;

98

//链表类

//构造函数 //析构函数

//创建链表结点, 其值为item //建立链表, 以输入retvalue结束 //输出链表所有结点数据 //求链表所有数据的最大值 //求链表中数据个数 //求链表所有数据的平均值

//创建新链表结点

//建立链表, 以输入retvalue结束 //提示 //输入 //输入有效

//建立包含value的新结点

//空表时, 新结点成为链表第一个结点//非空表时, 新结点链入链尾 //再输入 //链尾封闭

//输出链表

}

while ( p != NULL ) { cout << p->data << ' '; p = p->link; } cout << ‘\\n’;

(1) 求链表中的最大整数

int List :: Max ( ListNode *f ) {

}

//递归算法 : 求链表中的最大值 //递归结束条件

//在当前结点的后继链表中求最大值 //如果当前结点的值还要大, 返回当前检点值 //否则返回后继链表中的最大值

if ( f ->link == NULL ) return f ->data; int temp = Max ( f ->link ); else return temp;

if ( f ->data > temp ) return f ->data;

(2) 求链表的结点个数

int List :: Num ( ListNode *f ) {

}

if ( f == NULL ) return 0; return 1+ Num ( f ->link );

//递归算法 : 求链表中结点个数 //空表, 返回0

//否则, 返回后继链表结点个数加1

(3) 求所有整数的平均值

float List :: Avg ( ListNode *f , int& n ) {

}

if ( f ->link == NULL )

//递归算法 : 求链表中所有元素的平均值 //链表中只有一个结点, 递归结束条件

{ n = 1; return ( float ) (f ->data ); }

else { float Sum = Avg ( f ->link, n ) * n; n++; return ( f ->data + Sum ) / n; }

#include \

//定义在主文件中

int main ( int argc, char* argv[ ] ) {

List test; int finished;

cout << “输入建表结束标志数据 ：”; cin >> finished;

}

test.PrintList ( );

//输入建表结束标志数据 //建立链表 //打印链表

test.NewList ( finished );

cout << \; cout << \; cout << \; printf ( \return 0;

5-6 画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 【解答】

(1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1))

99