Список FIFO (движущиеся элементы) [C ++]

Добрый вечер, люди!

Я пытаюсь решить довольно простую проблему, но ... кажется, я не могу. :)

Идея состоит в том, что у меня есть список FIFO (очередь FIFO) с n элементами, и ему дано значение k (k <n). Моя маленькая программа должна переместить элементы влево с помощью k элементов. (например, для n = 4, k = 3, a [] = (1, 2, 3, 4), результат равен 4 1 2 3).

Но хорошо, я не дохожу до этого.

Это то, что я написал до сих пор:

#include <iostream>
using namespace std;

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=0; i<=n-1; i++) t[i]=a[i];
        for (i=0; i<=k-1; i++) a[i]=a[i+k-1];
        for (i=k; i<=n-1; i++) a[i]=t[i+1];
}

int main () {
        int a[100];
        unsigned k, n, i;
        cout<<"n; k= "; cin>>n>>k;
        for (i=0; i<=n-1; i++) cin>>a[i];
        move (a, n, k);
        for (i=0; i<=n-1; i++) cout<<a[i]<<" ";
}

Любая помощь будет принята с благодарностью. Заранее спасибо.

4 голоса | спросил flowerpowerduck 3 FebruaryEurope/MoscowbWed, 03 Feb 2010 20:50:19 +0300000000pmWed, 03 Feb 2010 20:50:19 +030010 2010, 20:50:19

5 ответов


0

Я не уверен, что полностью понял ваш вопрос. Но похоже, что вы действительно хотите повернуть содержимое массива.

Чтобы повернуть содержимое массива влево k раз. Вы можете сделать следующее:

  • Поменять местами первые K элементов.
  • Инвертируйте оставшиеся элементы N-K.
  • Перевернуть весь массив.

Пример:

  

N = 5, K = 3 и массив = [1 2 3 4 5]

  • шаг 1: поменяйте местами первые 3 элемента: [3 2 1 4 5]
  • шаг 2: отменить оставшиеся 2 элементы: [3 2 1 5 4]
  • шаг 3: перевернуть весь массив: [4 5 1 2 3]

C ++ функция для того же:

void move (int a[100], int n, int k) {
        int t[100];
        int i,j;
        for (i=k-1,j=0; i>=0; i--,j++) t[j]=a[i];
        for (i=n-1; i>=k; i--,j++) t[j]=a[i];
        for (i=n-1,j=0; i>=0; i--,j++) a[j]=t[i];
}

Лучший способ сделать это в постоянном пространстве - сделать реверсирование на месте:

void arr_rev(int a[100], int start, int end) {
        int temp;

        for(;start<end;start++,end--) {
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
        }
}

void move2 (int a[100], int n, int k) {
        arr_rev(a,0,k-1);
        arr_rev(a,k,n-1);
        arr_rev(a,0,n-1);
}
ответил codaddict 3 FebruaryEurope/MoscowbWed, 03 Feb 2010 21:23:15 +0300000000pmWed, 03 Feb 2010 21:23:15 +030010 2010, 21:23:15
0

Поскольку вы отметили это как C ++, я предполагаю, что это то, что вы используете. В этом случае вы почти наверняка должны использовать std::deque вместо массива для хранения данных. Кроме того, очередь обычно имеет «передний» и «задний», поэтому «оставленный» на самом деле ничего не значит.

Предполагая (просто для аргумента), что вам нужно взять k элементов из задней части очереди и переместить их вперед, вы можете сделать что-то вроде:

typedef std::deque<your_type> data;

void push_to_front(data &d, int k) { 
    if (k > d.size())
        return;
    for (int i=0; i<k; i++) {
        data::value_type v = d.pop_back();
        d.erase(d.back());
        d.push_front(v);
    }
}      

Если вы хотите повернуть в другом направлении, это в значительной степени вопрос обмена ролями спереди и сзади.

ответил Jerry Coffin 3 FebruaryEurope/MoscowbWed, 03 Feb 2010 21:03:19 +0300000000pmWed, 03 Feb 2010 21:03:19 +030010 2010, 21:03:19
0

Похоже, вы хотите повернуть налево? Это не должно быть очень сложно. Просто удалите из очереди первые элементы k, сдвиньте оставшиеся n-k

Чтобы изменить код таким образом, он может выглядеть следующим образом:

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=k; i<=n-1; i++) t[i-k]=a[i];
        for (int x=0; x<=k-1; x++) t[i++-k]=a[x];
}

И поскольку это все еще ужасно, вы можете переписать его, чтобы сделать логику более ясной, но я оставлю это в качестве упражнения.

Это также предполагает, что вам не разрешено использовать структуры данных STL; если это не так, см. ответ Джерри Коффина.

ответил danben 3 FebruaryEurope/MoscowbWed, 03 Feb 2010 21:02:59 +0300000000pmWed, 03 Feb 2010 21:02:59 +030010 2010, 21:02:59
0

Если вы имеете в виду «переместить k-й элемент в начало очереди», то это один из способов сделать это:

void move( int *a, unsigned n, unsigned k )
{ 
    int t; // To store the temporary for the k'th element 

    t = a[ k ];

    // Shift all the elements to the right by one.
    for( unsigned i = k; i > 0; --i )
        a[ i ] = a[ i - 1 ];

    // Put the k'th element at the left of the queue.
    a[ 0 ] = t;
}
ответил Jon Benedicto 3 FebruaryEurope/MoscowbWed, 03 Feb 2010 21:08:06 +0300000000pmWed, 03 Feb 2010 21:08:06 +030010 2010, 21:08:06
0
#include <iostream>
#include <list>
template <typename T>
void Rotate(std::list<T>& list, int k){
    for(int i=0; i<k; ++i){
        T tmp(list.back());
        list.pop_back();
        list.push_front(tmp);
    }
}
int main(){
    std::list<int> ints;
    ints.push_back(1); ints.push_back(2);
    ints.push_back(3); ints.push_back(4);
    Rotate(ints,2);
    for(std::list<int>::const_iterator i = ints.begin(); i!=ints.end(); ++i)
        std::cout << *i << std::endl;
    return 0;
}

Будет выводить:

3
4
1
2
ответил Notinlist 3 FebruaryEurope/MoscowbWed, 03 Feb 2010 21:19:37 +0300000000pmWed, 03 Feb 2010 21:19:37 +030010 2010, 21:19:37

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132