Форум программистов, компьютерный форум CyberForum.ru

Слияние двух отсортированых массивов в один - C++

Восстановить пароль Регистрация
 
Vasiliy43
Заблокирован
25.06.2013, 14:48     Слияние двух отсортированых массивов в один #1
задание: Задано два массива. Массив А состоит из N элементов и отсортированный по увеличению . Массив В состоит из N элементов и отсортированный по уменьшению. Разработать программу для слияния этих массивов в отсортированный по уменьшению массив С который не имеет одинаковых элементов.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
25.06.2013, 15:01     Слияние двух отсортированых массивов в один #2
std::sort + std::merge + std::unique
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
25.06.2013, 15:28     Слияние двух отсортированых массивов в один #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
const int NA = 5;
const int NB = 7;
const int NC = 12;
 
void Merge(int *a, int na, int *b, int nb, int *c, int &nc)
{
   int i = na - 1, j = 0, k = 0;
   if (a[i] > b[j])
      c[k++] = a[i--];
   else c[k++] = b[j++];
   while (i >= 0 && j < nb)
      if (a[i] == c[k - 1])
         --i;
      else if (b[j] == c[k - 1])
         j++;
      else if (a[i] > b[j])
         c[k++] = a[i--];
      else
         c[k++] = b[j++];
   if (j == nb)
   {
      for(j = i; j >= 0; --j)
         if (a[j] != c[k])
            c[k++] = a[j];
   }
   else
   {
      for(i = j; i < nb; ++i)
         if (b[i] != c[k - 1])
            c[k++] = b[i];
   }
   nc = k;
}
 
void Print(int *a, int n)
{
   for(int i = 0; i < n; ++i)
      std::cout << a[i] << " ";
   std::cout << std::endl;      
}
 
int main()
{
   int a[NA] = {1, 2, 2, 3, 3}, b[NC] = {10, 10, 7, 7, 7, 1 ,1}, c[NC], nc;
   Print(a, NA);    
   Print(b, NB);
   Merge(a, NA, b, NB, c, nc);  
   Print(c, nc);    
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
25.06.2013, 15:36     Слияние двух отсортированых массивов в один #4
А вот мой вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iterator>
 
int main() {
    
    const int N = 5;
 
    int a[N] = { 1,2,3,4,9 };
    int b[N] = { 8,7,6,5,4 };
 
    std::vector<int> c;
 
    int* ai = &a[N-1];
    int* bi = &b[0];
 
    while( ai != &a[-1] && bi != &b[N] )
    {
        if( *ai == *bi )
        {
            c.push_back( *ai );
            ai--;
            bi++;
        }
        else if( *ai < *bi )
        {
            c.push_back( *bi );
            bi++;
        }
        else
        {
            c.push_back( *ai );
            ai--;
        }
    }
 
    while( ai != &a[-1] )
    {
        c.push_back( *ai );
        ai--;       
    }
 
    while( bi != &b[N] )
    {
        c.push_back( *bi );
        bi++;
    }
 
    std::copy( c.begin(), c.end(), std::ostream_iterator<int>( std::cout, " " ) );
 
    std::system( "pause" );
    return 0;
}
P.S. Правда у меня не допускаются дубли в исходных массивах.
ViktorKozlov
133 / 125 / 2
Регистрация: 13.12.2012
Сообщений: 293
25.06.2013, 15:42     Слияние двух отсортированых массивов в один #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using std::cout;
using std::endl;
#include <iomanip>
using std::setw;
 
const int N1=8, N2=10;
 
int main()
{
    short arr1[N1]={-7,-5,-5,-5,-3,0,0,7};
    short arr2[N2]={9,8,7,6,4,4,4,4,-5,-5};
    short arr3[N1+N2];
 
    int count1=N1-1,count2=0,count3=0;
    while (count1>=0 && count2<N2)
    {
        if (arr1[count1]>arr2[count2])
            arr3[count3++]=arr1[count1--];
        else
            arr3[count3++]=arr2[count2++];
        if (count3>=2 && arr3[count3-1]==arr3[count3-2])
            count3--;
    }
    if (!(count1>=0))
        for (int i=count2;i<N2;i++)
            if (count3>0 && arr3[count3-1]!=arr1[i])
            arr3[count3++]=arr2[i];
    if (!(count2<N2))
        for (int i=count1;i>=0;i--)
            if (count3>0 && arr3[count3-1]!=arr1[i])
                arr3[count3++]=arr1[i];
 
    for (int i=0;i<count3;i++)
        cout<<setw(3)<<arr3[i];
    cout<<endl;
}
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
25.06.2013, 16:50     Слияние двух отсортированых массивов в один #6
можно залить в std::set, оно сразу откинет повторения и хранится там все в сортированном виде
Yandex
Объявления
25.06.2013, 16:50     Слияние двух отсортированых массивов в один
Ответ Создать тему
Опции темы

Текущее время: 05:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru