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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как подтверждать свои знания при устройстве на работу? http://www.cyberforum.ru/cpp-beginners/thread1498228.html
Добрый день! Вопрос к тем кто уже работает программистами или кем-то другим. Как вы подтверждали свои знания С++ при устройстве на работу? Потому обычно у человека , закончившего институт есть какой-то общий диплом, а программисты - это люди, которые,как правило, учатся самостоятельно.
C++ Как мне инициализировать данные в конструкторе //Файл содержит определение функций класса Invoice #include <iostream> using std::cout; using std::endl; #include <string> using std::string; #include "Invoice.h" http://www.cyberforum.ru/cpp-beginners/thread1498203.html
Вызов функции в параметре другой функции C++
программа: #include <iostream> using namespace std; struct E { E() {} }; void f(const E& e)
C++ Программа для поиска файлов
Ребят хочу вылезти из типичных примеров в книгах и написать прогу для поиска файлов хоть бы самую приметивную. Ища в нэте ничего толкового не нашел. Мог бы кто-то объяснить словами как это выглядит и по возможности хоть несколько строк кода черкануть. Спасибо :friends:
C++ Идентификаторы интерфейсов http://www.cyberforum.ru/cpp-beginners/thread1498061.html
Есть код что он означает static const IID IID_IMotion= {0x692d03a4,0xc689,0x11ce,{0xb3,0x37,0x88,0xae,0x36,0xde,0x9e,0x4e}}; //{692D0eA5-C689-11CE-B337-88EA36DE9E4E} static const IID IID_IVisual= {0x692d03a5,0xc689,0x11ce,{0xb3,0x37,0x88,0xea,0x36,0xde,0x9e,0x4e}}; Что они означают? Это заполняется какими то числами структура И идентификаторы интерфейсов получаются и зачем они нужны?
C++ Книга по алгоритмам и структурам данных на С++ или на Си Здравствуйте, форумчане. Посоветуйте книгу по алгоритмам и структурам данных на С++ или на Си. подробнее

Показать сообщение отдельно
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
13.07.2015, 19:15     Упорядочить два списка и произвести их слияние
Цитата Сообщение от 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;
}
Результат работы кода
 
Текущее время: 06:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru