Циклический сдвиг массива влево с помощью указателей

Опубликовано 28.06.2012 | Автор: admin

Интересной и полезной может быть задача на арифметику указателей: циклический сдвиг одномерного массива влево.

Показываемое решение взято из алгоритма стандартной библиотеки. Ради любителей самостоятельно пытать свои умы, это решение спрятано вовнутрь спойлера. Немного модифицировано, но суть — что используется алгоритм, применяемый в std::rotate.

показать решение

//clang     Сдвиг массива влево на k позиций указателями      Листинг #1
#include <iostream>

using namespace std;

int main(){
    const int N = 10;
    int arr[N];

       for (int i=0; i<N; i++) arr[i] =i +1;
       for (int i=0; i<N; i++) cout << arr[i] << '\t';


    int k = 0;
    cin >> k;

    k = k % N;      //Это если введено очень большое число

    /*АЛГОРИТМ СДВИГА ВЛЕВО*/
    int *first = arr;
    int *middle = arr+k;
    int *last = arr+N-1;

  int*  next = middle;
  while (first!=next)
  {
    swap (*first++,*next++);
    if (next==last+1) next=middle;
    else if (first==middle) middle=next;
  }
  /*КОНЕЦ АЛГОРИТМА СДВИГА ВЛЕВО*/

    cout << '\n';
    for (int i=0; i<N; i++) cout << arr[i] << '\t';
}

//clang Сдвиг массива влево на k позиций указателями Листинг #1

#include <iostream>

using namespace std;

int main(){

const int N = 10;

int arr[N];

for (int i=0; i<N; i++) arr[i] =i +1;

for (int i=0; i<N; i++) cout << arr[i] << '\t';

int k = 0;

cin >> k;

k = k % N; //Это если введено очень большое число

/*АЛГОРИТМ СДВИГА ВЛЕВО*/

int *first = arr;

int *middle = arr+k;

int *last = arr+N-1;

int* next = middle;

while (first!=next)

{

swap (*first++,*next++);

if (next==last+1) next=middle;

else if (first==middle) middle=next;

}

/*КОНЕЦ АЛГОРИТМА СДВИГА ВЛЕВО*/

cout << '\n';

for (int i=0; i<N; i++) cout << arr[i] << '\t';

}

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

Например, у меня в коде задан массив в 10 ячеек. Задан сдвиг в 3 элемента. Разбиваем мой массив на массивы, где максимальное число ячеек равно количеству сдвигов, получаем 4 массива: М1[3 ячейки] + М2[3 ячейки] + М3[3ячейки] + М4[1 ячейка] = 10 ячеек. Буква М — это обозначение массива. В коде происходит следующее М1 обменивается значениями с М2, М2 с М3, М3 обменивается одним значением с М4. В результате таких манипуляций в конечном итоге получается сдвинутый массив.

Наиболее простой алгоритм сдвига — это использование функции копирования блоков памяти. Этот способ можно не считать за решение поставленной задачи по сдвигу, потому что прямой работы программиста с указателями нет и весь кайф от задачи с таким решением не поймаешь. Но поскольку имя массива С++ умеет приводить к указателю на свой первый элемент, а функция, копирующая блоки памяти, работает с указательной переменной, то можно с натяжкой считать, что то, что будет показано ниже, всё-таки тоже решение.

  //clang       Использование функции копирования блоков памяти для сдвига массивов     Листинг #2
  #include <iostream>
#include <cstring>      //memmove

using namespace std;

int main(){
    const int N = 10;
    int arr[N];

    for (int i=0; i<N; i++)   arr[i] = i+1;
    for (int i=0; i<N; i++)    cout << arr[i] << '\t';

    int k;                      //число сдвигов
    cout <<"\n\n input k: ";      //Диалог: введите насколько сдвигать влево
    cin >> k;
    k = k % N;                  //Для того, чтобы можно было давать например 100 сдвигов

    /*НАЧАЛО СДВИГА ВЛЕВО*/
    int temp[N];
        memmove(temp,arr+k,(N-k)*sizeof(int));      //копируем левую часть
        memmove(temp+N-k,arr,k*sizeof(int));        //копируем правую часть
        memmove(arr,temp,N * sizeof(int));           //переписываем основной массив

        cout << '\n';
        for (int i=0; i<N; i++)    cout << arr[i] << '\t';
}

//clang Использование функции копирования блоков памяти для сдвига массивов Листинг #2

#include <iostream>

