• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C++中数组的普通移位和循环移位

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

普通移位:

若数组想从某一位开始向右移n位,一般是从数组的最后一位开始逐次向右移位。

程序如下:

View Code
#include <iostream>
#include <stdlib.h>
using namespace std;
int s[11]={1,2,3,4,5,6,7,8,9,0};
void main()
{
for (int i=0;i<11;i++)
{
cout<<s[i];
}
cout<<endl;
//移位代码,此地假设向右移移位
for (int j=10;j>0;j--)
{
s[j]=s[j-1];
}
for (int k=0;k<11;k++)
{
cout<<s[k];
}
cout<<endl;
}

程序运行结果截图:

  

循环移位,下面是自己编的一个:

View Code
#include<iostream>
#include<stdlib.h>
using namespace std;
int s[10]={1,2,3,4,5,6,7,8,9,0};
void main()
{
int temp;
//向右循环移位3位
for(int i=1;i<=3;i++)
{
temp=s[9];
for(int j=9;j>=1;j-- )
{
s[j]=s[j-1];
}
s[0]=temp;
}
for(int k=0;k<=9;k++)
{
cout<<s[k];
}
}

其实原理就是通过一个间接的变量,对数组进行移位。假设数组长度为N,需要循环右移K次,则算法的复杂度为O(K*N),当K>N时算法的复杂度甚至大于O(N^2)。

运行结果图:

通过分析可以发现,K>N时所移动的位数和K'=K%N相同,如是衍生出如下算法:

View Code
#include<iostream>
#include<stdlib.h>
using namespace std;
int s[10]={1,2,3,4,5,6,7,8,9,0};
void main()
{
int temp;
int K,KK;
K=99;
//向右循环移位K位
KK=K%10;//数组长度为10
for(int i=1;i<=K;i++)
{
temp=s[9];
for(int j=9;j>=1;j-- )
{
s[j]=s[j-1];
}
s[0]=temp;
}
for(int k=0;k<=9;k++)
{
cout<<s[k];
}
cout<<endl;
}


运行结果略。

在网上找到一种复杂度为:O(N)的方法,原理如下:

假设原序列为:abcd1234

移位4位后为:1234abcd

移位过程可以表示成如下步骤:

逆序排列abcd:dcba1234

逆序排列1234:dcba4321

逆序排列dcba4321:1234abcd

也就是说需要编写一个逆序函数,并进行三次逆序变换。

代码如下:

View Code
 1 #include<iostream>
2 #include<stdlib.h>
3 using namespace std;
4 void Reverse(int *arr,int b,int e);
5 int s[10]={1,2,3,4,5,6,7,8,9,0};
6 void main()
7 {
8 int k,kk,N;
9 N=10;
10 k=99;
11 kk=k%10;
12 //下面为循环移位部分
13 Reverse(s,0,N-kk-1);
14 Reverse(s,N-kk,N-1);
15 Reverse(s,0,N-1);
16 //显示
17 for(int i=0;i<=9;i++)
18 {
19 cout<<s[i];
20 }
21 cout<<endl;
22 }
23 void Reverse(int *arr,int b,int e)
24 {
25 int temp;
26 for(;b<e;b++,e--)
27 {
28 temp=arr[e];
29 arr[e]=arr[b];
30 arr[b]=temp;
31 }
32 }



 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap