【例1】循環(huán)左移1位

輸入10個(gè)整數(shù)到數(shù)組a中，將數(shù)組各元素依次循環(huán)左移一個(gè)位置（如下圖1），輸出移動(dòng)后的數(shù)組a。

圖1? 數(shù)組元素循環(huán)左移1位

• 編程思路

先將a[0]保存起來（t=a[0]），再用一個(gè)循環(huán)將a[1]~a[9]依次前移一位，最后將預(yù)存起來的a[0]送至a[9]即可。

• 源程序及運(yùn)行結(jié)果

#include <iostream>

using namespace std;

int? main( )

{

?? int? a[10],i,t ;??????????????????????????

?? for (i=0;i<10;i++)

?????? cin>>a[i];

?? t=a[0];

?? for(i=0;i<9;i++)

?????? a[i]=a[i+1];

?? a[9]=t;

?? for (i=0;i<10;i++)

?? cout<<a[i]<<"?? ";

?? cout<<endl;

?? return 0;

}

編譯并執(zhí)行以上程序，得到如下所示的結(jié)果。

1 2 3 4 5 6 7 8 9 10

2?? 3?? 4?? 5?? 6?? 7?? 8?? 9?? 10?? 1

Press any key to continue

?

【例2】循環(huán)左移P位

設(shè)有n（n>1）個(gè)整數(shù)存放在一維數(shù)組R中。試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能高效的算法。將R中的序列循環(huán)左移P（0<P<n）個(gè)位置，即將R中的數(shù)據(jù)由（X₀，X₁，…X_n-1）變換為（X_p，X_p+1，…，X_n-1，X₀，X₁，…，X_p-1）。

• 編程思路1

上一個(gè)實(shí)例中，程序段：

?? t=a[0];

?? for(i=0;i<9;i++)

?????? a[i]=a[i+1];

?? a[9]=t;

實(shí)現(xiàn)了循環(huán)左移1位。將這個(gè)程序段循環(huán)執(zhí)行p次，即可完成循環(huán)左移p位的操作。

按這一思路所設(shè)計(jì)的算法的時(shí)間復(fù)雜度為O（p*n），空間復(fù)雜度為O（1）。

• 源程序1及運(yùn)行結(jié)果

#include <iostream>

using namespace std;

int main()

{

??? int? r[10]={1,2,3,4,5,6,7,8,9,10};

??? int i,p,t,times;

??? cout<<"請輸入需要左移的次數(shù)p （0<p<10):";

?????? cin>>p;

??? cout<<"數(shù)組初始情況為：";

?????? for (i = 0; i <10 ; i++)??

?????? ? cout<<r[i]<<"? ";

??? cout<<endl;

??? for(times=1;? times<=p; times++)

?????? {

????? t=r[0];

????? for(i=0;i<9;i++)

????????? r[i]=r[i+1];

????? r[9]=t;

??? }

??? cout<<"循環(huán)左移"<<p<<"位后，數(shù)組變換為：";

?????? for (i = 0; i <10 ; i++)??

?????? ? cout<<r[i]<<"? ";

??? cout<<endl;

??? return 0;

}

編譯并執(zhí)行以上程序，得到如下所示的結(jié)果。

請輸入需要左移的次數(shù)p （0<p<10):4

數(shù)組初始情況為：1? 2? 3? 4? 5? 6? 7? 8? 9? 10

循環(huán)左移4位后，數(shù)組變換為：5? 6? 7? 8? 9? 10? 1? 2? 3? 4

Press any key to continue

?

• 編程思路2

定義一個(gè)可以放下p個(gè)整數(shù)的輔助數(shù)組temp，將數(shù)組R中的前p個(gè)整數(shù)依次存入輔助數(shù)組temp中，將R中后面的n-p個(gè)整數(shù)依次前移p個(gè)位置，將輔助數(shù)組中的數(shù)據(jù)依次取出，放入R中第n-p個(gè)整數(shù)開始的位置。

按這一思路所設(shè)計(jì)的算法的時(shí)間復(fù)雜度為O（n），空間復(fù)雜度為O（p）。

• 源程序2

#include <iostream>

using namespace std;

int main()

{

??? int? r[10]={1,2,3,4,5,6,7,8,9,10};

??? int temp[10];???????? // 輔助數(shù)組，存放要移出的整數(shù)

??? int i,p;

??? cout<<"請輸入需要左移的次數(shù)p （0<p<10):";

?????? cin>>p;

??? cout<<"數(shù)組初始情況為：";

?????? for (i = 0; i <10 ; i++)??

?????? ? cout<<r[i]<<"? ";

??? cout<<endl;

?????? for(i=0;i<p;i++)?????? // 將R中前p個(gè)數(shù)據(jù)存入輔助數(shù)組中

??????? temp[i]=r[i];

??? for(i=0;? i< 10-p;i++)? // 將R中從第p個(gè)整數(shù)開始的整數(shù)前移p個(gè)位置

?????? r[i]=r[p+i];

??? for(i=0; i<p; i++)????? // 將輔助數(shù)組中的p個(gè)數(shù)據(jù)放到R中第n-p個(gè)數(shù)據(jù)的后面

?????? r[10-p+i]=temp[i];

??? cout<<"循環(huán)左移"<<p<<"位后，數(shù)組變換為：";

?????? for (i = 0; i <10 ; i++)??

?????? ? cout<<r[i]<<"? ";

??? cout<<endl;

??? return 0;

}

?

• ?編程思路3

將數(shù)組R循環(huán)左移p位后，前p個(gè)數(shù)一定移動(dòng)到后面，而后n-p移動(dòng)到前面，因此可先將數(shù)組R逆置，然后再將R中前n-p個(gè)元素原地逆置，再將后p個(gè)元素原地逆置，如圖2所示。

?

圖2? 用逆置的方法將數(shù)組R中的數(shù)據(jù)循環(huán)移位

為了程序編寫簡捷，可以將數(shù)組R中從begin開始到end結(jié)束（包括end）的元素進(jìn)行逆置的操作寫成如下的函數(shù)：

void Reverse(int r[],int begin,int end)

{

??? int i,temp;

?????? for(i=0;i<(end-begin+1)/2;i++)

?????? {

????????????? temp=r[begin+i];? r[begin+i]=r[end-i]; r[end-i]=temp;

?????? }

}

這樣，上述算法中三個(gè)Reverse函數(shù)的時(shí)間復(fù)雜度分別為O（n/2）、O（(n-p)/2）和O（p/2），故所設(shè)計(jì)的算法的時(shí)間復(fù)雜度為O（n），空間復(fù)雜度為O（1）。

• 源程序3

#include <iostream>

using namespace std;

void Reverse(int r[],int begin,int end)

{

??? int i,temp;

?????? for(i=0;i<(end-begin+1)/2;i++)

?????? {

????????????? temp=r[begin+i];? r[begin+i]=r[end-i]; r[end-i]=temp;

?????? }

}

int main()

{

??? int? r[10]={1,2,3,4,5,6,7,8,9,10};

??? int i,p;

??? cout<<"請輸入需要左移的次數(shù)p （0<p<10):";

?????? cin>>p;

??? cout<<"數(shù)組初始情況為：";

?????? for (i = 0; i <10 ; i++)??

?????? ? cout<<r[i]<<"? ";

??? cout<<endl;

??? Reverse(r,0,10-1);?????? // 全部逆置

?????? Reverse(r,0,10-p-1);???? // 前n-p個(gè)元素逆置

?????? Reverse(r,10-p,10-1);??? // 后p個(gè)元素逆置

??? cout<<"循環(huán)左移"<<p<<"位后，數(shù)組變換為：";

?????? for (i = 0; i <10 ; i++)??

?????? ? cout<<r[i]<<"? ";

??? cout<<endl;

??? return 0;

}

?

轉(zhuǎn)載于:https://www.cnblogs.com/cs-whut/p/10975293.html

總結(jié)

以上是生活随笔為你收集整理的数组循环移位的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。