#include <cstring> //memmove

using namespace std;

int main(){

const int N = 10;

int arr[N];

for (int i=0; i<N; i++) arr[i] = i+1;

for (int i=0; i<N; i++) cout << arr[i] << '\t';

int k; //число сдвигов

cout <<"\n\n input k: "; //Диалог: введите насколько сдвигать влево

cin >> k;

k = k % N; //Для того, чтобы можно было давать например 100 сдвигов

/*НАЧАЛО СДВИГА ВЛЕВО*/

int temp[N];

memmove(temp,arr+k,(N-k)*sizeof(int)); //копируем левую часть

memmove(temp+N-k,arr,k*sizeof(int)); //копируем правую часть

memmove(arr,temp,N * sizeof(int)); //переписываем основной массив

cout << '\n';

for (int i=0; i<N; i++) cout << arr[i] << '\t';

}

Конечно чисто на указателях, как показано в первом листинге, выполнять круче и правильнее с точки зрения поставленной задачи. Но и с копированием областей памяти кому-то может быть окажется пример полезным. При копировании областей память вовнутрь круглых скобок по очереди отдавались: массив, в который копируем, массив, из которого копируем, и количество копируемых байт.

Чтобы копировались все значения ячеек массива, нужно домножить количество ячеек на размер типа массива. Т. е. если у массива был бы тип double и он состоял из N ячеек, то нужно бы было в количестве байтов использовать умножение: N*sizeof(double).

Рубрика: Массивы, Решения задач, Указатели

Аноним:

31.03.2013 в 9:33 дп

😛

Ответить

Gen:

17.10.2013 в 12:15 дп

В CODE::BLOCK для работы функции memcpy необходимо подключить

 #include <cstring>

1	#include <cstring>

и соответственно using namespace std; и главная функция int main().и все работает на ура.Спасибо. 😛

admin:

17.10.2013 в 6:00 дп

В CodeBlock

#include <iostream>
#include <mem.h> 

using namespace std;

//ФУНКЦИЯ ВВОДА ЭЛЕМЕНТОВ В МАССИВ
void input(int *&Arr,int N)
{
    for (int i=0;i<N;i++) Arr[i]=i; //Заполнение массива
}

//ФУНКЦИЯ ОТОБРАЖЕНИЯ МАССИВА НА ЭКРАНЕ
void show(int *&Arr,int N)
{
    for (int i=0;i<N;i++) cout<<Arr[i]<<" "; //Вывод массива
    cout<<endl;
}

//ФУНКЦИЯ ЦИКЛИЧЕСКОГО СДВИГА МАССИВА ВЛЕВО
void sdvig(int *&Arr,int N,int step)
{

 int *tempArr=Arr; //Сохраняем указатель на начало основного массива Arr
 int *temp=new int[step]; //Локальный массив для частичного копирования данных из Arr
   memcpy(temp,Arr,step*sizeof(step)); //Копирование в temp части массива Arr

   Arr+=step; //Смена адреса начала основного массива Arr на адрес своего же элемента по индексу step

   memcpy(tempArr,Arr,N*sizeof(N)); //Копирование данных на исходный адрес основного массива (В данный момент Адрес основного массива не исходный)
   memcpy(tempArr+N-step,temp,step*sizeof(step)); //Копирование обрезанных данных в конец массива (В данный момент Адрес основного массива не исходный)

   Arr-=step; //Возврат адреса основного массива в исходное положение

 delete []temp; //Очистка памяти от созданного локально массива
}

int main()
{

    int N=0;
    int step=0;

    cout<<"ЭЛЕМЕНТОВ В МАССИВЕ:  "; cin>>N;
    cout<<"ВЛЕВО НА:   "; cin>>step;
 int *Arr=new int [N]; //Выделяем память под  массив Arr

   input(Arr,N); //Ввод данных в массив
   show(Arr,N);  //Отображение массива на экране
   sdvig(Arr,N,step%N); //Сдвиг элементов на step влево
   show(Arr,N); //Отображение массива на экране
  delete []Arr; //Очищаем память от Arr

 return 0;
}

#include <mem.h>

//ФУНКЦИЯ ВВОДА ЭЛЕМЕНТОВ В МАССИВ

void input(int *&Arr,int N)

for (int i=0;i<N;i++) Arr[i]=i; //Заполнение массива

//ФУНКЦИЯ ОТОБРАЖЕНИЯ МАССИВА НА ЭКРАНЕ

void show(int *&Arr,int N)

for (int i=0;i<N;i++) cout<<Arr[i]<<" "; //Вывод массива

cout<<endl;

//ФУНКЦИЯ ЦИКЛИЧЕСКОГО СДВИГА МАССИВА ВЛЕВО

void sdvig(int *&Arr,int N,int step)

int *tempArr=Arr; //Сохраняем указатель на начало основного массива Arr

int *temp=new int[step]; //Локальный массив для частичного копирования данных из Arr

memcpy(temp,Arr,step*sizeof(step)); //Копирование в temp части массива Arr

Arr+=step; //Смена адреса начала основного массива Arr на адрес своего же элемента по индексу step

memcpy(tempArr,Arr,N*sizeof(N)); //Копирование данных на исходный адрес основного массива (В данный момент Адрес основного массива не исходный)

memcpy(tempArr+N-step,temp,step*sizeof(step)); //Копирование обрезанных данных в конец массива (В данный момент Адрес основного массива не исходный)

Arr-=step; //Возврат адреса основного массива в исходное положение

delete []temp; //Очистка памяти от созданного локально массива

int main()

int N=0;

int step=0;

cout<<"ЭЛЕМЕНТОВ В МАССИВЕ: "; cin>>N;

cout<<"ВЛЕВО НА: "; cin>>step;

int *Arr=new int [N]; //Выделяем память под массив Arr

input(Arr,N); //Ввод данных в массив

show(Arr,N); //Отображение массива на экране

sdvig(Arr,N,step%N); //Сдвиг элементов на step влево

delete []Arr; //Очищаем память от Arr

return 0;

18.10.2013 в 1:32 дп

Эти коды идентичны? И как лучше писать с прототипами или как у вас?

#include 
#include 
#include 

using namespace std;

//Прототипы функций
void input(int[],int );//ФУНКЦИЯ ВВОДА ЭЛЕМЕНТОВ В МАССИВ
void show(int[],int);//ФУНКЦИЯ ОТОБРАЖЕНИЯ МАССИВА НА ЭКРАНЕ
void sdvig(int[],int N,int step);//ФУНКЦИЯ ЦИКЛИЧЕСКОГО СДВИГА МАССИВА ВЛЕВО

int main()
{
	system("chcp 1251 > nul");
    int N=0;
    int step=0;
    cout<>N;
    cout<>step;
int *Arr=new int [N]; //Выделяем память под  массив Arr
//вызов функций
   input(Arr,N); //Ввод данных в массив
   show(Arr,N);  //Отображение массива на экране
   sdvig(Arr,N,step%N); //Сдвиг элементов на step влево
   show(Arr,N); //Отображение массива на экране
  delete []Arr; //Очищаем память от Arr
return 0;
}
//Описание функций
void input(int Arr[],int N)
{
    for (int i=0;i<N;i++) Arr[i]=i; //Заполнение массива
}

void show(int Arr[],int N)
{
    for (int i=0;i<N;i++) cout<<Arr[i]<<" "; //Вывод массива
    cout<<endl;
}

void sdvig(int Arr[],int N,int step)
{
int *tempArr=Arr; //Сохраняем указатель на начало основного массива Arr
int *temp=new int[step]; //Локальный массив для частичного копирования данных из Arr
   memcpy(temp,Arr,step*sizeof(step)); //Копирование в temp части массива Arr
   Arr+=step; //Смена адреса начала основного массива Arr на адрес своего же элемента по индексу step
   memcpy(tempArr,Arr,N*sizeof(N)); //Копирование данных на исходный адрес основного массива (В данный момент Адрес основного массива не исходный)
   memcpy(tempArr+N-step,temp,step*sizeof(step)); //Копирование обрезанных данных в конец массива (В данный момент Адрес основного массива не исходный)
   Arr-=step; //Возврат адреса основного массива в исходное положение
delete []temp; //Очистка памяти от созданного локально массива
}

#include

//Прототипы функций

void input(int[],int );//ФУНКЦИЯ ВВОДА ЭЛЕМЕНТОВ В МАССИВ

void show(int[],int);//ФУНКЦИЯ ОТОБРАЖЕНИЯ МАССИВА НА ЭКРАНЕ

void sdvig(int[],int N,int step);//ФУНКЦИЯ ЦИКЛИЧЕСКОГО СДВИГА МАССИВА ВЛЕВО

system("chcp 1251 > nul");

cout<>N;

cout<>step;

//вызов функций

//Описание функций

void input(int Arr[],int N)

void show(int Arr[],int N)

void sdvig(int Arr[],int N,int step)

admin:

18.10.2013 в 2:18 дп

Да, идентичны. В маленьких программах Принципиальной разницы нет, но в больших проектах использование прототипов может сильно улучшить читаемость кода и ускорить компиляцию проекта.
Я такие вещи не описывал, но это можно найти в любом популярном поисковике, задав вопрос: «Зачем нужны прототипы». Многие авторы книг используют прототипы, при этом не особо углубляясь в механизм их работы. Так, например, в одном из изданий Дейтелов есть интересная ошибка, связанная с прототипами (интересна с той точки зрения, что новичкам её очень сложно исправить). Там описывается пример моделирования колоды карт и этот пример описан на сайте.
Я это к тому, что всё от ситуации зависит. Если что-то есть в языке, то не обязательно это это что-то использовать везде и повсюду, лучше это что-то уметь применять и применять только тогда когда это действительно нужно.
Вот как-то так, наверное.

Ответить
- admin:
  
  18.10.2013 в 2:43 дп
  
  Пример описан не в виде ошибки и ее исправления, а просто в виде правильного примера. Издание я не помню.
  
  Ответить

18.10.2013 в 1:37 дп

Угловые скобки не принимает ни при каком раскладе.инклуды iostream,mem.h,stdlib.h

18.10.2013 в 5:24 пп

Спасибо!Растолковали стало понятнее.Речь об ошибках не идет, ошибок нет оба кода работают одинаково верно.

Максим:

07.01.2014 в 3:19 пп

передавать массив по ссылке тут нет никакой надобности, достаточно было локальной копии указателя на начало массива. если сотрёте амперсанд в описании точно также всё будет отлично работать, даже со статичными массивами. и даже можно удалить 30 строчку, так как это будет локальной копией.

грубейшие ошибки в 28 строке
1- это использование мемкопи для пересекающихся областей памяти, если области накладываются то нужно использовать memmove
2- вы выходите за границу массива, копировать нужно только N-step элементов.

«В коде видно, что в функции сдвига сначала идет смещение указателя на несколько позиций, потом идет возвращение его на исходную. Делается это для корректного удаления выделенной беглецу памяти, так как уже было описано, память за массивом не бегает.»

тут дело не только в «утечке памяти» вы поломали внешнюю переменную, указывавшую на начало массива, и вам необходимо её починить, это одна из причин почему передавать данные по ссылке без острой на то необходимости считается плохим тоном..

admin:

07.01.2014 в 8:17 пп

Я достаточно часто передавал данные по ссылке, хотя иногда зазря. Не могу этого отрицать.
Вы скорее всего тут не совсем точно выразились. Может и дурной тон с ссылками, но большинство компиляторов умеют игнорировать передачу по ссылке в тех случаях когда передача по ссылке не имеет смысла.
То, что я говорю: «Неточно выразились» — просто выражение: «острая на то необходимость» достаточно расплывчато. А может в меня стрельнули бы и убили, если бы я не передавал данные по ссылке. Или может обещали заплатить миллион, если я передам по ссылке. А это всё — острая необходимость.
=================
И я с вами кое в чем не согласен.
Здесь дурной тон не передача по ссылке, а то, что я ломаю внешнюю переменную, которую ломать не должен.
==================
я это достаточно давно писал и честно говоря не врубаюсь пока, как выхожу за границу массива, пока не врублюсь, исправлять этот момент не стану.
==================
по поводу того, что можно убрать 30 строчку. Эта строчка важна с той точки зрения, что должна показывать, что то, что мы вытворяем, иногда нужно откатывать. Здесь это маловажно, но зато актуально становится при работе с памятью. И вы должны хорошо понимать к чему я клоню.

Ответить
- admin:
  
  07.01.2014 в 8:45 пп
  
  По поводу выходов за границы. Посмотрел, подумал, но так и не увидел в чем проблема.
  В 28 строке я копирую step элементов. Просто применяю арифметику указателей, чтобы копировать не с первого элемента по индексу, а начиная с элемента по индексу (N-step). Т.е. последние step элементов.
  
  Ответить

Последние комментарии

Александр к записи Хороший стиль программирования
Аноним к записи Список тем сайта
Аноним к записи Список тем сайта

Циклический сдвиг массива влево с помощью указателей

11 комментариев на «“Циклический сдвиг массива влево с помощью указателей”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета