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

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

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

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

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

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

Написать функцию, которая из списка образует два новых списка. Один содержит нечетные числа, а второй - парные - C++
Помогите закончить одно из заданий по работе со списком: Написать функцию, которая использует первоначальный список L и образует два...

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

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

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

Построить класс для работы с односвязным списком. Создать два списка: List1 и List2. Проверить, содержатся ли элементы списка List1 в списке List2 в у - C++
Построить класс для работы с односвязным списком. Создать два списка: List1 и List2. Проверить, содержатся ли элементы списка List1 в...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 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;
}
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
13.07.2015, 19:04 #3
ForEveR, а смысл данного кода? поупражняться в знании английского языка? В том что знаешь, что merge это "слияние", а sort это "упорядочить"? Может лучше потрудишься алгоритм расписать, который продемонстрирует твоё знание списков и указателей?
0
Геомеханик
622 / 429 / 310
Регистрация: 26.06.2015
Сообщений: 968
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;
}
Результат работы кода
2
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
14.07.2015, 00:13 #5
Kuzia domovenok, Код, делает ровно то, что указано в посте ТСа. Не написано ничего, про написание списка и так далее. Зачем мне придумывать себе задание на список?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2015, 00:13
Привет! Вот еще темы с ответами:

Даны два одномерные массивы 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++
создать односвязный линейный список чисел. Методом вставки упорядочить список по возрастанию и удалить из отсортированного списка все...

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.07.2015, 00:13
Ответ Создать тему
Опции темы

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