钟馗伏魔之石魂镇,xbookmaker,台湾凤梨
【例1】循环左移1位
输入10个整数到数组a中，将数组各元素依次循环左移一个位置（如下图1），输出移动后的数组a。
图1 数组元素循环左移1位
先将a[0]保存起来（t=a[0]），再用一个循环将a[1]~a[9]依次前移一位，最后将预存起来的a[0]送至a[9]即可。
#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;
}
编译并执行以上程序，得到如下所示的结果。
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】循环左移p位
设有n（n>1）个整数存放在一维数组r中。试设计一个在时间和空间两方面尽可能高效的算法。将r中的序列循环左移p（0<p<n）个位置，即将r中的数据由（x0，x1，…xn-1）变换为（xp，xp+1，…，xn-1，x0，x1，…，xp-1）。
上一个实例中，程序段：
t=a[0];
for(i=0;i<9;i++)
a[i]=a[i+1];
a[9]=t;
实现了循环左移1位。将这个程序段循环执行p次，即可完成循环左移p位的操作。
按这一思路所设计的算法的时间复杂度为o（p*n），空间复杂度为o（1）。
#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<<"请输入需要左移的次数p （0<p<10):";
cin>>p;
cout<<"数组初始情况为：";
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<<"循环左移"<<p<<"位后，数组变换为：";
for (i = 0; i <10 ; i++)
cout<<r[i]<<" ";
cout<<endl;
return 0;
}
编译并执行以上程序，得到如下所示的结果。
请输入需要左移的次数p （0<p<10):4
数组初始情况为：1 2 3 4 5 6 7 8 9 10
循环左移4位后，数组变换为：5 6 7 8 9 10 1 2 3 4
press any key to continue
定义一个可以放下p个整数的辅助数组temp，将数组r中的前p个整数依次存入辅助数组temp中，将r中后面的n-p个整数依次前移p个位置，将辅助数组中的数据依次取出，放入r中第n-p个整数开始的位置。
按这一思路所设计的算法的时间复杂度为o（n），空间复杂度为o（p）。
#include <iostream>
using namespace std;
int main()
{
int r[10]={1,2,3,4,5,6,7,8,9,10};
int temp[10]; // 辅助数组，存放要移出的整数
int i,p;
cout<<"请输入需要左移的次数p （0<p<10):";
cin>>p;
cout<<"数组初始情况为：";
for (i = 0; i <10 ; i++)
cout<<r[i]<<" ";
cout<<endl;
for(i=0;i<p;i++) // 将r中前p个数据存入辅助数组中
temp[i]=r[i];
for(i=0; i< 10-p;i++) // 将r中从第p个整数开始的整数前移p个位置
r[i]=r[p+i];
for(i=0; i<p; i++) // 将辅助数组中的p个数据放到r中第n-p个数据的后面
r[10-p+i]=temp[i];
cout<<"循环左移"<<p<<"位后，数组变换为：";
for (i = 0; i <10 ; i++)
cout<<r[i]<<" ";
cout<<endl;
return 0;
}
将数组r循环左移p位后，前p个数一定移动到后面，而后n-p移动到前面，因此可先将数组r逆置，然后再将r中前n-p个元素原地逆置，再将后p个元素原地逆置，如图2所示。
图2 用逆置的方法将数组r中的数据循环移位
为了程序编写简捷，可以将数组r中从begin开始到end结束（包括end）的元素进行逆置的操作写成如下的函数：
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;
}
}
这样，上述算法中三个reverse函数的时间复杂度分别为o（n/2）、o（(n-p)/2）和o（p/2），故所设计的算法的时间复杂度为o（n），空间复杂度为o（1）。
#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<<"请输入需要左移的次数p （0<p<10):";
cin>>p;
cout<<"数组初始情况为：";
for (i = 0; i <10 ; i++)
cout<<r[i]<<" ";
cout<<endl;
reverse(r,0,10-1); // 全部逆置
reverse(r,0,10-p-1); // 前n-p个元素逆置
reverse(r,10-p,10-1); // 后p个元素逆置
cout<<"循环左移"<<p<<"位后，数组变换为：";
for (i = 0; i <10 ; i++)
cout<<r[i]<<" ";
cout<<endl;
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
我要评论
网友评论