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

из 2-х стеков в один - C++

Восстановить пароль Регистрация
 
media_kot
1 / 1 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 11:35     из 2-х стеков в один #1
Подскажите, пожалуйста, есть такая задача:
Дано 2 стека, элементы которых упорядочены по возрастанию. Создать 3-й стек из 2-х заданных в котором элементы тоже упорядочены по возрастанию. Объединять и пересортировывать не допустимо.

С массивами у меня получается, а вот со стеками никак.

Добавлено через 40 минут
язык С++
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2010, 11:35     из 2-х стеков в один
Посмотрите здесь:

C++ Анализ применеия стеков
Разработайте класс стеков C++
C++ Создание нескольких стеков
C++ на основе стеков..... на С++
Конкатенация (присоединение) стеков C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.09.2010, 11:49     из 2-х стеков в один #2
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
#include <iostream>
#include <stack>
 
int main()
{
    std::stack<int> first;
    std::stack<int> second;
    std::stack<int> result;
 
    std::cout << "first stack: ";
    for(int i = 0; i < 5; ++i) {
        std::cout << i << " ";
        first.push(i);
    }
    std::cout << std::endl;
        
    std::cout << "second stack: ";
    for(int i = 0; i < 10; ++i) {
        std::cout << i + 2 << " ";
        second.push(i + 2);
    }
    std::cout << std::endl;
        
    while(!first.empty() && !second.empty()) {
        if(first.top() > second.top()) {
            result.push(first.top());
            first.pop();
        }
        else {
            result.push(second.top());
            second.pop();
        }
    }
    
    while(!first.empty()) {
        result.push(first.top());
        first.pop();
    }
    
    while(!second.empty()) {
        result.push(second.top());
        second.pop();
    }
    
    std::cout << "result stack: ";
    while(!result.empty()) {
        std::cout << result.top() << " ";
        result.pop();
    }
}
media_kot
1 / 1 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 11:49  [ТС]     из 2-х стеков в один #3
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
// Курс.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include "iostream"
#include "time.h"
using namespace std;
 
int main()
{
    setlocale(LC_ALL,"Russian");
 
    typedef struct S1{int a; S1* next;} S1_t; // одно связанный список
 
    typedef struct S2{int b; S2* next;} S2_t; // одно связанный список
 
    typedef struct S3{int c; S3* next;} S3_t; // одно связанный список
 
    //int mass3[20];
    int len1=0, len2=0, len3, size = 0, i = 0,j = 0, n_min;
 
    for(;;){
 
            cout << "Введите количество элементов 1-го массива: ";  //Ввод исходных данных
            cin >> len1; cout<< "\n";
            
            cout << "Введите количество элементов 2-го массива: ";
            cin >> len2; cout<< "\n";
            
            len3=len1+len2;
            srand(time(NULL));  
    
            S1_t *r2=0, *rLast2=0, *rFirst=0;
 
              //построение списка
 
              for(int i=0;i<len1;i++)
              {
                r2=(S1_t *)malloc(sizeof(S1_t));
                memset(r2,0,sizeof(S1_t));
                r2->a=i*3;
                if(rLast2)
                   rLast2->next=r2;
                else
                   rFirst=r2;
                rLast2=r2;
 }
               r2=rFirst;
               while(r2){
                   cout << r2->a; cout << "\n";
                   r2=r2->next;
               }
 
               cout << "\n";
 
 
 
            S2_t *p2=0, *plast2=0, *pfirst=0;
 
              //построение списка
 
              for(int i=0;i<len2;i++)
              {
                p2=(S2_t *)malloc(sizeof(S2_t));
                memset(p2,0,sizeof(S2_t));
                p2->b=i*2;
                if(plast2)
                   plast2->next=p2;
                else
                   pfirst=p2;
                plast2=p2;
 }
               p2=pfirst;
               while(p2){
                   cout << p2->b; cout << "\n" ;
                   p2=p2->next;
               }
               r2=rFirst;
               p2=pfirst;
 
               cout <<"\n\n\n"; //cout  << p2->b;
 
              S3_t *k2=0, *kLast2=0, *kFirst=0;
 
              
               while ( i<len1 && j<len2 )   // В цикле while происходит создание обьединнёного массива m3 и упорядочивание его по возрастанию.
            {
                n_min = min( r2->a, p2->b );
                k2=(S3_t *)malloc(sizeof(S3_t));
                memset(k2,0,sizeof(S3_t));
                k2->c = n_min; 
                if(kLast2)kLast2->next=k2;
                else kFirst=k2;
                kLast2=k2;
                //cout  << n_min << "\n" ;
                // cout  <<  rLast2->next<< "\n";
                if(r2->a < p2->b){ 
                    i++;
                 r2=r2->next;
                }
                else{ 
                    j++;
                 p2=p2->next;
                }
 
            }
            while( i<len1 )k2->c = r2->a;
            while ( j<len2 )k2->c = p2->b;
 
 
            k2=kFirst;
               while(k2){
                   cout << k2->c; cout << "\n" ;
                   k2=k2->next;
               }
    }
    return 0;
}
Вот что получилось у меня, стеки создать могу, а вот в третий слить не получается.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.09.2010, 11:57     из 2-х стеков в один #4
media_kot, а стек упорядоченный по возрастанию это когда верхушка равна наибольшему или корень?
media_kot
1 / 1 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 11:58  [ТС]     из 2-х стеков в один #5
Наверное всё таки корень
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.09.2010, 12:00     из 2-х стеков в один #6
и вам нужна именно собственная реализация стека? то есть без STL?
media_kot
1 / 1 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 12:01  [ТС]     из 2-х стеков в один #7
Да нет, спасибо вам за помощь. Если есть стандартные функции зачем изобретать велосипед. Просто ещё мало знаю
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2010, 12:15     из 2-х стеков в один
Еще ссылки по теме:

