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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ss-20
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 25
#1

Слить два линейных списка, сохранив сортировку по возрастанию - C++

04.02.2013, 23:52. Просмотров 851. Ответов 4
Метки нет (Все метки)

лучше через стандартные, только начали изучать.

Есть 2 лин.списка, где эл-ты по возрастанию, нужно их слить в один, чтобы эл-ты шли по возрастанию.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2013, 23:52     Слить два линейных списка, сохранив сортировку по возрастанию
Посмотрите здесь:
Нужен листинг на С++ (даны два вектора, упорядоченные по возрастанию. Слить их в один вектор, так чтобы сохранилась упорядоченность) C++
C++ Создать два линейных списка, во второй перенести элементы первого, которые >100, а в первом их удалить
Описать функцию, которая объединяет два упорядоченных по возрастанию списка в один C++
C++ Слить два упорядоченных массива в третий
Даны два упорядоченных массива. Слить их в третий, но чтобы элементы не повторялись C++
C++ Найти сортировку по возрастанию
Реализовать сортировку по возрастанию и убыванию C++
Сделать сортировку строк по сумме элементов по возрастанию C++
Выполнить сортировку каждого столбца матрицы по возрастанию C++
C++ Провести сортировку по возрастанию отрицательных чисел в нечетных строках
Выполнить сортировку элементов в каждой строке матрицы по возрастанию C++
C++ Два линейных массива

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
05.02.2013, 00:29     Слить два линейных списка, сохранив сортировку по возрастанию #2
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
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <list>
#include <string>
 
typedef std::list<int> List;
 
void FillList(List& lst)
{
    lst.push_back(3);
    lst.push_back(2);
    lst.push_back(1);
}
 
void PrintList(const List& lst, const std::string& info)
{
    std::cout << info << ": ";
    for (List::const_iterator it = lst.begin(), end = lst.end(); it != end; ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}
 
int main()
{
    List lst1;
    List lst2;
 
    FillList(lst1);
    FillList(lst2);
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "sorting..." << std::endl;
 
    lst1.sort();
    lst2.sort();
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "splicing..." << std::endl;
 
    lst1.splice(lst1.end(), lst2);
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "sorting..." << std::endl;
 
    lst1.sort();
    lst2.sort();
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
    return 0;
}
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
05.02.2013, 00:53     Слить два линейных списка, сохранив сортировку по возрастанию #3
Цитата Сообщение от DU Посмотреть сообщение
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
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <list>
#include <string>
 
typedef std::list<int> List;
 
void FillList(List& lst)
{
    lst.push_back(3);
    lst.push_back(2);
    lst.push_back(1);
}
 
void PrintList(const List& lst, const std::string& info)
{
    std::cout << info << ": ";
    for (List::const_iterator it = lst.begin(), end = lst.end(); it != end; ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}
 
int main()
{
    List lst1;
    List lst2;
 
    FillList(lst1);
    FillList(lst2);
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "sorting..." << std::endl;
 
    lst1.sort();
    lst2.sort();
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "splicing..." << std::endl;
 
    lst1.splice(lst1.end(), lst2);
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "sorting..." << std::endl;
 
    lst1.sort();
    lst2.sort();
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
    return 0;
}
зачем сортировать, если исходный списки уже отсортированы по условию, не спроста же это?
вчера делал аналогичную задачу для массивов:
Из двух массивов чисел образовать третий, и сортировать числа в порядке невозрастания
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
05.02.2013, 08:38     Слить два линейных списка, сохранив сортировку по возрастанию #4
По-буржуйски это действие называется merge. Есть даже стандартная функция в STL.

Велосипед, используя стандартные функции (стандарт C++98, ISO/IEC 14882):
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
56
57
58
59
60
61
62
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
 
// сливает два упорядоченных по возрастанию массива
template <class InputIterator, class OutputIterator>
OutputIterator merge(InputIterator beginA, InputIterator endA, 
  InputIterator beginB, InputIterator endB, OutputIterator inserter) {
  while (true) {
    *inserter++ = (*beginA < *beginB) ? *beginA++ : *beginB++;
    if (beginA == endA) {
      // тут можно return std::copy(beginB, endB, inserter);
      while (beginB != endB) *inserter++ = *beginB++;
      return inserter;
    }
    if (beginB == endB) {
      // тут можно return std::copy(beginA, endA, inserter);
      while (beginA != endA) *inserter++ = *beginA++;
      return inserter;
    }
  }
  return inserter;
};
 
int main(int argc, char **argv) { 
  srand(time(0));
  
  // рандомно генерируются два массива
  int aSize = 10 + rand() % 10;
  int *a = new int[aSize];
  for (int i = 0; i < aSize; ++i) a[i] = rand() % 20;
 
  int bSize = 10 + rand() % 10;
  int *b = new int[bSize];
  for (int i = 0; i < aSize; ++i) b[i] = rand() % 20;
 
  // сортируются
  std::sort(a, a + aSize);
  std::sort(b, b + bSize);
  
  // выводятся на экран
  std::copy(a, a + aSize, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  std::copy(b, b + bSize, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  
  // создается третий массив, в котором будет храниться результат
  int *c = new int[aSize + bSize];
  // слияние
  merge(a, a + aSize, b, b + bSize, c);
  // вывод результата
  std::copy(c, c + aSize + bSize, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  
  delete [] a;
  delete [] b;
  delete [] c;
  return 0;
};
ss-20
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 25
20.02.2013, 00:50  [ТС]     Слить два линейных списка, сохранив сортировку по возрастанию #5
спасибо!!
Yandex
Объявления
20.02.2013, 00:50     Слить два линейных списка, сохранив сортировку по возрастанию
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru