用c++实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中（假设这两个有序顺序表中没有相同的元素）。 - 编程论坛

#2

rjsp2016-09-02 22:53

std::set_union

#3

yangfrancis2016-09-02 23:53

#include<iostream>
#include<algorithm>
using namespace std;
bool compare(short x,short y)
{return x<y;}
class List
{
private:
    short num;
public:
    short*factor;
    short GetLength(){return num;}
    void Input()
    {
        short i;
        for(i=0;i<num;i++)
        {
            cin>>factor[i];
        }
        sort(factor,factor+num,compare);
    }
    List(short n)
    {
        num=n;
        factor=new short[n];
        for(short i=0;i<n;i++)
            factor[i]=0;
    }
    ~List(){delete factor;factor=NULL;}
    void Show()
    {
        for(short i=0;i<num;i++)
            cout<<factor[i];
    }
    void Add(List&lt)
    {
        short i;short*p;p=factor+num;
        p=new short[lt.GetLength()];
        for(i=num;i<(num+lt.GetLength());i++)
        {
            factor[i]=lt.factor[i-GetLength()];
        }
        num=num+lt.GetLength();
        sort(factor,factor+num,compare);
    }
};
int main()
{
    List l(3);
    l.Input();
    l.Show();
    cout<<endl;
    List t(3);
    t.Input();
    l.Add(t);
    l.Show();
    return 0;
}

#4

令狐少侠562016-09-04 14:38

/将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

#5

rjsp2016-09-05 08:35

如果不需要去重，则使用 std::merge

程序代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main( void )
{
    vector<int> a = { 0, 1, 3, 4, 7, 9 };
    vector<int> b = { 0, 2, 5, 6, 8, 9 };

    vector<int> tmp( a.size()+b.size() );
    merge( a.begin(), a.end(), b.begin(), b.end(), tmp.begin() );
    swap( a, tmp );

    copy( a.begin(), a.end(), std::ostream_iterator<int>(cout,", ") );
}

输出
0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9,

如果需要去重，则使用 set_union

程序代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main( void )
{
    vector<int> a = { 0, 1, 3, 4, 7, 9 };
    vector<int> b = { 0, 2, 5, 6, 8, 9 };

    vector<int> tmp;
    tmp.reserve( a.size()+b.size() );
    std::set_union( a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(tmp) );
    swap( a, tmp );

    copy( a.begin(), a.end(), std::ostream_iterator<int>(cout,", ") );
}

输出
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,