Помощь - Поиск - Пользователи - Календарь
Полная версия: Объединение 2 упорядоченных списков
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
DruiD
Помогите составить программу, которая объединяет 2 упорядоченных по убыванию списка в один, тоже упорядоченный по убыванию. После к-того элемента вставить max элемент списка.
klem4
Поиск -> Сортировка слияниями
DruiD
Искал я сортировку слияниями в поиске. Близкого к моей задаче ничего не нашёл. Подскажите алгоритм: как выбирать позицию для вставки элемента из 2 списка в 1 список или другие путь решения моей задачи
klem4
Отредактировано

Начинаем:

1:

если оба списка пусты, завершаем программу, иначе

Если один из списков пуст, закидываем в третий список остввшиеся элементы из второго списка, если он конечно не пуст, завершаем программу иначе

Если Текущий элемент списка1 >= текущего элемента списка2, то в список3 заносим текущий элемент списка1 и список1 := список1.NEXT иначе заносим текущий элемент списка2 в третий список и список2 := списо2.NEXT

GOTO 1 smile.gif

ps метки использовать не надо smile.gif
DruiD
Алгоритм понял и прогу прикрепил, но тогда приходится создавать 1-й элемент для 3 списка.
Можно ли решить эту задачу не используя 3 список, а делая действия над двумя данными?
volvo
Не нужен никакой третий список... Все прекрасно делается с двумя:


{ Объявляешь доп. переменные }
var
p1, p2, T: spisok;
first: boolean;

... { Здесь - ввод списков }

{
Проверяешь, в каком списке стартовый элемент больший...
Этот список для тебя - ПЕРВЫЙ
}
if begqa^.inf > begqb^.inf then begin
p1 := begqa; p2 := begqb;
first := true;
end
else begin
p1 := begqb; p2 := begqa;
first := false;
end;

{
Дальше - сам алгоритм
}
while (p1 <> nil) and (p2 <> nil) do begin

while (p1^.link <> nil) and (p1^.link^.inf > p2^.inf) do p1 := p1^.link;
if p1.link <> nil then begin

T := p2^.link;

p2^.link := p1^.link;
p1^.link := p2;

p2 := T;
end;
T := p1;
p1 := p1^.link;

end;

{
Не забываем "прилепить" к концу первого списка остаток второго, если он есть
}
T^.link := p2;

{
ну, и распечатыаем соответственно тот список, который ПЕРВЫЙ (см. выше)
}
if first then p := begqa
else p := begqb;

while p<>nil do begin
write(' ',p^.inf); p:=p^.link;
end;
writeln;



Добавлено через 1 мин.
Тестировалось на
<17, 15, 9, 1, 0>
и
<14, 7, 6, 2, -2>

Вроде работает...
DruiD
Не подскажите почему на паскале 7.0 отрицательные числа не проходят, а на 7.1 проходят
volvo
Цитата
почему на паскале 7.0 отрицательные числа не проходят
Обратил внимание, я привел тебе тестовую последовательность с отрицательными числами... Проверялось именно на TP 7.0... Что ты вводил?

Добавлено через 4 мин.
Кстати, зачем ты делаешь
i,k,max:byte;
? А если будет два отрицательных числа в начале обоих списков? Проблема... Описывай как Integer...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.