1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
1

Слияние двух стеков

09.06.2015, 22:03. Показов 2057. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день. В задаче нужно слить два отсортированных стека, так чтобы получился новый третий отсортированный стек. Не особо разобрался в стеках. Буду рад помощи.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.06.2015, 22:03
Ответы с готовыми решениями:

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

Сравнение двух стеков (Equal)
Нужно осуществить проверку равенства (Equal) двух стеков. Осуществил проверку подобия (Similar),а...

Слияние двух файлов
Здравствуйте. В папке есть два тхт файла, как мне их соединить и записать в третий и в третьем...

Слияние двух матрицы
Программисты,помогите пожалуйста решить задачу 10 класса) Заданы две матрицы А и В размером...

6
13104 / 5885 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
11.06.2015, 00:09 2
Лучший ответ Сообщение было отмечено Ovenvan как решение

Решение

Цитата Сообщение от Ovenvan Посмотреть сообщение
В задаче нужно слить два отсортированных стека, так чтобы получился новый третий отсортированный стек.
Решение в виде консольного приложения. Там я ещё реализовал сортировку стека, хотя по заданию это не требуется. Если сортировка не нужна, то можно убрать её. Но тогда элементы в исходные стеки надо изначально добавлять в упорядоченном виде.
Delphi
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
program Project1;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils, Windows;
 
type
  //Тип основных данных.
  TData = Integer;
  //Тип указателя на элемент стека.
  TPElem = ^TElem;
  //Элемент стека.
  TElem = record
    Data : TData;   //Основные данные.
    PNext : TPElem; //Указатель на следующий элемент.
  end;
 
//Добавление элемента на вершину стека.
procedure Push(var aPSt : TPElem; const aData : TData);
var
  P : TPElem;
begin
  New(P);
  P^.Data := aData;
  P^.PNext := aPSt;
  aPSt := P;
end;
 
{Изъятие элемента с вершины стека.
Если стек не пуст, то с вершины стека изымается элемент и его данные возвращаются
через параметр aData. В этом случае функция возвращает значение True.
Если стек пуст, то операция отменяется, а функция возвращает значение False.}
function Pop(var aPSt : TPElem; var aData : TData) : Boolean;
var
  P : TPElem;
begin
  Result := False;
  if aPSt <> nil then
  begin
    P := aPSt;           //Указатель на исключаемый элемент.
    aPSt := aPSt^.PNext; //Исключаем элемент из стека.
    aData := P^.Data;    //Возвращаем данные искючённого элемента.
    Dispose(P);          //Освобождение памяти, занятой для исключённого элемента.
    Result := True;      //Отмечаем, что действие выполнено.
  end;
end;
 
//Освобождение памяти, занятой для элементов стека (очистка стека).
procedure StFree(var aPSt : TPElem);
var
  Data : TData;
begin
  while Pop(aPSt, Data) do;
end;
 
//Распечатка стека.
procedure StWriteln(aPSt : TPElem);
begin
  if aPSt = nil then
    Write('Стек пуст.')
  else
  repeat
    Write(aPSt^.Data:3);
    aPSt := aPSt^.PNext;
  until aPSt = nil;
  Writeln;
end;
 
{Сортировка стека по возрастанию в направлении вершина-дно (на вершине - меньшие, у дна - бОльшие).
Метод сортировки - сортировка вставками.}
procedure SortAsc(var aPSt : TPElem);
var
  PStSort, PStTmp : TPElem;
  D, Dt : TData;
begin
  //Начальная инициализация вспомогательных стеков.
  PStSort := nil; //Обратно-сортированный стек (на вершине - бОльшие, у дна - меньшие).
  PStTmp := nil;  //Вспомогательный стек.
  //Сортировка.
  while Pop(aPSt, Dt) do     //Берём с вершины входного стека элемент Dt.
  begin
    //Подбираем место вставки элемента Dt в обратно-сортированном стеке.
    while Pop(PStSort, D) do //Берём с вершины обратно-сортированного стека элемент D.
      if  D <= Dt then       //Если по обратному правилу элемент D должен лежать ниже элемента Dt.
      begin
        Push(PStSort, D);    //Возвращаем элемент D в обратно-сортированный стек.
        Break;               //Прерываем цикл поиска.
      end
      else                   //Иначе, если по обратному правилу элемент Dt должен лежать ниже элемента D.
        Push(PStTmp, D);     //Помещаем элемент D во вспомогательный стек.
    //Помещаем в обратно-сортированный стек элемент Dt.
    Push(PStSort, Dt);
    //Возвращаем элементы из вспомогательного стека в обратно-сортированный стек.
    while Pop(PStTmp, D) do
      Push(PStSort, D);
  end;
  {Переписываем элементы из обратно-сортированного стека во входной стек. При этом порядок
  элементов поменяется на обратный и, соответственно, сортировка поменяется на обратную.}
  while Pop(PStSort, D) do
    Push(aPSt, D);
end;
 
{Слияние двух стеков, отсортированных по возрастанию в направлении вершина-дно
(на вершине - меньшие, у дна - бОльшие).}
procedure MergeAsc(var aPSt1, aPSt2, aPStMerge : TPElem);
var
  PStSort : TPElem;
  D1, D2 : TData;
