算法一日一练 01

故乡的风

在一维数组A[m+n]中顺序存放两个线性表(a1,  a2, a3, ... , am)和(b1, b2, b3, ... , bn)，编写函数，将两个线性表位置互换，即将(b1, b2, b3, ... , bn)放在(a1,  a2, a3, ... , am)前面。
试着设计在时间及空间两方面都尽量高效的算法，并将想法及源码贴出来（语言不限，最好C/C++）。我将适量给予评分，希望大家踊跃参与。

qiusuo

我负责顶贴

囩戨

路过。。得分。。。

Potato丶

1. void exchangelist(int *list,int m,int n)
   
2. {
   
3.         void exch(int *list , int i ,int j);
   
4.         int i=0,j=m+n-1;
   
5.         
   
6.         exch(list,i,j);
   
7.         
   
8.     exch(list,i,n-1);
   
9.         
   
10.         exch(list,n,j);
    
11.         
    
12. }
    
13. 
    
14. void exch(int *list , int i ,int j)
    
15. {
    
16.         int temp;
    
17.         while (i<j)
    
18.         {
    
19.                 temp=*(list+i);
    
20.                 *(list+i)=*(list+j);
    
21.                 *(list+j)=temp;
    
22.                 i++;
    
23.                 j--;
    
24.         }
    
25. }
    

复制代码

基本思想：先把整个表倒序。例如a1-am  b1-bn 翻转得到bn-b1  am-a1  再将b表，a表依次翻转即可。


测试代码：

1. #include <stdio.h>
   
2. 
   
3. void exchangelist(int *list,int m,int n);
   
4. 
   
5. void main()
   
6. {
   
7.         int list[20];
   
8.     int i;
   
9.         
   
10.         for (i=0;i<20;i++)
    
11.                 list[i]=i+1;
    
12.         exchangelist(list,12,8);
    
13.         printf("Exchange successfully!\n");
    
14.         for (i=0;i<20;i++)
    
15.                 printf("%3d",list[i]);
    
16.         printf("\n");
    
17. }

复制代码

快乐阳光

路过...........................................

天下无敌丑爸爸

矮油，支持啊，搞算法的大神，你把小甲鱼拉着，我可以每天陪你一算！哈哈！

非常7十1

路过，顶一下

ssyss501

算法不是太了解

天下无敌丑爸爸

要是能快点我就写楼上那个算法了，以前也看过，唉，为了完全摆脱这种逆序思维，真是麻烦，不知道楼主看看我这样的折叠然后进行加头加尾的方法有没有可能能够进一步的提高效率，而且我不要鱼币你给我点荣誉值哈，我要早点升到鱼油1.像楼主致敬，明天的算法帖子我要早点来了。
#include <iostream>
#define MIN(a,b)                a>b?b:a
#define MAX(a,b)        a>b?a:b
void sort(int* p,int m,int n);
void rush(int* p,int m,int n);
void addhead(int* p,int j,int k);
void addtail(int* p,int j,int k);
void display();
void main()
{       
int p[20]={0};
for(int i=0;i<20;i++)
p[i]=i+1;
for(int j=0;j<i;j++)
std::cout<<p[j]<<std::ends;
std::cout<<std::endl;
sort(p,8,12);
for(j=0;j<i;j++)
std::cout<<p[j]<<std::ends;
}
void sort(int* p,int m,int n)
{
rush(p,m,n);
if(m>n)
addhead(p,n,m);
else if(m<n)
addtail(p,n,m);
}
void rush(int* p,int m,int n)
{
int rep;
int a=MIN(m,n);
int b=MAX(m,n);
for(int i=0;i<a;i++)
{
rep=p[b+i];
p[b+i]=p[i];
p[i]=rep;
}
}
void addhead(int* p,int j,int k)
{
for(int q=j;q>0;q--)
{
int rep=p[j+k-1];
for(int i=k;i>0;i--)
{
        p[i+j-1]=p[i+j-2];
}
p[i+j]=rep;
}
}
void addtail(int* p,int j,int k)
{
for(int q=j-k;q>0;q--)
{
int rep=p[j-1];
for(int i=j-1;i>0;i--)
{
p[i]=p[i-1];
}
p[i]=rep;
}
}
思路：首先进行折叠，然后进行加尾，当m<n时进行加头。对于m=18，n=2。这样m n差距较大的时候我算法估计要快一点。

晨风吹过

不错，学习了

330740120

路过！~拿点分回家

qingtiancao

我这都是哪天了，赶不上了

牡丹花下死做鬼

qingtiancao 发表于 2013-8-15 09:30

                               
登录/注册后可看大图

我这都是哪天了，赶不上了

只要你有思路就不怕晚 我想了半天没想出什么好的方法来 ~~~~(>_<)~~~~

风雪傲月3728

只是路过，看看

繁空.星雨

顶一下

14709722197

唉  跟不上

wangerwanger

负责支持楼主！！

mumudontcry

感谢楼主分享，突然发现：我适量给予评分
这样的话会导致拿分的多余讨论的

醉、爱

Potato丶 发表于 2013-7-20 10:14
基本思想：先把整个表倒序。例如a1-am  b1-bn 翻转得到bn-b1  am-a1  再将b表，a表依次翻转即可。

厉害。。。。

waliemiao

厉害。。。。