第四章算法与数据结构(C 版)[漆涛][电子教案]

15
bool eight_queen2() { fill_n(column_free, num_queens, true); fill_n(diag_free, fifteen; true); fill_n(inv_diag_free, fifteen, true); Gstack<int> board(num_queens); while(board.size() < num_queens) { for(int j = zero; !check(board.size(), j); ++j){ while(j >= seven) { if(board.empty()) return false; // j = board.top(); board.pop(); remove_queen(board.size(), j); } } set_queen(board.size(), j); board.push(j); } write_board(board); // return true; // }
{0, 1a, 1b, 3a, 3b, 9a, 9b}
21
: {29, 31, 93, 10, 23, 21, 29}
10 0 :
31, 21 1 2
93, 23 3
···
29, 29 9
{10, 31, 21, 93, 23, 29, 29} : 21, 23, 29, 29 2 3 ··· 9
bool check(Gstack<int> const& board) { // , int row = boarቤተ መጻሕፍቲ ባይዱ.size() - 1; for(int k = 1; --row >= 0; ++k) if( (board[row] == board.top() ) || (board[row] == board.top() + k) || (board[row] == board.top() - k) ) return false; return true; }
10 0 : 1
31
93
10, 21, 23, 29, 29, 31, 93
22
#include "Queue.h" enum{ radix = 10 }; typedef unsigned int T; typedef Queue<T> QT; void distribute(QT queues[], T const* first, T const* last, int power) { for(; first != last; ++first) queues[(*first/power)%radix].push(*first); } void collect(T* first, QT queues[]) { for(int digit = 0; digit < radix; ++digit) while(!queues[digit].empty()) { *first++ = queues[digit].front(); queues[digit].pop(); } } void radix_sort_10(T* first, T* last, int d = 10) { QT queues[radix]; for(int pow = 1; --d >= 0; pow *= radix) { distribute(queues, first, last, pow); collect(first, queues); } }
2
c
c E
first Ea n−1
an−2
E
···
E
a0 0
template <typename T> struct Lstack : private Slist<T> { typedef Slist<T> Base; Lstack(void) : Base(void){ } bool empty(void)const{ return Base::empty(); } int size(void)const{ return Base::size(); } T& top(void){ return Base::front(); } void pop(void){ Base::pop_front(); } void push(T const& v){ Base::push_front(v); } void clear(void){ Base::clear(); } };
20
: {9a, 1a, 3a, 0, 3b, 1b, 9b} :
h h h h h
0
¤ ¤
¤ h ¤ h ¤ h h h
1a 1b
¤ h ¤ h ¤ ¤ ¤ h h h ¤ ¤
¤ h ¤ h ¤ h h h
3a 3b
¤ ¤ ¤ ¤ ¤
···
h h h h h
9a 9b
¤ ¤ ¤ ¤ ¤
0
1
2
3
9
void set_queen(int i, int j) { // (i,j) column_free[j] = inv_diag_free[seven + i - j] = diag_free[i + j] = false; } void remove_queen(int i, int j) { // (i,j) column_free[j] = inv_diag_free[seven + i - j] = diag_free[i + j] = true; }
12
int const num_queens = 8; int const zero = 0; int const seven = num_queens - 1; bool eight_queen() { Gstack<int> board(num_queens); while(board.size() < num_queens) { board.push(zero); for(; !check(board); ++board.top()) { while(board.top() >= seven){ //top board.pop(); if(board.empty()) return false; // } } } write_board(board); // return true; }
10
while( { // while( { while( {
)
) ) //
if( ) return } ; } } return
11
,
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Q 7 Q 6 Q 5 Q Q 4 d Q 3 d d d Q 2 d d d Q 1 d d d Q 0 d check
(C++
)
:
2009
:
•
•
•
•
•
•
•
1
: a0
a0 a1 ···
; an−1 an−1
'
. pop
E
push
template <typename T> struct Stack : private std::vector<T> { typedef std::vector<T> Base; Stack(void) : Base(void) { } // bool empty(void)const{ return Base::empty();} int size(void)const{ return Base::size(); } T& top(void){ return Base::back(); } void pop(void){ Base::pop_back(); } void push(T const& v){ Base::push_back(v); } void clear(void){ Base::clear(); } };
13
while( ) { // x = while(x ) { while( x { if( ) return ; x = ; ; // } x = x ; } x } return ;
)
14
check
int const num_queens = 8; int const zero = 0; int const seven = num_queens - 1; // int const fifteen = 2*num_queens - 1; bool column_free[num_queens]; bool diag_free[fifteen]; bool inv_diag_free[fifteen]; // (i,j) bool check(int i, int j) { return column_free[j] && diag_free[i + j] && inv_diag_free[seven + i - j]; }
8
main
.
h3 1 h3 2 m1 3
a a a
b c b
c b c a
,
h1
b ,
c h3
h3 2 m1 3
a a
c b
b c a , b c h1
h5 1 h3 2 m1 3
c a a
a c b
b b c , h3 b
9
a
b
c
m1 3
a
b