begin
  StFree(aPStMerge); //Освобождаем память, занятую для элементов выходного стека.
  PStSort := nil;    //Инициализируем обратно-сортированный стек (на вершине - бОльшие, у дна - меньшие).
  //Слияние.
  while Pop(aPSt1, D1) do   //Берём с вершины первого стека элемент D1.
  begin
    while Pop(aPSt2, D2) do //Берём с вершины второго стека элемент D2.
      if D2 <= D1 then      //Если по обратному правилу элемент D2 должен лежать ниже элемента D1.
        Push(PStSort, D2)   //Помещаем элемент D2 в обратно-сортированный стек.
      else                  //Иначе, если по обратному правилу элемент D1 должен лежать ниже элемента D2.
      begin
        Push(aPSt2, D2);    //Возвращаем элемент D2 во воторой стек.
        Break;
      end;
    Push(PStSort, D1);      //Помещаем в обратно-сортированный стек элемент D1.
  end;
  {Сейчас второй стек может оказаться не пустым. Переливаем его элементы
  в обратно-сортированный стек.}
  while Pop(aPSt2, D2) do
    Push(PStSort, D2);
  {Теперь стек PStSort содержит элементы, отсортированные по ОБРАТНОМУ правилу.
  Перепишем из него элементы в выходной стек. При этом порядок элементов поменяется
  на обратный и, соответственно, сортировка поменяется на обратную - что нам и нужно.}
  while Pop(PStSort, D1) do
    Push(aPStMerge, D1);
end;
 
var
  PSt1, PSt2, PStMerge : TPElem;
  i : Integer;
  S : String;
begin
  {Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
  Если после переключения русские буквы показываются неверно, то следует
  открыть системное меню консольного окна - щелчком мыши в левом верхнем
  углу консольного окна и выбрать:
  Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".}
  SetConsoleCP(1251);
  SetConsoleOutputCP(1251);
 
  //Начальная инициализация стеков.
  PSt1 := nil;
  PSt2 := nil;
  PStMerge := nil;
  repeat
    Writeln('--------------------------------------------------');
    //Формируем содержимое двух стеков.
    Randomize;
    for i := 1 to 3 + Random(8) do
      Push(PSt1, Random(20));
    for i := 1 to 3 + Random(8) do
      Push(PSt2, Random(20));
    //Распечатка стеков.
    Writeln('Исходное состояние стеков.');
    Write('Первый стек: ');
    StWriteln(PSt1);
    Write('Второй стек: ');
    StWriteln(PSt2);
 
    //Сортировка стеков.
    SortAsc(PSt1);
    SortAsc(PSt2);
    //Распечатка стеков.
    Writeln('---');
    Writeln('Состояние отсортированных стеков:');
    Write('Первый стек: ');
    StWriteln(PSt1);
    Write('Второй стек: ');
    StWriteln(PSt2);
 
    //Слияние.
    MergeAsc(PSt1, PSt2, PStMerge);
    //Распечатка стеков.
    Writeln('---');
    Writeln('Результирующий стек после слияния:');
    StWriteln(PStMerge);
 
    //Освобождение памяти, занятой для элементов стеков.
    StFree(PSt1);
    StFree(PSt2);
    StFree(PStMerge);
    Writeln('---');
    Writeln('Память, выделенная для стеков, освобождена.');
 
    Writeln('---');
    Write('Повторить - Enter. Выход - любой символ + Enter. ');
    Readln(S);
  until S <> '';
end.
1
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
13.06.2015, 16:58  [ТС] 3
Спасибо Вам больше за столь понятное и подробное решение.

Не могли бы ещё помочь с такой задачей. Нужно создать список из вещественных элементов и найти их сумму, вывести сам список и сумму.
Я всё, в принципе, сделал, только вот список неправильно выводит, то есть выводит только последний элемент.
Проект прикреплю.
Вложения
Тип файла: rar 6.1.1.rar (2.88 Мб, 1 просмотров)
0
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
15.06.2015, 18:06  [ТС] 4
Ни у кого нет идей в чём проблема?
0
4 / 4 / 1
Регистрация: 27.03.2015
Сообщений: 99
15.06.2015, 23:05 5
проблема в неправильном выводе или в неправильном расчете?
0
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
16.06.2015, 08:43  [ТС] 6
Как я уже написал, выводит только последний элемент списка, а нужно весь.
0
1 / 1 / 3
Регистрация: 27.12.2014
Сообщений: 68
17.06.2015, 11:53  [ТС] 7
Спасибо за помощь и внимание. Со всем разобрался (во второй задаче TextOut заменил просто на Memo, и всё нормально выводится).
0
17.06.2015, 11:53
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.06.2015, 11:53
Помогаю со студенческими работами здесь

Слияние двух Мемо
Есть такая задача. У меня есть два Мемо, я загружаю файл, и текст появляется в Мемо1. Что нужно,...

Слияние двух массивов. Спасайте ;)
Проект1 - нужно упорядочить массив по возрастанию. Сделано. Упорядоченные значения - в текстовом...

Произвести построчное слияние двух матриц А(m,n) и B(k, n), упорядоченных по неубыванию эле¬ментов первого столбца.
Произвести построчное слияние двух матриц А(m,n) и B(k, n), упорядоченных по неубыванию эле¬ментов...

Слияние двух упорядоченных массивов.
Элементы каждого из массивов X и Y упорядочены по не убыванию. Объединить элементы этих двух...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru