UC知道关于C 怎样实现这个算法？
来源：百度知道 编辑：UC知道 时间：2024/06/25 19:13:35
有n个整数，使其前面的各数顺序向后移m个位置，最后m个数变成最前面的m个数。谁给我说一下，实现这个算法的思路。有其代码，但看不懂。代码如下：
move(int array[20],int n,int m)
{
int *p,array_end;
array_end=*(array+n-1);
for(p=array+n-1;p>array;p--)
*p=*(p-1);
*array=array_end;
m--;
if(m>0)
move(array,n,m);
}
move(int array[20],int n,int m)
{
int *p,array_end;
array_end=*(array+n-1);
for(p=array+n-1;p>array;p--)
*p=*(p-1);
*array=array_end;
m--;
if(m>0)
move(array,n,m);
}
如果你能理解往一个数组插如一个元素的算法,这个就好办了
实际上是这样
这是一个递归调用
每一次都先把数组的最后一个数先拿出保存,然后把第1个元素到第n-1的元素向右移动一位,再把先保存的最后一个元素存放到移动出来空着的第一位上
就是把数组最后一位插入到第一位上,也就是数组整体右移一次
这样,调用m次以后,算法就完成了
顺序表还是链表?
楼上的算法,效率太低了吧~!时间复杂度为O(m*n)
为什么我们不能重新复制一个,再回填?这样的时间复杂度仅为2n
array_end=*(array+n-1); 把最后一个数赋给array_end
for(p=array+n-1;p>array;p--)
*p=*(p-1); 数组中的数每个向后移一位，除了最后一个数
*array=array_end; 把原来的最后一个数放到一位
以上就完成了每个数顺序向后移一位
m--; 每移动数组一次减一
if(m>0)
move(array,n,m); 当m>0时，重复之前的程序