C++ Передача стеков
C++ Сравнение элементов стеков
Реализация k-стеков C++

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

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.09.2010, 12:15     из 2-х стеков в один #8
Цитата Сообщение от media_kot Посмотреть сообщение
Да нет, спасибо вам за помощь. Если есть стандартные функции зачем изобретать велосипед. Просто ещё мало знаю
Тогда в моем варианте немного не то, что Вам требуется.
В моем варианте исходные стеки имеют наибольший элемент в верхушке. А в результирующем стеке верхушка это наименьший элемент. Изменить несложно.

Вот исправленный вариант с комментариями, если захотите привертеть собственную реализацию, то алгоритм останется таким же.

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
#include <iostream>
#include <stack>
 
int main()
{
    std::stack<int> first;
    std::stack<int> second;
    std::stack<int> result;
    std::stack<int> tmp;
 
    // заполняем первый стек так, чтобы корень был максимальным
    for(int i = 5; i >= 0; --i) {
        first.push(i);
    }
           
    // заполняем второй стек также 
    for(int i = 10; i >= 0; --i) {
        second.push(i + 2);
    }
 
    // переносим элементы в обратном порядке во временный стек
    // пока один из стеков не опустеет
    while(!first.empty() && !second.empty()) {
        if(first.top() < second.top()) {
            tmp.push(first.top());
            first.pop();
        }
        else {
            tmp.push(second.top());
            second.pop();
        }
    }
    
    // переносим оставшиееся элементы из стека
    // так как мы не знаем, в каком стеке еще остались записи, то
    // копируем как бы из обоих (при этом один стек точно уже пустой)
    while(!first.empty()) {
        tmp.push(first.top());
        first.pop();
    }
    
    while(!second.empty()) {
        tmp.push(second.top());
        second.pop();
    }
    
    // чтобы сохранить правильный порядок в результирующем стеке
    // переносим все элементы в новый стек
    // производится как бы реверс стека
    while(!tmp.empty()) {
        result.push(tmp.top());
        tmp.pop();
    }
    
    // вывод результата
    std::cout << "result stack: ";
    while(!result.empty()) {
        std::cout << result.top() << " ";
        result.pop();
    }
}
Yandex
Объявления
12.09.2010, 12:15     из 2-х стеков в один
Ответ Создать тему
Опции темы

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