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

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

Войти
Регистрация
Восстановить пароль
 
Yuralug
1 / 1 / 0
Регистрация: 19.11.2014
Сообщений: 22
#1

Упорядочить два списка и произвести их слияние - C++

13.07.2015, 16:11. Просмотров 240. Ответов 4
Метки нет (Все метки)

Нужно создать 2 списка L1 и L2. В списке числа упорядочить. Потом провести слияние списков и снова упорядочить конечный список.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2015, 16:11     Упорядочить два списка и произвести их слияние
Посмотрите здесь:

C++ Из списка фамилий упорядочить их по алфавиту
C++ Построить класс для работы с односвязным списком. Создать два списка: List1 и List2. Проверить, содержатся ли элементы списка List1 в списке List2 в у
Два двусвязных списка C++
Упорядочить элементы списка по возрастанию C++
Список преобразовать в два списка C++
C++ Даны два одномерные массивы A (a [1], a [2], ..., a [n]) и B (b [1], b [2], ..., b [m]), размеры равны n и m . Упорядочить их указанными методами
Методом вставки упорядочить список по возрастанию и удалить из отсортированного списка положительные элементы C++
C++ Упорядочить массив вещественных чисел по убыванию модулей элементов и найти два числа по условию
C++ Написать функцию, которая из списка образует два новых списка. Один содержит нечетные числа, а второй - парные
C++ Упорядочить по возрастанию только: положительные элементы списка
C++ Отсортировать в отдельный список игрушки и упорядочить оба списка по алфавиту
Два значения в одном элементе списка C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.07.2015, 16:44     Упорядочить два списка и произвести их слияние #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <list>
#include <iostream>
#include <algorithm>
#include <iterator>
 
int main()
{
   std::list<int> l1 = {3,4,1,5,2,6};
   std::list<int> l2 = {10,8,9,0,7};
   l1.sort();
   l2.sort();
   l1.merge(l2);
   std::copy(l1.begin(), l1.end(), std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1886 / 1741 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
13.07.2015, 19:04     Упорядочить два списка и произвести их слияние #3
ForEveR, а смысл данного кода? поупражняться в знании английского языка? В том что знаешь, что merge это "слияние", а sort это "упорядочить"? Может лучше потрудишься алгоритм расписать, который продемонстрирует твоё знание списков и указателей?
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
13.07.2015, 19:15     Упорядочить два списка и произвести их слияние #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Yuralug Посмотреть сообщение
и снова упорядочить конечный список.
Не стоит упорядочивать уже упорядоченное множество, так как после слияние упорядоченных списков упорядоченность сохранится.

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <cstdlib>
 
struct node {
    int   num;
    node* next;
};
 
struct slist {
    node* head;
    node* tail;
    slist(void):head(NULL), tail(NULL){}
};
 
bool slist_add(slist* lst, int num);
void slist_clear(slist* lst);
 
 
//сортировка односвязного списка слиянием
void slist_sort(node*& head, node*& tail) {
    if((head == NULL) || (head->next == NULL))
        return;
 
    node* ptr, *next, *end, *pos;
    node* iter = head;
    node* last = head;
 
    ptr = next = end = NULL;
    pos = head;
    while((pos != NULL) && (pos->next != NULL)){
        last = iter;
        iter = iter->next;
        pos  = pos->next->next;
    }
    last->next = NULL;
    
    slist_sort(head, tail);
    slist_sort(iter, tail);
 
    while((head != NULL) || (iter != NULL)) {
        if(iter == NULL) {
            next = head;
            head = head->next;
        } else if(head == NULL) {
            next = iter;
            iter = iter->next;
        } else if(head->num < iter->num) {
            next = head;
            head = head->next;
        } else {
            next = iter;
            iter = iter->next;
        }
 
        if(ptr == NULL) 
            ptr = next;
        else
            end->next = next;
        end = next;
    }
    head = ptr;
    tail = end;
}
 
 
//слияние списков
void slist_union(slist* l3, slist* l1, slist* l2){
    node*  p1 = l1->head;
    node*  p2 = l2->head; 
    node** r3 = &l3->head;
 
    while((p1 != NULL) && (p2 != NULL)){
        if(p1->num < p2->num){
            *r3 = p1;
            p1  = p1->next;
        } else {
            if(p1->num == p2->num){
                *r3 = p1;
                p1  = p1->next;
                r3  = &(*r3)->next;
            }
            *r3 = p2;
            p2  = p2->next;
        }
        r3 = &(*r3)->next;
    }
 
    if(p1 != NULL){
        *r3      = p1;
        l3->tail = l1->tail; 
    } else {
        *r3      = p2;
        l3->tail = l2->tail;
    }
    l1->head = l1->tail =
    l2->head = l2->tail = NULL;
}
 
 
int main(void){
    slist l1;
    for(int i = 0; i < 10; ++i)
        slist_add(&l1, std::rand() % 10);
 
    slist l2;
    for(int j = 0; j < 20; ++j)
        slist_add(&l2, std::rand() % 20);       
 
    //сортируем списки
    slist_sort(l1.head, l1.tail);
    slist_sort(l2.head, l2.tail);
 
    slist l3;
    slist_union(&l3, &l1, &l2);
 
    const node* p = l3.head;
    while(p != NULL){
        std::cout << p->num << ' ';
        p = p->next;
    }
    slist_clear(&l3);
    return 0;
}
 
//вставка в конец списка
bool slist_add(slist* lst, int num){
    node* ptr = new (std::nothrow) node();
    if(ptr != NULL){
        ptr->num  = num;
        ptr->next = NULL;
        if(lst->head == NULL)
            lst->head = lst->tail = ptr;
        else {
            lst->tail->next = ptr;
            lst->tail = ptr;
        }
    }
    return (ptr != NULL);
}
 
//удаление списка
void slist_clear(slist* lst){
    node* tmp;
    while(lst->head != NULL){
        tmp       = lst->head;
        lst->head = lst->head->next;
        delete tmp;
    }
    lst->tail = NULL;
}
Результат работы кода
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние #5
Kuzia domovenok, Код, делает ровно то, что указано в посте ТСа. Не написано ничего, про написание списка и так далее. Зачем мне придумывать себе задание на список?
Yandex
Объявления
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние
Ответ Создать тему
Опции темы

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