您的位置：程序门 -> c/c++ -> c++ 语言

请教两个数组怎么样互补的问题

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

请教两个数组怎么样互补的问题

发表于：2007-12-24 11:21:01 楼主

假设:
int a[]={1,3,5,7,9};
int b[]={2,4,6,8};
要求:
不能将两个数组合并后再分别复制到两个数组中.
结果:
a[]={1,2,3,4,5,6,7,8,9};
b[]={1,2,3,4,5,6,7,8,9};

请达人指教.

发表于：2007-12-24 11:27:231楼得分:0

按这种声明不可能,因为ab的空间不够

发表于：2007-12-24 11:33:042楼得分:0

假设空间足够大的情况下

发表于：2007-12-24 11:46:233楼得分:0

插入排序

发表于：2007-12-24 11:48:374楼得分:0

不能将两个数组合并后再分别复制到两个数组中？
空间够就先合并再排序不是蛮好吗

发表于：2007-12-24 12:18:075楼得分:0

其实排不排序不重要,我只想两个数组的元素互补

发表于：2007-12-24 12:41:426楼得分:0

c/c++ code


//比较基础的，没有怎么测试，有错的话，自己改一下，
#include <iostream>
using namespace std;

int main（)
{
    int a[]={1,3,5,7,9}; 
    int b[]={2,4,6,8}; 
    int dest[9], count=0, i;
    for （i=0; i<5; i++)
    {
        dest[i]=a[i];
    }
    count=i;
    for （int j=0; j<4; j++)
    {
        int k;
        for （k=0; k<count; k++)
        {
            if（dest[k]==b[j])
                break;
        }
        if（k==count) //没有找到相同的元素，
        {
            dest[count]=b[j];
            count++;
        }
    }
    for （int k=0; k<count; k++) cout<<dest[k]<<endl;
    return 0;
}

发表于：2007-12-24 13:13:557楼得分:0

有解决办法：

空间问题：
栈中数据是从高低址到低地址连续存储的，所以只要定义一个指针ｃ：
int * c = b;[注：因为ｂ是后定义的，所以在高地址］
这样ｃ就相当于一个新的数组｛２，４，６，８，１，３，５，７｝

排序问题：
原地按间隔将a插入b：
i从0开始迭代，直到i = sizeof a;
1 将a[i]取出，存入tmp
2 将b[2*i]及后面的元素后移一个元素，再将tmp插入b[2*i]：c变为{1，2，4，6，8，3，5，7}
3 i++;

迭代结束，将c的地址付给a,b

发表于：2007-12-24 14:29:408楼得分:0

6楼只是把两个数组合并,不是我想要的
7楼的"int*c=b;c相当于一个新数组{2,4,6,8,1,3,5,7} "这是什么意思?你是想说c是一个指向数组b的指针吗?b并没有1,3,5,7等元素.另外我想要的是不需要第3个数组也不需要临时（或虚拟)第3数组的情况.

以下是我自己的笨办法.
//前提每个数组中的元素值都是唯一的
int n=20;
int i=j=0;
bool iscopy=true;
int a[n]={1,3,5,7,8,9};
int b[n]={1,2,4,5,6,8};
int lon（int * m)
{
int l=0;
while（m[e]!=0)
{
l++;
}
return --l;
}
int la=lon（a);
int lb=lon（b);
while（i <la)
{
j=0;
while（j <lb)
{
if（b[j]==a[i])
{
iscopy=false;
break;
}
j++;
}
if（iscopy)
{
a[la+1]=b[j];
}
i++;
}
i=0;
iscopy=true;
while（i <lb)
{
j=0;
while（j <la)
{
if（a[j]==b[i])
{
iscopy=false;
break;
}
j++;
}
if（iscopy)
{
b[lb+1]=a[j];
}
i++;
}

发表于：2007-12-24 14:31:179楼得分:0

c/c++ code


//前提每个数组中的元素值都是唯一的
int n=20;
int i=j=0;
bool iscopy=true;
int   a[n]={1,3,5,7,8,9}; 
int   b[n]={1,2,4,5,6,8};
int lon（int * m)
{
    int l=0;
    while（m[e]!=0)
    {
        l++;
    }
    return --l;
} 
int la=lon（a);
int lb=lon（b);
while（i<la)
{
    j=0;
    while（j<lb)
    {
        if（b[j]==a[i])
        {
            iscopy=false;    
            break;
        }
        j++;
    }
    if（iscopy)
    {
        a[la+1]=b[j];
    }
    i++;
}
i=0;
iscopy=true;
while（i<lb)
{
    j=0;
    while（j<la)
    {
        if（a[j]==b[i])
        {
            iscopy=false;    
            break;
        }
        j++;
    }
    if（iscopy)
    {
        b[lb+1]=a[j];
    }
    i++;
}

发表于：2007-12-24 15:34:3610楼得分:0

不好意思上面的代码错误比较多,下面这个调试过可以运行的

c/c++ code


#include <iostream.h>
int lon（int * m)
{
    int l=0;
    while（m[l]!=0)
    {
        l++;
    }
    return l;
} 
//前提每个数组中的元素值都是唯一的
void main（){
const int n=20;
int i=0,j=0;
bool iscopy=true;
int   a[n]={1,3,5,7,8,9}; 
int   b[n]={1,2,4,5,6,8};

int la=lon（a);
int lb=lon（b);
int nlb=lb;
int nla=la;
while（i<la)
{
    
    j=0;
    iscopy=true;
    while（j<lb)
    {
        if（b[j]==a[i])
        {
            iscopy=false;    
            break;
        }
        j++;
    }
    if（iscopy)
    {
        b[nlb]=a[i];
        nlb++;
    }
    i++;
}
i=0;
iscopy=true;
while（i<lb)
{
    j=0;
    iscopy=true;
    while（j<la)
    {
        if（a[j]==b[i])
        {
            iscopy=false;    
            break;
        }
        j++;
    }
    if（iscopy)
    {
        a[nla]=b[i];
        nla++;
    }
    i++;
}

la=lon（a);
for（int x=0;x<la;x++)
cout<<a[x]<<" ";
cout<<endl;
lb=lon（b);
for（int z=0;z<lb;z++)
cout<<b[z]<<" ";

}

发表于：2007-12-24 17:03:5611楼得分:0

看错了，以为要间隔插入呢...

c/c++ code

int main（)
{    
    const int n = 20;
    int   a[n]={1,3,5,7,8,9}; 
    int   b[n]={1,2,4,5,6,8};
    
    int i=0, j=0, addlen=0, flag=0;
    for （; a[i]; ++i) {
        for （j=0; b[j]; ++j) {
            if （a[i] == b[j]) {
                flag = 1;
            }
        }

        if （flag) {
            flag = 0;
            continue;
        }

        addlen++;
        b[j] = a[i];        
    }

    for （j-=addlen; j>=0; --j) {
        for （i=0; a[i]; ++i) {
            if （a[i] == b[j]) {
                flag = 1;
            }
        }

        if （flag) {
            flag = 0;
            continue;
        }
        
        a[i] = b[j];        
    }
    
    std::copy（a, a+n, std::ostream_iterator<int>（cout, ", "));
    cout << endl;
    std::copy（b, b+n, std::ostream_iterator<int>（cout, ", "));
    return 0;
}

发表于：2007-12-24 17:34:3312楼得分:0

看不懂题目，汗。。。

因为开始的数组a只有4个int元素，现在合并后想存储8个元素，可以另写算法扩展，但是这个新的能存储8个int元素的数组就已经不是以前那个数组a 了。。。

发表于：2007-12-24 18:42:5013楼得分:0

我说过假设数组空间足够大,所以并没有限制到一开始是4个元素.就好象我上面的代码一样.

发表于：2007-12-24 18:49:3814楼得分:0

11楼跟我的思路基本相同

发表于：2007-12-24 18:52:0215楼得分:0

如果可以减少些循环就好了,可是我没想到有什么好算法

发表于：2007-12-24 19:06:2216楼得分:0

mark一个，呵呵

发表于：2007-12-25 11:42:1917楼得分:0

c/c++ code


/**
 *    project name: testcpp
 *    file name: test.cpp
 *    author:    glenn
 *    date: 2007-12-25 am
 *    purpose: merge two array
 *
**/

#include <iostream>
#include <list>

using namespace std;


int main（int argc, char *argv[])
{
    int   a[32]={1,3,5,7,9};
    int   b[]={2,4,6,8};
    list<int> la,lb;
    list<int>::iterator it;

    for （int i=0;i<static_cast<int>（sizeof（a)/sizeof（int)) && a[i]!='\0';i++)
        la.push_back（a[i]);
    for （int j=0;j<static_cast<int>（sizeof（b)/sizeof（int)) && b[j]!='\0';j++)
        lb.push_back（b[j]);

    la.merge（lb);
    la.sort（);

    memset（a,0,sizeof（a));
    int n=0;
    for （it=la.begin（);it!=la.end（) && sizeof（a)/sizeof（int)>=la.size（);it++)
    {
        a[n++]=*it;
    }

    for （int m=0;m<n;m++)
    {
        cout<<a[m]<<",";
    }
    cout<<endl;

    return 0;
}

发表于：2007-12-25 13:15:1218楼得分:0

17楼你的做法是把两个数组分别建立列表,然后将列表b存入列表a然后再将列表a存回数组a.这样的话循环次数还是一样四次啊.并且我不想用借用第三方缓存的方式.

发表于：2007-12-25 16:47:4219楼得分:0

如果你的两个数据是有序的,那么就直接插入排序,把结果保存到某一个数组中,这样的话就能完全满足你的要求,如果是乱序的,那就先将两个数组排下序.或者先将两个数组融合到一起,再进行排序就可以了.

发表于：2007-12-25 18:28:1220楼得分:0

回19楼,我根本不需要排序哦

发表于：2007-12-26 10:00:3921楼得分:0

c/c++ code


/**
    假设:
    int   a[]={1,3,5,7,9};
    int   b[]={2,4,6,8};
    要求:
    不能将两个数组合并后再分别复制到两个数组中.
    结果:
    a[]={1,2,3,4,5,6,7,8,9};
    b[]={1,2,3,4,5,6,7,8,9};
**/

#include <stdio.h>
#include <stdlib.h>

int main（int argc, char *argv[])
{
    int a[32]={1,3,5,7,9},b[32]={2,4,6,8};
    int i=0,j=0;

    while （'\0'!=a[i] && '\0'!=b[i])
    {
        if （a[i]!=b[i])
        {
            for （j=sizeof（a)/sizeof（int)-1;j>i+1;--j)
                a[j]=a[j-1];    //将a[i]后面的数据移动一位
            for （j=sizeof（b)/sizeof（int)-1;j>i+1;--j)
                b[j]=b[j-1];    //将b[i]后面的数据移动一位

            if （a[i]<b[i])
            {//按升序组合两个数组
                a[i+1]=b[i];
                b[i]=a[i];
            }
            else
            {//按升序组合两个数组
                b[i+1]=a[i];
                a[i]=b[i];
            }
        }
        ++i;
    }
    if （'\0'!=a[i])
    {//如果a中还有数据
        while （'\0'!=a[i])
        {//将a剩余的数据组合到b中
            b[i]=a[i];
            ++i;
        }
    }
    if （'\0'!=b[i])
    {//如果b中还有数据
        while （'\0'!=b[i])
        {//将b剩余的数据组合到a中
            a[i]=b[i];
            ++i;
        }
    }

    for （i=0;i<sizeof（a)/sizeof（int) && '\0'!=a[i];i++)
        printf（"a[%d]=%d\n",i,a[i]);
    for （i=0;i<sizeof（b)/sizeof（int) && '\0'!=b[i];i++)
        printf（"b[%d]=%d\n",i,b[i]);

    return 0;
}

注意:
该程序只有在两个数组是有序的,并且不存在交集的前提下才能得到正确结果.

to lz
感觉你的题目不够严谨,a和b一定是升序数组吗?a和b一定是互斥的吗?如果不满足这两个要求,你能得到两个没有重复元素和有序的数组吗?还有就是前面有人提到的数组空间的问题,每个数组的空间必须大于或等于a和b中所有互斥元素的总和.

发表于：2007-12-26 10:12:5322楼得分:0

c/c++ code


