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

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

Восстановить пароль Регистрация
 
Yuralug
1 / 1 / 0
Регистрация: 19.11.2014
Сообщений: 22
13.07.2015, 16:11     Упорядочить два списка и произвести их слияние #1
Нужно создать 2 списка L1 и L2. В списке числа упорядочить. Потом провести слияние списков и снова упорядочить конечный список.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние #5
Kuzia domovenok, Код, делает ровно то, что указано в посте ТСа. Не написано ничего, про написание списка и так далее. Зачем мне придумывать себе задание на список?
Yandex
Объявления
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние
Ответ Создать тему
Опции темы

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