//出现错务的代码已标记
#pragma once
#include<iostream>
using namespace std;
using Rank = int;
#define DEFAULT_CAPACITY 3
template <typename T> class Vector {
public:
Rank _size; int _capacity; T* _elem; int num;
public:
void copyFrom(T const* A, Rank lo, Rank hi);
void expand();
void shrink();
void merge(Rank lo, Rank mi, Rank hi);
void mergeSort(Rank lo, Rank hi);
public:
Vector() {}
Vector(int c, int s, T v)
{
_elem = new T[_capacity = c]; for (_size = 0; _size < s; _elem[_size++] = v);
} //s<=c
Vector(T const* A, Rank n) { copyFrom(A, 0, n); }
Vector(T const* A, Rank lo, Rank hi) { copyFrom(A, lo, hi); }
Vector(Vector<T> const& V) { copyFrom(V._elem, 0, V._size); }
Vector(Vector<T> const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); }
// 析构函数
~Vector() {}
Rank size(); //规模
bool empty() const { return !_size; } //判空
Rank find(T const& e) const { return find(e, 0, _size); } //无序向量整体查找
Rank find(T const& e, Rank lo, Rank hi) const; //无序向量区间查找
Rank search(T const& e) const //有序向量整体查找
{
return (0 >= _size) ? -1 : search(e, 0, _size);
}
// 可写访问接口
T& operator[] (Rank r); //重载下标操作符，可以类似于数组形式引用各元素
Vector<T>& operator= (Vector<T> const&); //重载赋值操作符，以便直接克隆向量
T remove(Rank r); //删除秩为r的元素
int remove(Rank lo, Rank hi); //删除秩在区间[lo, hi)之内的元素
Rank insert(Rank r, T const& e); //插入元素
Rank insert(T const& e) { return insert(_size, e); } //默认作为末元素插入
// 遍历
void traverse(void (*) (T&)); //遍历（使用函数指针，只读或局部性修改）
public:
void push(T const& e) { insert(_size, e); }
T pop() { return remove(_size - 1); }
T& top() { return (*this)[_size - 1]; }
};
//——————————————————————————————————
#include "Vector.h"
template <typename T> void Vector<T>::shrink() {
if (_capacity < DEFAULT_CAPACITY << 1) return;
if (_size << 2 > _capacity) return;
T* oldElem = _elem; _elem = new T[_capacity >>= 1];
for (int i = 0; i < _size; i++) _elem[i] = oldElem[i];
delete[] oldElem;
}
template <typename T> void Vector<T>::expand() {
if (_size < _capacity) return;
if (_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY;
T* oldElem = _elem; _elem = new T[_capacity <<= 1];
for (int i = 0; i < _size; i++) _elem[i] = oldElem[i];
delete[] oldElem;
}
template<typename T>
void Vector<T>::merge(Rank lo, Rank mi, Rank hi)
{
Rank i = 0, j = 0, k = 0;
Rank* A = _elem + lo;
Rank lb = mi - lo; Rank* B = new Rank[lb];
for (Rank i = 0; i < lb; B[i] = A[i++]);
int lc = hi - mi; Rank* C = _elem + mi;
for (i, j, k; (j < lb) || (k < lc);)
{
if ((j < lb) && (!(k < lc) || (B[j] <= C[k])))A[i++] = B[j++];
if ((k < lc) && (!(j < lb) || (C[k] < B[j])))A[i++] = C[k++];
}
}
template<typename T>
void Vector<T>::mergeSort(Rank lo, Rank hi)
{
if (hi - lo < 2)return;
Rank mi = (hi + lo) / 2;
mergeSort(lo, mi); mergeSort(mi, hi);
merge(lo, mi, hi);
}
template<typename T>
void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi)
{
num = hi;
_elem = new T[_capacity = 2 * (hi - lo)]; _size = 0;
while (lo < hi)
_elem[_size++] = A[lo++];
}
template<typename T>Vector<T>& Vector<T>::operator=(Vector<T>const& V)
{
if (_elem)delete[]_elem;
copyFrom(V._elem, 0, V.size());
return*this;
}
template<typename T>
T& Vector<T>::operator[](Rank r)
{
return _elem[r];
}
template<typename T>
Rank Vector<T>::insert(Rank r, T const& e) {
expand();
for (int i = _size; i > r; i--)
{
_elem[i] = _elem[i - 1];
_elem[r] = e; _size++;
return r;
}
}
template<typename T>
int Vector<T>::remove(Rank lo, Rank hi)
{
if (lo == hi)return 0;
while (hi < _size)_elem[lo++] = _elem[hi++];
_size = lo;
shrink();
return hi - lo;
}
template<typename T>T Vector<T>::remove(Rank r) {
T e = _elem[r];
remove(r, r + 1);
return e;
}
template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi)const {
while ((lo < hi--) && (e != _elem[hi]));
return hi;
}
template<typename T>
Rank Vector<T>::size()
{
return _size;
}
//——————————————————————————————————
#pragma once
#include"Vector.h"
template<typename T>class Stack :public Vector<T>
{
Vector<int> V;
public:
**void push(T const& e) { V.insert(V.size(), e); }_**
T pop() { return V.remove(V.size() - 1); }
T& top() { return (*this)[V.size() - 1]; }
};
//——————————————————————————————————
#pragma once
#include"Stack.h"
class Queen
{
public:
int _x;
int _y;
public:
Queen(int x = 0, int y = 0) :_x(x), _y(y) {};
bool operator==(Queen const& q)const
{
return(_x == q._x) || (_y == q._y) || (_x - q._y == _y - q._y) || (_x - q._y == q._y - _y);
}
bool operator!=(Queen const& q)const {
return !(*this == q);
}
};
class NQueenSolution {
public:
int nSolu;
int nCheck;
int N;
Vector<Stack<Queen>> solutions;
public:
NQueenSolution(int s) { nSolu = 0, nCheck = 0; N = s; }
void placeQueens();
void showQueensPos();
};
//——————————————————————————————————
#include "Queen.h"
void NQueenSolution::placeQueens()
{
Stack<Queen>solu;
Queen q(0, 0);
do {
if (N <= solu.size() || N <= q._y)
{
q = solu.pop();
q._y++;
}
else {
while ((q._y < N) && (0 <= solu.find(q)))
{
q._y++;
nCheck++;
}
if (N > q._y) {
solu.push(q);
if (N <= solu.size()) {
nSolu++; solutions.insert(solu);
}
q._x++;
q._y = 0;
}
}
} while ((0 < q._x) || (q._y < N));
}
void NQueenSolution::showQueensPos()
{
if (nSolu > 0)
{
int N = solutions[0].size();
for (size_t i = 0; i < nSolu; i++)
{
std::cout << "Soluion No." << i + 1 << std::endl;
for (size_t j = 0; j < N; j++)
{
std::cout << "Queen No." << j << ":(" << solutions[i][j]._x << "," << solutions[i][j]._y << ")" << std::endl;
}
}
}
}
//——————————————————————————————————
#include<iostream>
#include "Queen.h"
using namespace std;
int main()
{
NQueenSolution mySolution(8);
mySolution.placeQueens();
cout << "nSolu=" << mySolution.nSolu << "," << "nCheck=" << mySolution.nCheck << endl;
mySolution.showQueensPos();
}
你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答
本次提问扣除的有问必答次数，已经为您补发到账户，我们后续会持续优化，扩大我们的服务范围，为您带来更好地服务。