/**
    假设:
    int   a[]={1,3,5,7,9};
    int   b[]={2,4,6,8};
    要求:
    不能将两个数组合并后再分别复制到两个数组中.
    结果:
    a[]={1,2,3,4,5,6,7,8,9};
    b[]={1,2,3,4,5,6,7,8,9};
**/

#include <stdio.h>
#include <stdlib.h>

int main（int argc, char *argv[])
{
    int a[32]={1,3,5,7,9},b[32]={2,4,6,8};
    int i=0,j=0;

    while （'\0'!=a[i] && '\0'!=b[i])
    {
        if （a[i]!=b[i])
        {
            for （j=sizeof（a)/sizeof（int)-1;j>i+1;--j)
                a[j]=a[j-1];    //将a[i]后面的数据移动一位
            for （j=sizeof（b)/sizeof（int)-1;j>i;--j)
                b[j]=b[j-1];    //将b[i]后面的数据移动一位

            if （a[i]<b[i])
            {//按升序组合两个数组
                a[i+1]=b[i];
                b[i]=a[i];
            }
            else
            {//按升序组合两个数组
                b[i+1]=a[i];
                a[i]=b[i];
            }
            ++i;
        }
        ++i;
    }
    if （'\0'!=a[i])
    {//如果a中还有数据
        while （'\0'!=a[i])
        {//将a剩余的数据组合到b中
            b[i]=a[i];
            ++i;
        }
    }
    if （'\0'!=b[i])
    {//如果b中还有数据
        while （'\0'!=b[i])
        {//将b剩余的数据组合到a中
            a[i]=b[i];
            ++i;
        }
    }

    for （i=0;i<sizeof（a)/sizeof（int) && '\0'!=a[i];i++)
        printf（"a[%d]=%d\n",i,a[i]);
    for （i=0;i<sizeof（b)/sizeof（int) && '\0'!=b[i];i++)
        printf（"b[%d]=%d\n",i,b[i]);

    return 0;
}

上面的代码还有点问题,纠正一下.

发表于：2007-12-26 11:35:4023楼得分:0

1 获取a,b有效长度，分别为a_len, b_len;

2 循环a_len次：
选取a[0]，开始与b[i]的比较：如果遇到相等的就说明a和b同时有该数据，于是将b[i]与b[b_len]交换，b_len--;
　　　　　　　　　　　　　　 ¦---如果遇到b[i]==0就把a[0]付给b[i]
选取a[1]，继续循环。

3 b[b_len]之前的b[i]都是a没有的，添加到a[a_len]后面即可

发表于：2007-12-26 13:25:0324楼得分:0

回23楼,你的方法最后还是要把a[a_lan]整个复制到b里b数组才能得到同步.如果可以不用复制整个数组又可以一起同步就好了.

发表于：2007-12-26 14:14:3025楼得分:0

robot1314
不好意思,可能我的第一楼问题把你误导了,请看我的10楼吧.我其实是想把两个不同的数组互补,要求不能整个数组覆盖,数组里面的数是唯一的.

发表于：2007-12-26 16:41:1426楼得分:0

to lz

那你的两个数组都是有序的吗?如果是,那么各个数组的数据都是按什么顺序排列呢?

发表于：2007-12-26 16:54:2327楼得分:0

回楼上,全部无序

发表于：2007-12-26 21:45:1928楼得分:0

to nobelb

麻烦你把你的题目的要求再完整地述说一遍,我怎么感觉有点糊涂了,汗```

发表于：2007-12-26 21:54:1929楼得分:0

有两个无序数组,里面的元素（在自己的数组里)都是唯一的.要求把两个数组互补,不用排顺序.要求不能用整个数组覆盖,只能用元素插入的方式来填补,最后两个数组里都有相同的元素（不用管顺序).不改变原来数组里的元素顺序（就是直接把新元素插到后面就好了).
a[n]={1,3,5,7,8,9};
b[n]={1,2,4,5,6,8};
处理后
a[n]={1,3,5,7,8,9,2,4,6}
a[n]={1,2,4,5,6,8,3,7,9}

下一篇：用deviceioctol（)建立usb芯片和主机通信，奇怪的现象
上一篇：一个简单的类型转换问题

其他资讯