Версия для печати темы

Автор: DruiD 21.04.2007 16:33

Помогите составить программу, которая объединяет 2 упорядоченных по убыванию списка в один, тоже упорядоченный по убыванию. После к-того элемента вставить max элемент списка.

Автор: klem4 21.04.2007 16:34

Поиск -> Сортировка слияниями

Автор: DruiD 21.04.2007 23:07

Искал я сортировку слияниями в поиске. Близкого к моей задаче ничего не нашёл. Подскажите алгоритм: как выбирать позицию для вставки элемента из 2 списка в 1 список или другие путь решения моей задачи

Автор: klem4 21.04.2007 23:12

Отредактировано

Начинаем:

1:

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

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

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

GOTO 1

ps метки использовать не надо

Автор: DruiD 22.04.2007 14:20

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


Прикрепленные файлы
 XM.PAS ( 1.58 килобайт ) Кол-во скачиваний: 423

Автор: volvo 22.04.2007 16:59

Не нужен никакой третий список... Все прекрасно делается с двумя:

{ Объявляешь доп. переменные }
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 26.04.2007 21:44

Не подскажите почему на паскале 7.0 отрицательные числа не проходят, а на 7.1 проходят


Прикрепленные файлы
 SPISKI_reshenie.PAS ( 2.1 килобайт ) Кол-во скачиваний: 412

Автор: volvo 26.04.2007 22:07

Обратил внимание, я привел тебе тестовую последовательность с отрицательными числами... Проверялось именно на TP 7.0... Что ты вводил?

Добавлено через 4 мин.
Кстати, зачем ты делаешь

i,k,max:byte;

? А если будет два отрицательных числа в начале обоих списков? Проблема... Описывай как Integer...