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

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

Войти
Регистрация
Восстановить пароль
 
media_kot
2 / 2 / 0
Регистрация: 12.09.2010
Сообщений: 35
#1

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

12.09.2010, 11:35. Просмотров 613. Ответов 7
Метки нет (Все метки)

Подскажите, пожалуйста, есть такая задача:
Дано 2 стека, элементы которых упорядочены по возрастанию. Создать 3-й стек из 2-х заданных в котором элементы тоже упорядочены по возрастанию. Объединять и пересортировывать не допустимо.

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

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

Из двух стеков в один - C++
Привет всем!) У меня есть вто такое задание : Using C++ functions written during the class, write C++ program that creates stacks A, B,...

Передача стеков - C++
Немного глупый вопрос, но всё же. Как нужно переписывать стек в стек? Т.е. у меня есть 2 стека. к примеру в стеке с именем Stack1 будет...

Реализация k-стеков - C++
Добрый день! Никак не могу найти информацию по реализации k-стеков. Задача состоит в следующем: 1. описать объектовый тип стек и взять...

на основе стеков..... на С++ - C++
Всем привет!!! Нужна ваша помощь.... Проверить в выражении баланс скобок «(« и «)«.

Анализ применеия стеков - C++
Уважаемые, более опытные коллеги, прошу помочь по такому вопросу мне нужно сделать анализ по приминению стеков, тоесть где...

Шаблон для стеков - C++
Нужно написать шаблонный класс для работы со стеком элементов типа T. Я делаю так, чтобы в классе была структура Element, которая содержит...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
fasked
Эксперт С++
4934 / 2514 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.09.2010, 11:49 #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
2 / 2 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 11:49  [ТС] #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
Эксперт С++
4934 / 2514 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.09.2010, 11:57 #4
media_kot, а стек упорядоченный по возрастанию это когда верхушка равна наибольшему или корень?
media_kot
2 / 2 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 11:58  [ТС] #5
Наверное всё таки корень
fasked
Эксперт С++
4934 / 2514 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.09.2010, 12:00 #6
и вам нужна именно собственная реализация стека? то есть без STL?
media_kot
2 / 2 / 0
Регистрация: 12.09.2010
Сообщений: 35
12.09.2010, 12:01  [ТС] #7
Да нет, спасибо вам за помощь. Если есть стандартные функции зачем изобретать велосипед. Просто ещё мало знаю
fasked
Эксперт С++
4934 / 2514 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.09.2010, 12:15 #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();
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2010, 12:15
Привет! Вот еще темы с ответами:

Конкатенация (присоединение) стеков - C++
Привет всем, я имею код конкатинации (присоединения) строки в другую строку. Мне нужно его переделать не для строки а для стека!!! И все,...

Сравнение элементов стеков - C++
Даны два стека. Задача состоит в том, чтобы создать третий стек из элементов первого, которых нет во втором. Не могу найти ошибку,...

Разработайте класс стеков - C++
Разработайте класс стеков для хранения символов с реализацией в виде массива. Создать стек и заполнить его произвольными символами ...

Создание нескольких стеков - C++
//--------------------------------------------------------------------------- #pragma hdrstop #include &lt;tchar.h&gt; #include...


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

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

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