вращение — вращать круговой массив на месте переполнения стека
У меня возникли проблемы при написании функции для вращения кругового массива. Мне нужно повернуть его на место (без временных массивов), и мне нужно перемещать как можно меньше элементов. Для справочной информации класс «Кряк» — это просто очередь, смешанная со стеком. Таким образом, элементы могут быть сдвинуты с обоих концов кругового массива. Вот что у меня так далеко:
void Quack::rotate(int r)
{
front = (front + capacity + r) % capacity;
back = (back + capacity + r) % capacity;
}
front и back являются целочисленными значениями, которые действуют как индексы для массива. r — это количество, которое нужно повернуть. емкость — максимальный размер массива.
Проблема в том, что если в массиве есть «мусорные» значения, я в конечном итоге поворачиваю их в массив. Например, допустим, что массив ACTUAL состоит из символов {a, b, c, d, e, f, g}, а front равен 5, а back равен 3. Если бы я напечатал круговой массив, я бы увидел {f, g, a , б, в, д}. Так как front равен 5, а back равен 3, индекс 4 является «мусорным» значением (в какой-то момент оно появилось). Так что моя функция поворота в том виде, в каком она есть, имеет проблему в том, что индекс 4 «вращается». Если я поверну массив на 2, массив ACTUAL будет по-прежнему {a, b, c, d, e, f, g}, за исключением того случая, когда я распечатываю его, так как передняя и задняя части разные, я получаю {a, b, c , д, е, е}. То, что я хочу видеть, это {a, b, c, d, f, g}. Моя функция печати просто печатает спереди назад (оборачиваясь по мере необходимости), поэтому мне нужна моя функция поворота, чтобы каким-то образом устранить значение мусора.
Я думаю, что мне нужно переместить элементы назад, чтобы у меня были последовательные значения без мусора в середине. Но я не уверен, как это сделать.
Решение
С циклическим итератором и std :: rotate:
#include <algorithm>
#include <iterator>
template <typename Iterator>
class cyclic_range
{
public:
typedef Iterator iterator;
cyclic_range(iterator first, iterator middle, iterator last)
: m_first(first), m_middle(middle), m_last(last)
{
if(m_middle == m_last) m_middle = m_first;
}
iterator first() const { return m_first; }
iterator middle() const { return m_middle; }
iterator last() const { return m_last; }
private:
iterator m_first;
iterator m_middle;
iterator m_last;
};
template <typename Iterator>
inline cyclic_range<Iterator>
make_cyclic_range(Iterator first, Iterator middle, Iterator last) {
return cyclic_range<Iterator>(first, middle, last);
}/// A cyclic random access iterator operating on a iterator range [first, last).
/// If an iterator reaches the last (or is at last) position of the range the iterator
/// becomes equal to the first position of the range.
template <
typename RandomAccessIterator,
typename CyclicRange = cyclic_range<RandomAccessIterator> >
class cyclic_iterator
{
public:
typedef RandomAccessIterator inner_iterator;
typedef std::iterator_traits<inner_iterator> inner_iterator_traits;
typedef typename std::random_access_iterator_tag iterator_category;
typedef typename inner_iterator_traits::value_type value_type;
typedef typename inner_iterator_traits::difference_type difference_type;
typedef typename inner_iterator_traits::reference reference;
typedef typename inner_iterator_traits::pointer pointer;
typedef CyclicRange range_type;
public:
cyclic_iterator(inner_iterator pos, range_type range, bool at_end = false)
: m_pos(pos), m_range(range), m_at_end(at_end)
{
if(m_pos == range.last()) {
m_pos = range.first();
}
if(m_range.first() == m_range.last()) m_at_end = true;
}
const range_type& range() const { return m_range; }
/// True if the incremented or decremented iterator is at the middle of
/// the circular range.
bool at_end() const { return m_at_end; }
reference operator * () const noexcept {
return *m_pos;
}
pointer operator -> () const noexcept { return &*m_pos; }
cyclic_iterator& operator ++ () noexcept {
if(++m_pos == m_range.last()) m_pos = m_range.first();
m_at_end = (m_pos == m_range.middle());
return *this;
}
cyclic_iterator operator ++ (int) noexcept {
return ++cyclic_iterator(*this);
}
cyclic_iterator& operator += (difference_type n) noexcept {
if(n) {
if(n < 0) *this -= -n;
else {
n %= (m_range.last() - m_range.first());
difference_type avail = m_range.last() - m_pos;
if(n < avail) m_pos += n;
else {
m_pos = m_range.first();
n -= avail;
m_pos += n;
}
m_at_end = (m_pos == m_range.middle());
}
}
return *this;
}
cyclic_iterator operator + (difference_type n) const noexcept {
return cyclic_iterator(*this) += n;
}
cyclic_iterator& operator -- () noexcept {
if(m_pos == m_range.first()) m_pos = m_range.last();
--m_pos;
m_at_end = (m_pos == m_range.middle());
return *this;
}
cyclic_iterator operator -- (int) noexcept {
return --cyclic_iterator(*this);
}
cyclic_iterator& operator -= (difference_type n) noexcept {
if(n) {
if(n < 0) *this += -n;
else {
n %= (m_range.last() - m_range.first());
difference_type avail = m_pos - m_range.first();
if(avail < n) {
m_pos = m_range.last();
n -= avail;
}
m_pos -= n;
m_at_end = (m_pos == m_range.middle());
}
}
return *this;
}
cyclic_iterator operator - (difference_type n) const noexcept {
return cyclic_iterator(*this) -= n;
}
difference_type operator - (const cyclic_iterator& other) const noexcept {
return index() - other.index();
}
bool operator == (const cyclic_iterator& other) noexcept {
return (index() == other.index());
}
bool operator != (const cyclic_iterator& other) noexcept {
return ! (*this == other);
}
bool operator < (const cyclic_iterator& other) noexcept {
return index < other.index();
}
bool operator <= (const cyclic_iterator& other) noexcept {
return ! (other < this);
}
bool operator > (const cyclic_iterator& other) noexcept {
return (other < this);
}
bool operator >= (const cyclic_iterator& other) noexcept {
return ! (this < other);
}
private:
/// The index of the iterator position.
typedef std::size_t size_type;
size_type index() const noexcept {
size_type n = m_range.last() - m_range.first();
if( ! m_at_end) {
if(m_range.middle() <= m_pos) {
n = m_pos - m_range.middle();
}
else {
n = (m_pos - m_range.first()) + (m_range.last() - m_range.middle());
}
}
return n;
}
private:
inner_iterator m_pos;
range_type m_range;
bool m_at_end;
};
template <typename Iterator>
cyclic_iterator<Iterator> begin(const cyclic_range<Iterator>& range) {
return cyclic_iterator<Iterator>(range.middle(), range);
}
template <typename Iterator>
cyclic_iterator<Iterator> end(const cyclic_range<Iterator>& range) {
return cyclic_iterator<Iterator>(range.middle(), range, true);
}
// Test
// ====
#include <iostream>
#include <vector>
template <typename Iterator>
void print_cyclic_range(Iterator first, Iterator last) {
std::cout << "Cyclic Range: ";
for( ; first != last; ++first) {
std::cout << *first << ' ';
}
std::cout << '\n';
}
template <typename Iterator>
void print_range(Iterator first, Iterator last) {
std::cout << " Range: ";
for( ; first != last; ++first) {
std::cout << *first << ' ';
}
std::cout << '\n';
}
int main()
{
typedef cyclic_iterator<char*> cyclic_iterator;
char v[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g'};
print_range(v, v + sizeof(v));
// The cyclic range from 'f' to (including) 'e'
cyclic_iterator::range_type range(v, v + 5, v + sizeof(v));
// The cyclic iterator pointing to 'f'
cyclic_iterator first = begin(range);
// The cyclic iterator pointing to 'e'
cyclic_iterator last = end(range) - 1;
print_cyclic_range(first, last);
// Rotate the cyclic range from 'f' to (including) 'd', excluding 'e'
std::rotate(first, first + 2, last);
print_range(v, v + sizeof(v));
print_cyclic_range(first, last);
return 0;
}
Предоставление:
Range: a b c d e f g
Cyclic Range: f g a b c d
Range: c d f g e a b
Cyclic Range: a b c d f g
Другие решения
Так что, если массив не заполнен, вам нужно переместить несколько символов вокруг. Сначала вы проверяете, положительный или отрицательный r. Если оно отрицательное, вам нужно отодвинуть заднюю часть, чтобы она находилась на одном уровне с передней частью для числа r или наоборот. пример:
распечатать: c, b, a, z, f, g повернуть 2
a z f g — c b
0 1 2 3 4 5 6
c (items [5]) находится спереди, а g (items [3]) сзади. Если мы просто добавим r к обоим, это выведет мусор для пустого пространства. Если r равно 2, мы хотим скопировать c в items [4] и b в items [5]. Тогда элементы [0] должны быть спереди, а теперь элементы [5] должны быть спереди.
void Quack::rotate(int r)
{
if (nItems < capacity) { //if it's not full
if (r < 0) { // if r is negative
int r2 = r*(-1); //find absolute value
for (int i = 0; i < r2; i++) {
items[(back + 1 - i) % (capacity)] = items[(back - i < 0) ? capacity + back - i : back - i]; //push back the back chars up to the front r times
}
}
else {
for (int i = 0; i < r; i++){
items[(back + 1 + i)% capacity] = items[(front + i) % capacity];
}
}
}
front = ((front + r > 0) ? (front + r)%capacity : front + r + capacity); //if front + r is negative add capacity to it
back = (back + r) % capacity;
}
detector