计算机考研王道数据结构2.2.4编程第8题另解
计算机考研王道数据结构2.2.4编程第8题另解
- 因为本人考研所以在学习王道的数据结构做到这题的时候有了和答案不一样的想法,打算发出来和大家讨论一下能不能这样解
- 题目大意是将线性表的前m个和后面n个在交换位置。直接上图说明
- 书上的解法我感觉大概要运行2(m+n)次交换(每次交换又3次交换),我大概脑洞大开了一下,感觉自己的算法只要O(m),不知道有没有错误
代码
void ChangeList(int A[],int m,int n){//A的元素的总量为n+m ,m是前面的个数,n是后面的个数
int temp=0;//交换中间变量
if(n<=m){//如果n<m,从前往后m次三元交换,可以看后面写的示意也许会更好理解
for(int i = 0;i<n ;i++){
temp=A[i];
A[i]=A[i+m];
A[i+m]=A[i+n];
A[i+n]=temp;
}
}
else{
for(int i = n+m-1;i>=n ;i--){
temp=A[i];
A[i]=A[i-n];
A[i-n]=A[i-m];
A[i-m]=temp;
}
}
//循环次数只有m次
}
代码解释:
- 如一开始是0 1 2 3 4 5 6 7 8 9 ,如果n>m就进行如下交换
0 1 2 5 4 9 6 7 8 3
0 1 4 5 8 9 6 7 2 3
0 5 4 7 8 9 6 1 2 3
4 5 6 7 8 9 0 1 2 3
从而经历了m次达到了目标 - 如果n<m将会开始
6 1 2 3 0 5 4 7 8 9
6 7 2 3 0 1 4 5 8 9
6 7 8 3 0 1 2 5 4 9
6 7 8 9 0 1 2 3 4 5 同样经历了m次交换(每次交换有4次交换)达到了目标
另一种情况的输出结果,貌似也符合要求。
目前跑的情况来看应该是没有问题,不知道有没有能提供下意见,谢谢大神赐教。