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

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

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

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

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

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

Упорядочить элементы списка по возрастанию - C++
Линейный односвязный список.Узел списка-целое число.Упорядочить элементы списка по возрастанию...Помогите пжлст кто сможет

Из списка фамилий упорядочить их по алфавиту - C++
Из списка фамилий упорядочить их по алфавиту проверить написание большой буквы Добавлено через 5 минут помогите плс...мучаюсь...

Упорядочить по возрастанию только: положительные элементы списка - C++
Упорядочить по возрастанию только: положительные элементы списка

Отсортировать в отдельный список игрушки и упорядочить оба списка по алфавиту - C++
Нужна помощь. Задача: создать циклический однонаправленный список, включающий в себя имена предметов и типы предметов( 2 инф. поля)...

Даны два одномерные массивы A (a [1], a [2], ..., a [n]) и B (b [1], b [2], ..., b [m]), размеры равны n и m . Упорядочить их указанными методами - C++
Даны два одномерные массивы A (a , a , ..., a ) и B (b , b , ..., b ), размеры которых равны n и m соответственно. Упорядочить их...

Методом вставки упорядочить список по возрастанию и удалить из отсортированного списка положительные элементы - C++
создать односвязный линейный список чисел. Методом вставки упорядочить список по возрастанию и удалить из отсортированного списка все...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
13.07.2015, 19:04     Упорядочить два списка и произвести их слияние #3
ForEveR, а смысл данного кода? поупражняться в знании английского языка? В том что знаешь, что merge это "слияние", а sort это "упорядочить"? Может лучше потрудишься алгоритм расписать, который продемонстрирует твоё знание списков и указателей?
Геомеханик
584 / 391 / 288
Регистрация: 26.06.2015
Сообщений: 884
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;
}
Результат работы кода
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние
Еще ссылки по теме:

Два двусвязных списка - C++
Здравствуйте. Подайте хотя бы идею на задание: Даны два двусвязных списка. Сформировать новый двусвязный список из элементов, входящих...

Упорядочить массив вещественных чисел по убыванию модулей элементов и найти два числа по условию - C++
Программа была написана для другой похожей задачи, помогите подстроить под следующие условия. &quot;В одномерном массиве, состоящем из n...

Список преобразовать в два списка - C++
Всем привет! Помогите список преобразовать в два списка. Первый должен содержать только положительные числа, а второй – только...

Сформировать два списка из элементов исходного - C++
Ребята, нужна функция для реализации такой вот задачки: Создается линейный список L, из него нужно составить два списка L1 и L2, по...


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

Или воспользуйтесь поиском по форуму:
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние #5
Kuzia domovenok, Код, делает ровно то, что указано в посте ТСа. Не написано ничего, про написание списка и так далее. Зачем мне придумывать себе задание на список?
Yandex
Объявления
14.07.2015, 00:13     Упорядочить два списка и произвести их слияние
Ответ Создать тему
Опции темы

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